Optimality of the final model found via Stochastic Gradient Descent
This provides theoretical guarantees for SGD in non-smooth convex optimization, which is incremental but relevant for machine learning practitioners using SGD in such settings.
The paper tackles the problem of establishing convergence guarantees for Stochastic Gradient Descent (SGD) on convex objectives without smoothness or strict convexity assumptions, showing that with high probability, the final model parameters achieve an objective value close to the minimal value.
We study convergence properties of Stochastic Gradient Descent (SGD) for convex objectives without assumptions on smoothness or strict convexity. We consider the question of establishing that with high probability the objective evaluated at the candidate minimizer returned by SGD is close to the minimal value of the objective. We compare this result concerning the final candidate minimzer (i.e. the final model parameters learned after all gradient steps) to the online learning techniques of [Zin03] that take a rolling average of the model parameters at the different steps of SGD.