# Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2021.

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

- [Gradient Descent Converges Linearly for Logistic Regression on Separable Data](https://mlsanity.com/paper/2306.14381/) (2023)

## Abstract (arXiv)

We provide several algorithms for constrained optimization of a large class of convex problems, including softmax, ℓp regression, and logistic regression. Central to our approach is the notion of width reduction, a technique which has proven immensely useful in the context of maximum flow [Christiano et al., STOC'11] and, more recently, ℓp regression [Adil et al., SODA'19], in terms of improving the iteration complexity from O(m1/2) to tildeO(m1/3), where m is the number of rows of the design matrix, and where each iteration amounts to a linear system solve. However, a considerable drawback is that these methods require both problem-specific potentials and individually tailored analyses. As our main contribution, we initiate a new direction of study by presenting the first unified approach to achieving m1/3-type rates. Notably, our method goes beyond these previously considered problems to more broadly capture quasi-self-concordant losses, a class which has recently generated much interest and includes the well-studied problem of logistic regression, among others. In order to do so, we develop a unified width reduction method for carefully handling these losses based on a more general set of potentials. Additionally, we directly achieve m1/3-type rates in the constrained setting without the need for any explicit acceleration schemes, thus naturally complementing recent work based on a ball-oracle approach [Carmon et al., NeurIPS'20].