Nonmonotone Line Search for Nonconvex Optimization

107 concepts69 papers1 proposal

In classical optimization, we are conditioned to think of progress as a strict, unbroken downhill walk. Standard line search methods, such as the Armijo or Wolfe backtracking rules, enforce a greedy constraint: every single step must decrease the objective function value.

While this monotonic requirement provides a straightforward proof of convergence, it often acts as a computational straightjacket. In complex, nonconvex, or ill-conditioned landscapes, requiring a strict decrease at every iteration forces algorithms to take infinitesimally small steps, causes them to stall in narrow valleys, and traps them in suboptimal local minima.

Nonmonotone line search breaks this constraint. By allowing the objective function to temporarily increase, nonmonotone methods gain the flexibility to step over local hurdles, deploy aggressive step sizes, and navigate noisy or stochastic landscapes far more efficiently.

The Monotonicity Trap

To understand why nonmonotone methods work, we must first look at why monotonic methods fail. Consider a narrow, curved valley in a loss landscape. A standard gradient descent algorithm with a monotonic line search will quickly hit the valley walls. To guarantee a decrease at every step, the line search is forced to drastically reduce the step size, leading to an inefficient "zig-zagging" behavior where the optimizer makes almost no forward progress.

As Leonardo Galli et al. observe in Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models, this strictness is particularly damaging in modern machine learning. When optimizing over-parameterized models, mandatory descent conditions force the optimizer to operate with highly conservative learning rates, preventing it from traversing the "edge of stability" where optimization is often fastest.

Relaxing the Descent Condition

How can we allow an algorithm to go uphill without risking total divergence? The core insight of nonmonotone optimization is to replace the immediate previous function value, $f(x_k)$, with a more permissive reference value, $R_k$, in the sufficient decrease condition:

$$f(x_{k+1}) \le R_k + \alpha \gamma \nabla f(x_k)^T d_k$$

There are two primary philosophies for constructing this reference value $R_k$:

  1. The Maximum Window Strategy (GLL): The reference value is chosen as the maximum objective value observed over a fixed window of recent iterations: $R_k = \max_{0 \le j \le M} f(x_{k-j})$. As long as the new step is lower than the worst step in recent history, it is accepted.
  2. The Weighted Average Strategy (ZH): Instead of the maximum, $R_k$ is maintained as a geometric moving average of all past function values.

Huan Li et al. demonstrate in Accelerated Proximal Gradient Methods for Nonconvex Programming that this moving average relaxation dramatically reduces the computational overhead of accelerated proximal methods. By skipping expensive validation steps and avoiding excessively small steps, the algorithm maintains a fast $O(1/k^2)$ convergence rate in convex regions while remaining highly robust in nonconvex zones.

Similarly, the PoNoS (POlyak NOnmonotone Stochastic) framework proposed by Leonardo Galli et al. leverages a historical average to accept temporary increases in loss, allowing the optimizer to break out of local bottlenecks and discover significantly larger, more effective step sizes.

Capitalizing on Local Geometry

Allowing nonmonotone steps unlocks advanced step-size selection strategies that are fundamentally incompatible with strict descent rules.

Barzilai-Borwein and Variable Metrics

The Barzilai-Borwein (BB) method chooses step sizes by approximating the secant equation of the Hessian using only gradient information from the two most recent steps. BB steps are notoriously nonmonotone—they cause the objective function to fluctuate wildly—but they achieve exceptional convergence speeds on ill-conditioned problems.

Sauptik Dhar et al. exploit this in Variable Metric Proximal Gradient Method with Diagonal Barzilai-Borwein Stepsize. By pairing a diagonal BB stepsize with a nonmonotone line search, the authors compensate for the inherent inaccuracies of diagonal Hessian approximations. The nonmonotone buffer prevents the algorithm from stalling when the diagonal approximation overestimates or underestimates local curvature, allowing for rapid traversal of complex loss landscapes.

Fractal and Non-Greedy Scheduling

In some cases, we do not even need an adaptive line search to benefit from nonmonotonicity. Uri M. Ascher et al. show in Gradient descent and fast artificial time integration that intentionally alternating between different step-size calculation methods—or using their harmonic mean—breaks the greedy local minimization loop, eliminating the classic zig-zagging of steepest descent.

