From inexact optimization to learning via gradient concentration
This work addresses the fundamental problem of generalization in machine learning for researchers and practitioners, providing theoretical insights into how optimization affects learning outcomes.
The paper tackles the gap between minimizing empirical training error and achieving low test error by combining gradient concentration with inexact optimization theory, deriving sharp test error guarantees and highlighting implicit regularization in unconstrained objectives.
Optimization in machine learning typically deals with the minimization of empirical objectives defined by training data. However, the ultimate goal of learning is to minimize the error on future data (test error), for which the training data provides only partial information. In this view, the optimization problems that are practically feasible are based on inexact quantities that are stochastic in nature. In this paper, we show how probabilistic results, specifically gradient concentration, can be combined with results from inexact optimization to derive sharp test error guarantees. By considering unconstrained objectives we highlight the implicit regularization properties of optimization for learning.