On the Oracle Complexity of Interpolation-Based Gradient Descent

Traditional gradient descent (GD) methods for empirical risk minimization (ERM) require computing the full gradient of the loss function, which involves querying the oracle for every training sample in each iteration. This paper investigates whether the smoothness of the loss function with respect to the data—rather than just the optimization parameters—can be exploited to reduce the number of required oracle calls. The authors aim to develop an algorithm that approximates the full gradient more efficiently by using numerical interpolation techniques.

The authors propose Piecewise Polynomial Interpolation-based Gradient Descent (PPI-GD). Instead of querying the gradient at every training point, PPI-GD divides the data space into smaller patches and constructs polynomial interpolants of the gradient samples at equidistant grid points within these patches. By evaluating the gradient only at these grid points, the algorithm significantly reduces the number of oracle calls per iteration. The authors provide a rigorous analysis of the oracle complexity for both strongly convex and non-convex loss functions, extending techniques from bicubic spline error analysis to multivariate tensor product polynomial interpolants.

PPI-GD demonstrates improved oracle complexity compared to standard GD and stochastic gradient descent (SGD) in regimes where the loss function is sufficiently smooth and the data dimension $d$ is bounded by a polylogarithmic function of the number of samples $n$. Specifically, the authors resolve a conjecture regarding the scaling of $d$, showing that their method remains efficient for a broader range of data dimensions than previous local polynomial regression-based approaches. The paper also establishes new error bounds for multivariate tensor product polynomial interpolants, which are used to derive the complexity results.