Quasi-Self-Concordant Optimization with $\ell_{\infty}$ Lewis Weights
Alina Ene, Ta Duy Nguyen, Adrian Vladu
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-regionmethod with an oracle  that can be implemented using $\widetilde{O}(d^{1/3})$linear system solves, improving the $\widetilde{O}(n^{1/3})$ oracleby [Adil-Bullins-Sachdeva, NeurIPS 2021]. Our implementation ofthe oracle relies on solving the overdetermined $\ell\_{\infty}$-regressionproblem $\min\_{x\in R^{d},Nx=v}\|Ax-b\|\_{\infty}$. We provide analgorithm that finds a $(1+\epsilon)$-approximate solution to thisproblem using $O((d^{1/3}/\epsilon^{2/3}+1/\epsilon^{2})\log(n/\epsilon))$linear system solves. This algorithm leverages $\ell\_{\infty}$ Lewisweight overestimates and achieves this iteration complexity via asimple lightweight IRLS approach, inspired by the work of [Ene-Vladu,ICML 2019]. Experimentally, we demonstrate that our algorithm significantlyimproves the runtime of the standard CVX solver.