Generalization error bounds for iterative learning algorithms with bounded updates
It addresses generalization theory for machine learning practitioners, but is incremental as it builds on existing information-theoretic approaches.
This paper tackles the problem of generalization error for iterative learning algorithms with bounded updates in non-convex settings, resulting in a novel bound derived using information-theoretic techniques and demonstrating improved bounds under various analyses.
This paper explores the generalization characteristics of iterative learning algorithms with bounded updates for non-convex loss functions, employing information-theoretic techniques. Our key contribution is a novel bound for the generalization error of these algorithms with bounded updates. Our approach introduces two main novelties: 1) we reformulate the mutual information as the uncertainty of updates, providing a new perspective, and 2) instead of using the chaining rule of mutual information, we employ a variance decomposition technique to decompose information across iterations, allowing for a simpler surrogate process. We analyze our generalization bound under various settings and demonstrate improved bounds. To bridge the gap between theory and practice, we also examine the previously observed scaling behavior in large language models. Ultimately, our work takes a further step for developing practical generalization theories.