Research map / Optimization / Optimizers
Adaptive backtracking line search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes adaptive backtracking line search that replaces the constant backtracking factor with one depending on the size of the Armijo or descent-lemma violation, and proves it matches regular backtracking's guarantees.
Problem
Standard backtracking line search shrinks step sizes by a fixed constant factor, ignoring how badly the line search criterion (Armijo or descent lemma) is violated, which wastes function evaluations and can yield poor step sizes.
Approach
Replace the constant backtracking factor rho with an online adaptive factor that is a function of the criterion violation v(alpha): for Armijo, rho_hat = max(eps, rho(1-c)/(1-c v)); for the descent lemma, rho_hat = rho v. The procedure has no extra computational cost and keeps the theoretical guarantees of regular backtracking.
Key results
- On logistic regression, ABLS reduced elapsed time versus the best BLS variant by roughly 3% to 75% across datasets and base methods (GD, AGD, Adagrad).
- On matrix factorization (MovieLens 100K), ABLS for GD reduced elapsed time by 67% to 94% versus the best BLS variant, and for AGD by 55% to 75%.
- Theory: for convex problems adaptive BLS takes no more function evaluations than regular BLS to return a feasible step size, and for nonconvex smooth problems it matches regular BLS's step-size lower bounds and iteration complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace fixed-factor backtracking with adaptive backtracking | GD and Adagrad · logistic regression datasets | ET [s]: 46.7% ; 47.3% ; 55.9% ; 45.5% ; 57.6% ; 7.7% ; (5.4%)* | Helped |
| replace fixed-factor backtracking with adaptive backtracking | AGD · logistic regression datasets | ET [s]: 52.5% ; 26.8% ; 37.4% ; 15.5% ; 53.6% ; 15.8% ; 3.3% | Helped |
| replace fixed-factor backtracking with adaptive backtracking | FISTA · linear inverse problem datasets | # ∇f: 40.8% ; 2.2% ; 12.3% ; 8.0% ; 22.2% ; 19.1% ; 5.7% ; 10.7% | Helped |
| replace fixed-factor backtracking with adaptive backtracking | GD and AGD · MovieLens 100K matrix factorization | ET [s]: 93.5% ; 83.1% ; 67.1% ; 54.7% ; 75.3% ; 60.9% | Helped |
| replace PoNoS backtracking with adaptive backtracking | PoNoS on MNIST MLP · MNIST | epochs: 56 -> 41 | Helped |
| replace PoNoS backtracking with adaptive backtracking | PoNoS on MNIST MLP · MNIST | seconds: 583 -> 464 | Helped |
| use ABLS for GD on web-1 | GD · web-1 logistic regression | function and gradient evaluations | Hurt |
Surprising findings
- The step-size returned by regular backtracking is not monotone in rho even for convex problems, so smaller rho does not always help.
- On one logistic regression dataset (web-1) GD with ABLS terminated faster in time but needed more function and gradient evaluations than the best BLS variant.
Limitations
- Theory and experiments focus on Armijo and descent lemma; Wolfe conditions are not affine in the step size and are not handled by the method.
- Unclear applicability to general stochastic line search methods that do not rely on interpolation.
- Gains on some datasets are small (e.g., 3% to 8%) and one case needed more evaluations.
Experimental setup
Datasets: adult g_scale mnist mushrooms phishing protein web-1 digits iris olivetti lfw spear3
Benchmarks: logistic regression on LIBSVM-style datasets lasso linear inverse problems Rosenbrock function matrix factorization on MovieLens 100K MLP on MNIST (stochastic line search)
Metrics: number of function evaluations number of gradient evaluations elapsed time (s) gain in elapsed time over best BLS
Baselines: regular backtracking line search (BLS) GD with constant step size AGD with constant step size Adam SLS SPS PoNoS FISTA with BLS
Builds on: Armijo condition backtracking line search FISTA Nesterov accelerated gradient Adagrad
Closest papers by meaning
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.86)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.85)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.85)
- Taking the Road Less Scheduled with Adaptive Polyak Steps (NeurIPS 2026 · similarity 0.84)
- The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms (NeurIPS 2024 · similarity 0.84)
- Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.