Inexact Non-Convex Newton-Type Methods

Zhewei Yao, Peng Xu, Farbod Roosta-Khorasani, Michael W. MahoneyarXiv 2018 · DOI · arXiv

Abstract

For solving large-scale non-convex problems, we propose inexact variants of trust region and adaptive cubic regularization methods, which, to increase efficiency, incorporate various approximations. In particular, in addition to approximate sub-problem solves, both the Hessian and the gradient are suitably approximated. Using rather mild conditions on such approximations, we show that our proposed inexact methods achieve similar optimal worst-case iteration complexities as the exact counterparts. Our proposed algorithms, and their respective theoretical analysis, do not require knowledge of any unknowable problem-related quantities, and hence are easily implementable in practice.

Introduction: The Challenge of Non-Convex Optimization

In modern machine learning, non-convex optimization is ubiquitous, particularly in training deep neural networks. While first-order methods like Stochastic Gradient Descent (SGD) are computationally inexpensive, they often struggle with saddle points—regions where the gradient vanishes but the objective is not at a minimum.

Second-order (Newton-type) methods address this by utilizing curvature information (the Hessian) to navigate complex landscapes. However, computing an exact Hessian for large datasets is computationally prohibitive. Previous "inexact" or "stochastic" second-order methods often required exact gradients or relied on "unknowable" problem constants, such as Lipschitz continuity parameters. Incorrectly estimating these constants can lead to algorithmic instability or failure.

Proposed Methods: Inexact TR and ARC

The authors introduce two adaptive algorithms: Inexact Trust Region (TR) and Inexact Adaptive Cubic Regularization (ARC). These methods are designed to be computationally efficient by allowing three simultaneous levels of approximation:

  1. Inexact Gradients: Utilizing approximations (e.g., via sub-sampling) instead of full gradients.
  2. Inexact Hessians: Employing Hessian matrix approximations.
  3. Inexact Sub-problem Solves: Requiring only "good enough" solutions to internal direction-finding steps.
Algorithms 1 and 2 for Inexact TR and Inexact ARC.

A key feature of these algorithms is their adaptivity. By monitoring the ratio between actual and predicted objective function reduction, the algorithms adjust their trust region radius or regularization parameter dynamically, eliminating the need for pre-defined Lipschitz constants.

Key Insights: Balancing Accuracy and Complexity

A significant finding of this work is that optimal worst-case iteration complexity can be maintained even with "sloppy" gradient and Hessian approximations, provided the error is bounded relative to the target accuracy $\epsilon$.

Furthermore, the algorithms implement a strategy for handling small gradients: when the gradient estimate is below a certain threshold, the algorithm prioritizes Hessian information (negative curvature) to escape saddle points. This robustness makes the methods "parameter-free" in a practical sense, significantly reducing the need for extensive hyper-parameter tuning.

Performance and Theoretical Guarantees

The proposed methods achieve optimal theoretical convergence rates while demonstrating superior empirical performance. In experiments on non-convex nonlinear least squares tasks, Inexact TR was found to be 3–5 times faster than versions using exact gradients and up to 10 times faster than standard "Full TR" in terms of total oracle calls.

Comparison of the proposed Inexact TR and ARC algorithms against existing methods.

As shown in the comparison table above, the proposed algorithms (Algorithm 1 and 2) are the only ones that simultaneously support inexact gradients, inexact Hessians, and practical implementability without requiring unknowable parameters, all while maintaining optimal iteration complexity ($O(\epsilon^{-2.5})$ for TR and $O(\epsilon^{-1.5})$ for ARC).

Conclusion and Future Directions

While the results are promising, some theoretical and practical challenges remain. Achieving the optimal $O(\epsilon^{-1.5})$ rate for the ARC variant currently requires a stricter gradient approximation condition, which may be an artifact of the proof technique. Future work could explore applying these frameworks to modern over-parameterized deep learning models and investigating more advanced sampling strategies, such as sketching, to further enhance computational efficiency.

Summary updated

Abstract

For solving large-scale non-convex problems, we propose inexact variants of trust region and adaptive cubic regularization methods, which, to increase efficiency, incorporate various approximations. In particular, in addition to approximate sub-problem solves, both the Hessian and the gradient are suitably approximated. Using rather mild conditions on such approximations, we show that our proposed inexact methods achieve similar optimal worst-case iteration complexities as the exact counterparts. Our proposed algorithms, and their respective theoretical analysis, do not require knowledge of any unknowable problem-related quantities, and hence are easily implementable in practice. In the context of finite-sum problems, we then explore randomized sub-sampling methods as ways to construct the gradient and Hessian approximations and examine the empirical performance of our algorithms on some real datasets.
BibTeX
@misc{yao2018inexact,
  author = {Zhewei Yao and Peng Xu and Farbod Roosta-Khorasani and Michael W. Mahoney},
  title = {{Inexact Non-Convex Newton-Type Methods}},
  year = {2018},
  eprint = {1802.06925},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.06925},
}
Figure