TL;DR
This paper introduces iVPGSA, the first inexact proximal algorithm designed to solve a broad class of fractional optimization problems (minimizing a ratio of functions). By allowing for approximate subproblem solutions and utilizing a "variable metric" to adapt to problem geometry, the algorithm achieves significant speedups—often over 5x faster than existing methods—while maintaining rigorous global convergence guarantees.
What Problem Does This Paper Address?
Many tasks in signal processing and machine learning involve minimizing a ratio, such as the $\ell_1/\ell_2$ norm used for sparse signal recovery. These are known as fractional optimization problems. Specifically, the authors look at problems where the numerator is a mix of convex and smooth functions, and the denominator is a nonsmooth convex function.
The core challenge is that existing algorithms (like Dinkelbach’s method or the Proximal Gradient-subgradient Algorithm) usually require solving a "subproblem" exactly at every iteration. In practice, finding an exact solution is often computationally exhausting or impossible, especially when dealing with complex constraints. There was a clear gap: we needed an algorithm that could handle inexact (approximate) solutions while still guaranteeing that the overall process would eventually reach the correct answer.
Methods
The authors propose the inexact Variable Metric Proximal Gradient-subgradient Algorithm (iVPGSA). Its novelty lies in three main areas:
- Inexactness with Verifiable Criteria: Instead of demanding a perfect solution to the proximal subproblem, iVPGSA accepts an approximate one. Crucially, it provides a practical "error criterion" that a developer can actually check during execution to ensure the approximation is "good enough."
- Variable Metric: Standard proximal methods use a fixed step size (effectively a "circular" geometry). iVPGSA uses a variable metric ($H_k$), allowing the algorithm to warp its search space to fit the "contours" of the problem. This enables the use of powerful second-order solvers, like the Semi-smooth Newton (SSN) method, to solve the subproblems.
- Improved KL Analysis: Proving that an algorithm converges usually requires showing that the objective function drops by a "sufficient" amount every single step. Inexact algorithms are messy and don't always drop strictly. The authors developed a new theoretical framework based on the Kurdyka-Łojasiewicz (KL) property that proves global convergence even when the descent is only approximate.
Datasets
The researchers evaluated iVPGSA using both synthetic and real-world data:
- Synthetic Data: Randomly generated Gaussian matrices for testing $\ell_1/\ell_2$ Lasso and constrained sparse optimization.
- Real-world Benchmarks: Two datasets from the UCI Machine Learning Repository:
- mpg7: A dataset expanded with polynomials to test basis function selection.
- gisette: A handwritten digit recognition dataset (originally from a NIPS 2003 challenge) used to test high-dimensional sparse recovery.
Key Insights and Ideas
- The "Good Enough" Principle: You don't need perfection at every step to reach the peak (or in this case, the valley). By relaxing the subproblem requirement, the algorithm spends less time on "over-solving" early iterations.
- Bridging First and Second Order: iVPGSA acts as a bridge. It has the global convergence stability of a first-order proximal method but can leverage the blistering local speed of second-order Newton-type methods through its variable metric.
- Theoretical Versatility: The "Improved KL Analysis" presented isn't just for this algorithm. It provides a blueprint for other researchers to prove convergence rates for any inexact algorithm that lacks a strict sufficient descent property.
Key Results
The numerical experiments compared iVPGSA against state-of-the-art methods like PGSA_BE and the Moving Balls-approximation (MBA) algorithm.
- Speed: On the $\ell_1/\ell_2$ Lasso problem with large datasets ($n \geq 10,000$), iVPGSA was consistently at least 5 times faster than PGSA_BE.
- Robustness: On real-world data (
mpg7andgisette), existing methods often struggled with slow reduction rates due to large Lipschitz constants. iVPGSA, thanks to its second-order subproblem solver, maintained high performance where others stalled. - Convergence: The authors proved that the algorithm's convergence rate is explicitly tied to the "KL exponent" of the objective function—providing a mathematical guarantee of how fast the error vanishes over time.
Limitations and Future Work
The authors acknowledge one primary theoretical constraint: Assumption D. This assumption requires that one specific type of error ($\delta_k$) must eventually become zero after a certain number of iterations. While they showed this is achievable for problems like the $\ell_1/\ell_2$ Lasso, it might be harder to satisfy for problems with extremely complex, non-box constraints.
Future directions include:
- Eliminating Assumption D to make the algorithm even more general.
- Applying the iVPGSA framework to other types of fractional problems, such as "sum-of-ratios" optimization, which appears in wireless communication and finance.
Summary updated