On the Oracle Complexity of Interpolation-Based Gradient Descent

The evolution of optimization algorithms in machine learning has been driven by the need to handle increasingly large and complex datasets. Classical methods like GD and SGD have been the backbone of training neural networks, but their efficiency diminishes as data dimensionality and model complexity grow. Researchers have explored various strategies, including variance reduction, adaptive step sizes, and stochastic approximations, to improve convergence rates and reduce computational costs. Notably, the concept of oracle complexity, introduced by Nemirovski and Yudin, quantifies the minimal number of gradient evaluations required for convergence. Recent work has shown that exploiting the smoothness of the loss function in data space can lead to algorithms with better oracle complexity bounds. In particular, methods like LPI-GD (local polynomial interpolation GD) have demonstrated promising results in low-dimensional settings, but their scalability remains limited. Numerical analysis offers a rich toolkit, especially tensor product polynomial interpolation, which provides high-accuracy approximations in multiple dimensions. Extending these techniques to optimization algorithms has the potential to address the curse of dimensionality, but rigorous error analysis and complexity bounds are still under development. This paper situates itself at this intersection, proposing a novel interpolation-based gradient approximation method that leverages advanced error bounds to achieve superior oracle complexity in high-dimensional regimes.

The core challenge addressed in this work is reducing the number of gradient oracle calls in high-dimensional empirical risk minimization (ERM). Traditional gradient-based methods require a full gradient computation at each iteration, which becomes computationally prohibitive when data dimension d is large. While stochastic methods like SGD mitigate this to some extent, they often suffer from slower convergence and variance issues, especially in highly smooth or structured loss landscapes. Existing interpolation approaches, such as LPI-GD, are effective only when d is extremely small (O(log log n)), limiting their practical utility. The fundamental problem is how to approximate the full gradient accurately using fewer oracle queries, exploiting the smoothness in data space without incurring exponential complexity. Achieving this requires developing new interpolation error bounds suitable for high-dimensional tensor product polynomials, and designing algorithms that balance approximation accuracy with computational efficiency. Addressing this problem can significantly accelerate training in high-dimensional machine learning models, including deep neural networks, where each gradient evaluation is costly.

The main innovations of this paper are:

1) Development of PPI-GD, which partitions the data domain into patches and constructs tensor product polynomial interpolants within each patch, drastically reducing oracle calls.

2) Extension of classical bicubic spline error bounds to general multivariate tensor product polynomials, with a recursive error decomposition technique that isolates axis-specific errors.

3) Theoretical analysis demonstrating that, under Hölder smoothness assumptions, the oracle complexity scales as Õ((p/ε)^{d/(2ℓ)}), valid for data dimension d=O(log^{0.49}(n)), thus overcoming previous limitations.

4) Empirical validation on standard datasets, confirming the theoretical advantages and demonstrating practical convergence improvements.

This combination of numerical analysis and optimization theory represents a significant step forward in high-dimensional gradient approximation, enabling scalable algorithms with provable guarantees.

• �� Data domain partitioning: Divide the data space [0,1]^d into patches P, each associated with a grid Gd_m, constructed via uniform spacing.
• �� Precomputation: Calculate basis functions ψs,y for each patch and each grid point, which serve as the building blocks for tensor product polynomial interpolants.
• �� Gradient query: At each iteration, query the oracle at all grid points within the patches to obtain gradient samples.
• �� Interpolant construction: For each patch, build polynomial interpolants ρs,i(x) for each component of the gradient using the precomputed basis functions and the queried samples.
• �� Gradient approximation: Evaluate the interpolants at data points to estimate the full gradient, reducing the total oracle calls compared to full gradient computation.
• �� Parameter update: Use the approximated gradient in a standard gradient descent step with a fixed step size based on smoothness constants.
• �� Error analysis: Derive bounds on the interpolation error by extending classical spline bounds to tensor product polynomials, employing recursive decomposition across axes.
• �� Complexity analysis: Show that the oracle complexity scales sublinearly with n when d=O(log^{0.49}(n)), leveraging the smoothness assumptions and error bounds.

The experimental setup involves synthetic datasets and real benchmarks such as MNIST and CIFAR-10. The hyperparameters, including the interpolation degree ℓ and grid size m, are optimized via grid search. The evaluation metrics include the objective function value, gradient approximation error, and total oracle calls required to reach a target accuracy. Baseline comparisons are made against classical GD and SGD, with fixed step sizes and similar initializations. The results demonstrate that PPI-GD converges faster in terms of oracle calls, often requiring 30-50% fewer queries to achieve comparable accuracy. Sensitivity analyses show that the method maintains robustness across different data dimensions and smoothness parameters. The experiments validate the theoretical complexity bounds, confirming that the polynomial interpolation error remains controlled in practice, and highlight the method’s scalability for high-dimensional problems.

• �� Theoretically, for d=O(log^{0.49}(n)), PPI-GD achieves oracle complexity of approximately Õ((p/ε)^{d/(2ℓ)}), outperforming traditional GD and SGD bounds.
• �� Empirically, on MNIST and CIFAR-10, PPI-GD reaches target accuracy with 30-50% fewer gradient queries, confirming the efficiency predicted by theory.
• �� The interpolation error bounds derived extend classical spline results, ensuring the gradient approximation remains accurate enough for convergence.
• �� The recursive error decomposition technique provides a new analytical tool for high-dimensional interpolation, with potential applications beyond optimization.

This method is particularly suitable for training large neural networks where gradient evaluations are expensive, such as in natural language processing and computer vision tasks. It can be integrated into existing training pipelines to reduce computational costs, especially when data exhibits smoothness properties. Additionally, the approach can be adapted for distributed or federated learning scenarios, where communication costs are significant. In the long term, this interpolation-based framework might enable real-time optimization in resource-constrained environments, such as edge devices or embedded systems, by minimizing the number of gradient computations required.

• �� The effectiveness relies heavily on the smoothness assumptions of the loss function; non-smooth or highly irregular functions may not benefit.
• �� The method's computational overhead for precomputing basis functions and managing patches increases with data dimension, potentially limiting scalability beyond certain thresholds.
• �� Hyperparameter tuning (e.g., ℓ, m) is necessary for optimal performance, which can be challenging in practice.
• �� The approach assumes the data domain is bounded and continuous; discrete or categorical features require modifications.
• �� Extending the technique to non-smooth or highly non-convex functions remains an open challenge, as the current error bounds depend on smoothness parameters.