💻 computer science

Stochastic Adaptive Gradient Descent Without Descent

This paper introduces a hyperparameter-free, theoretically-grounded stochastic adaptive step-size strategy for convex optimization that leverages local geometry via a first-order oracle, proving convergence under various assumptions and demonstrating empirical competitiveness against tuned baselines.

Original authors: Jean-François Aujol, Jérémie Bigot, Camille Castera

Published 2026-06-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jean-François Aujol, Jérémie Bigot, Camille Castera

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Hiking in the Fog

Imagine you are trying to find the lowest point in a vast, foggy valley (the "minimum" of a function). You can't see the whole landscape, only the ground immediately under your feet. This is a common problem in machine learning, where computers try to learn from data by finding the best settings to minimize errors.

The standard way to do this is Stochastic Gradient Descent (SGD). Think of this as taking steps downhill. Every step you take is based on a "stochastic" (random) guess of which way is down, because the fog is so thick you can only see a tiny patch of ground at a time.

The Problem: To take a step, you need to decide how big that step should be.

If your step is too big, you might overshoot the bottom, bounce up the other side, and never settle.
If your step is too small, you will inch along painfully slowly, taking forever to get anywhere.

In traditional methods, you have to manually tune this step size. It's like trying to find the perfect stride length for a hike without a map. You have to guess, test, and adjust. If you guess wrong, the whole trip fails.

The Solution: A Self-Adjusting Compass

The authors of this paper introduce a new method called AdaSGD. They created a "smart compass" that automatically adjusts your step size based on the terrain you are currently walking on, without needing you to guess a starting number.

Here is how it works, using the paper's specific claims:

1. The "Without Descent" Trick

Usually, optimization algorithms promise that every single step will take you downhill (decreasing the error). The authors' method, inspired by a previous deterministic algorithm, is called "Adaptive Gradient Descent Without Descent."

The Analogy: Imagine you are walking down a mountain, but sometimes the ground is slippery or bumpy. A strict rule would say, "You must go down every step." But this new method says, "It's okay if you accidentally take a tiny step sideways or even slightly up, as long as your overall path is heading toward the bottom."
Why it helps: By relaxing the rule that every single step must go down, the algorithm can be much more flexible. It can take larger, bolder steps when the ground is flat and smooth, and smaller, cautious steps when the ground is steep or bumpy, without getting stuck.

2. No "Tuning" Required

Most adaptive methods still require you to set a "sensitivity knob" (a hyper-parameter) at the start. If you turn the knob too high, it's chaotic; too low, it's slow.

The Paper's Claim: The authors show that their method works well without tuning any knobs.
The "Small Step" Secret: They found that if you just start with a very small, safe step size (like $10^{-3}$ ), the algorithm's internal math automatically figures out how to speed up or slow down.
The Result: In their experiments, they tested their method on various problems (like predicting house prices or classifying images). They showed that even if you pick a "bad" starting step size, their method performs just as well as other methods that were perfectly tuned by experts. It is "robust" to bad choices.

3. How It "Feels" the Terrain

The algorithm doesn't need to know the shape of the mountain in advance. Instead, it uses a clever trick to estimate the "steepness" (local geometry) of the ground right where you are standing.

The Mechanism: At every step, it looks at how much the "slope" changed between the last two spots you visited.
- If the slope changed a lot (bumpy terrain), it shrinks the step size to be safe.
- If the slope stayed the same (smooth terrain), it keeps the step size larger to move faster.
The "Extra Step": To do this, the algorithm has to take one extra "look" at the ground (an extra calculation) at every turn. The authors admit this is a small cost, but they argue it is worth it because you don't have to spend hours tuning the settings beforehand.

The Three Variants (V-I, V-II, V-III)

The paper proposes three slightly different versions of this compass:

V-I: The basic version.
V-II & V-III: These include a "decay" factor, meaning they slowly reduce the step size over time as a safety net.
Recommendation: The authors suggest using V-III because it has the strongest mathematical guarantees, but they note that all three work well in practice.

