Search papers, labs, and topics across Lattice.
This paper reframes generalization analysis in machine learning through the lens of sensitivity analysis, moving away from the traditional reliance on i.i.d. assumptions. It derives deterministic generalization bounds based on variational principles that relate in-sample and out-of-sample performance through a data proximity error term. This approach allows for statistical assumptions to be applied *ex post* to characterize when this error term is small, offering a more flexible and verifiable framework for understanding generalization.
Ditch unverifiable i.i.d. assumptions: a new, deterministic approach to generalization bounds leverages sensitivity analysis and variational principles.
The goal of machine learning is to find models that minimize prediction error on data that has not yet been seen. Its operational paradigm assumes access to a dataset $S$ and articulates a scheme for evaluating how well a given model performs on an arbitrary sample. The sample can be $S$ (in which case we speak of ``in-sample'' performance) or some entirely new $S'$ (in which case we speak of ``out-of-sample'' performance). Traditional analysis of generalization assumes that both in- and out-of-sample data are i.i.d.\ draws from an infinite population. However, these probabilistic assumptions cannot be verified even in principle. This paper presents an alternative view of generalization through the lens of sensitivity analysis of solutions of optimization problems to perturbations in the problem data. Under this framework, generalization bounds are obtained by purely deterministic means and take the form of variational principles that relate in-sample and out-of-sample evaluations through an error term that quantifies how close out-of-sample data are to in-sample data. Statistical assumptions can then be used \textit{ex post} to characterize the situations when this error term is small (either on average or with high probability).
