Minimax-Optimal Early Stopping for Continuous-Time SGD via the Discrepancy Principle
Abstract
We study early stopping for a continuous-time model of stochastic gradient descent (SGD) in ill-posed linear inverse problems. We consider an a posteriori stopping rule based on the discrepancy principle, which stops the dynamics once the residual reaches the noise level. Unlike deterministic gradient flow, the stochastic dynamics exhibits persistent multiplicative fluctuations whose amplitude scales with the residual itself. Under a source condition on the initial error and a polynomial bound on the spectrum of the empirical covariance operator, we prove that, with high probability, the error at this random stopping time achieves the minimax rate over the corresponding source class, up to a logarithmic factor. Our results therefore establish the discrepancy principle as an adaptive regularization strategy for continuous-time SGD that is minimax-optimal up to a logarithmic factor, despite the persistent fluctuations induced by stochastic sampling. To our knowledge, this is the first convergence-rate result for a continuous-time model of stochastic gradient descent in inverse problems under an a posteriori stopping rule: existing analyses, including those of variance-reduced variants, bound the stopping time but do not quantify the error attained there.
Related
- Early stopping of stochastic variance reduced gradient for linear inverse problems by the discrepancy principle
- Continuous-time q-Learning for Finite-Horizon Portfolio Choice with Optimal Stopping in Jump-Diffusion Markets
- Minimax-Optimal Robust Identification of Continuous-Time Systems: Handling Narrow-Band Disturbances in the Frequency Domain
- Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
- A Smoothed Discrepancy Principle for Random Feature Methods and Neural Networks
BibTeX
@misc{jahn2026minimaxoptimal,
title = {{Minimax-Optimal Early Stopping for Continuous-Time SGD via the Discrepancy Principle}},
author = {Tim Jahn and Loucas Pillaud-Vivien and Adrien Schertzer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11273},
eprint = {2609.11273},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11273},
}
RIS
TY - UNPB
TI - Minimax-Optimal Early Stopping for Continuous-Time SGD via the Discrepancy Principle
AU - Tim Jahn
AU - Loucas Pillaud-Vivien
AU - Adrien Schertzer
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11273
UR - https://arxiv.org/abs/2609.11273
AB - We study early stopping for a continuous-time model of stochastic gradient descent (SGD) in ill-posed linear inverse problems. We consider an a posteriori stopping rule based on the discrepancy principle, which stops the dynamics once the residual reaches the noise level. Unlike deterministic gradient flow, the stochastic dynamics exhibits persistent multiplicative fluctuations whose amplitude scales with the residual itself. Under a source condition on the initial error and a polynomial bound on the spectrum of the empirical covariance operator, we prove that, with high probability, the error at this random stopping time achieves the minimax rate over the corresponding source class, up to a logarithmic factor. Our results therefore establish the discrepancy principle as an adaptive regularization strategy for continuous-time SGD that is minimax-optimal up to a logarithmic factor, despite the persistent fluctuations induced by stochastic sampling. To our knowledge, this is the first convergence-rate result for a continuous-time model of stochastic gradient descent in inverse problems under an a posteriori stopping rule: existing analyses, including those of variance-reduced variants, bound the stopping time but do not quantify the error attained there.
ER -