Papers › Corner Gradient Descent
Corner Gradient Descent
Dmitry Yarotsky
We consider SGD-type optimization on infinite-dimensional quadratic problems with power law spectral conditions. It is well-known that on such problems deterministic GD has loss convergence rates Lₜ=O(t^(-ζ)), which can be improved to Lₜ=O(t^(-2ζ)) by using Heavy Ball with a non-stationary Jacobi-based schedule (and the latter rate is optimal among fixed schedules). However, in the mini-batch Stochastic GD setting, the sampling noise causes the Jacobi HB to diverge; accordingly no O(t^(-2ζ)) algorithm is known. In this paper we show that rates up to O(t^(-2ζ)) can be achieved by a generalized stationary SGD with infinite memory. We start by identifying generalized (S)GD algorithms with contours in the complex plane. We then show that contours that have a corner with external angle θπ accelerate the plain GD rate O(t^(-ζ)) to O(t^(-θζ)). For deterministic GD, increasing θ allows to achieve rates arbitrarily close to O(t^(-2ζ)). However, in Stochastic GD, increasing θ also amplifies the sampling noise, so in general θ needs to be optimized by balancing the acceleration and noise effects. We prove that the optimal rate is given by θₘₐₓ=min(2,ν,2ζ+1/ν), where ν,ζ are the exponents appearing in the capacity and source spectral conditions. Furthermore, using fast rational approximations of the power functions, we show that ideal corner algorithms can be efficiently approximated by finite-memory algorithms, and demonstrate their practical efficiency on a synthetic problem and MNIST.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections