A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes
This work addresses a foundational challenge in machine learning for scenarios with large model sets, offering a more flexible approach that could benefit theoretical and applied researchers, though it appears incremental relative to existing regularization methods.
The paper tackles the problem of learning with large hypothesis classes where uniform convergence fails, proposing a data-dependent paradigm that reduces reliance on prior assumptions. It demonstrates generalization capabilities across various learning assumptions, such as similarity of close points and Lipschitzness, without requiring prior knowledge of true parameters.
We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses. While the common approach to such challenges is SRM (or regularization) based learning algorithms, we propose a novel learning paradigm that relies on stronger incorporation of empirical data and requires less algorithmic decisions to be based on prior assumptions. We analyze the generalization capabilities of our approach and demonstrate its merits in several common learning assumptions, including similarity of close points, clustering of the domain into highly label-homogeneous regions, Lipschitzness assumptions of the labeling rule, and contrastive learning assumptions. Our approach allows utilizing such assumptions without the need to know their true parameters a priori.