mlsanityData to 7 Oct 2026

Toward L_∞-recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields

arXiv 2305.00322 ↗First posted 29 Apr 2023cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Many machine learning applications require learning a function with a small worst-case error over the entire input domain, that is, the L_∞-error, whereas most existing theoretical works only guarantee recovery in average errors such as the L2-error. L_∞-recovery from polynomial samples is even impossible for seemingly simple function classes such as constant-norm infinite-width two-layer neural nets. This paper makes some initial steps beyond the impossibility results by leveraging the randomness in the ground-truth functions. We prove a polynomial sample complexity bound for random ground-truth functions drawn from Gaussian random fields. Our key technical novelty is to prove that the degree-k spherical harmonics components of a function from Gaussian random field cannot be spiky in that their L_∞/L2 ratios are upperbounded by O(d √ln k) with high probability. In contrast, the worst-case L_∞/L2 ratio for degree-k spherical harmonics is on the order of Omega(mindk/2,kd/2).

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 32 of its 70 references that are in the map. First posted on arXiv 29 Apr 2023.

Builds on

32 of 70 references.

References · 32

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2016Wide Residual Networkscited by 3,057
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  5. 2021Characterizing possible failure modes in physics-informed neural networkscited by 632
  6. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
  7. 2017On Kernelized Multi-armed Banditscited by 348
  8. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  9. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
  10. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  11. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  12. 2020Neural Thompson Samplingcited by 127
20 more
  1. 2017Sobolev Norm Learning Rates for Regularized Least-Squares Algorithmcited by 113
  2. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  3. 2018Model Reconstruction from Model Explanationscited by 84
  4. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  5. 2019Uniform Error Bounds for Gaussian Process Regression with Application to Safe Controlcited by 64
  6. 2019Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margincited by 56
  7. 2018Learning One-hidden-layer ReLU Networks via Gradient Descentcited by 50
  8. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  9. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  10. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  11. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
  12. 2014Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameterscited by 30
  13. 2022Is L2 Physics-Informed Loss Always Suitable for Training Physics-Informed Neural Network?cited by 23
  14. 2018Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropycited by 22
  15. 2017Gaussian Process bandits with adaptive discretizationcited by 20
  16. 2021Optimal Gradient-based Algorithms for Non-concave Bandit Optimizationcited by 15
  17. 2021Going Beyond Linear RL: Sample Efficient Neural Function Approximationcited by 9
  18. 2017Function approximation with zonal function networks with activation functions analogous to the rectified linear unit functionscited by 8
  19. 2021Uniform Error and Posterior Variance Bounds for Gaussian Process Regression with Application to Safe Controlcited by 7
  20. 2023Reinforcement Learning with Function Approximation: From Linear to Nonlinearcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 2.

4 papers.

  1. 2023Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Timecited by 20
  2. 2024Mitigating Covariate Shift in Misspecified Regression with Applications to Reinforcement Learningcited by 4
  3. 2024Optimal Rates and Saturation for Noiseless Kernel Ridge Regressioncited by 3
  4. 2023The L^∞ Learnability of Reproducing Kernel Hilbert Spacescited by 0