# Unified Acceleration of High-Order Algorithms under H"older Continuity and Uniform Convexity

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

## Key facts

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

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

- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Cyclic Coordinate Dual Averaging with Extrapolation](https://mlsanity.com/paper/2102.13244/) (2021)

## Abstract (arXiv)

In this paper, through a very intuitive vanilla proximal method perspective, we derive accelerated high-order optimization algorithms for minimizing a convex function that has H"older continuous derivatives. In this general convex setting, we propose a concise unified acceleration framework (UAF), which reconciles the two different high-order acceleration approaches, one by Nesterov and Baes [29, 3, 33] and one by Monteiro and Svaiter [25]. As result, the UAF unifies the high-order acceleration instances [29, 3, 33, 15, 16, 25, 19, 6, 14] of the two approaches by only two problem-related parameters and two additional parameters for framework design. Furthermore, the UAF (and its analysis) is the first approach to make high-order methods applicable for high-order smoothness conditions with respect to non-Euclidean norms. If the function is further uniformly convex, we propose a general restart scheme for the UAF. The iteration complexities of instances of both the UAF and the restarted UAF match existing lower bounds in most important cases [2, 16]. For practical implementation, we introduce a new and effective heuristic that significantly simplifies the binary search procedure required by the framework. We use experiments to verify the effectiveness of the heuristic and demonstrate clear and consistent advantages of high-order acceleration methods over first-order ones, in terms of run-time complexity. Finally, the UAF is proposed directly in the general composite convex setting, thus show that the existing high-order algorithms [29, 3, 33, 16, 6, 14] can be naturally extended to the general composite convex setting.