On the Oracle Complexity of Interpolation-Based Gradient Descent

arXiv:2606.19878 · cs.LG, math.OC, stat.ML · Submitted 2026-06-18 · Read on arXiv

Dongmin Lee, William Lu, Anuran Makur

cs.LG, math.OC, stat.ML

Submitted: 2026-06-18

Comments: 16 pages, 2 figures

DOI: 10.1109/TAC.2026.3682210

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Loss Function — 20× in this paper · explained in 2 episodes
• Dimensionality Reduction — 5× in this paper · explained in 2 episodes
• Generalization — 5× in this paper · explained in 14 episodes
• System Identification — 5× in this paper · explained in 3 episodes
• Objective Function — 4× in this paper · explained in 2 episodes
• Adam — 3× in this paper · explained in 3 episodes
• Curse of Dimensionality — 3× in this paper · explained in 6 episodes
• Hyperparameters — 3× in this paper · explained in 2 episodes
• Accuracy — 2× in this paper · explained in 1 episode
• Annual Conference on Decision and Control — 2× in this paper
• Core — 2× in this paper · explained in 2 episodes
• Variance Reduction — 2× in this paper · explained in 2 episodes
• Benchmark — 1× in this paper · explained in 2 episodes
• Clustering — 1× in this paper · explained in 2 episodes
• Consistency — 1× in this paper · explained in 3 episodes
• Papers — 1× in this paper · explained in 3 episodes
• Regularization — 1× in this paper · explained in 3 episodes
• Robustness — 1× in this paper · explained in 6 episodes
• Sparsity — 1× in this paper · explained in 5 episodes
• Stochastic Gradient Descent (SGD) — 1× in this paper · explained in 5 episodes
• Tenth International Conference on Learning Representations — 1× in this paper

Sources

• A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method
• Gradient Descent Happens in a Tiny Subspace
• The Full Spectrum of Deepnet Hessians at Scale: Dynamics with SGD Training and Sample Size

Related papers

• Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
• AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
• Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
• Convergence issues in Relational Concept Analysis based on AOC-posets
• Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
• Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks