Source-linked AI summary
Minimax-Optimal Early Stopping for Continuous-Time SGD via the Discrepancy Principle
Tim Jahn, Loucas Pillaud-Vivien, Adrien Schertzer
TL;DR
Prior analyses of stochastic-gradient stopping do not provide a rate for a pathwise data-driven rule. This paper studies the discrepancy principle for continuous-time SGD, whose fluctuations scale with the residual, and proves a high-probability minimax rate up to a logarithmic factor under stated spectral and source conditions.
Problem
Existing analyses do not give a rate for a pathwise data-driven stopping rule for stochastic dynamics, leaving its attained error unquantified.
Source: §1 · p. 5Method
The paper analyzes continuous-time SGD with residual-scaled stochastic fluctuations and stops when the residual reaches the known noise scale.
Source: §1 · pp. 3–4Results
Under polynomial spectral decay and a source condition, discrepancy stopping attains the minimax-optimal algebraic rate up to a logarithmic factor with high probability.
Source: §1 · pp. 5–6Takeaways & Limitations
The result gives a high-probability rate guarantee for pathwise discrepancy stopping, beyond prior guarantees limited to termination or convergence or using an a priori stopping index.
Source: §1 · p. 5The guarantee assumes polynomial spectral decay and a source condition; confidence tends to one only logarithmically and depends on uniform incoherence.
Source: §1 · pp. 5–6
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks whether residual-based stopping remains rate-optimal for continuous-time SGD despite stochastic fluctuations that scale with the residual. It proves a high-probability minimax rate up to a logarithmic factor under spectral and source conditions.
1 Introduction
- Without early stopping, SGD can converge to an interpolating solution whose reconstruction error is large when the design is ill-conditioned and observations are noisy.Early stopping interrupts the fit before directions that amplify noise are fitted.Source: §1 · pp. 2–3
- The discrepancy principle stops when the residual reaches the data-noise scale, using the known noise level rather than unknown smoothness.With an adequate safety factor, the threshold remains above the irreducible residual when interpolation fails.Source: §1 · p. 3
- At macroscopic step sizes, stochastic fluctuations cannot be treated as negligible because their amplitude scales with the residual being monitored.Thus the stopping time is a hitting time for a stochastic process, rather than a perturbation of deterministic gradient flow.Source: §1 · p. 4
- A Volterra inequality for expected loss bounds stochastic fluctuations through a convolution kernel whose mass is the noise-feedback strength.The analysis is a finite-sample counterpart to high-dimensional loss descriptions, with incoherence closing the inequality.Source: §1 · p. 4
- Prior discrepancy analyses concern deterministic dynamics, while prior SGD stopping results do not provide a rate for a pathwise data-driven stopping rule.Existing results either bound termination or convergence, use an a priori stopping index, or evaluate the discrepancy functional at the mean process.Source: §1 · p. 5
- The rate result assumes polynomial spectral decay and a Hölder source condition, and requires compatibility between spectral decay and smoothness.The confidence tends to one only logarithmically and depends on uniform incoherence; the error bound involves neither incoherence parameter.Source: §1 · pp. 5–6
- With high probability, discrepancy stopping attains the minimax-optimal algebraic rate up to a logarithmic factor.The logarithmic loss arises because the random stopping time is localized only up to a horizon logarithmically larger than the deterministic stopping scale.Source: §1 · pp. 5–6
2 Analysis
Section 2 analyzes discrepancy-based stopping under polynomial spectral decay, a source condition, and a step-size constraint on noise feedback, covering the mean flow and stochastic fluctuations. It establishes a high-probability upper bound on late stopping and, under Assumption 1 and a sufficiently small noise-to-signal ratio, shows that the error at the discrepancy stopping time attains the minimax rate up to a logarithmic factor, while leaving open whether the threshold C_stop=1 is optimal.
2 Analysis
- Polynomial spectral decay and a source condition constrain the spectrum and initial error, while the step-size condition uses spectrum-weighted incoherence to control stochastic noise feedback.The analysis leaves incoherence unrestricted in its structural assumptions; it reports that the step-size condition holds for several design families at macroscopic step sizes.Source: §2 · pp. 7–8
2.1 Mean flow
- The process mean follows gradient flow (Showalter regularization), and balancing its bias and noise scales gives an oracle stopping scale that is minimax over the source class.The mean-flow discrepancy principle attains that rate without requiring knowledge of the source smoothness and radius.Source: §2.1 · pp. 8–9
2.2 Fluctuations: a Volterra second-moment inequality
- A Volterra inequality controls expected residual loss and yields a fluctuation envelope of the mean-flow order, under the stated assumptions and compatibility condition.The envelope is used to control fluctuations at stopping; the analysis notes that an upper bound on the stopping time alone can suffice to control the error there.Source: §2.2 · pp. 9, 11
2.3 Stability: no late stopping
- With high probability, the discrepancy stopping time does not exceed the a priori time by more than a logarithmic factor, using checkpoints and contraction between them.The block argument bounds tail fluctuations as smaller by a power of δ/ρ, while the deterministic tail component is absorbed into contraction when stopping has not occurred.Source: §2.3 · pp. 11–13
- Relaxing ν < 1/2 is not pursued because it affects neither the rate nor exponent c_G; whether C_stop=1 is optimal here remains open, unlike for most deterministic filter methods under white noise.Source: §2.3 · p. 14
2.4 Optimality: Minimax up to a Logarithm
- The error analysis separates a pathwise term controlled by the discrepancy value and source condition from fluctuations whose expectation stays at the minimax scale without logarithmic loss when β > 1.Source: §2.4 · p. 14
- With C_stop ≥ κ0 and δ/ρ ≤ ε0, the error at the stopping time achieves the minimax rate M up to a logarithmic factor with high probability.The result is established under Assumption 1.Source: §2.4 · pp. 14, 16
3 Numerical Experiments
The experiments compare uniform and spectrum-weighted incoherence across three designs, then test discrepancy-stopped SGD against Landweber on the Phillips problem. Weighting sharply reduces incoherence growth for data-driven designs, while the stopping-rule results depend on the source smoothness of the ground truth.
3 Numerical Experiments
- The numerical studies evaluate incoherence on Phillips, MNIST, and Superconductivity designs, and compare discrepancy-stopped SGD’s error and data-access cost with Landweber.The data-driven designs use means over 15 random subsamples; Phillips is deterministic.Source: §3 · p. 16, §3.1 · p. 17
3.1 The (weighted) incoherence
- On MNIST and Superconductivity, uniform incoherence grows by roughly 30-fold and 20-fold, while weighted incoherence increases by less than twofold; Phillips uniform incoherence rises about 20%.At n = 2048, weighting yields a ratio of 100–150 on the two data-driven designs, versus roughly 6–7.5 on Phillips.Source: §3.1 · p. 17
- The admitted step-size ratio γours/γcap(aopt) is 109 for Phillips, 58±4 to 47 ± 3 for MNIST, and 43 ± 3 to 30 ± 1 for Superconductivity across n = 128–2048.The authors caution that the constants in the step-size conditions are not optimized, so these factors are indicative rather than sharp.Source: §3.1 · p. 18
3.2 Numerical evaluation of the stopping rule
- At γLW, SGD never reaches the discrepancy threshold in any of 30 runs for either truth or any noise level, while the diffusion model does reach it.The diffusion model tracks SGD closely in relative error over the sampled step sizes, but is a consistency check rather than a runnable algorithm.Source: §3.2 · pp. 19–20
- For the rough Phillips truth, SGD matches Landweber’s relative error, with cost ratios of roughly 42–45 at γours and 116–202 at γsgd; for the smoothed truth, it is less accurate at every noise level.The smoothed case violates 2r < (β −1)/β substantially; its reported cost ratios of 10–70 come with significantly worse accuracy, whereas rough-truth accuracy is retained up to γceil.Source: §3.2 · p. 19
4 Remaining proofs
The remaining proofs establish spectral-tail bounds and develop the estimates used for the mean-flow and stopping-time arguments. The Section 2.3 proof conditions on the process history and applies conditional second-moment estimates to obtain the stated bound.
4 Remaining proofs
- The spectral-tail lemma bounds sums for p ∈ {1, 2} under the polynomial spectral condition (A1), using separate estimates for indices above and below a cutoff.For the tail indices, the proof uses (A1) and an integral comparison; for indices below the cutoff, it uses the relation λj < 1/t.Source: §4 · p. 20
4.1 Proofs of Section 2.2
- In Lemma 4, integrating (20) over t ∈ [0, T] with Tonelli’s theorem and splitting the integral at t/2 leads to bounds whose combination proves (25).The local term in (26) satisfies the desired envelope; the memory-term argument invokes the compatibility condition.Source: §4.1 · pp. 22–23
4.2 Proofs of Section 2.3
- For Section 2.3, conditioning on the process history yields a conditional Volterra inequality, and the proof combines signal- and noise-dependent bounds to establish (33).The argument invokes Duhamel’s formula and the conditional Itô isometry; the displayed conclusion is stated as proving (33).Source: §4.2 · pp. 24–25