Convex optimization with p-norm oracles

In recent years, there have been significant advances in efficiently solving ℓs-regression using linear system solvers and ℓ2-regression [Adil-Kyng-Peng-Sachdeva, J. ACM'24]. Would efficient smoothed ℓp-norm solvers lead to even faster rates for solving ℓs-regression when 2 ≤ p < s? In this paper, we give an affirmative answer to this question and show how to solve ℓs-regression using tildeO(n^fracnu1+nu) iterations of solving smoothed ℓp regression problems, where nu := frac1p - frac1s. To obtain this result, we provide improved accelerated rates for convex optimization problems when given access to an ℓps(λ)-proximal oracle, which, for a point c, returns the solution of the regularized problem minx f(x) + λ ||x-c||ps. Additionally, we show that these rates for the ℓps(λ)-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.