Analytic Step Size Selection for Faster Optimization

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 147 papers58 conceptsfrozen 2026-10-04

In the standard toolkit of numerical optimization, the "step size" or "learning rate" is often treated as a troublesome hyperparameter. Practitioners typically choose between two suboptimal paths: manually tuning a fixed rate through trial and error, or employing an iterative "line search" (like backtracking) that repeatedly evaluates the objective function to find a distance that satisfies stability conditions.

A growing body of research suggests a more elegant third way. By exploiting the local geometric structure of an objective function—such as its curvature, self-concordance, or algebraic form—we can often derive analytic, closed-form solutions for the optimal step size. This approach transforms a computationally expensive search process into a single, precise calculation.

The Quadratic Shortcut

The most common intuition for analytic step sizes comes from local quadratic approximations. If a function $f(x)$ behaves locally like a parabola, we don't need to "search" for its minimum along a descent direction; we can calculate it using the gradient and the Hessian.

Dario Balboni and Davide Bacciu demonstrate this with ADLER (ADLER - An efficient Hessian-based strategy for adaptive learning rate), which uses a computationally cheap approximation of the Hessian to reach the minimum of the local quadratic landscape in a single step. Similarly, in the context of inverse problems, Minwoo Kim and colleagues show in FAST‑DIPS that calculating a model-optimal step size from a local quadratic approximation can yield up to a 19.5× speedup over heuristic methods.

This principle extends to complex matrix problems. For instance, Venkatesh Saligrama and Ziming Zhang developed RAPID (RAPID: Rapidly Accelerated Proximal Gradient Algorithms for Convex Minimization), which uses closed-form scaling factors for quadratic losses to refine updates with negligible overhead.

Beyond Parabolas: Higher-Order Algebraic Solutions

When the objective function is more complex than a simple quadratic, the "optimal" step might be the root of a higher-order polynomial. Rather than iterating, researchers have found success by solving these equations directly.

By solving these polynomials, the algorithms ensure they take the mathematically best possible step along a descent direction in every single iteration, maximizing progress without the "trial and error" of traditional line searches.

Leveraging Self-Concordance and Geometry

For functions where the gradient isn't globally well-behaved (i.e., not Lipschitz continuous), standard step sizes often fail. However, many of these functions (like the log-barrier functions used in interior-point methods) are self-concordant, meaning their third derivative is bounded by their second derivative.

Quoc Tran-Dinh and Volkan Cevher have pioneered methods that derive analytic step sizes directly from this self-concordant structure (Composite Self-Concordant Minimization). By using the Newton decrement—a measure of how far the current point is from the minimum of the local quadratic model—they can guarantee a monotonic decrease in the objective function without ever performing a backtracking search.

This geometric approach is also visible in constrained optimization. In Frank-Wolfe (conditional gradient) algorithms, which are popular for their "projection-free" nature, researchers like Sebastian Pokutta have shown that secant-based methods can identify optimal step sizes for quadratic objectives in exactly one iteration (Secant Line Search for Frank-Wolfe Algorithms).

From Scalars to Matrices

While most optimization uses a single scalar step size, the most recent frontier involves matrix-valued stepsizes. Hanmin Li and Avetik G. Karagulyan introduced Det-CGD (Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization), which calculates an optimal stepsize matrix by solving a convex sub-problem. This allows the optimizer to adapt to the different "smoothness" levels across different layers of a neural network or different dimensions of a dataset, providing a much more granular and efficient descent path than any scalar could provide.

Why It Works: Turning Search into Calculation

The shift toward analytic step sizes works because it replaces an external search loop with an internal structural property.

Traditional line search is "blind"—it probes the function at various distances until it finds one that works. Analytic selection is "informed"—it uses the mathematical DNA of the problem (its derivatives and algebraic structure) to point exactly to where the step should land. As shown by Stefano Di Cairano in the context of ADMM (ADMM for Convex Quadratic Programs: Linear Convergence and Infeasibility Detection), these explicit formulas don't just speed up the code; they provide rigorous convergence guarantees that heuristic tuning cannot match.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_analytic_step_size_selection_for_faster__834e1380,
  title = {Analytic Step Size Selection for Faster Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/analytic-step-size-selection-for-faster-optimization/rdr_834e13804a77408bae6bc83cdb0fb910},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_analytic_step_size_selection_for_faster__834e1380_v1,
  title = {Analytic Step Size Selection for Faster Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/analytic-step-size-selection-for-faster-optimization/rdr_834e13804a77408bae6bc83cdb0fb910/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}