Skip to yearly menu bar Skip to main content

Workshop: OPT2020: Optimization for Machine Learning

Invited speaker: Fast convergence of stochastic subgradient method under interpolation, Michael Friedlander

Michael Friedlander


This paper studies the behaviour of the stochastic subgradient descent (SSGD) method applied to over-parameterized empirical-risk optimization models that exactly fit the training data. We prove that for models with composite structures often found in neural networks, the interpolation condition implies that the model is effectively smooth at all minimizers, and therefore that SSGD converges at rates normally achievable only for smooth convex problems. We also prove that the fast rates we derive are optimal for any subgradient method applied to convex problems where interpolation holds.

This is joint work with Huang Fang and Zhenan Fan.