Minimax-Optimal Early Stopping for SGD via the Discrepancy Principle

Abstract

We study early stopping for stochastic gradient descent with a constant step size applied to noisy linear inverse problems with polynomially decaying spectrum. The iteration is stopped by the discrepancy principle, that is, as soon as its residual reaches the prescribed noise level. For Hölder source conditions below a saturation level determined by the polynomial decay, we prove that the mean-square reconstruction error at the stopping index is bounded by the classical rate, up to an explicit factor involving the step size and the incoherence of the design, and that the expected number of iterations is of the order of the oracle stopping index. The rate is minimax-optimal for deterministic noise whenever the spectrum contains an eigenvalue at the oracle scale and this factor stays bounded. The step size is restricted by a spectrum-weighted incoherence condition. The analysis allows rank-deficient designs and inconsistent observations.