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

Deeksha Adil, Brian Bullins, Sushant Sachdeva

Introduction

Fast constrained convex optimization is a cornerstone of modern machine learning and theoretical computer science. Specifically, problems of the form $\min_{Ax=b} \sum f((Px)_i)$ frequently arise across various domains. A highly relevant class of functions within this space are quasi-self-concordant (q.s.c.) functions, defined by the property that their third derivative is bounded by their second derivative. This property is shared by widely used machine learning loss functions, including logistic regression, softmax, and $\ell_p$ regression.

Historically, solving these constrained optimization problems required iterative methods where the number of iterations scaled with $O(m^{1/2})$, where $m$ is the number of rows in the design matrix. To accelerate this, researchers introduced a technique called width reduction, which successfully dropped the dependence to $\tilde{O}(m^{1/3})$. However, width reduction has traditionally been notoriously finicky: past applications required researchers to invent highly specialized potential functions and bespoke mathematical proofs for every single new problem (e.g., one proof for max flow, a completely different one for $\ell_p$ regression).

This paper bridges that gap by presenting the first unified algorithmic framework for optimizing the broad class of q.s.c. functions, eliminating the need for problem-specific, individually tailored mathematical analyses.

Methodology: A Unified Width-Reduced MWU

The core contribution of the paper is the development of a unified width-reduced Multiplicative Weight Update (MWU) algorithm. Instead of custom-building the mathematics for each specific loss function, the authors introduce a generalized pair of coupled potential functions ($\Psi$ and $\Phi$) that can govern the width reduction process for any q.s.c. function.

The optimization approach is split into two main phases:

  1. Crude Approximation: The algorithm alternates between solving a linear regression subproblem and updating weights. If the proposed update is well-behaved (i.e., its "width" does not exceed a certain threshold), the algorithm takes a "flow step" (an additive update). If certain coordinates exceed the threshold, it takes a "width reduction step" (a multiplicative update to the weights/resistances). This phase yields a feasible solution bounded in the $\ell_\infty$-norm.
  2. High-Accuracy Boosting: Using the crude solution as a warm start, the algorithm iteratively refines the answer. It accomplishes this by solving a sequence of residual optimization problems inside small $\ell_\infty$ boxes using binary search and a secondary width-reduced MWU routine, ultimately yielding a high-accuracy solution.

(Note: As a purely theoretical optimization paper focused on algorithmic complexity bounds, empirical dataset evaluations are not discussed.)

Key Insights

  • Universal Potentials: The major breakthrough of the paper is proving that a single, carefully designed pair of potential functions can manage the width reduction process for the entire class of quasi-self-concordant functions. Researchers no longer need a custom proof for every new machine learning loss function that fits this profile.
  • Implicit Acceleration: The method achieves accelerated $m^{1/3}$-type rates directly in the constrained setting without relying on complex, explicit acceleration schemes (such as Monteiro-Svaiter acceleration). This naturally complements recent unconstrained "ball-oracle" approaches.
  • A Milestone for Logistic Regression: Because the framework is unified, this marks the first time width reduction has been successfully and directly applied to constrained logistic regression, a fundamental problem in statistics and machine learning.

Theoretical Results

The paper provides rigorous theoretical bounds on the number of linear system solves required to reach an $\epsilon$-approximate solution across various problem settings:

  • General Q.S.C. Functions: Achieves high accuracy in $\tilde{O}(M R m^{1/3} \log(MR) \log(1/\epsilon))$ linear system solves, where $R$ is the $\ell_\infty$ bound on the optimum, and $M$ is the q.s.c. parameter.
  • Softmax / $\ell_\infty$ Regression: Achieves a $(1+\epsilon)$ approximate solution in $\tilde{O}(m^{1/3}\epsilon^{-5/3})$ linear system solves.
  • $\ell_p$ Regression ($p \ge 3$): Solves the $\mu$-regularized problem in $\tilde{O}(p^2 \mu^{-1/(p-2)} m^{1/3} R)$ linear system solves.
  • Logistic Regression: Achieves high accuracy in $\tilde{O}(m^{1/3} R)$ linear system solves.

Limitations and Future Directions

While the theoretical speedups are significant, the runtime guarantees depend linearly on $R$ (the $\ell_\infty$-norm bound of the optimal solution). In worst-case scenarios, $R$ can be large, which could bottleneck the theoretical efficiency. Additionally, the algorithm assumes access to an exact linear system solver at each iteration; in practice, this can be computationally expensive for massive, dense matrices.

Looking forward, the authors note that their unified width reduction achieves algorithmic improvements remarkably similar to those achieved by Monteiro-Svaiter acceleration. They suggest that a deeper, yet-to-be-understood theoretical connection likely exists between the mechanics of width reduction and Monteiro-Svaiter acceleration, highlighting this as a prime target for future theoretical research.

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 \emph{unified} approach to achieving $m^{1/3}$-type rates. Notably, our method goes beyond these previously considered problems to more broadly capture \emph{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},
}

Loading related content...

Figure