Alex Buna

Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

This work shows that early stopping can overcome suboptimality: in a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimax-optimal excess zero-one risk for covariance spectra with fast and continuous decay, including polynomial and exponential spectral decays.