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

Deeksha Adil, Brian Bullins, Sushant Sachdeva

Abstract

We provide several algorithms for constrained optimization of a large class of convex problems, including softmax, $\ell_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, $\ell_p$ regression [Adil et al., SODA'19], in terms of improving the iteration complexity from $O(m^{1/2})$ to $\tilde{O}(m^{1/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 $m^{1/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 $m^{1/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].

Introduction

In large-scale optimization, the standard goal is to minimize a convex function subject to linear constraints (e.g., $Ax = b$). Traditional methods, such as Interior Point Methods (IPMs), typically require $O(m^{1/2})$ iterations to reach high accuracy. While $m^{1/2}$ is theoretically efficient, for modern datasets where $m$ (the number of rows or constraints) reaches millions, this complexity remains a significant computational bottleneck.

Previously, the "width reduction" technique was employed to break this barrier, achieving a faster rate of $\tilde{O}(m^{1/3})$ iterations. However, these applications were problem-specific, tailored for tasks like maximum flow or $\ell_p$ regression. This work addresses the lack of a unified theory, bringing the $m^{1/3}$ speedup to the broader class of "quasi-self-concordant" functions.

The Quasi-Self-Concordant (q.s.c.) Framework

The authors base their unification on the property of Quasi-Self-Concordance (q.s.c.). A function is defined as $M$-q.s.c. if its third derivative is bounded by its second derivative: $|f'''(x)| \leq M f''(x)$. This class is remarkably broad, encompassing logistic regression, softmax, and $\ell_p$ regression.

The Unified Width-Reduction Algorithm

The proposed approach utilizes a two-stage algorithmic structure. The first stage, the Crude Oracle (Algorithm 1), uses a Multiplicative Weight Update (MWU) scheme combined with width reduction to find a "rough" solution that satisfies constraints with a bounded norm. The second stage, Boosting to High Accuracy, performs iterative refinement by solving a sequence of simpler quadratic "residual problems" within small $\ell_\infty$ boxes to rapidly converge to the true optimum.

Algorithm 1: Width-Reduced Algorithm for M-q.s.c. Functions (QSC-MWU).

The core innovation lies in the management of potentials. By tracking coupled potential functions—one for dual weights and another for "resistances"—the algorithm ensures that no single coordinate (the "width") dominates the complexity. This allows for larger steps and more efficient traversal of the search space.

Key Results and Insights

The primary contribution is the proof of a convergence rate of $\tilde{O}(m^{1/3})$ iterations for any $M$-quasi-self-concordant function. Specific results include:

  • Softmax/$\ell_\infty$ Regression: A rate of $\tilde{O}(m^{1/3} \epsilon^{-5/3})$ for an $\epsilon$-approximate solution.
  • High-Accuracy General Case: Complexity of $\tilde{O}(M R m^{1/3} \log(1/\epsilon))$, where $R$ is the norm of the optimal solution.
  • Linear System Solves: Each iteration reduces to solving a linear system, making the per-iteration cost comparable to standard Newton-type methods but requiring significantly fewer total iterations.

Notably, this method achieves the $m^{1/3}$ rate directly through width reduction without relying on complex Nesterov-style acceleration. This represents the first time width reduction has been successfully applied to directly solve constrained logistic regression with such theoretical guarantees.

Discussion

As a theoretical advancement, this work focuses on algorithmic complexity and convergence proofs rather than empirical benchmarks. While the $\tilde{O}(m^{1/3})$ iteration count is a major theoretical improvement, practical implementation must consider the constant factors and the specific costs of width-reduction steps. The complexity's linear dependence on the norm of the optimum ($R$) and the q.s.c. constant ($M$) suggests that the $m^{1/3}$ advantage is most pronounced when these values are well-behaved. Future research may explore deeper connections between width reduction and Monteiro-Svaiter acceleration to further push the boundaries of optimization speed.

Summary updated

Abstract

We provide several algorithms for constrained optimization of a large class of convex problems, including softmax, $\ell_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, $\ell_p$ regression [Adil et al., SODA'19], in terms of improving the iteration complexity from $O(m^{1/2})$ to $\tilde{O}(m^{1/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 $m^{1/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 $m^{1/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].
BibTeX
@inproceedings{adil2021unifying,
  author = {Deeksha Adil and Brian Bullins and Sushant Sachdeva},
  title = {{Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=8n0eirHTH7I},
}
Figure