Abstract
We develop algorithms for the optimization of convex objectives that have H"older continuous $q$-th derivatives with respect to a $p$-norm by using a $q$-th order oracle, for $p, q \geq 1$. We can also optimize other structured functions. We do this by developing a non-Euclidean inexact accelerated proximal point method that makes use of an inexact uniformly convex regularizer. We also provide nearly matching lower bounds for any deterministic algorithm that interacts with the function via a local oracle.
Introduction
Most classical optimization algorithms are designed for Euclidean space, where the geometry is defined by the standard $\ell_2$ norm. However, many modern problems in machine learning and operations research possess structures better captured by non-Euclidean norms, such as the $\ell_1$ norm for sparsity or the $\ell_\infty$ norm for robustness.
While recent advancements have introduced "high-order" methods—algorithms that utilize $q$-th order derivatives (tensors) to accelerate convergence—these have largely been restricted to Euclidean settings. This paper bridges the gap by developing near-optimal high-order algorithms that function across general, non-Euclidean norms, resolving long-standing questions regarding the limits of optimization and parallelization.
Algorithmic Framework
The authors propose a Non-Euclidean Inexact Accelerated Proximal Point Method. The core innovation is the use of an "inexact uniformly convex regularizer." This technical advancement allows the framework to handle a broader range of norms and smoothness parameters than previous iterations of high-order methods.
Key Algorithmic Features:
- Inexactness as a Tool: By explicitly accounting for inexact oracles and regularizers, the framework becomes more robust against the noise inherent in approximating high-order tensors.
- Convexity of Subproblems: High-order methods typically require solving a "Taylor subproblem" at each step. The authors demonstrate that these subproblems remain convex in non-Euclidean settings—specifically when the square of the norm is strongly convex—ensuring the algorithms remain computationally tractable.
- Adaptivity: The paper provides an adaptive version of the algorithm that does not require prior knowledge of proximal parameters, enhancing its utility for real-world objective functions.
Theoretical Contributions and Lower Bounds
To establish the fundamental limits of these methods, the authors introduce a novel Randomized Smoothing technique. By applying the divergence theorem, they created a method to smooth non-differentiable functions into high-order smooth ones across any norm.
This "norm-agnostic" smoothing is a significant step forward. It allows for the construction of "hard" optimization instances to prove lower bounds without relying on the complex high-dimensional embeddings previously required for $\ell_p$ norms where $p \in [1, 2)$.
Resolving the Parallelism Limit
A notable result of this work is the resolution of an open question regarding parallelization. For first-order smooth optimization in the $\ell_1$ setting, the authors establish a nearly optimal $\Omega(\epsilon^{-1/2})$ lower bound. This proves that parallelization cannot provide polynomial acceleration beyond a certain threshold in this geometry.
Convergence Results
The paper establishes near-optimal convergence rates for achieving an $\epsilon$-minimizer across different geometries:
- For $p \in [1, \infty)$: The rate is approximately $\tilde{O}(\epsilon^{-\frac{m}{(m+1)(q+\nu)-m}})$, where $m = \max\{2, p\}$.
- For $p = \infty$: The rate is $O(\epsilon^{-\frac{1}{q+\nu-1}})$.
These rates are shown to be nearly optimal in high dimensions within the black-box oracle model, meaning no deterministic algorithm can significantly outperform them.
Limitations and Future Directions
While this work provides a comprehensive theoretical foundation, several areas remain for future exploration:
- Computational Complexity: Although the oracle complexity (the number of function queries) is near-optimal, the actual cost of solving $q$-th order Taylor subproblems can be high. Future research may focus on more efficient implementations of these subroutines.
- Dimensionality: The lower bounds are established for the high-dimensional regime; behavior in low-dimensional settings may differ.
- Non-Convexity: The current framework is strictly for convex objectives. Extending these non-Euclidean high-order insights to non-convex optimization, such as finding stationary points in complex geometries, is a natural next step.
Summary updated