A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness

Zhenyu Sun, Ermin Wei

Abstract

Modern machine learning models, particularly deep neural networks, often operate in non-convex landscapes where the rate of gradient change is not constant—a property known as non-uniform smoothness. While first-order methods have been adapted for these environments using gradient clipping, second-order quasi-Newton methods have historically struggled with stability in such volatile settings. This paper introduces ClippedSQN, a stochastic quasi-Newton framework that integrates gradient clipping, variance reduction, and a novel adaptive L-BFGS update. We demonstrate that ClippedSQN achieves the optimal $O(\epsilon^{-3})$ sample complexity for finding $\epsilon$-approximate stationary points, effectively bridging the gap between the stability of clipped first-order methods and the accelerated convergence of second-order optimization.

Introduction

In the field of mathematical optimization, the "uniform smoothness" assumption—the idea that the gradient of a function changes no faster than a fixed constant $L$—is a cornerstone of convergence analysis. However, empirical evidence from deep learning suggests that many objective functions exhibit non-uniform smoothness, where the local curvature increases as the gradient norm grows. This phenomenon, often modeled as $(L_0, L_1)$-smoothness, renders standard stochastic gradient descent (SGD) and traditional quasi-Newton methods inefficient or unstable.

While first-order methods have addressed this through gradient clipping, quasi-Newton methods—which utilize curvature information via Hessian approximations—have remained difficult to stabilize under non-uniform conditions. This research presents ClippedSQN, the first stochastic quasi-Newton method specifically engineered to handle non-convex problems with non-uniform smoothness while maintaining theoretical optimality.

The ClippedSQN Framework

ClippedSQN is built upon three algorithmic pillars designed to balance stability with convergence speed:

1. Gradient Clipping

To navigate regions of high curvature without taking excessively large, unstable steps, ClippedSQN employs gradient clipping. By bounding the update based on the gradient norm, the algorithm prevents the "exploding" updates that typically occur when a quasi-Newton method encounters a region where the smoothness constant is locally very high.

2. Spider-style Variance Reduction

To improve the fidelity of the gradient estimates, the method incorporates a variance reduction technique inspired by the Spider algorithm. ClippedSQN periodically computes a full gradient (or a large-batch estimate) and then uses smaller, efficient mini-batch updates to track the gradient's trajectory. This high-fidelity estimation is crucial for the quasi-Newton update to accurately approximate the Hessian.

3. Stochastic Adaptive L-BFGS

The core innovation is the Adaptive L-BFGS (Limited-memory Broyden–Fletcher–Goldfarb–Shanno) update. The authors introduce specific design parameters ($\delta, q, \kappa$) to modify the standard L-BFGS recursion. These parameters allow for explicit control over the eigenvalues of the Hessian approximation, ensuring it remains positive definite and well-conditioned even in non-uniform landscapes. This mathematical control is the key to proving convergence in non-convex settings.

Experimental Evaluation

The authors evaluated ClippedSQN against state-of-the-art first-order and second-order methods using synthetic datasets ($d=100$) designed to simulate the challenges of non-uniformity:

  • Non-convex Robust Linear Regression: Utilizing a logarithmic loss function that creates a highly non-convex landscape.
  • Non-convex Logistic Regression: A classification task using a sigmoid-based loss function.

Key Results

  • Optimal Complexity: ClippedSQN achieves a sample complexity of $O(\epsilon^{-3})$, matching the theoretical lower bound for stochastic non-convex optimization.
  • Performance Gains: In head-to-head comparisons, ClippedSQN converged faster and reached lower training errors than Spider and (L0, L1)-Spider.
  • Stability: Unlike other quasi-Newton variants such as SdLBFGS, ClippedSQN remained stable in non-uniform test cases, reaching higher accuracy without the divergence issues typically associated with second-order methods in volatile landscapes.

Discussion and Insights

The primary insight of this work is that second-order curvature information is not just compatible with non-uniform landscapes—it is actually highly beneficial, provided the algorithm can stabilize the Hessian approximation. By leveraging $(L_0, L_1)$-smoothness as a more realistic model for deep learning, the authors demonstrate that one does not have to sacrifice the speed of quasi-Newton methods to achieve the robustness of clipped SGD.

Limitations and Future Work

Despite its theoretical and empirical success, ClippedSQN introduces several hyperparameters ($\delta, q, \kappa, \beta, c$) that may require careful tuning for specific architectures. Additionally, while quasi-Newton methods are more computationally efficient than full Newton methods, they still incur an $O(pd)$ cost per step (where $p$ is memory size and $d$ is dimension), which is higher than standard first-order methods. Future research should focus on scaling ClippedSQN to large-scale models, such as Transformers, to determine if these benefits persist in high-dimensional production environments.

Summary updated

BibTeX
@inproceedings{sun2024stochastic,
  author = {Zhenyu Sun and Ermin Wei},
  title = {{A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness}},
  booktitle = {CDC},
  year = {2024},
  doi = {10.1109/cdc56724.2024.10886208},
}
Figure