# On the Oracle Complexity of Interpolation-Based Gradient Descent

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 91 references that are in the map.
- First posted on arXiv 18 Jun 2026.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Empirical Analysis of the Hessian of Over-Parametrized Neural Networks](https://mlsanity.com/paper/1706.04454/) (2017)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Gradient Descent Happens in a Tiny Subspace](https://mlsanity.com/paper/1812.04754/) (2018)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [MiME: Multilevel Medical Embedding of Electronic Health Records for Predictive Healthcare](https://mlsanity.com/paper/1810.09593/) (2018)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Analytic Insights into Structure and Rank of Neural Network Hessian Maps](https://mlsanity.com/paper/2106.16225/) (2021)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Deep networks for system identification: a Survey](https://mlsanity.com/paper/2301.12832/) (2023)
- [Training invariances and the low-rank phenomenon: beyond linear networks](https://mlsanity.com/paper/2201.11968/) (2022)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [On Robustness of Principal Component Regression](https://mlsanity.com/paper/1902.10920/) (2019)
- [Accelerated Distributed Nesterov Gradient Descent](https://mlsanity.com/paper/1705.07176/) (2017)
- [On Universal Features for High-Dimensional Learning and Inference](https://mlsanity.com/paper/1911.09105/) (2019)
- [Second-Order Guarantees of Stochastic Gradient Descent in Non-Convex Optimization](https://mlsanity.com/paper/1908.07023/) (2019)
- [Analysis of gradient descent methods with non-diminishing, bounded errors](https://mlsanity.com/paper/1604.00151/) (2016)
- [Non-asymptotic bounds for stochastic optimization with biased noisy gradient oracles](https://mlsanity.com/paper/2002.11440/) (2020)
- [Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic Bounds and Applications](https://mlsanity.com/paper/2006.15043/) (2020)
- [Federated Optimization of Smooth Loss Functions](https://mlsanity.com/paper/2201.01954/) (2022)
- [Gradient-Based Empirical Risk Minimization using Local Polynomial Regression](https://mlsanity.com/paper/2011.02522/) (2020)
- [Generalized AdaGrad (G-AdaGrad) and Adam: A State-Space Perspective](https://mlsanity.com/paper/2106.00092/) (2021)
- [Explaining the Success of Nearest Neighbor Methods in Prediction](https://mlsanity.com/paper/2502.15900/) (2025)
- [On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regression](https://mlsanity.com/paper/2204.07702/) (2022)

## Abstract (arXiv)

Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimization parameters, can be leveraged to improve the oracle complexity of gradient descent (GD) methods. In this paper, we propose an inexact gradient method, piecewise polynomial interpolation-based gradient descent (PPI-GD), which approximates the full gradient in each iteration by querying the first-order oracle at equidistant points in the data domain to construct polynomial interpolants of the resulting gradient samples over appropriately sized patches of the data domain. We analyze the oracle complexity of PPI-GD for strongly convex and non-convex loss functions when the data space dimension is bounded by a polylogarithmic function of the number of training samples, and find it to outperform several GD variants in key regimes when the loss function is sufficiently smooth. Furthermore, our analysis extends several techniques from the error analysis of bicubic spline interpolants to the setting of d-variate tensor product polynomial interpolants which may be of independent interest in interpolation analysis.