On the Oracle Complexity of Interpolation-Based Gradient Descent

• URL: http://arxiv.org/abs/2606.19878v1
• Date: Thu, 18 Jun 2026 07:35:38 GMT
• Title: On the Oracle Complexity of Interpolation-Based Gradient Descent
• Abstract summary: We propose an inexact gradient method, piecewise-based gradient descent (PPIGD)<n> PPIGD approximates the full gradient by querying the first-order oracle atdistant points in the data domain.<n>We find it to outperform several GD variants in key regimes when the loss function is sufficiently convex.
• Score: 11.560648074990366
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Hessian-augmented Supervised Learning for Hamilton-Jacobi-Bellman PDEs [4.858637148112423]
  A data-driven method is developed for approxing value functions in deterministic optimal control problems with nonlinear control-affine dynamics.<n>The Pontryagin Principle optimality system is solved from multiple initial conditions to generate training data consisting of values, gradients, and Hessians of the value function.<n>Second-order data augmentation is shown to improve approximation accuracy and closed-loop performance.
  arXiv  Detail & Related papers  (2026-06-22T18:11:14Z)
• An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions [2.738648582869357]
  We show that a piecewise-analytic lower-boundangular representation in reduced-space spatial branch-and-bound yields a valid for the mean.<n>Results show that PALM-Mean improves on representative general-purpose global training as the number of data points increases.
  arXiv  Detail & Related papers  (2026-04-21T01:13:54Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation [8.802387139798808]
  We propose a novel framework for high-order principal component analysis (SHOPCA) that introduces a perspective to tensor-dependent decomposition.<n>We show that sparseGeoHOP supports in high-dimensional image settings and on ImageNet.
  arXiv  Detail & Related papers  (2025-06-10T10:30:48Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Inexact subgradient methods for semialgebraic functions [18.293072574300798]
  Motivated by the extensive application of approximate gradients in machine learning, we investigate subexact additive methods subject to persistent errors.<n>Our analysis addresses both vanishing and constant step-size regimes.
  arXiv  Detail & Related papers  (2024-04-30T12:47:42Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [7.8086907734474345]
  Class of composite optimization problems with nonsmooth components.<n>Proposed iLPA is applied to a robust factorization model matrix with outliers and non-uniform sampling.
  arXiv  Detail & Related papers  (2023-03-29T16:15:34Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Piecewise linear regression and classification [0.20305676256390928]
  This paper proposes a method for solving multivariate regression and classification problems using piecewise linear predictors. A Python implementation of the algorithm described in this paper is available at http://cse.lab.imtlucca.it/bemporad/parc.
  arXiv  Detail & Related papers  (2021-03-10T17:07:57Z)
• Gradient-Based Empirical Risk Minimization using Local Polynomial Regression [39.29885444997579]
  A major goal of this literature has been to compare different algorithms, such as gradient descent (GD) or gradient descent (SGD) We demonstrate that when the loss function is smooth in the data, we can learn the oracle at every iteration and beat the oracle complexities of both GD and SGD.
  arXiv  Detail & Related papers  (2020-11-04T20:10:31Z)
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nystr\"om method [76.73096213472897]
  We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees. Our approach leads to significantly better bounds for datasets with known rates of singular value decay. We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
  arXiv  Detail & Related papers  (2020-02-21T00:43:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.