Regularized Barzilai-Borwein method

Congpei An, Xin Xu

TL;DR

Researchers have developed a new family of gradient descent step sizes called Regularized Barzilai-Borwein (RBB). By adding a regularization term to the classic BB method, they’ve created an algorithm that maintains the high speed of quasi-Newton methods while significantly reducing the "violent oscillations" and instability common in ill-conditioned optimization problems.

What Problem Does This Paper Address?

In the world of unconstrained optimization, the Gradient Descent method is the foundational tool. However, its efficiency lives or dies by the "step size"—how far you move in the direction of the steepest descent.

The classic Steepest Descent (SD) method is notoriously slow because it tends to "zigzag" toward the minimum. In 1988, Barzilai and Borwein (BB) revolutionized this by introducing a step size that uses information from the previous iteration to approximate the Hessian (the matrix of second derivatives). This makes it a "quasi-Newton" method: it’s nearly as fast as Newton’s method but much cheaper to compute.

The catch? The BB method is erratic. It is non-monotonic, meaning the objective function value can jump up and down wildly before settling. In "ill-conditioned" problems—where the optimization landscape is a narrow, steep-walled canyon—the BB method can oscillate so violently that it struggles to converge. This paper seeks to "tame" the BB method without losing its signature speed.

Methods

The authors introduce Regularized Barzilai-Borwein (RBB). Here is the breakdown of their approach:

  1. The Regularization Term: The original BB step size is derived by solving a simple least-squares problem. The authors add an $\ell_2^2$-regularization term to this model. This acts as a "stabilizer" that prevents the step size from becoming too extreme.
  2. Adaptive Parameter Scheme: Instead of using a fixed regularization weight ($\tau$), they developed a "three-step" adaptive scheme. This scheme looks at the local mean curvature (how "curvy" the landscape is right now) and the search direction to dynamically adjust the regularization.
  3. Enhanced RBB (ERBB): They further refined the method by introducing a new "alternate step size criterion." This allows the algorithm to intelligently switch between "long" steps (which target small eigenvalues of the Hessian to speed up convergence) and "short" steps (which target large eigenvalues to provide stability).
  4. Global Convergence: For non-quadratic (general) functions, they integrate the Grippo-Lampariello-Lucidi (GLL) non-monotone line search, ensuring the algorithm eventually finds a minimum even when the landscape is complex.

Datasets

The authors evaluated their methods on several challenging benchmarks:

  • Synthetic Quadratic Problems: Strictly convex problems designed with specific condition numbers to test stability.
  • Two-Point Boundary Value Problems: Linear systems derived from differential equations.
  • The Rosenbrock Function: A classic optimization "torture test" featuring a long, narrow, parabolic valley.
  • CUTEst Collection: A standard library of 74 diverse unconstrained optimization problems.
  • Spherical $t$-designs: A complex, non-linear, non-convex optimization problem on an "Oblique manifold" (finding points evenly distributed on a sphere).

Key Insights and Ideas

  • Balancing the Spectrum: The BB method is essentially an eigenvalue approximation tool. Long steps help "clear out" components of the gradient associated with small eigenvalues, while short steps handle the large ones. RBB acts as a bridge, balancing these two extremes.
  • Morphology Awareness: By using the ratio of local curvatures ($\Lambda_k / \Lambda_{k-1}$), the algorithm becomes "aware" of the local morphology. If the landscape suddenly becomes "steep," the algorithm automatically shifts toward a more stable, shorter step size.
  • The "Aha" Moment on Alternation: The authors realized that existing "Alternate BB" (ABB) methods only accounted for one specific scenario of gradient behavior. Their new ERBB criterion identifies a second scenario (where the gradient component is comparable to previous steps), allowing for a more robust switching logic.

Key Results

  • Superior Stability: In ill-conditioned quadratic tests, the standard BB1 method showed "violent oscillations" in gradient norm. RBB and ERBB smoothed these out significantly, leading to faster and more reliable convergence.
  • Performance Profiles: Using "performance profiles" (a way to show the probability of an algorithm being the fastest across many problems), ERBB and RBB consistently outperformed standard BB, ABB, and even the more recent ABBmin method.
  • Manifold Optimization: In the spherical $t$-design tests, RBB proved to be highly efficient, often requiring fewer function evaluations than state-of-the-art competitors like the BBQ method.
  • Robustness: On the Rosenbrock function, ERBB remained stable across varying levels of difficulty ($c$), whereas other methods often required significantly more iterations as the "valley" became narrower.

Limitations and Future Work

  • Computational Overhead: One specific variant, RBBA, requires the computation of $n+3$ inner products per iteration. While negligible for many problems, this could become a bottleneck in extremely high-dimensional spaces compared to the $2$ inner products required by standard BB.
  • Scaling Factor $q$: The adaptive scheme introduces a scaling factor $q$. While the authors suggest $q=8$ based on their experiments, the "optimal" $q$ might vary for highly specific domains.
  • Theoretical Expansion: The current mathematical analysis of the search direction influence is primarily focused on 2D cases. The authors note that a deeper exploration of these principles for $n \ge 3$ dimensions is a necessary next step.

Summary updated

Abstract

We develop a novel stepsize based on \BB method for solving some challenging optimization problems efficiently, named regularized \BB (RBB) stepsize. We indicate that RBB stepsize is the close solution to a $\ell_{2}^{2}$-regularized least squares problem. When the regularized item vanishes, the RBB stepsize reduces to the original \BB stepsize. RBB stepsize includes a class of valid stepsizes, such as another version of \BB stepsize. The global convergence of the corresponding RBB algorithm is proved in solving convex quadratic optimization problems. One scheme for adaptively generating regularization parameters was proposed, named adaptive two-step parameter. An enhanced RBB stepsize is used for solving quadratic and general optimization problems more efficiently. RBB stepsize could overcome the instability of BB stepsize in many ill-conditioned optimization problems. Moreover, RBB stepsize is more robust than BB stepsize in numerical experiments. Numerical examples show the advantage of using the proposed stepsize to solve some challenging optimization problems vividly.
BibTeX
@misc{an2022regularized,
  author = {Congpei An and Xin Xu},
  title = {{Regularized Barzilai-Borwein method}},
  year = {2022},
  eprint = {2211.06624},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2211.06624},
}
Figure