# Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales

arXiv: https://arxiv.org/abs/2111.03137 · HTML: https://mlsanity.com/paper/2111.03137/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2021.

## Built on by (most cited first, 7 of 7)

- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes](https://mlsanity.com/paper/2504.04105/) (2025)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [Data-induced multiscale losses and efficient multirate gradient descent schemes](https://mlsanity.com/paper/2402.03021/) (2024)
- [A short proof of near-linear convergence of adaptive gradient descent under fourth-order growth and convexity](https://mlsanity.com/paper/2604.13393/) (2026)

## Abstract (arXiv)

We provide new gradient-based methods for efficiently solving a broad class of ill-conditioned optimization problems. We consider the problem of minimizing a function f : ℝd rightarrow ℝ which is implicitly decomposable as the sum of m unknown non-interacting smooth, strongly convex functions and provide a method which solves this problem with a number of gradient evaluations that scales (up to logarithmic factors) as the product of the square-root of the condition numbers of the components. This complexity bound (which we prove is nearly optimal) can improve almost exponentially on that of accelerated gradient methods, which grow as the square root of the condition number of f. Additionally, we provide efficient methods for solving stochastic, quadratic variants of this multiscale optimization problem. Rather than learn the decomposition of f (which would be prohibitively expensive), our methods apply a clean recursive "Big-Step-Little-Step" interleaving of standard methods. The resulting algorithms use tildeO(d m) space, are numerically stable, and open the door to a more fine-grained understanding of the complexity of convex optimization beyond condition number.