Taking this to its logical conclusion, Naman Agarwal et al. introduce Acceleration via Fractal Learning Rate Schedules. They prove that vanilla gradient descent can match the accelerated convergence rates of Nesterov's momentum purely through a fixed, non-adaptive sequence of step sizes derived from Chebyshev polynomials.

Monotonic Path:   [x_0] -> [x_1] -> [x_2] -> [x_3]  (Tiny, cautious steps)
Fractal Path:     [x_0] ----------> [x_1]           (Massive, destabilizing step)
                          <--- [x_2]                (Corrective step)
                               ----> [x_3]          (Net massive progress)

This fractal schedule deliberately introduces massive, destabilizing steps that make the loss temporarily worse, followed by a planned sequence of smaller, corrective steps. The overall architecture remains stable and converges faster than any strictly monotonic sequence could allow.

Optimization Without Function Evaluations

Traditional line searches require evaluating the objective function $f(x)$ multiple times per iteration to verify the descent condition. In many modern applications—such as stochastic optimization or large-scale data fitting—evaluating the full objective function is computationally prohibitive or impossible.

To solve this, Yura Malitsky et al. proposed a paradigm shift in Adaptive Gradient Descent without Descent. Instead of checking function values, the algorithm estimates the local Lipschitz constant dynamically using only the differences between consecutive gradients:

$$\frac{\|\nabla f(x_k) - \nabla f(x_{k-1})\|}{\|x_k - x_{k-1}\|}$$

Because the step size adjusts based on this local curvature estimate rather than an explicit check on the function value, the resulting optimization path is inherently nonmonotone.

The authors prove that this local adaptation guarantees long-term convergence without requiring global smoothness constants. Jean-François Aujol et al. successfully extended this principle to the stochastic regime in Stochastic Adaptive Gradient Descent Without Descent, creating an automated, hyperparameter-free version of SGD that adapts to local geometry without being constrained by immediate progress requirements.

Managing Constraints and Stationarity

Nonmonotone mechanisms are equally potent when adapting to constrained optimization domains, where algorithms must balance minimizing an objective function with staying inside a feasible region.

Active-Set and Filter Methods

In bound-constrained optimization, first-order methods often struggle to quickly identify which constraints are active (i.e., which variables sit exactly on the boundaries). Andrea Cristofari et al. demonstrate in Minimization over the ℓ 1-ball using an active-set non-monotone projected gradient that embedding a nonmonotone line search within an active-set identification framework prevents the solver from getting stuck in regions with vanishingly small gradients. The objective function is allowed to fluctuate, which gives the algorithm the freedom to rapidly swap variables in and out of the active set.

For broader robust estimation problems, Huu Le introduces a multi-objective approach in A Graduated Filter Method for Large Scale Robust Estimation. Instead of a scalar line search, the algorithm tracks a "filter"—a Pareto front of non-dominated pairs representing objective values and constraint feasibility violations. A step is accepted if it improves either the objective or the feasibility. This allows the objective function to temporarily increase if the step makes the parameters significantly more feasible, providing a powerful mechanism to escape the local minima that routinely trap traditional descent methods.

Theoretical Guarantees

Does relaxing the monotone condition compromise mathematical rigor? On the contrary, the theoretical foundations of nonmonotone line searches are robust. Guillaume Olikier et al. analyze this in Projected gradient descent accumulates at Bouligand stationary points, proving that nonmonotone backtracking line searches over non-convex sets successfully accumulate at Bouligand (B-) stationary points. This confirms that the long-term convergence guarantees of nonmonotone optimization are fully equivalent to their monotonic counterparts, while offering vastly superior dynamical properties along the optimization path.

Key Foundational Work

An Alternating Direction Method for Finding Dantzig Selectors (2010) — contributed 2 concept elements to this direction.
A scalable trust-region algorithm with application to mixed-norm regression (2010) — contributed 2 concept elements to this direction.
Accelerating Constrained SIRTwith Applications in Tomographic Particle Image Reconstruction (2009) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 74 papers
  2. Version 1 · 2026-10-04 · 96 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_nonmonotone_line_search_29d10b44,
  title = {nonmonotone line search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nonmonotone-line-search/rdr_29d10b448e244773ae97dfde3eaf1bed},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_nonmonotone_line_search_29d10b44_v2,
  title = {nonmonotone line search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nonmonotone-line-search/rdr_29d10b448e244773ae97dfde3eaf1bed/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake