Tal Burla

All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension

We study the sample complexity of *best-case* Empirical Risk Minimizer in the setting of Stochastic Convex Optimization. We show that there exists an instance, where sample size is linear in dimension, learning is possible, but an Empirical Risk Minimizer is likely to be *unique* and *overfits*. Thi…