Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes

This paper establishes new convergence rates for the last iterate of stochastic gradient descent and stochastic heavy ball methods in parametric settings with globally convex or non-convex objectives having $\gamma$-Hölder gradients, utilizing discrete Gronwall's inequality to derive improved bounds without relying on the Robbins-Siegmund theorem.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy valley. This valley represents a complex problem you want to solve, like training an AI to recognize cats or predicting stock prices. The "height" of the valley at any point is your Error (how wrong your current guess is), and the lowest point is the perfect solution.

To find the bottom, you can't see the whole map. You can only take a step, feel the slope under your feet, and decide where to go next. This is Stochastic Gradient Descent (SGD).

However, the fog is thick, and the ground is uneven. Sometimes you step on a rock that makes you think the slope is steeper than it really is (noise). Sometimes you step on a patch of mud that makes you think it's flat.

This paper is about two specific ways of walking down this foggy hill:

1. The Standard Hiker (SGD): You look at the slope, take a step, and stop. You rely entirely on your current feeling.
2. The Rolling Ball (Stochastic Heavy Ball - SHB): You are a heavy ball. When you roll, you don't just go where the slope points right now; you also carry momentum. If you were rolling fast downhill a second ago, you keep rolling fast, even if the slope flattens out a bit. This helps you bounce over small bumps (noise) and roll faster down long slopes.

The Big Problem: "Last Step" vs. "Average Step"

Most math papers about these hikers say: "If you walk long enough, the average of all your steps will get you very close to the bottom."

But in real life, you don't care about your average position. You care about where you are standing right now (the "last iterate"). If the average is good but your last step was a giant leap into a ditch, you haven't solved the problem.

The author, Marcel Hudiani, asks: "How fast does the hiker actually reach the bottom with their very last step?"

The Terrain: How "Bumpy" is the Hill?

The paper studies two types of terrain:

1. Smooth Hills (Convex): The valley has a single, clear bottom. No hidden pits.
2. Rough Hills (Non-Convex): The valley has many small dips and bumps (local minima). It's harder to find the true bottom.

Crucially, the author looks at hills where the ground isn't perfectly smooth. It's a bit "grainy" or "fractal." In math terms, the gradient (slope) is Hölder continuous. Think of it as a hill that is smooth enough to walk on, but if you zoom in, it's a bit jagged, not perfectly glass-like.

The Main Discoveries

1. The "Momentum" Trade-off

The paper finds that for the Rolling Ball (SHB) method:

• Good News: It works great! It reaches the bottom almost as fast as the best possible method, even on these rough, grainy hills.
• The Catch: If the hill is very rough (low smoothness) and you have a lot of momentum, the ball might overshoot the bottom slightly more than a cautious hiker would. The paper calculates exactly how much this "overshoot" slows you down. It turns out, for very rough hills, the momentum factor actually adds a tiny bit of "drag" to the final speed, but it's still very fast.

2. The "Last Step" Guarantee

The author proves that if you keep walking long enough, your very last step will eventually be incredibly close to the bottom.

• For the Standard Hiker (SGD): They get close at a predictable speed.
• For the Rolling Ball (SHB): They also get close, but the speed depends on how "bumpy" the hill is. The paper gives a precise formula for this speed.

3. A New Way to Prove It (No Magic Tricks)

Mathematicians usually prove these things using a heavy, complex tool called the Robbins-Siegmund theorem. It's like using a giant sledgehammer to crack a nut. It works, but it's messy.

The author says, "Let's try a different tool." They used a simpler, more direct method involving Gronwall's inequality (think of it as a way to track how a small error grows over time) and Martingale theory (a way to track random luck).

• Analogy: Instead of using a sledgehammer, they used a precise scalpel. This makes the proof cleaner and easier to understand, and it applies to a wider range of "bumpy" hills than previous methods.

The "High Probability" Result

The paper also asks: "What if we want to be 99% sure we are close to the bottom?"
Usually, with random noise, you might get lucky and be close, or unlucky and be far away. The author proves that with the Rolling Ball method, if you choose your step size (how big your steps are) correctly, you can be highly confident (with probability $1-\delta$) that you are close to the solution.

Summary in Plain English

Imagine you are trying to find the exit of a maze in the dark.

• Old methods told you: "If you walk randomly for a long time, your average position will be near the exit."
• This paper says: "No, let's look at where you are right now. We found that if you keep your momentum (don't stop and start every second), you will reach the exit faster, even if the walls are jagged and uneven."
• The Innovation: The author didn't use the standard, complicated math tools everyone else uses. They built a new, simpler bridge to prove this, showing that the "Rolling Ball" method is robust and fast, even on difficult, rough terrain.

The Takeaway: If you are building an AI or solving a complex optimization problem, using a "Heavy Ball" approach (momentum) is a very reliable way to ensure your final answer is good, even if the data is noisy and the problem is tricky. And now, we have a clearer, simpler mathematical proof of exactly why and how fast it works.

Technical Summary

Here is a detailed technical summary of the paper "Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes" by Marcel Hudiani.

1. Problem Statement

The paper investigates the almost sure convergence rates of the last iterate (as opposed to averaged iterates) for two stochastic optimization algorithms:

1. Stochastic Gradient Descent (SGD): $\beta = 0$.
2. Stochastic Heavy Ball (SHB): $\beta \in (0, 1)$, a momentum-based method.

The study focuses on unconstrained optimization problems minimizing a cost function $F(w) = \mathbb{E}_\rho[\ell(Z, w)]$ defined on $\mathbb{R}^d$. The key novelty lies in the assumptions regarding the objective function:

