Convex optimization with p-norm oracles

Abstract

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 Õ(n^ν/1+ν) iterations of solving smoothed ℓ_p regression problems, where ν := 1/p - 1/s. To obtain this result, we provide improved accelerated rates for convex optimization problems when given access to an _ℓ_p^s(λ)-proximal oracle_, which, for a point c, returns the solution of the regularized problem min_x f(x) + λ ||x-c||_p^s. Additionally, we show that these rates for the ℓ_p^s(λ)-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.