The $\varphi$ Curve: The Shape of Generalization through the Lens of Norm-based Capacity Control

Understanding how the test risk scales with model complexity is a central question in machine learning. Classical theory is challenged by the learning curves observed for large over-parametrized deep networks. Capacity measures based on parameter count typically fail to account for these empirical observations. To tackle this challenge, we consider norm-based capacity measures and develop our study for random features based estimators, widely used as simplified theoretical models for more complex networks. In this context, we provide a precise characterization of how the estimator’s norm concentrates and how it governs the associated test error. Our results show that the predicted learning curve admits a phase transition from under- to over-parameterization, but no double descent behavior. This confirms that more classical U-shaped behavior is recovered considering appropriate capacity measures based on models norms rather than size. From a technical point of view, we leverage deterministic equivalence as the key tool and further develop new deterministic quantities which are of independent interest.

Authors

• Yichen Wang National Engineering Research Center for Big Data Technology and System Services Computing Technology and System Lab Hubei Engineering Research Center on Big Data Security Hubei Key Laboratory of Distributed System Security School of Cyber Science and Engineering, Huazhong University of Science and Technology
• Yudong Chen University of Wisconsin-Madison
• Lorenzo Rosasco
• Fanghui Liu University of Warwick

Keywords

No keywords are indexed for this paper.