Early stopping of stochastic variance reduced gradient for linear inverse problems by the discrepancy principle

1 Introduction

• SVRG and stochastic gradient methods are popular for large-scale inverse problems because of their scalability, while their regularization-theory analysis remains incomplete.The paper focuses on linear inverse problems in Hilbert spaces.Source: §1 · pp. 1–2
• A priori stopping rules depend on the unknown regularity of the exact solution, motivating rules based only on noisy data and the noise level.The discrepancy principle chooses a stopping index using a fixed constant τ > 1.Source: §1 · pp. 2–3
• SVRG checks the residual every M iterations, so applying the discrepancy rule at anchor points adds no extra cost and may benefit from smoother residual trajectories.The built-in variance reduction may enhance the rule’s numerical stability.Source: §1 · p. 3
• For any frequency M, suitable step sizes yield a noise-level convergence rate to the minimum-norm solution that is nearly optimal for nonsmooth solutions.The rates are comparable with rates for SGD and SVRG using a priori stopping rules.Source: §1 · p. 3
• The analysis establishes finite-iteration termination, regularizing properties, and convergence rates for discrepancy-stopped SVRG, including the first convergence-rate results for a stochastic iterative method with an a posteriori rule.The rates are established in high probability and in the uniform sense, and are nearly order optimal for nonsmooth solutions.Source: §1 · p. 3

2 Main results and discussions

• The analysis assumes a constant step size ηj = c0 with c0 ≤ L^-1, where L is the maximum squared operator norm among the Ai.It also assumes δ ≤ 1 and M ≥ 2; when M = 1, SVRG reduces to Landweber.Source: §2 · p. 4
• Under the source condition x† − x0 = B^νw, the analysis derives convergence rates for SVRG iterates.The source condition encodes regularity of the initial error and is used to derive rates.Source: §2 · pp. 4–5
• For large iteration index k, the variance component of the residual contributes only marginally to the rate analysis.The paper notes that the stochastic-gradient gap becomes weaker relative to the full gradient as k grows, supporting a uniform deterministic error bound.Source: §2 · pp. 4–5
• The convergence rates are nearly optimal and comparable, up to a logarithmic factor, with rates for a priori-stopped SVRG and the Landweber method.The stated comparison concerns the rate bounds for SVRG stopped by the discrepancy principle.Source: §2 · p. 5
• The rate analysis restricts ν to (0, 1/2), a bound also present for standard SGD and SVRG and attributed to variance-related saturation.Theorem 2.2 imposes an additional boundedness condition involving (1 − 2ν)^-1.Source: §2 · p. 5
• Without the source condition, finite-iteration termination and the regularizing property of SVRG remain valid.The paper identifies the discrepancy principle as a valid a posteriori stopping rule in this case.Source: §2 · p. 5

3.1 Notation and key preliminary estimates

• The preliminary analysis shows that unbiased SVRG gradients yield a monotonically decreasing expected residual, under Assumption 2.1(i).The expected residual property is used as a preliminary estimate in the convergence analysis.Source: §3.1 · p. 9

3.2 Proof of Theorem 2.1

• Theorem 2.1 gives finite-iteration termination in probability and convergence rates in conditional expectation on a high-probability event.The proof decomposes the error into noise propagation and remaining terms, then bounds them using the noise level.Source: §3.2 · p. 9

3.3 Proof of Theorem 2.2

• Theorem 2.2 establishes finite-iteration termination and a convergence rate for SVRG in the uniform sense.The supplied passages state these results but do not provide their explicit bounds.Source: §3.3 · p. 12

3.4 Proof of Theorem 2.3

• Theorem 2.3 establishes the regularizing property of discrepancy-stopped SVRG in uniform and high-probability analyses, alongside a uniform finite-iteration termination bound.The uniform regularization proof treats stopping indices that remain finite separately from those tending to infinity as the noise level vanishes.Source: §3.4 · p. 14
• The cutoff kL(δ) is independent of the path θ and tends to infinity as δ→0+, enabling the final bracket term’s vanishing-limit estimate.The estimate invokes Lemma C.3.Source: §3.4 · p. 17
• Combining the preceding estimates yields the concluding bound from (3.29), completing the proof of Theorem 2.3.Source: §3.4 · p. 18

4 Numerical experiments and discussions

• The experiments use 1000-by-1000 discretized systems, three ill-posed examples, and frequency choices M ∈ {0.1n, n, 2n}.The methods use comparable computational budgets, and SVRG statistics are based on ten independent runs.Source: §4 · pp. 18–19
• SVRG with suitable constant step sizes achieves accuracy comparable to optimal LM across ν ∈{0, 0.25, 0.5, 1}, with much fewer iterations in relatively low-regularity cases.The comparisons cover s-phillips, s-gravity, and s-shaw.Source: §4 · p. 19, Table 1 · p. 19, Table 2 · p. 20
• Higher noise levels or regularity typically require fewer iterations, while higher regularity requires a smaller step size to overcome SVRG saturation.The theoretical results also give (nearly) optimal convergence rates and stopping-index upper bounds that decrease as noise or regularity increases.Source: §4 · p. 19

5 Concluding remarks

• For constant step sizes under the canonical source condition, SVRG with the discrepancy principle has finite-iteration termination and convergence rates in probability and uniformly.The authors state that these results indicate near-optimality for nonsmooth solutions.Source: §5 · p. 22
• Without the source condition, the analysis establishes finite-iteration termination and regularizing properties, and experiments show order-optimality and computational efficiency.The numerical findings concern linear inverse problems with varying degrees of ill-posedness.Source: §5 · p. 22
• The discrepancy principle requires a priori knowledge of the noise level, which may be unknown in practice.The authors leave heuristic a posteriori stopping rules for stochastic iterative methods as future work.Source: §5 · p. 22

A Preliminary estimates

• The preliminary estimates include bounds on successive errors that are used in the subsequent analysis.The section identifies these as estimates collected from prior work.Source: A Preliminary estimates · p. 22
• A refined estimate makes the dependence on the update frequency M more explicit than the cited earlier result.The passage says the refinement follows from Lemmas 3.1 and A.4.Source: A Preliminary estimates · p. 22
• An iteration-error decomposition is used to bound residuals, derive convergence rates, and establish the regularizing property.The appendix also states an interpolation inequality for elements of X.Source: A Preliminary estimates · p. 23

B High-probability events

• The analysis considers events involving a bounded stopping index and the events Q and Qp0, which are used in deriving convergence rates in expectation.The stated applications are Theorems 2.1 and 2.3(ii).Source: B High-probability events · p. 23
• Under Assumption 2.1(i) and c0 < C0, Proposition B.2 gives a bound for event Qp0 when δ ≤ 1.The passage specifies p0 ∈ (0, 1).Source: B High-probability events · p. 25
• For paths where k(δ) remains finite as δ tends to zero, the proof states that terms in the upper bound on the iteration error are uniformly bounded for sufficiently small δ.The argument uses a δ0 ∈ (0, 1) and also presents probability bounds involving Qp0.Source: B High-probability events · p. 26

• k(δ) is crucial for deriving the convergence rates in Theorem 2.1.Source: C Technical estimates for the proofs… · p. 26
• Lemma C.3 assumes Assumption 2.1(i) and treats any k′ ≥ k; its proof uses a telescopic sum from k to k′.Source: C Technical estimates for the proofs… · pp. 30–31
• Lemma C.4 provides estimates under Assumption 2.1(i), for k ≥ 3 and δ ≤ 1.Source: C Technical estimates for the proofs… · p. 31