Convex optimization with $p$-norm oracles

Abstract

In recent years, there have been significant advances in efficiently solving ${\ell }_s$-regression using linear system solvers and ${\ell }_2$-regression [Adil-Kyng-Peng-Sachdeva, J. ACM'24]. Would efficient smoothed ${\ell }_p$-norm solvers lead to even faster rates for solving ${\ell }_s$-regression when $2\le p<s$? In this paper, we give an affirmative answer to this question and show how to solve ${\ell }_s$-regression using $\tilde{O}(n^{\frac{\hat{I}}{½}1+\hat{I}½})$ iterations of solving smoothed ${\ell }_p$ regression problems, where $\hat{I}½:=\frac{1}{p}-\frac{1}{s}$. To obtain this result, we provide improved accelerated rates for convex optimization problems when given access to an ${\ell }_p^s(\hat{I}»)$-proximal oracle, which, for a point $c$, returns the solution of the regularized problem ${\min }_{x}f(x)+\hat{I}»||x-c|{|}_p^s$. Additionally, we show that these rates for the ${\ell }_p^s(\hat{I}»)$-proximal oracle are optimal for algorithms that query in the span of the outputs of the oracle, and we further apply our techniques to settings of high-order and quasi-self-concordant optimization.

34 pages