# Convex optimization with p-norm oracles

arXiv: https://arxiv.org/abs/2410.24158 · HTML: https://mlsanity.com/paper/2410.24158/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2024.

## Built on by (most cited first, 5 of 5)

- [The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications](https://mlsanity.com/paper/2502.02002/) (2025)
- [Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization](https://mlsanity.com/paper/2510.00823/) (2025)
- [Non-Euclidean High-Order Smooth Convex Optimization](https://mlsanity.com/paper/2411.08987/) (2024)
- [Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization](https://mlsanity.com/paper/2506.06606/) (2025)
- [Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization](https://mlsanity.com/paper/2609.21880/) (2026)

## Abstract (arXiv)

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.