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

We study the sample complexity of the *best-case* Empirical Risk Minimizer in the setting of stochastic convex optimization. We show that there exists an instance in which the sample size is linear in the dimension, learning is possible, but the Empirical Risk Minimizer is likely to be *unique* and to *overfit*. This resolves an open question by Feldman. We also extend this to approximate ERMs. Building on our construction we also show that (constrained) Gradient Descent potentially overfits when horizon and learning rate grow w.r.t sample size. Specifically we provide a novel generalization lower bound of $\Omega\left(\sqrt{\eta T/m^{1.5}}\right)$ for Gradient Descent, where $\eta$ is the learning rate, $T$ is the horizon and $m$ is the sample size. This narrows down, exponentially, the gap between the best known upper bound of $O(\eta T/m)$ and existing lower bounds from previous constructions.

Modern AI systems often have enough flexibility to fit their training data perfectly. A central question is why some fitted solutions still work well on new data, while others only memorize the examples they saw during training. We study this question in a simplified mathematical model of learning, where the training objective has a well-behaved convex shape. One might hope that in such a clean setting, any solution that fits the training data, or even a typical one, would be safe. We show that this is not true. We construct examples where learning is possible, but every exact best-fitting solution, and even very accurate approximate best-fitting solutions, performs poorly on new data. Our construction works in a number of dimensions only proportional to the sample size, resolving an open question. We also use the same ideas to show that gradient descent, a standard training method, can overfit when run for too long. These results clarify that good generalization does not come just from the shape of the training problem, the algorithm used to choose among fitting solutions matters.