Introduction
In the realm of machine learning, training complex models like deep neural networks often boils down to solving nonconvex finite-sum optimization problems. The goal is to minimize an objective function $f(x)$ that is the average of $n$ individual loss functions. Because finding a global minimum is generally NP-hard in nonconvex settings, researchers target an $\epsilon$-stationary point, where the gradient norm is sufficiently small ($\|\nabla f(x)\|_2 \le \epsilon$).
This paper addresses a long-standing theoretical bottleneck in this domain: dimension dependence in stochastic high-order optimization. The authors successfully close this gap, proving that dimension-dependent complexity bounds are not a fundamental requirement. They introduce two novel algorithms, OP-TE and TP-TE, which achieve state-of-the-art, dimension-free oracle complexities even when utilizing small batch sizes.
The Problem: The Dimension Penalty in High-Order Methods
First-order stochastic methods, such as Stochastic Gradient Descent (SGD), are celebrated for being dimension-free—their convergence rates do not depend on the number of parameters, $d$. However, they suffer from a relatively poor dependence on the target accuracy $\epsilon$ (typically $O(\epsilon^{-2})$).
High-order methods, which leverage Hessians or $p$-th order derivatives, offer vastly superior $\epsilon$ dependence. Yet, translating these benefits to the stochastic setting has historically introduced two major hurdles:
- Dimension Dependence: Previous stochastic high-order bounds relied on matrix or tensor concentration inequalities, introducing a polylogarithmic $\log d$ factor into the complexity. This made them theoretically "heavier" than their deterministic counterparts.
- Large Batch Size Requirements: To control the variance of high-order derivative estimators, existing methods often required impractically large batch sizes.
The central question of this research is whether we can design a dimension-free stochastic high-order algorithm that maintains optimal dependence on both the dataset size $n$ and the accuracy $\epsilon$.
The Solution: Taylor Expansion-Based Estimators
To overcome these challenges, the authors propose a High-order Meta Algorithm that utilizes a constrained, regularized Taylor expansion. The breakthrough lies in how they estimate the $p$-th order derivatives without relying on dimension-dependent concentration inequalities. They introduce two specific estimators:
- OP-TE (One-Point Taylor Expansion): This algorithm operates on a two-loop framework. It computes a full derivative periodically (every $m$ steps). Between these full computations, it uses a Taylor series expanded at a fixed "reference point" to estimate derivatives. While deterministic, this approach introduces bias.
- TP-TE (Two-Point Taylor Expansion): This more advanced version employs a recursive estimator. It updates the gradient estimate by evaluating the difference between the current and previous points. This technique extends the intuition of first-order variance reduction methods (like SPIDER or SARAH) to high-order tensors.
A crucial component of both methods is the enforcement of a ball constraint ($||h||_2 \le r$) during the subproblem optimization step. This constraint guarantees that the iteration step does not stray so far that the Taylor-based derivative estimates lose their accuracy.
Key Results and Complexity Bounds
The primary contribution of this paper is the derivation of optimal, dimension-free complexity bounds. The table below summarizes how OP-TE and TP-TE compare against existing state-of-the-art methods.
As shown in the comparison:
- Optimal Complexity: TP-TE achieves an impressive oracle complexity of $O(n^{(2p-1)/(2p)} / \epsilon^{(p+1)/p})$.
- Improved $n$ Dependence: Standard deterministic $p$-th order methods have a complexity of $O(n / \epsilon^{(p+1)/p})$. TP-TE strictly improves this dependence on the number of samples $n$ by a factor of $n^{1/(2p)}$.
- Truly Dimension-Free: Unlike prior stochastic methods like SVRC and STR2, which carry a $\log d$ penalty, the bounds for OP-TE and TP-TE are completely independent of the parameter dimension $d$.
- Small Batch Support: TP-TE functions effectively even with a batch size of 1, provided the reference point update frequency is tuned correctly, freeing practitioners from the massive batch size requirements of previous methods.
Limitations and Future Directions
While this work represents a significant theoretical leap, the authors note a few remaining challenges:
- The $\sqrt{n}$ Gap: There remains a $\sqrt{n}$ gap between the upper bound proven for TP-TE and the known theoretical lower bound for this class of problems. The authors hypothesize this might be closed by adopting an "average-smoothness" condition instead of the standard Lipschitz assumption.
- Computational Overhead for $p > 2$: Although the oracle complexity (number of derivative evaluations) is minimized, actually solving the $p$-th order regularized subproblem for $p > 2$ remains computationally expensive in practice. Solutions are provided for $p=1$ and $p=2$, leaving higher-order implementations for future work.
- Strict Assumptions: The theoretical guarantees rely heavily on the assumption that the $p$-th order derivative is Lipschitz continuous. This is a strong regularity assumption that may not hold universally across all practical machine learning architectures.
Summary updated