Nonmonotone Optimization for Nonconvex Landscapes

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 296 papers138 conceptsfrozen 2026-10-04

In classical optimization, the rule is simple: every step must go down. This "greedy" approach, known as monotonic descent, ensures that the objective function value decreases at every iteration. While intuitive, this requirement often acts as a straitjacket. In the complex, rugged landscapes of modern machine learning and signal processing, requiring a strict decrease at every step can cause an algorithm to stall in narrow valleys, get trapped in shallow local minima, or take agonizingly small steps.

Nonmonotone optimization relaxes this constraint. It allows the objective function to temporarily increase, providing the algorithm with the "breathing room" necessary to navigate difficult geometry and find better global solutions.

The Intuition of Taking a Step Back

Imagine navigating a mountain range in thick fog. A strict descent strategy dictates that you must always move to a lower elevation. If you find yourself in a small crater on a high ridge, you are stuck; any direction leads "up" to the crater's rim.

As Haiping Huang and Taro Toyoizumi point out in Reinforced backpropagation improves test performance of deep networks, allowing temporary increases in error enables an optimizer to cross these ridges. By moving "uphill" briefly, the algorithm can escape local traps and eventually reach much deeper valleys that offer better generalization.

One of the primary reasons optimization slows down is the presence of "ill-conditioned" valleys—regions where the landscape is very steep in one direction but nearly flat in another. In these narrow corridors, a standard line search often forces the step size to be tiny to ensure the objective value doesn't accidentally increase due to the valley's curvature.

Wei Xue and Wensheng Zhang demonstrate in Learning Unknown Structure in CRFs via Adaptive Gradient Projection Method that a nonmonotone line search allows the algorithm to "jump" across these narrow valleys. By permitting the objective to fluctuate, the solver can maintain a higher velocity through regions that would otherwise cause a monotonic solver to stall. Similarly, quanming yao and James Kwok show in their work on inexact proximal gradient algorithms that this flexibility is essential for navigating the complex, non-convex landscapes of regularized risk minimization.

Safeguarding Progress without Strict Descent

If we don't require a decrease at every step, how do we ensure the algorithm actually converges? Most nonmonotone methods use a "sliding window" or a "moving average" of previous function values as a reference.

  1. The Max-Value Criterion: A step is accepted if the new function value is lower than the maximum of the last $m$ iterations. This was notably utilized by Zhaosong Lu and Lin Xiao in Randomized Block Coordinate Non-Monotone Gradient Method to allow for more aggressive updates.
  2. The Average Criterion: A step is accepted if it is lower than a weighted average of all previous values, a strategy explored by Huan Li and Zhouchen Lin to accelerate proximal gradient methods.
  3. The Filter Method: In A Graduated Filter Method for Large Scale Robust Estimation, Huu Le uses a "filter" that tracks pairs of objective values and constraint violations. A step is accepted if it improves either the objective or the feasibility, allowing the loss to increase if the model becomes more "robust."

Acceleration through Destabilization

Perhaps the most surprising result in this field is that non-monotonicity can lead to faster convergence even in convex problems. Traditional Gradient Descent (GD) is limited by the "Lipschitz constant"—a measure of how fast the gradient changes. To stay stable and monotonic, GD must use a step size inversely proportional to this constant.

However, Naman Agarwal and colleagues in Acceleration via Fractal Learning Rate Schedules proved that one can achieve "accelerated" rates (similar to Nesterov's momentum) using only vanilla GD. The secret is a "fractal" schedule of learning rates where some steps are intentionally so large they destabilize the system and increase the loss, only to be corrected by a planned sequence of smaller steps.

This concept is further refined by Jason M. Altschuler and Pablo Parrilo in their Silver Stepsize Schedule, which breaks the $O(1/k)$ convergence barrier of standard GD by hedging against the requirement of monotonic descent.

Applications Across Domains

The benefits of nonmonotone strategies appear across a wide variety of high-dimensional problems:

  • Imaging: Stefania Petra and Constantin Popa achieved 100x speedups in tomographic reconstruction by applying nonmonotone line searches to SIRT algorithms.
  • Sparse Selection: For tasks like the Dantzig Selector or index tracking, Ting Kei Pong and Fengmin Xu show that nonmonotone methods are significantly faster at finding sparse solutions in non-convex landscapes.
  • Matrix Factorization: In Positive Semidefinite Matrix Factorization, Dana Lahat and co-authors found that algorithms permitting temporary error increases were the only ones capable of escaping the local minima that stall traditional coordinate descent.

By relaxing the requirement for immediate progress, nonmonotone optimization transforms the search for a minimum from a cautious, step-by-step crawl into a more dynamic and robust exploration of the mathematical landscape.

Papers in this version

Showing 60 of 96 papers.

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 1, frozen text):

@misc{lacuna_nonmonotone_optimization_for_nonconvex_l_29d10b44_v1,
  title = {Nonmonotone Optimization for Nonconvex Landscapes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/nonmonotone-optimization-for-nonconvex-landscapes/rdr_29d10b448e244773ae97dfde3eaf1bed/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}