# On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 40 references that are in the map.
- First posted on arXiv 8 Mar 2021.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Lower Bounds for Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/1901.11224/) (2019)
- [Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization](https://mlsanity.com/paper/1802.07372/) (2018)
- [Stochastic Recursive Variance-Reduced Cubic Regularization Methods](https://mlsanity.com/paper/1901.11518/) (2019)
- [Robust Linear Regression: A Review and Comparison](https://mlsanity.com/paper/1404.6274/) (2014)
- [Breaking the Span Assumption Yields Fast Finite-Sum Minimization](https://mlsanity.com/paper/1805.07786/) (2018)
- [A Stochastic Trust Region Method for Non-convex Minimization](https://mlsanity.com/paper/1903.01540/) (2019)
- [Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method](https://mlsanity.com/paper/1811.11989/) (2018)

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

- [Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization](https://mlsanity.com/paper/2606.05438/) (2026)

## Abstract (arXiv)

We prove lower bounds for higher-order methods in smooth non-convex finite-sum optimization. Our contribution is threefold: We first show that a deterministic algorithm cannot profit from the finite-sum structure of the objective, and that simulating a pth-order regularized method on the whole function by constructing exact gradient information is optimal up to constant factors. We further show lower bounds for randomized algorithms and compare them with the best known upper bounds. To address some gaps between the bounds, we propose a new second-order smoothness assumption that can be seen as an analogue of the first-order mean-squared smoothness assumption. We prove that it is sufficient to ensure state-of-the-art convergence guarantees, while allowing for a sharper lower bound.