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:
- 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.
- 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