Abstract
Traditional Interior Point Methods (IPMs) are the gold standard for high-precision convex optimization but are often bottlenecked by the requirement for second-order information—specifically, the computation and inversion of the Hessian matrix. This paper introduces a novel quasi-Newton IPM that achieves state-of-the-art theoretical running times for linear optimization and semidefinite programming (SDP) using only a first-order gradient oracle. By maintaining a dynamic preconditioner and leveraging the property of strong self-concordance, the proposed method matches the performance of second-order methods while significantly reducing the per-iteration computational burden.
Introduction
Interior Point Methods (IPMs) have long been favored for their ability to solve convex optimization problems to high precision in a polynomial number of iterations. However, the practical and theoretical efficiency of these methods is often limited by the "Hessian bottleneck." In each iteration, a standard IPM requires the calculation of the Hessian matrix of a barrier function, followed by solving a linear system. For large-scale problems, particularly Semidefinite Programs (SDPs), the cost of storing and inverting these matrices is prohibitive.
While first-order methods (gradient-only) are computationally cheaper per iteration, they typically lack the rapid convergence to high precision that characterizes IPMs. This research addresses a fundamental question: Is it possible to design an IPM that maintains the convergence guarantees of second-order methods while relying solely on a gradient oracle?
Methodology
The core of the proposed approach is a quasi-Newton framework that replaces the exact Hessian with a dynamic preconditioner, $\tilde{H}$. The algorithm updates this preconditioner iteratively to ensure it remains a faithful approximation of the true Hessian $H$.
1. Adaptive Preconditioning and Excentricity
Instead of recomputing the Hessian at every step, the algorithm maintains $\tilde{H}$ through a series of rank-1 updates. The quality of this approximation is monitored using an "excentricity" potential function, a technique adapted from Dunagan and Harvey. This potential function measures the spectral divergence between the preconditioner and the true Hessian. If a Newton-like step fails to provide sufficient progress, the failure serves as a certificate, identifying a specific direction in which the preconditioner needs adjustment via a rank-1 update.
2. Hessian-Vector Product Estimation
Because the algorithm lacks direct access to the Hessian, it approximates Hessian-vector products using finite differences of gradients: $$H_y v \approx \frac{1}{\tau}(\nabla g(y + \tau v) - \nabla g(y))$$ This allows the method to simulate the behavior of second-order steps using only first-order queries.
3. Strong Self-Concordance
The analysis hinges on the property of strong self-concordance. Unlike standard self-concordance, which bounds Hessian changes in the spectral norm, strong self-concordance utilizes the more restrictive Frobenius norm. This property allows for tighter control over the excentricity potential as the algorithm traverses the central path, ensuring that the preconditioner does not degrade too rapidly.
4. Amortized Path-Following
To maintain the validity of the preconditioner across iterations, the algorithm employs a "slowed" path-following strategy. By taking slightly shorter steps than a traditional IPM, the method "recycles" the preconditioner, amortizing the cost of updates over many iterations and keeping the total query complexity low.
Theoretical Results
As a theoretical contribution to the field of optimization, the paper provides rigorous complexity bounds for two primary classes of problems:
- Linear Optimization: The algorithm solves linear problems over an $n$-dimensional convex set in $\tilde{O}(Tn + n^3)$ time, where $T$ represents the time for a single gradient query. This result is competitive with the best-known cutting-plane methods.
- Semidefinite Programming (SDP): For an SDP with $m$ constraints and $n \times n$ variables (where $m \ge n$), the algorithm achieves a running time of $\tilde{O}(mn^4 + m^{1.25}n^{3.5})$.
By avoiding the explicit construction of the full Hessian—which in SDPs involves complex rectangular matrix multiplications—this method offers a significant theoretical improvement for applications where the number of constraints $m$ is large.
Discussion and Limitations
One of the most striking insights of this work is the parallel it draws between gradient oracles and separation oracles. The matching complexity between this gradient-based IPM and traditional cutting-plane methods suggests a deep underlying connection between these two modes of convex set access.
However, the method is not without limitations. The requirement for a strongly self-concordant barrier, while satisfied by standard barriers (logarithmic, universal, and entropic), may require specific scaling that can impact iteration counts. Additionally, while the algorithm is theoretically robust, the practical implementation of high-precision finite difference approximations requires careful consideration of numerical stability and bit-complexity.
Conclusion
This paper demonstrates that second-order information is not strictly necessary to achieve the high-precision convergence rates of Interior Point Methods. By dynamically maintaining a preconditioner through gradient queries, the proposed method bridges the gap between first-order efficiency and second-order convergence, providing a new theoretical foundation for large-scale convex optimization.
Summary updated