  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.
