# Coordinate Descent Methods for Fractional Minimization

arXiv: https://arxiv.org/abs/2201.12691 · HTML: https://mlsanity.com/paper/2201.12691/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 55 references that are in the map.
- First posted on arXiv 30 Jan 2022.

## Builds on (most cited first, 18 of 18)

- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems](https://mlsanity.com/paper/1707.03505/) (2017)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [Computing B-Stationary Points of Nonsmooth DC Programs](https://mlsanity.com/paper/1511.01796/) (2015)
- [Variable Smoothing for Weakly Convex Composite Functions](https://mlsanity.com/paper/2003.07612/) (2020)
- [Solving Large-Scale Sparse PCA to Certifiable (Near) Optimality](https://mlsanity.com/paper/2005.05195/) (2020)
- [Sum-of-Squares Lower Bounds for Sparse PCA](https://mlsanity.com/paper/1507.06370/) (2015)
- [A Family of Inexact SQA Methods for Non-Smooth Convex Minimization with Provable Convergence Guarantees Based on the Luo-Tseng Error Bound Property](https://mlsanity.com/paper/1605.07522/) (2016)
- [A Block Decomposition Algorithm for Sparse Optimization](https://mlsanity.com/paper/1905.11031/) (2019)
- [Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization](https://mlsanity.com/paper/1305.4027/) (2013)
- [Exact penalty decomposition method for zero-norm minimization based on MPEC formulation](https://mlsanity.com/paper/1412.4452/) (2014)
- [Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs](https://mlsanity.com/paper/2003.04124/) (2020)
- [First-order algorithms for a class of fractional optimization problems](https://mlsanity.com/paper/2005.06207/) (2020)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [A Decomposition Augmented Lagrangian Method for Low-rank Semidefinite Programming](https://mlsanity.com/paper/2109.11707/) (2021)
- [Proximal-gradient algorithms for fractional programming](https://mlsanity.com/paper/1601.08166/) (2016)

## Built on by (most cited first, 2 of 2)

- [A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2304.03641/) (2023)
- [ADMM for Structured Fractional Minimization](https://mlsanity.com/paper/2411.07496/) (2024)

## Abstract (arXiv)

We consider a class of structured fractional minimization problems, in which the numerator part of the objective is the sum of a differentiable convex function and a convex non-smooth function, while the denominator part is a convex or concave function. This problem is difficult to solve since it is non-convex. By exploiting the structure of the problem, we propose two Coordinate Descent (CD) methods for solving this problem. The proposed methods iteratively solve a one-dimensional subproblem textitglobally, and they are guaranteed to converge to coordinate-wise stationary points. In the case of a convex denominator, under a weak textitlocally bounded non-convexity condition, we prove that the optimality of coordinate-wise stationary point is stronger than that of the standard critical point and directional point. Under additional suitable conditions, CD methods converge Q-linearly to coordinate-wise stationary points. In the case of a concave denominator, we show that any critical point is a global minimum, and CD methods converge to the global minimum with a sublinear convergence rate. We demonstrate the applicability of the proposed methods to some machine learning and signal processing models. Our experiments on real-world data have shown that our method significantly and consistently outperforms existing methods in terms of accuracy.