Quasi-Self-Concordant Optimization with ${\ell }_{\infty }$ Lewis Weights

In this paper, we study the problem ${\min }_{x\in R^d,Nx=v}\sum {}_{i=1}^{n}f((Ax-b{)}_i)$ for a quasi-self-concordant function $f:R\to R$, where $A,N$ are $n\times d$ and $m\times d$ matrices, $b,v$ are vectors of length $n$ and $m$ with $n\ge d.$

We show an algorithm based on a trust-region method with an oracle that can be implemented using $O(d^{1/3})$ linear system solves, improving the $O(n^{1/3})$ oracle by Adil-Bullins-Sachdeva, NeurIPS 2021.

Our implementation of the oracle relies on solving the overdetermined $\ell {}_{\infty }$-regression problem ${\min }_{x\in R^d,Nx=v}\Vert Ax-b\Vert$∞. We provide an algorithm that finds a $(1+ϵ)$-approximate solution to this problem using $O((d^{1/3}/ϵ+1/{ϵ}^2)\log (n/ϵ))$ linear system solves. This algorithm leverages $\ell \infty$ Lewis weight overestimates and achieves this iteration complexity via a simple lightweight IRLS approach, inspired by the work of Ene-Vladu, ICML 2019.

Experimentally, we demonstrate that our algorithm significantly improves the runtime of the standard CVX solver.