What the Paper Proves (and Doesn't Prove)

What it proves: The authors mathematically proved that this method will eventually find the bottom of the valley (convergence) for a wide range of "convex" problems (bowl-shaped valleys). They also proved the speed at which it gets there.
What it doesn't claim:
- They do not claim this works for non-convex problems (like training deep neural networks with complex, multi-peaked landscapes). They explicitly state that extending this to neural networks is a future challenge because the math relies on the "bowl shape" assumption.
- They do not claim it is faster than the best possible tuned method in every single scenario. They claim it is comparable to the best tuned methods but without the hassle of tuning.

Summary

Think of this paper as introducing a self-driving car for optimization.

Old way: You have to manually adjust the steering sensitivity and gas pedal for every new road. If you guess wrong, you crash or drive too slow.
New way (AdaSGD): You just set the car to "Drive." It looks at the road, feels the bumps, and automatically adjusts the steering and speed. It might take a tiny extra sensor reading every second, but it saves you the headache of manual tuning and gets you to the destination just as fast as an expert driver would.

The core message is: Stop guessing the step size. Let the algorithm figure it out for you.

Problem Statement
The paper addresses the stochastic convex optimization problem:
$\min_{x \in \mathbb{R}^d} f(x) = \min_{x \in \mathbb{R}^d} \mathbb{E}[f_\xi(x)]$
where $f$ is a convex, differentiable, and lower-bounded function. The goal is to find a minimizer $x^\star$ using a stochastic gradient oracle $\nabla f_{\xi_k}$ without requiring the careful tuning of hyper-parameters, specifically the initial step-size $\lambda_0$ . While standard Stochastic Gradient Descent (SGD) requires tuning $\lambda_0$ to balance convergence speed and stability, and existing adaptive methods (like those by Malitsky and Mishchenko [2020]) often retain a dependency on a tunable parameter $\alpha$ in the stochastic setting, this work seeks a "tuning-free" approach that adapts to the local geometry of the objective function using only first-order oracle calls.

Methodology
The authors propose AdaSGD, a stochastic adaptation of the "Adaptive Gradient Descent Without Descent" (AdaGD) method. The core innovation lies in the step-size update rule, which avoids the hyper-parameter $\alpha$ required by previous stochastic adaptations.

The algorithm follows the standard stochastic recursion $x_{k+1} = x_k - \lambda_k \nabla f_{\xi_k}(x_k)$ . The step-size $\lambda_k$ is updated based on the local geometry of the function. A key distinction from the deterministic AdaGD and previous stochastic attempts is the evaluation of the gradient difference. Instead of using the current batch $\xi_k$ for both points (which introduces bias or requires a second independent batch $\zeta_k$ ), the method evaluates the gradient difference using the previous random variable $\xi_{k-1}$ :
$\hat{L}_{k-1} = \frac{\|\nabla f_{\xi_{k-1}}(x_k) - \nabla f_{\xi_{k-1}}(x_{k-1})\|}{\|x_k - x_{k-1}\|}$
This allows the step-size to be defined without an external scaling parameter. The paper proposes three variants (V-I, V-II, V-III) for $k \ge 2$ :
$\lambda_k = \min \left( \frac{c_k}{2\sqrt{2}\hat{L}_{k-1}}, \frac{\lambda_{k-1}}{\sqrt{1 + \theta_{k-1}}} \right)$
where $\theta_{k-1} = \lambda_{k-1}/\lambda_{k-2}$ and $c_k$ is a decay factor (specifically $c_k = 1$ for V-I, and $c_k = k^{1/2+\delta}$ for V-II and V-III with $0 < \delta < 1/2$ ). V-III is recommended as it provides the strongest theoretical guarantees.

Theoretical Analysis
The convergence analysis relies on constructing a Lyapunov sequence $(T_k)$ , inspired by Malitsky and Mishchenko [2020] but adapted for the stochastic setting. The sequence is defined as:
$T_k = \|x_{k+1} - x^\star\|^2 + 2(\lambda_k(1+\theta_k))(f(x_k) - f^\star) + \frac{\|x_{k+1} - x_k\|^2}{2}$
The authors prove that under specific assumptions (finite-sum structure with Lipschitz gradients, or bounded iterates), the sequence $(T_k)$ converges almost surely.

Almost Sure Convergence: Theorem 3.2 establishes that if the step-sizes are square-summable ( $\sum \lambda_k^2 < \infty$ ), the Lyapunov sequence converges. This condition is shown to hold in cases of strong convexity, linear regression, and sums of ridge functions.
Convergence Rates: For strongly convex functions (Case-1), Theorem 3.4 derives a convergence rate of $O(1/k^{1/2+\delta})$ for the expected error. Crucially, the exponential factors governing the transient behavior depend on the ratio $L^2/\mu^2$ (where $L$ is the smoothness constant and $\mu$ is the strong convexity parameter) rather than the initial step-size $\lambda_0$ . This contrasts with vanilla SGD, where the initial step-size can cause exponential growth in the error bound before convergence.

Key Contributions

Tuning-Free Stochastic Adaptation: The paper introduces a stochastic step-size strategy that eliminates the need for tuning the parameter $\alpha$ (or $\lambda_0$ ) required in the stochastic version of AdaGD by Malitsky and Mishchenko [2020].
Theoretical Guarantees: The authors provide rigorous convergence proofs and rates under standard assumptions (strong convexity, Lipschitz gradients) without requiring global knowledge of $L$ or $\mu$ .
Robustness to Initialization: The method is designed such that choosing a small initial step-size $\lambda_0$ is always safe, avoiding the sensitivity issues common in other adaptive methods.

Experimental Results
Numerical experiments were conducted on six stochastic convex optimization problems (linear/ridge/logistic/Poisson regression) using synthetic and real-world data (Diabetes, 2moons, w8a).

Sensitivity to $\lambda_0$ : The results demonstrate that AdaSGD is significantly less sensitive to the choice of the initial step-size $\lambda_0$ compared to vanilla SGD, decaying SGD, Adagrad, and the stochastic AdaGD-MM. While other methods require a dense grid search to find an optimal $\lambda_0$ , AdaSGD performs consistently well with a fixed small value (e.g., $\lambda_0 = 10^{-3}$ ).
Performance: In terms of minimization performance (optimality gap), AdaSGD (specifically variants V-II and V-III) achieves results comparable to optimally tuned baselines. The authors note that while V-I sometimes struggles with oscillations due to noise, the decay introduced in V-II and V-III stabilizes the method.
Cost: The method requires one extra stochastic gradient evaluation per iteration (to compute $\nabla f_{\xi_{k-1}}(x_k)$ ), but the authors argue this cost is offset by the elimination of the grid search required for hyper-parameter tuning.

Significance and Claims
The paper claims that AdaSGD successfully transfers the benefits of the deterministic "Adaptive Gradient Descent Without Descent" to the stochastic setting, a transition that previous attempts failed to achieve without reintroducing hyper-parameter tuning. The primary contribution is a method that is "tuning-free" in practice: it allows practitioners to use a fixed, small initial step-size without sacrificing convergence rates or stability. The authors emphasize that while the method is not strictly "parameter-free" (as it depends on the initial $\lambda_0$ for the Lyapunov function's initial value), the dependence is weak enough that small values are universally effective, rendering the method robust and practical for stochastic optimization without the need for extensive hyper-parameter search. The work remains focused on convex settings, with non-convex extensions noted as a significant future challenge due to the reliance on convexity inequalities in the derivation.