On Uniform Convergence and Low-Norm Interpolation Learning
Authors: Lijia Zhou, Danica J. Sutherland, Nati Srebro
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider an underdetermined noisy linear regression model where the minimum-norm interpolating predictor is known to be consistent, and ask: can uniform convergence in a norm ball, or at least (following Nagarajan and Kolter) the subset of a norm ball that the algorithm selects on a typical input set, explain this success? We show that uniformly bounding the difference between empirical and population errors cannot show any learning in the norm ball, and cannot show consistency for any set, even one depending on the exact algorithm and distribution. But we argue we can explain the consistency of the minimal-norm interpolator with a slightly weaker, yet standard, notion: uniform convergence of zero-error predictors in a norm ball. We use this to bound the generalization error of low(but not minimal-) norm interpolating predictors. |
| Researcher Affiliation | Academia | Lijia Zhou University of Chicago zlj@uchicago.edu Danica J. Sutherland TTI-Chicago danica@ttic.edu Nathan Srebro TTI-Chicago nati@ttic.edu |
| Pseudocode | No | The paper is theoretical and focuses on mathematical derivations and proofs, not pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for its methodology. |
| Open Datasets | No | The paper is theoretical and does not mention using any datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not specify any dataset splits for validation or training. |
| Hardware Specification | No | The paper is theoretical and does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup or hyperparameters. |