Abstract
We investigate a family of approximate multi-step proximal point methods, framed as implicit linear discretizations of gradient flow. The resulting methods are multi-step proximal point methods, with similar computational cost in each update as the proximal point method. We explore several optimization methods where applying an approximate multistep proximal points method results in improved convergence behavior. We also include convergence analysis for the proposed method in several problem settings: quadratic problems, general problems that are strongly or weakly (non)convex, and accelerated results for alternating projections.
1. Introduction
In machine learning and signal processing, optimization problems often take the form $\min F(x) = f(x) + h(x)$, where $f$ is smooth and $h$ is a convex, potentially non-smooth regularizer. Standard first-order methods, such as the Proximal Point Method (PPM) or proximal gradient descent, update iterates based solely on the current position. While robust, these single-step methods frequently suffer from slow convergence or instability when faced with poorly conditioned landscapes—where the objective function exhibits vastly different scales of curvature in different directions.
This work proposes a family of multi-step proximal point methods inspired by Backward Differentiation Formulas (BDF), commonly used for the numerical solution of stiff differential equations. By interpreting optimization as the discretization of a continuous "proximal flow," we can leverage higher-order implicit schemes to improve stability and convergence speed without significantly increasing the per-iteration computational cost.
2. Methodology
The core idea is to treat the optimization process as finding the stationary point of a continuous dynamical system. While standard gradient descent corresponds to an explicit Euler discretization and the standard PPM to an implicit Euler discretization, we extend this to multi-step implicit discretizations.
2.1 Multi-Step BDF Schemes
In a $\tau$-step BDF method, the next iterate is determined by a linear combination of the previous $\tau$ iterates. The update rule utilizes specific coefficients to maintain stability and accuracy. The coefficients for BDF schemes of orders 1 through 4 are summarized in the table below.
2.2 Inexact Proximal Steps
A common barrier to using implicit methods is the computational cost of solving the proximal subproblem exactly. We address this by demonstrating that the algorithm remains effective even with approximate proximal steps. Specifically, we analyze the case where the inner subproblem is solved using a few iterations of a standard proximal gradient solver, achieving a $\gamma$-contractive approximation.
3. Experimental Setup
We evaluate the proposed multi-step methods using synthetic datasets designed to test performance under controlled mathematical conditions:
- Compressed Sensing: We generate random sensing matrices with varying singular value decay profiles (uniform, $1/r$, and $\exp(-r)$) to simulate different conditioning levels.
- Alternating Projections: We use random linear subspaces with a noise parameter $\sigma$ to control the coherency (angle) between subspaces.
- Matrix Factorization: We test non-convex alternating minimization on random matrices of varying ranks.
4. Results and Key Insights
Our analysis and experiments yield several key findings:
- Theoretical Convergence: We prove linear convergence rates for strongly convex functions and $O(1/\sqrt{k})$ rates for weakly convex functions, even in the presence of inexact proximal steps.
- Performance Gains: Higher-order schemes (BDF3, BDF4) consistently outperform single-step methods, particularly on ill-conditioned problems. In compressed sensing tasks with exponentially decaying singular values, the performance gap is most pronounced.
- Computational Efficiency: The multi-step extension requires only a simple linear combination of past iterates, adding negligible overhead compared to standard PPM. This provides a "free lunch" in terms of improved convergence per unit of computation.
- Acceleration in Alternating Projections: We mathematically demonstrate that tuning BDF coefficients for a 2-step method can accelerate convergence from $O((1-\rho)^k)$ to $O(\exp(-k\sqrt{\rho}))$, where $\rho$ is the condition number.
- Stability Limits: In non-convex matrix factorization, while BDF2 and BDF3 show advantages, higher orders (BDF4+) can exhibit instability, reflecting the restricted stability regions of higher-order ODE solvers.
5. Conclusion
Multi-step proximal methods inspired by BDF offer a practical and theoretically grounded approach to accelerating optimization. While higher-order methods provide significant benefits for ill-conditioned problems, care must be taken in non-convex settings where instability can arise. Future work will explore other multi-step discretization families and broader applications where these acceleration techniques can be further exploited.
Summary updated