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:
- Inexact Gradients: Utilizing approximations (e.g., via sub-sampling) instead of full gradients.
- Inexact Hessians: Employing Hessian matrix approximations.
- Inexact Sub-problem Solves: Requiring only "good enough" solutions to internal direction-finding steps.
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.
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