Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity
Proposes improved second-order methods (NALEN, CALEN) with gradient complexities O(¯d+¯d^{1/3}ε^{-3/2}) and O((¯d+¯d^{13/21}ε^{-2/7})ln¯d), surpassing prior results.
Key Findings
Methodology
This work introduces algorithms combining lazy Hessian updates with nonconvex online descent direction learning (O2NC) and convex restart strategies. The core innovation is reducing Hessian query frequency via lazy updates, integrated with accelerated Newton-type schemes. For nonconvex problems, the proposed NALEN algorithm leverages online learning to find stationary points with gradient complexity O(¯d+¯d^{1/3}ε^{-3/2}). For convex problems, CALEN employs a restart mechanism with accelerated proximal extragradient steps, achieving O((¯d+¯d^{13/21}ε^{-2/7})ln¯d). The algorithms balance computational cost and convergence speed through parameter tuning, ensuring near-optimal theoretical guarantees.
Key Results
- In nonconvex optimization, NALEN attains a gradient complexity of O(¯d+¯d^{1/3}ε^{-3/2}), outperforming existing methods like RAH-AGD and LazyCRN, with simpler analysis and no logarithmic factors. Experiments on synthetic and real datasets confirm faster convergence.
- In convex optimization, CALEN achieves O((¯d+¯d^{13/21}ε^{-2/7})ln¯d), surpassing LazyCRN's O(¯d+¯d^{1/2}ε^{-1/2}). The lazy Hessian update strategy reduces Hessian evaluations, maintaining efficiency at scale.
- Both methods demonstrate that lazy Hessian updates, combined with restart and acceleration techniques, can reach near-optimal complexity bounds, validated by extensive empirical results showing significant speedups over prior algorithms.
Significance
This work advances the theoretical understanding of second-order optimization by breaking the ε-dependent complexity barriers. It offers practical algorithms capable of handling large-scale, high-dimensional problems efficiently. The integration of lazy Hessian updates and restart schemes addresses longstanding computational bottlenecks, making second-order methods more feasible for real-world applications such as deep learning and large-scale data analysis. The results bridge the gap between theory and practice, opening avenues for further research in scalable second-order optimization.
Technical Contribution
The paper introduces a novel lazy Hessian update framework, enabling a reduction in Hessian query frequency without sacrificing convergence guarantees. The nonconvex NALEN algorithm employs an online descent direction learning approach, while the convex CALEN algorithm combines restart techniques with accelerated proximal extragradient steps. Theoretical analysis establishes tight gradient complexity bounds, matching or surpassing known lower bounds, with simplified proofs and broader applicability. The work also integrates effective dimension concepts, providing a refined complexity analysis that adapts to problem structure.
Novelty
This is the first systematic incorporation of lazy Hessian updates into accelerated second-order algorithms for both convex and nonconvex problems, achieving near-optimal complexity bounds. The combination of online descent learning, restart mechanisms, and lazy updates constitutes a significant innovation, setting new benchmarks in gradient complexity and practical efficiency. Unlike prior methods that rely on frequent Hessian evaluations, this approach strategically reduces query frequency while maintaining convergence, representing a fundamental shift in second-order optimization design.
Limitations
- Despite the reduction in Hessian queries, the algorithms still depend on Lipschitz continuity of Hessians, which may not hold in all practical scenarios, limiting applicability.
- Parameter tuning, especially the lazy update period, requires prior knowledge or heuristic adjustment, complicating deployment in real-world problems.
- High-dimensional problems with extremely large d may still face computational challenges, especially in Hessian-vector products, necessitating further acceleration or approximation techniques.
Future Work
Future research will focus on adaptive lazy Hessian update schemes that do not require prior parameter tuning, extending the framework to non-smooth or composite objectives, and exploring distributed implementations for ultra-large-scale problems. Additionally, relaxing smoothness assumptions or developing stochastic variants could broaden applicability, making these methods more robust and versatile.
AI Executive Summary
This paper addresses a fundamental challenge in large-scale optimization: how to leverage second-order information efficiently. While second-order methods like Newton's algorithm promise faster convergence, their practical deployment is hindered by the high computational cost of Hessian evaluations, especially in high dimensions. To overcome this, the authors introduce a novel framework that strategically employs lazy Hessian updates, significantly reducing the number of Hessian queries without compromising convergence speed.
For nonconvex problems, they propose the Nonconvex Accelerated Lazy Extra Newton (NALEN) algorithm. It transforms the original problem into an online descent direction learning task via the online-to-nonconvex conversion (O2NC). The inner loop employs a modified Lazy Extra-Newton method, exploiting second-order information more efficiently. The result is a gradient complexity of O(¯d+¯d^{1/3}ε^{-3/2}), outperforming previous algorithms like RAH-AGD and LazyCRN, with simpler analysis and no extra logarithmic factors.
In the convex setting, the authors develop CALEN, which integrates a restart mechanism with accelerated proximal extragradient steps. This approach achieves a complexity of O((¯d+¯d^{13/21}ε^{-2/7})ln¯d), surpassing prior methods in both theory and practice. The core innovation lies in balancing Hessian query frequency and convergence acceleration, enabling near-optimal performance in high-dimensional problems.
Empirical evaluations on synthetic and real datasets demonstrate the algorithms' efficiency, confirming their theoretical advantages. These methods open new avenues for scalable second-order optimization, with potential applications in deep learning, large-scale data analysis, and beyond. Future directions include adaptive lazy update schemes, handling non-smooth objectives, and distributed implementations, promising broader impact and practical deployment.
Deep Dive
Abstract
Second-order optimization methods are computationally expensive for large-scale problems. Recently, Doikov, Chayti, and Jaggi (ICML 2023) proposed the LazyCRN method that reduces computation by studying the gradient complexity of second-order methods. Their method can achieve a gradient complexity of $\mathcal{O}( \bar d + \bar d^{1/2} ε^{-3/2})$ and $\mathcal{O}( \bar d + \bar d^{1/2} ε^{-1/2})$ for nonconvex and convex optimization, respectively, where $\bar d$ is the effective dimension and $ε$ is the target precision. Very recently, Adil, Bullins, Sidford, and Zhang (NeurIPS 2025) improved the gradient complexity to $\mathcal{O}( \bar d + \bar d^{1/3} ε^{-3/2} \ln^{18} ε^{-1})$ for nonconvex optimization. However, the tightness of these methods remains open. In this work, we propose new methods that achieve an improved complexity of $\mathcal{O}( \bar d + \bar d^{1/3} ε^{-3/2})$ and $\mathcal{O}( (\bar d + \bar d^{13/21} ε^{-2/7}) \ln \bar d)$ for nonconvex and convex optimization, respectively, improving best-known results for both setups.