# Non-Euclidean High-Order Smooth Convex Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 13 Nov 2024.

## Builds on (most cited first, 14 of 14)

- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Lower Bounds for Parallel and Randomized Convex Optimization](https://mlsanity.com/paper/1811.01903/) (2018)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [An Optimal High-Order Tensor Method for Convex Optimization](https://mlsanity.com/paper/1812.06557/) (2018)
- [The global rate of convergence for optimal tensor methods in smooth convex optimization](https://mlsanity.com/paper/1809.00382/) (2018)
- [Global Riemannian Acceleration in Hyperbolic and Spherical Spaces](https://mlsanity.com/paper/2012.03618/) (2020)
- [Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities](https://mlsanity.com/paper/2205.06167/) (2022)
- [Convex optimization with p-norm oracles](https://mlsanity.com/paper/2410.24158/) (2024)
- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)
- [Cubic-quartic regularization models for solving polynomial subproblems in third-order tensor methods](https://mlsanity.com/paper/2312.10283/) (2023)
- [Global Convergence of High-Order Regularization Methods with Sums-of-Squares Taylor Models](https://mlsanity.com/paper/2404.03035/) (2024)

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

- [Stacey: Promoting Stochastic Steepest Descent via Accelerated ℓp-Smooth Nonconvex Optimization](https://mlsanity.com/paper/2506.06606/) (2025)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)
- [Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization](https://mlsanity.com/paper/2609.21880/) (2026)

## Abstract (arXiv)

We develop algorithms for the optimization of convex objectives that have H"older continuous q-th derivatives by using a q-th order oracle, for any q ≥ 1. Our algorithms work for general norms under mild conditions, including the ℓp-settings for 1≤ p≤ ∞. We can also optimize structured functions that allow for inexactly implementing a non-Euclidean ball optimization oracle. We do this by developing a non-Euclidean inexact accelerated proximal point method that makes use of an inexact uniformly convex regularizer. We show a lower bound for general norms that demonstrates our algorithms are nearly optimal in high-dimensions in the black-box oracle model for ℓp-settings and all q ≥ 1, even in randomized and parallel settings. This new lower bound, when applied to the first-order smooth case, resolves an open question in parallel convex optimization.