An Inexact Variable Metric Proximal Gradient-subgradient Algorithm for a Class of Fractional Optimization Problems

Lei Yang, Xiangrui Kong, Min Zhang, Yaohua HuarXiv 2025 · DOI · arXiv

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:

  1. 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."
  2. 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.
  3. 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 (mpg7 and gisette), 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

Abstract

In this paper, we study a class of fractional optimization problems, in which the numerator of the objective is the sum of a convex function and a differentiable function with a Lipschitz continuous gradient, while the denominator is a nonsmooth convex function. This model has broad applicability and encompasses several important optimization problems in the literature. To address these problems, we propose an inexact variable metric proximal gradient-subgradient algorithm (iVPGSA), which, to our knowledge, is the first inexact proximal algorithm specifically designed for solving such type of fractional problems. By incorporating a variable metric proximal term and allowing for inexact solutions to the subproblem under a flexible error criterion, the proposed algorithm is highly adaptable to a broader range of problems while achieving favorable computational efficiency. Under mild assumptions, we establish that any accumulation point of the sequence generated by the iVPGSA is a critical point of the target problem. Moreover, we develop an improved Kurdyka-Łojasiewicz (KL)-based analysis framework to prove the global convergence of the entire sequence and characterize its convergence rate, \textit{without} requiring a strict sufficient descent property. Our results offer detailed insights into how the KL exponent and inexactness influence the convergence rate. The proposed analysis framework also has the potential to serve as a theoretical tool for studying the convergence rates of a wide range of inexact algorithms beyond the iVPGSA. Finally, some numerical experiments on the $\ell_1/\ell_2$ Lasso problem and the constrained $\ell_1/\ell_2$ sparse optimization problem are conducted to show the superior performance of the iVPGSA in comparison to existing algorithms.
BibTeX
@misc{yang2025inexact,
  author = {Lei Yang and Xiangrui Kong and Min Zhang and Yaohua Hu},
  title = {{An Inexact Variable Metric Proximal Gradient-subgradient Algorithm for a Class of Fractional Optimization Problems}},
  year = {2025},
  eprint = {2504.11023},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.11023},
  howpublished = {arXiv},
}
Figure