• Regularity: The gradient $\nabla \ell$ is assumed to be $\gamma$-Hölder continuous with constant $L$, where $\gamma \in (0, 1]$. This generalizes the standard Lipschitz gradient assumption ($\gamma=1$).
• Convexity: The paper covers both non-convex objectives and convex objectives.
• Noise: The noise in the gradient estimator is handled under the ABC condition (Assumption 2.2), which bounds the $(1+\gamma)$-th moment of the gradient estimator in terms of the function suboptimality and the gradient norm, without requiring a global uniform variance bound.

2. Methodology

The author departs from the standard literature which heavily relies on the Robbins-Siegmund theorem (a convergence theorem for non-negative almost super-martingales). Instead, this paper employs a distinct analytical framework:

• Discrete Gronwall's Inequality: Used to derive uniform upper bounds on the sums of step sizes weighted by gradients and function values.
• Doob's Martingale Convergence Theorem: Utilized to establish almost sure convergence properties.
• Stochastic Recurrence Relations: The analysis involves constructing recursive inequalities for quantities like $F(w_t) - F^*$ and $\|v_t\|^2$ (where $v_t$ is the momentum term).
• Concentration Inequalities: For high-probability results (specifically when $\gamma=1$), the paper utilizes Azuma-Hoeffding and Bernstein inequalities to bound martingale difference terms. This requires establishing polynomial bounds on the distance to the minimizer $\|w_t - w^*\|$.
• Stopping Time Analysis: For the almost sure convergence rate of convex objectives, the analysis is restricted to the stopping time $\tau := \inf\{t > 0 : F(w_t) = F^*\}$ to handle the requirement that the error term remains positive for the specific inequalities used.

3. Key Contributions

The paper makes three primary contributions:

1. Alternative Proof Technique: It provides a new method to prove convergence rates using Gronwall's inequality and Doob's theorem instead of the Robbins-Siegmund theorem. This offers a different perspective on the stability of stochastic schemes.
2. First Almost Sure Rate for SHB with $\gamma$-Hölder Gradients: While SGD rates for $\gamma$-Hölder gradients were known (e.g., Lei et al., 2022), this is the first result establishing the almost sure convergence rate for SHB with constant momentum $\beta \in (0, 1)$ under $\gamma$-Hölder smoothness.
3. High-Probability Rates for SHB: It establishes convergence rates with high probability (h.p.) for the case $\gamma=1$ (Lipschitz gradient) for SHB, a result previously only available for SGD.

4. Main Results

A. Almost Sure Convergence Rates

Let the step size be $\alpha_t = \Theta(t^{-p})$ with $p \in (\frac{1}{1+\gamma}, 1)$.

• Non-Convex Case:
  The minimum gradient norm converges as:
  $$\min_{0 \le s \le t} \|\nabla F(w_s)\|^2 = o(t^{p-1}) \quad \text{a.s.}$$
  This holds for both SGD and SHB.

• Convex Case:

  • Minimum Function Value: $\min_{0 \le s \le t} (F(w_s) - F^*) = o(t^{p-1})$ a.s.
  • Last Iterate (up to stopping time $\tau$):
    $$F(w_{\tau \wedge t}) - F^* = o\left( t^{r_\gamma \max(p-1, 1-(1+\gamma)p) + \epsilon} \right) \quad \text{a.s.}$$
    where the slowdown factor $r_\gamma$ is:
    $$r_\gamma = \begin{cases} \frac{2\gamma}{1+\gamma} & \text{if } \beta \in (0, 1) \\ 1 & \text{if } \beta = 0 \text{ (SGD)} \end{cases}$$
  • Significance of $r_\gamma$: The paper notes that for $\beta > 0$ and $\gamma < 1$, the momentum term introduces a "slowdown factor" $r_\gamma < 1$ compared to SGD. This is counter-intuitive as momentum usually accelerates convergence, but the analysis suggests that under $\gamma$-Hölder smoothness, the interaction between momentum and the specific error bounds leads to a slower rate in the worst-case almost sure scenario.

B. High-Probability Convergence Rates (for $\gamma = 1$)

When the gradient is Lipschitz ($\gamma=1$) and $p \in (1/2, 1)$:
$$P\left( F(w_{T+1}) - F^* \le O\left( T^{\max(p-1, -2p+1)} \left(\log \frac{T}{\delta}\right)^2 \right) \right) \ge 1 - \delta$$
This result confirms that SHB with constant momentum achieves the same high-probability rate as SGD in the Lipschitz convex setting.

5. Significance and Implications

• Bridging the Gap: The paper fills a critical gap in the literature by analyzing SHB under weaker smoothness assumptions ($\gamma$-Hölder) where previous results were limited to SGD or required Lipschitz gradients.
• Momentum Analysis: It provides a nuanced view on the role of momentum. While momentum is often beneficial, the theoretical analysis here suggests that under specific non-Lipschitz smoothness conditions, constant momentum might theoretically slow down the almost sure convergence rate of the last iterate compared to pure SGD, though it matches SGD in high-probability bounds for the Lipschitz case.
• Methodological Shift: By avoiding the Robbins-Siegmund theorem, the paper opens the door for alternative proof techniques in stochastic optimization that may be more adaptable to different noise structures or non-standard smoothness conditions.
• Practical Relevance: The results apply to modern deep learning scenarios where loss functions may not be globally Lipschitz smooth but possess Hölder continuity, and where the "last iterate" is often the one used in practice rather than an average.

In summary, Hudiani's work rigorously extends the convergence theory of stochastic heavy ball methods to non-Lipschitz settings, offering new theoretical bounds that challenge and refine the understanding of how momentum interacts with gradient smoothness in stochastic optimization.