On the Oracle Complexity of Interpolation-Based Gradient Descent
Not on the map. Why?
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.
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
29 of 91 references.
References · 29
- 2014Adam: A Method for Stochastic Optimizationcited by 37,240
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
- 2017Empirical Analysis of the Hessian of Over-Parametrized Neural Networkscited by 290
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
- 2018Gradient Descent Happens in a Tiny Subspacecited by 217
- 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
- 2018MiME: Multilevel Medical Embedding of Electronic Health Records for Predictive Healthcarecited by 72
- 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
- 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 58
- 2021Analytic Insights into Structure and Rank of Neural Network Hessian Mapscited by 52
17 more
- 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
- 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
- 2023Deep networks for system identification: a Surveycited by 37
- 2022Training invariances and the low-rank phenomenon: beyond linear networkscited by 33
- 2017Rates of Convergence of Spectral Methods for Graphon Estimationcited by 28
- 2019On Robustness of Principal Component Regressioncited by 28
- 2017Accelerated Distributed Nesterov Gradient Descentcited by 25
- 2019On Universal Features for High-Dimensional Learning and Inferencecited by 20
- 2019Second-Order Guarantees of Stochastic Gradient Descent in Non-Convex Optimizationcited by 11
- 2016Analysis of gradient descent methods with non-diminishing, bounded errorscited by 9
- 2020Non-asymptotic bounds for stochastic optimization with biased noisy gradient oraclescited by 6
- 2020Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic Bounds and Applicationscited by 6
- 2022Federated Optimization of Smooth Loss Functionscited by 6
- 2020Gradient-Based Empirical Risk Minimization using Local Polynomial Regressioncited by 4
- 2021Generalized AdaGrad (G-AdaGrad) and Adam: A State-Space Perspectivecited by 2
- 2025Explaining the Success of Nearest Neighbor Methods in Predictioncited by 2
- 2022On Acceleration of Gradient-Based Empirical Risk Minimization using Local Polynomial Regressioncited by 1
Built on by
Not cited yet.