Gilles Blanchard
email: gilles.blanchard@math.uni-potsdam.de

Marc Hoffmann
email: hoffmann@ceremade.dauphine.fr

Markus Reiß

Optimal adaptation for early stopping in statistical inverse problems *

Keywords: Linear inverse problems, Early stopping, Discrepancy principle, Adaptive estimation, Oracle inequalities, AMS subject classification: 65J20, 62G07

For linear inverse problems Y = Aµ + ξ, it is classical to recover the unknown signal µ by iterative regularisation methods ( µ (m) , m = 0, 1, . . .) so that the weak (or prediction) error A( µ (τ ) -µ) 2 is controlled for some early stopping rule τ based on a discrepancy principle. In the context of statistical estimation with stochastic noise ξ, we study oracle adaptation in strong squared-error E µ (τ ) -µ 2 . We give precise lower bounds for estimation by early stopping. For a stopping rule based on the residual process oracle adaptation bounds are established for general linear iterative methods. The proofs use bias and variance transfer techniques from weak prediction error to strong L 2 -error as well as convexity arguments and concentration bounds for the stochastic part. For Sobolev balls the adaptation bounds are shown to match the lower bounds. Adaptive early stopping for the Landweber and spectral cutoff methods are studied in further detail.

1 Introduction and main results

Motivation

Statistical linear inverse problems

We wish to recover a function (a signal, an image) from noisy data when the observation of the signal is further challenged by the action of a linear operator. As an illustrative example, we consider the model of inverse regression in dimension d = 1 over [0 , 1]. We observe

Y k = Aµ(k/n) + σξ k , k = 1, . . . , n (1.1)
where µ ∈ L 2 ([0, 1]) is the signal of interest, A :

L 2 ([0, 1]) → L 2 ([0, 1]
) is a bounded linear operator (with Aµ a continuous function), σ > 0 is a measurement noise level and ξ 1 , . . . , ξ n are independent standard normal random variables. An idealised version of (1.1) is given by the continuous observation of

Y (t) = Aµ(t) + δ Ẇ (t), t ∈ [0, 1], (1.2)
where Ẇ is a Gaussian white noise in L 2 ([0, 1]) with noise level

δ = σ √ n . (1.3)
For the asymptotics n → ∞ the rigorous statistical equivalence between (1.1) and (1.2) goes back to Brown and Low [START_REF] Brown | Asymptotic equivalence of nonparametric regression and white noise[END_REF] and was extended to higher dimensions and possibly σ → 0 in Reiß [START_REF] Reiß | Asymptotic equivalence for nonparametric regression with multivariate and random design[END_REF]. This setting of statistical inverse problems is classical and has numerous practical applications, see among many other references Johnstone and Silverman [START_REF] Johnstone | Discretization effects in statistical inverse problems[END_REF], Mair and Ruymgaart [START_REF] Mair | Statistical estimation in hilbert scale[END_REF], Cohen et al. [START_REF] Cohen | Adaptive wavelet Galerkin methods for linear inverse problems[END_REF], Bissantz et al. [START_REF] Bissantz | Convergence rates of general regularization methods for statistical inverse problems and applications[END_REF] and the survey by Cavalier [START_REF] Cavalier | Inverse problems in statistics[END_REF].

The problem of early stopping

Most implemented estimation or recovery methods for µ are based on a combination of discretisation and iterative inversion or regularisation. Start with an approximation space V D ⊆ L 2 ([0, 1]) with dim(V D ) = D ≤ n. First, assume for further simplicity that (1.1) is observed without noise, i.e., σ = 0. An approximation µ D for µ is obtained by minimising the criterion

Y -Aµ 2 n = 1 n n k=1 Y k -Aµ(k/n) 2 → min µ∈V D !
By gradient descent, a common algorithm consists in implementing a fixed point iteration for A = A| V D : µ (0) = 0, µ (m+1) = µ (m) + A * Y -Aµ (m) .

(1.4)

If A * A < 2, we have the convergence µ (m) → µ D as m → ∞. The same program applies when the data are noisy: we fix a large approximation space V D and transfer our data into the approximating linear model

Y = Aµ + σξ (1.5)
with µ ∈ R D , A ∈ R n×D and Y, ξ ∈ R n , with obvious matrix-vector notation.

In formal analogy with (1.4) we obtain a sequence of estimators

µ (0) = 0, µ (m+1) = µ (m) + A * Y -A µ (m) . (1.6)
The presence of a noise term generates a classical conflict as m grows: the iterates µ (0) , µ (1) , . . . , µ (m) , . . . are ordered with decreasing bias and increasing variance. Early stopping at some iteration m thus serves as a regularisation method which simultaneously reduces numerical and statistical complexity at the cost of a bias term.

There are several ways to choose m = m = m(Y ) from the data Y so that a prescribed performance of the resulting estimator µ ( m) is (close to) optimal among the class of estimators ( µ (m) ) m . Recent results are formulated within the oracle approach, comparing the error of µ ( m) to the minimal error among ( µ (m) ) m for any signal µ individually, which entails optimal adaptation in minimax settings, see e.g. Cavalier [START_REF] Cavalier | Inverse problems in statistics[END_REF]. Typical methods use (generalized) cross validation, see e.g. Wahba [START_REF] Wahba | Practical approximate solutions to linear operator equations when the data are noisy[END_REF], unbiased risk estimation, see e.g. Cavalier et al. [START_REF] Cavalier | Oracle inequalities for inverse problems[END_REF], penalized empirical risk minimisation, see e.g. Cavalier and Golubev [START_REF] Cavalier | Risk hull method and regularization by projections of ill-posed inverse problems[END_REF], or Lepski's balancing principle for inverse problems, see e.g. Mathé and Pereverzev [START_REF] Mathé | Geometry of linear ill-posed problems in variable hilbert scales[END_REF]. They all share the drawback that the estimators µ (m) have first to be computed for all values of 1 ≤ m ≤ M up to some maximal iteration M prescribed prior to data analysis, and then be compared to each other in some way. In this paper, we investigate the possibility of a computationally optimal approach where we compute iteratively the estimators µ (m) for m = 0, 1, . . . , decide to stop at some step m and then use µ ( m) as an estimator. The aim is to minimise the computational cost of the estimation procedure while keeping up with optimal adaptation rates or oracle properties.

Our selection rules m shall only depend on the information generated by the iterates µ (m) prior to m, formalised as stopping times. In fact, our rules will use the easily computable residual

R 2 m = Y -A µ (m) 2 (1.7)
as a data fidelity criterion. In numerical analysis, this methodology falls under the scope of discrepancy principle, see Engl et al. [START_REF] Engl | Regularization of Inverse Problems[END_REF] for the deterministic analysis and Hansen [START_REF] Hansen | Discrete inverse problems: insight and algorithms, Fundamentals of Algorithms[END_REF] for practical issues, in particular his discussion in Chapter 5 on modifications for statistical noise. For statistical inverse problems Blanchard and Mathé [START_REF] Blanchard | Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration[END_REF], Lu and Mathé [START_REF] Lu | Discrepancy based model selection in statistical inverse problems[END_REF] introduce regularised residuals in order to encompass the fact that R 2 m becomes arbitrarily large as D grows, see also Remark 2.6 on corresponding lower bounds below. Our approach will not require such further regularisations.

In the deterministic approach the noise level σ must be known in advance in order to apply successfully a discrepancy principle, an observation going back to Bakushinski [START_REF] Bakushinskii | Remarks on the choice of regularization parameter from quasioptimality and relation tests[END_REF] (see also Bakushinskii and Goncharskii [START_REF] Bakushinsky | Ill-posed problems: theory and applications[END_REF]). An advantage of the statistical approach of (1.1) and (1.5) is that the noise level σ 2 can be estimated from the data Y , see e.g. Golubev [18]. This is transparent in the limiting model (1.2) since δ 2 related to σ 2 and the number n of observations in (1.3) is identified by the continuous observation of (Y (t), t ∈ [0, 1]) thanks to its quadratic variation.

Finally, let us point out that regularisation by early stopping is frequently used, e.g. in L 2 -boosting, see Bissantz et al. [START_REF] Bissantz | Convergence rates of general regularization methods for statistical inverse problems and applications[END_REF] for its connection to inverse problems. When to stop becomes then a fundamental question, see Yao et al. [START_REF] Yao | On early stopping in gradient descent learning[END_REF], Mayr et al. [START_REF] Mayr | The importance of knowing when to stop: A sequential stopping rule for component-wise gradient boosting[END_REF], Prechelt [START_REF] Prechelt | Early stopping-but when? In Neural Networks: Tricks of the trade[END_REF], Raskutti and Wainwright [START_REF] Raskutti | Early stopping and non-parametric regression: An optimal data-dependent stopping rule[END_REF] for some references on early stopping in other problem formulations.

Mathematical setting

Our analysis for the model (1.5) will use the representation of estimators in the singular value decomposition (SVD): let (A * A) 1/2 have eigenvalues 1 ≥ λ 1 ≥ λ 2 ≥ . . . ≥ λ D > 0 with a corresponding orthonormal basis of eigenvectors (v 1 , . . . , v D ). We obtain the diagonal SVD model in terms of

µ i = µ, v i n , Y i = Y, w i n , w i = A * v i Av i n and Y i = λ i µ i + δε i , i = 1, . . . , D, (1.8)
where the ε i are independent standard Gaussian random variables and δ = σ √ n is the noise level. Our objective is to recover the signal µ = (µ i ) 1≤i≤D

with best possible accuracy from the data (Y i ) 1≤i≤D .

Note that for large D the calculation of the full SVD for A is computationally heavy and, depending on the algorithm at hand, it is often numerically unstable, see e.g. Golub and Van Loan [START_REF] Golub | Matrix Computations[END_REF]. This advocates further in favour of an early stopping methodology. Still, we use the SVD representation of a linear estimator µ (m) of the form i ) m , corresponding to the gradient descent algorithm described in (1.4)- (1.6) and Tikhonov filters γ (m) i = λ 2 i /(λ 2 i + u m ) for some penalisation u m → 0 as m → ∞, see Example 3.6 below for details.

µ (m) i = γ (m) i λ -1 i Y i = γ (m) i µ i + γ (m) i λ -1 i δε i , i =
The squared bias-variance decomposition of the mean integrated squared-error writes

E µ (m) -µ 2 = B 2 m (µ) + V m with B 2 m (µ) = D i=1 (1 -γ (m) i ) 2 µ 2 i and V m = δ 2 D i=1 (γ (m) i ) 2 λ -2 i .
(1.9)

In distinction with the weak norm quantities defined below, we shall call B m (µ) strong bias and V m strong variance. While our approach is non-asymptotic in spirit, asymptotics for vanishing noise level δ → 0 often helps to reveal main features. We shall write A B whenever the parameter-dependent quantities A, B satisfy A ≤ CB for some universal constant C > 0. Similarly, A ∼ B means A B and B A. Let us recall that under a Sobolev-type source condition

µ ∈ H β d (R) of regularity β > 0 in dimension d ≥ 1, prescribed by i≥1 i 2β/d µ 2 i ≤ R 2
, and under polynomial singular value decay λ i ∼ i -p/d , for the spectral cutoff filter γ

(m) i = 1(i ≤ m) the error bound E µ (m) -µ 2 R 2 m -2β/d + δ 2 m 2p/d+1
holds and is of optimal order δ 4β/(2β+2p+d) for m ∼ δ -2d/(2t+d) , provided the dimension D is not smaller than that choice of m (otherwise m = D is optimal and the rate degenerates). This is also achieved by more general spectral regularisation schemes, e.g. the Landweber and Tikhonov method, and is in fact the minimax rate of estimation for µ ∈ H β d (R) as δ → 0, see e.g. Cavalier [START_REF] Cavalier | Inverse problems in statistics[END_REF], Section 5.3 in Bissantz et al. [START_REF] Bissantz | Convergence rates of general regularization methods for statistical inverse problems and applications[END_REF] or Cohen et al. [START_REF] Cohen | Adaptive wavelet Galerkin methods for linear inverse problems[END_REF].

Overview of main results

Lower bounds for frequency and residual filtrations

We study lower bounds for early stopping in the specific case of the benchmark spectral cutoff filter. In a first step, let

F m = σ µ (1) , . . . , µ (m) = σ Y 1 , . . . , Y m (1.10)
denote the sigma-field generated by the first m cutoff estimators or equivalently by the SVD observations up to 'frequency' m in the SVD representation (1.8). Call F = (F m ) 1≤m≤D the frequency filtration. For cutoff estimators of the form µ

(τ ) i = Y i 1(i ≤ τ )
, where τ is an F-stopping rule, we show in Proposition 2.1 that adaptation is generally not possible. In particular, Corollary 2.2 shows the impossibility to build in that way a minimax adaptive estimator over Sobolev smoothness classes. This implies also that the Lepski method cannot be applied in reverse order, starting from low variance estimators.

If we are additionally allowed to use the information of the residual R 2 m , defined in (1.7) above, the situation changes completely. Let G m be the sigma-field generated by R 2 0 , . . . , R 2 m . Call G = (G m ) 1≤m≤D the residual filtration and note that

G m = F m ∨ σ(R 2 m ) = F m ∨ σ Y 2 (1.11)
is the filtration F m enlarged by the residual at m or equivalently the residual at 0 which is Y 2 . In this enlarged information setting, Proposition 2.4 shows that oracle adaptation might be possible when the oracle cutoff m * ∈ argmin m=1,...,D E µ (m) -µ 2 is larger in order than √ D. In terms of minimax estimation over Sobolev balls, the result implies constraints for the maximal Sobolev regularity for which a G-stopping rule τ can possibly adapt, as described precisely in Corollaries 2.5 and 2.7.

Early stopping rules

We next construct G-stopping rules for general linear estimators that achieve oracle adaptivity within the feasible range of the lower bound result. For technical convenience, we consider continuous filters γ

(t) i , t ∈ [0, ∞), the discrete setting γ (m) i
, m ∈ N 0 , being retrieved by allowing for a discretisation error, which is typically small, see Remark 3.2 below. The estimators we consider now take the form µ (τ ) = ( µ

(τ ) i ) 1≤i≤D where µ (τ ) i = γ (τ ) i λ -1 i Y i . As
for the discrepancy principle, we search for a stopping rule τ based on the information generated by the continuous residual

R 2 t = Y -A µ (t) 2 = D i=1 (1 -γ (t) i ) 2 Y 2 i , t ≥ 0. (1.
12)

The information provided by R 2 t becomes transparent by considering the weak or prediction norm v A = Av and by decomposing the weak norm error

E[ µ (t) -µ 2 A ] = B 2 t,λ (µ) + V t,λ into a weak squared bias B 2 t,λ (
µ) and a weak variance V t,λ :

B 2 t,λ (µ) = E[ µ (t) ] -µ 2 A = D i=1 1 -γ (t) i 2 λ 2 i µ 2 i , (1.13)
V t,λ = E µ (t) -E[ µ (t) ] 2 A = δ 2 D i=1 γ (t) i 2 . (1.14)
Then a bias-corrected residual R 2 t estimates the weak squared bias:

E R 2 t -δ 2 D i=1 (1 -γ (t) i ) 2 = B 2 t,λ (µ). (1.15)
We are led to consider stopping rules of the form

τ = inf t ≥ t 0 : R 2 t ≤ κ (1.16)
for some initial smoothing step t 0 ≥ 0 and a threshold value κ > 0. A residual R 2 t larger than an appropriate choice of κ indicates strong evidence that there is relevant information about µ beyond t.

Weak and strong norm error bounds

In Proposition 3.1 the inequality

E µ (τ ) -µ (t * ) 2 A ≤ 4δ 2 B 2 t * ,λ (µ) + 2Dδ 4 1/2
is established where the deterministic stopping index

t * = t * (µ) = inf t ≥ t 0 : E µ [R 2 t ] ≤ κ
is interpreted as an oracle proxy. A main task will be to compare t * with the weakly and strongly balanced oracles

t w = t w (µ) = inf t ≥ t 0 : B 2 t,λ (µ) ≤ V t,λ ,
t s = t s (µ) = inf t ≥ t 0 : B 2 t (µ) ≤ V t .
By the monotonicity of the variance and bias terms in t ≥ t 0 we have

B 2 t,λ (µ) + V t,λ ≥ min B 2 tw,λ (µ), V tw,λ = 1 2 B 2 tw,λ (µ) + V tw,λ , provided B 2 tw,λ (µ) = V tw,λ . Otherwise, t w = t 0 holds and V t,λ ≥ V tw,λ ≥ 1 2 (B 2
tw,λ (µ)+V tw,λ ) follows directly. Consequently, the weakly balanced oracle attains up to a possible factor 2 the classical weak oracle risk:

E µ (tw) -µ 2 A ≤ 2 inf t≥t 0 E µ (t) -µ 2 A .
(1.17)

Note that based only on information about the residual, which is defined via the image of A, it is intrinsic that we can only aim at minimising a weak risk. Moreover, even if we knew B t,λ (µ) for t ≤ t at some time t > 0, we have no access to the classical weak oracle argmin t E[ µ (t) -µ 2 A ] because we cannot say whether after t the bias remains constant or drops immediately. In consequence, our stopping rule τ will be designed to mimic the weakly balanced oracle t w . Indeed, formula (1.15) above in connection with definition (1.13) shows that

E µ [R 2 t ] ≤ κ implies B 2 t,λ (µ) ≤ κ -δ 2 D i=1 (1 -γ (t) i ) 2 .
For κ = δ 2 D and the continuous interpolation of the spectral cutoff filter (see the detailed Example 3.4 below) the squared weak bias B 2 t * ,λ (µ) is almost identical to the weak variance V t * ,λ . Furthermore, we shall show that a weak balancing behaviour for t * will continue to hold for general families of filters and thresholds κ. Figure 1 visualizes for a concrete example from Section 5 below squared bias, variance and residual as a function of the number of Landweber iterations. The algorithm stops when the residual crosses the horizontal κ-line and yields τ , the weakly balanced oracle t w is obtained at the crossing of B 2 t,λ and V t,λ . Corresponding strong quantities are also depicted, see Section 5 for details.

The proof is based on a completely deterministic argument and readily entails the weak oracle bound for the prediction error

E µ (τ ) -µ A ≤ E µ (t * ) -µ A + √ 2 δB t * ,λ (µ) + δ 2 √ D 1/2 . (1.18)
This analysis leads us to choose from now on the initial smoothing step [START_REF] Golubev | Adaptive spectral regularizations of high dimensional linear models[END_REF]) is dominated by the oracle risk.

t 0 = t • such that V t•,λ ∼ δ 2 √ D holds: for t ≥ t • , the remainder term in (1.
In a second step, we turn estimates in weak

E µ (τ ) -µ 2 E µ (t * ) -µ 2 . (1.19)
The proof relies on an individual weak-to-strong transfer of bias and variance estimates separately, together with an appropriate control on remaining stochastic terms. The probabilistic parts of the proof are based on the control of maxima of weighted independent χ 2 -random variables with drift and convexity arguments. Let us emphasize that classical interpolation arguments between Hilbert scales, usually applied to control the approximation error under the discrepancy principle (e.g., Section 4.3 in Engl et al. [START_REF] Engl | Regularization of Inverse Problems[END_REF]), cannot be used for an oracle and thus non-minimax approach.

The choice of κ and oracle properties

It remains to investigate the relationship of the deterministic oracle proxy t * with the balanced oracles t w , t s , which is connected to the choice of the threshold κ that is free in the above estimates. This is the topic of Section 4.

We argue that the choice κ = Dδ 2 , up to deviations of order √ Dδ 2 , e.g. due to variance estimation, yields rate-optimal results. The strategy of proof is again a stepwise comparison argument.

First, Proposition 4.1 establishes for that choice of κ an oracle-type inequality for µ (τ ) in terms of the weakly balanced risk. Then the bias and variance transfer arguments yield an inequality in strong norm between the risk at the oracle proxy t * and at the weakly balanced oracle t w . In view of Corollary 3.11 this means that µ (τ ) satisfies a strong oracle-type inequality if µ (tw) does so. Note that the latter is independent of the stopping rule employed and this leads to the intrinsic question about the relationship between the balanced oracles t w and t s . For spectral cutoff this question is addressed in a very general minimax framework by Chernousova and Golubev [START_REF] Chernousova | Spectral cut-off regularizations for ill-posed linear models[END_REF] and falls in the abstract problem framework considered recently by Lepski [START_REF] Lepski | Some new ideas in nonparametric estimation[END_REF]. For spectral cutoff Theorem 4.3 here establishes indeed an oracle inequality with a universal constant C s > 0:

E µ (τ ) -µ 2 ≤ C s E µ (ts) -µ 2 .
(1.20)

Note in particular that there is no additional log-term in the bound, which is often present for sequential algorithms.

For general spectral methods, a similar bound holds for all signals µ with t w (µ) ≤ t s (µ). In the case t w (µ) > t s (µ), the variance part dominates in strong norm, and we cannot hope for an oracle inequality with the strong oracle risk on the right-hand side, as Counterexample 4.5 below shows. Still, we obtain a bound in terms of the rescaled weak oracle risk such that, in general,

E µ (τ ) -µ 2 max E µ (ts) -µ 2 , t 2 w E µ (tw) -µ 2
A holds, cf. Theorem 4.6. For the polynomial decay of singular values λ i ∼ i -1/ν , this bound becomes a more tractable interpolation-type bound in Corollary 4.7:

E µ (τ ) -µ 2 max E µ (ts) -µ 2 , δ -4/ν E µ (tw) -µ 2 A 1+2/ν .
The simple Corollary 4.8 of the latter, assuming that the spectral method has a sufficiently large qualification, states in particular that µ (τ ) attains the minimax-optimal rate over the Sobolev ellipsoids H β d (R) for β ranging in the adaptation interval, as predicted by the lower bound.

The reason why a perfect oracle-type result cannot be established lies in the fact that for very smooth signals the strong bias does not inflate as much from the weak bias as the strong variance does from the weak variance. This is in a sense a super-optimality property that we do not catch by our choice of κ which is designed to provide a universally robust control on the strong norm risk.

Section 5 studies more specifically the early stopping rule for Landweber iterations. First, a quite general class C of signals µ is identified for which an oracle inequality like (1.20) holds. Then some numerical results show the scope and the limitations of adaptive early stopping, confirming and illustrating the theoretical findings.

Lower bounds

The lower bounds will be derived for the benchmark setting of spectral cutoff estimators µ

(m) i = 1(i ≤ m)λ -1 i Y i , m, i = 1, . . . , D, in the SVD representa- tion (1.8).

The frequency filtration

Let τ be an F-stopping time, where F is the frequency filtration defined in (1.10) and let1 R(µ, τ

) 2 = E µ [ µ (τ ) -µ 2 ].
By Wald's identity we obtain the simple formula

R(µ, τ ) 2 = E µ D i=τ +1 µ 2 i + τ i=1 λ -2 i δ 2 ε 2 i = E µ B 2 τ (µ) + V τ (2.1) with B 2 m (µ) = D i=m+1 µ 2 i and V m = δ 2 m i=1 λ -2 i
as follows from (1.9) with the spectral cutoff. This implies in particular that an oracle stopping time, i.e., an optimal F-stopping time constructed using the knowledge of µ, coincides with the deterministic oracle argmin m B 2 m (µ) + V m almost surely.

2.1 Proposition. For i 0 ∈ {1, . . . , D -1} and any µ, μ ∈ R D with µ i = μi for all i ≤ i 0 we have for any F-stopping rule τ

R(μ, τ ) 2 ≥ B 2 i 0 (μ) 1 - R(µ, τ ) 2 V i 0 +1 .
Let m s = min{m ∈ {0, . . . , D} : V m ≥ B 2 m (µ)} be a balanced oracle for µ and suppose R(µ, τ ) 2 ≤ CR(µ, m s ) 2 for some C ≥ 1. Then for any μ ∈ R D with μi = µ i for i ≤ 3Cm s we obtain

R(μ, τ ) 2 ≥ 1 3 B 2 3Cms (μ).
Proof. We use the fact that (Y i ) 1≤i≤i 0 has the same law under P µ and P μ and so has 1(τ ≤ i 0 ) by the stopping time property of τ . Moreover, thanks to the monotonicity of m → V m , Markov inequality and the identity (2.1)

R(μ, τ ) 2 ≥ E μ[B 2 τ (μ)1(τ ≤ i 0 )] = E µ [B 2 τ (μ)1(τ ≤ i 0 )] ≥ B 2 i 0 (μ)P µ (τ ≤ i 0 ) ≥ B 2 i 0 (μ)(1 -P µ (V τ ≥ V i 0 +1 )) ≥ B 2 i 0 (μ) 1 - E µ [V τ ] V i 0 +1 ≥ B 2 i 0 (μ) 1 - R(µ, τ ) 2 V i 0 +1 .
The second assertion follows by inserting i 0 = 3Cm s and R(µ, τ ) 2 ≤ 2CV ms together with V ms /V i 0 +1 ≤ m s /(i 0 + 1) since the singular values λ i are decreasing.

The last statement clarifies that the signal µ can be changed arbitrarily to μ after the index 3Cm s , while the risk always stays larger than the squared bias of that part. Even if we put classical restrictions on the decay of the coefficients (μ i ), this implies suboptimal rates for adaptation over these classes of signals. As a specific example, consider Sobolev-type ellipsoids of regularity β ≥ 0 in dimension d ≥ 1

H β d (R) = µ ∈ R D : D i=1 i 2β/d µ 2 i ≤ R 2 , β ≥ 0, R > 0, (2.2)
and assume a polynomial decay of singular values λ i ∼ i -p/d for some p ≥ 0.

Then the minimax-optimal rate for estimation in H β d (R) in (normalised) integrated squared error loss is R(R -1 δ) 2β/(2β+2p+d) , see e.g. Cohen et al. [START_REF] Cohen | Adaptive wavelet Galerkin methods for linear inverse problems[END_REF]. To be precise, let us remark that in our non-asymptotic formulation, the discretisation dimension D is fixed; formally, the definitions of H β d (R) and the Euclidean loss function depend on D, and finally the eigenvalue sequence (λ i ) i≥1 could also depend on D since they depend on the approximation space V D (in the construction described in the introduction). This, however, does not pose a problem to recover usual asymptotic minimax rates if D = D δ → ∞ as δ → 0, provided D δ is at least as large as the minimax optimal discretisation in the classical (D = ∞) sequence space model, and the eigenvalues satisfy

c A i -p/d ≤ λ i ≤ C A i -p/d for constants c A , C A not depending on D.

Corollary. Assume the singular values satisfy

m i=1 λ -2 i ≥ c A m 1+2p/d with c A > 0, p ≥ 0 for all m ∈ {1, . . . , D}. If there exists µ ∈ H β d (R) with R(µ, τ ) ≤ C µ R(R -1 δ) 2β/(2β+2p+d) , then for any α ∈ [0, β], R ≥ 2R, there exists μ ∈ H α d ( R) such that R(μ, τ ) ≥ c μ R(R -1 δ) 2α/(2β+2p+d) , provided D ≥ (2C 2 µ c -1 A ) 1/(2p/d+1) (R -1 δ) -2d/(2β+2p+d) . The constant c μ > 0 only depends on C µ and c A . Proof. For i 0 = (2C 2 µ c -1 A ) 1/(2p/d+1) (R -1 δ) -2d/(2β+2p+d) , our assumptions imply i 0 ≤ D and 1 - R(µ, τ ) 2 V i 0 +1 ≥ 1 - C 2 µ c A (R -1 δ) -2d/(2β+2p+d) i 0 + 1 1+2p/d ≥ 1 2 . Put μi = µ i for i = i 0 + 1 and μi 0 +1 = 1 2 R(i 0 + 1) -α/d . Then μ ∈ H α d ( R) follows from µ ∈ H β d (R) ⊆ H α d (R) and R ≥ 2R. The bias bound B 2 i 0 (μ) ≥ 1 4
R2 (i 0 + 1) -2α/d inserted in Proposition 2.1 yields the result.

The conclusion for impossible rate-optimal adaptation is a direct consequence of Corollary 2.2: since for any α < β the rate δ 2α/(2β+2p+d) is suboptimal, no F-stopping rule can adapt over Sobolev classes with different regularities. Note also that for α = β, if we consider the asymptotics R/R → ∞, the lower bound gives a suboptimal rate in R and adaptation over Sobolev ellipsoids with different radii is impossible. Finally, the rate R(R -1 δ) 2α/(2β+2p+d) is attained by a deterministic stopping rule that stops at the oracle frequency for H β d (R), so that the lower bound is in fact a sharp no adaptation result.

Residual filtration

We start with a key lemma, similar in spirit to the first step in the proof of Proposition 2.1, but valid for an arbitrary random τ . Its proof is delayed until Appendix 6.3.

2.3 Lemma. Let τ = τ (Y i ) 1≤i≤D ∈ {0, . . . , D} be an arbitrary (measurable) data-dependent index. Then for any m ∈ {1, . . . , D} the following implication holds true:

V m ≥ 200 R(µ, τ ) 2 ⇒ P µ (τ ≥ m) ≤ 0.9.
For G-stopping rules, where G is the residual filtration defined in (1.11), we deduce the following lower bound:

2.4 Proposition. Let τ be an arbitrary G-stopping rule. Let µ ∈ R D and i 0 ∈ {1, . . . , D} such that V i 0 +1 ≥ 200R(µ, τ ) 2 . Then R(μ, τ ) 2 ≥ 0.05B 2 i 0 (μ) holds for any μ ∈ R D that satisfies (a) µ i = μi for all i ≤ i 0 , (b) the weak bias bound |B 2 i 0 ,λ (μ) -B 2 i 0 ,λ (µ)| ≤ 0.05 √ D-i 0 2 δ 2 and (c) B i 0 ,λ (µ) + B i 0 ,λ (μ) ≥ 5.25δ. Suppose that R(µ, τ ) 2 ≤ C µ R(µ, m s ) 2 holds with the balanced oracle m s = min{m ∈ {0, . . . , D} : V m ≥ B 2 m (µ)} and some C µ ≥ 1.
Then any i 0 ≥ 400C µ m s will satisfy the initial requirement.

Proof. First, we lower bound the risk of μ by its bias on {τ ≤ i 0 } and then transfer to the law of τ under P µ , using the total variation distance on G i 0 :

R(μ, τ ) 2 ≥ E μ[B 2 τ (μ)1(τ ≤ i 0 )] ≥ B 2 i 0 (μ)P μ(τ ≤ i 0 ) ≥ B 2 i 0 (μ) P µ (τ ≤ i 0 ) -P µ -P μ T V (G i 0 ) . By Lemma 2.3 we infer P µ (τ ≤ i 0 ) ≥ 0.1. Denote W i 0 = (Y 1 , . . . , Y i 0 )
. Since the law of W i 0 is identical under P µ and P μ, and W i 0 is independent of R i 0 for both measures, the total variation distance between P µ and P μ on G i 0 equals the total variation distance between the respective laws of the scaled residual

δ -2 R 2 i 0 . For ϑ ∈ R D , let P ϑ K be the non-central χ 2 -law of X ϑ = K k=1 (ϑ k + Z k ) 2 with Z k independent and standard Gaussian. With K = D -i 0 , ϑ k = δ -1 λ i 0 +k µ i 0 +k , θk = δ -1 λ i 0 +k
μi 0 +k the total variation distance between the respective laws of the scaled residual δ -2 R 2 i 0 exactly equals P ϑ K -P θ K T V . By Lemma 6.4 in the Appendix, taking account of

ϑ = δ -1 B i 0 ,λ (
µ) and similarly for θ , we infer from (c) the simplified bound

P µ -P μ T V (G i 0 ) ≤ 2|B 2 i 0 ,λ (μ) -B 2 i 0 ,λ (µ)| δ 2 √ D -i 0 .
Under our assumption on μ, this is at most 0.05, and the inequality follows.

From R(µ, τ ) 2 ≤ 2C µ V ms and V i 0 +1 /V ms ≥ (i 0 + 1)/m s , the last statement follows.

In comparison with the frequency filtration, the main new hypothesis is that at i 0 the weak bias of μ is sufficiently close to that of µ, while the lower bound is still expressed in terms of the strong bias. This is natural since the bias only appears in weak form in the residuals while the risk involves the strong bias. Condition (c) is just assumed to simplify the bound. To obtain valuable counterexamples, μ is usually chosen at maximal weak bias distance of µ in (b), so that (c) is always satisfied in the interesting cases where √ D -i 0 is not small. Considering the minimax rates over Sobolev-type ellipsoids as defined in (2.2), we obtain a similar lower bound result as Corollary 2.2 for the frequency filtration.

Corollary. Assume the singular values satisfy c

A i -p/d ≤ λ i ≤ C A i -p/d with C A ≥ c A > 0, p/d ≥ 0 for all i ∈ {1, . . . , D}. If there exists µ ∈ H β d (R) with R(µ, τ ) ≤ C µ R(R -1 δ) 2β/(2β+2p+d) , then for any α ∈ [0, β] and R ≥ 2R, there exists μ ∈ H α d ( R) such that R(μ, τ ) ≥ c μ R min R-1 δD 1/4 2α/(2α+2p) , (R -1 δ) 2α/(2β+2p+d) , provided R -1 δ ≤ c R,δ and D ≥ C D ( R2 δ -2 ) d/(2α+2p+d/2) . The constants c μ > 0, c R,δ ∈ (0, 1] and C D > 0 depend only on c A , C A , α, d, p.
Proof. Set μi = µ i for i = i 0 and μ2 2β+2p+d) with some suitably large constant C 0 > 0, depending only on C µ , C A , p, d, and for D ≥ 2i 0 , conditions (b') and (d') are satisfied. To check condition (c'), a sufficient condition is i 0 ≤ ( 2α+2p) . The first term in the maximum defining i 0 satisfies this condition (here again using

i 0 = µ 2 i 0 + 1 4 R2 i -2α/d 0 for some i 0 ∈ {1, . . . , D}, so that μ ∈ H α d ( R) and condition (a) of Proposition 2.4 is satisfied. If (b'): C 2 A 4 R2 i -2(α+p)/d 0 ≤ 0.025δ 2 D -i 0 holds, then condition (b) of Proposition 2.4 is ensured, whereas (c'): c 2 A 2 R2 i -2(α+p)/d 0 ≥ 5.25 2 δ 2 implies condition (c) of Proposition 2.4. Finally, for (d'): i 0 ≥ (200(1 + 2p/d)C 2 A C 2 µ ) d/(2p+d) (R 2 δ -2 ) d/(2β+2p+d) , we have V i 0 +1 ≥ 200R(µ, τ ) 2 . Hence, by Proposition 2.4, (b')-(c')-(d') imply R(μ, τ ) 2 ≥ 0.05B 2 i 0 (μ) ≥ 0.05 4 R2 i -2α/d 0 . For i 0 = C 0 max ( R2 δ -2 / √ D) d/(2α+2p) , (R 2 δ -2 ) d/(
c 2 A 56 ( R2 δ -2 )) d/(
D ≥ 2i 0 ) provided R -1 δ is smaller than a suitable constant c R,δ depending on c A , C A , C µ , α, d, p.
The second term in the maximum defining i 0 satisfies the sufficient condition

C 0 (R 2 δ -2 ) d/(2β+2p+d) ≤ C 0 ( R2 δ -2 ) d/(2α+2p+d) ≤ ( c 2 A 56 ( R2 δ -2 )) d/(2α+2p) ,
again as soon as R -1 δ is smaller than a suitable constant c R,δ depending on the same parameters as c R,δ . Finally, putting c R,δ = min(c R,δ , c R,δ , 1) and unwrapping the condition D ≥ 2i 0 , it is easy to see (using (Rδ -1 ) ≥ 1) that the inequality for D postulated in the statement of the corollary is sufficient. This yields the result.

The form of the lower bound is transparent: as in the case of the frequency filtration, the rate R(R -1 δ) 2α/(2β+2p+d) is attained by a deterministic rule that stops at the oracle frequency for H β d (R), whereas R R-1 δD 1/4 2α/(2α+2p) is the size of a signal that may be hidden in the noise of the residual (i.e., that is not detected with positive probability by any test) such that we also stop early erroneously. Note that for the direct problem (p = 0) the latter quantity is just δD 1/4 , which is exactly the critical signal strength in nonparametric testing, see Ingster and Suslina [START_REF] Ingster | Nonparametric goodness-of-fit testing under Gaussian models[END_REF], while for p > 0 it reflects the interplay between the weak bias part in the residual and the strong bias part in the risk within the Sobolev ellipsoid.

Remark (Smoothed residuals).

The analysis of statistical inverse problems often takes place in the continuous white-noise model (1.2) or the equivalent Gaussian sequence model (1.8) with D = ∞. Then, however, the residual A µ -Y 2 is a.s. infinite. One way out is to consider smoothed residuals (A * A) s (A µ-Y ) 2 for s > 0, cf. Blanchard and Mathé [START_REF] Blanchard | Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration[END_REF] and Lu and Mathé [START_REF] Lu | Discrepancy based model selection in statistical inverse problems[END_REF]. If the singular values of A satisfy λ i ∼ i -p/d for some p > 0 and if sp > d/4 holds, then (A * A) s is a Hilbert-Schmidt operator and the smoothed residual is finite a.s. In that case, however, a similar corollary, where μ is set equal to µ except at an index i 1 ∼ (i 2ps-d/4 0 /δ d ) 1/(2ps+p+α) , yields a rate in δ which is never optimal over Sobolev ellipsoids H α d ( R), α < β.

Corollary 2.5 implies in turn explicit constraints for the maximal Sobolev regularity to which a G-stopping rule can possibly adapt. Here, we argue asymptotically and let explicitly D = D δ tend to infinity as the noise level δ tends to zero.

2.7 Corollary. Assume λ i ∼ i -p/d and let β + > β -≥ 0, R + , R -> 0 be such that the rate-optimal cutoff indices for H

β - d (R -) satisfy δ -2d/(2β -+2p+d) = o( √ D δ ) as δ → 0.
Then there is no G-stopping rule τ such that R(µ, τ ) ≤ Cδ 2β/(2β+2p+d) holds for some C > 0 and for every

µ ∈ H β d (R) with (β, R) ∈ {(β -, R -), (β + , R + )}. In particular, if a G-stopping rule τ is rate-optimal over H β d (R) for β ∈ [β min , β max ], β max > β min ≥ 0,
and some R > 0, then we necessarily must have

β max /d ≤ lim inf δ→0 log δ -2 log D δ -p/d -1/2.
Proof. We apply Corollary 2.5 with

β = β + , α = β -and R = R -, R = min(R + , R/2). Because of δ -2d/(2β -+2p+d/2) ≤ δ -4d/(2β -+2p+d) = o(D δ
) the conditions are fulfilled for sufficiently small δ > 0 and we conclude (R + , R - are fixed)

∃μ ∈ H β - d (R -) : R(μ, τ ) min δD 1/4 δ 2β -/(2β -+2p) , δ 2β -/(2β + +2p+d) .
By assumption, that rate cannot be larger than δ 2β -/(2β -+2p+d) . This implies (δD

1/4 δ ) 2β -/(2β -+2p) δ 2β -/(2β -+2p+d) ⇐⇒ D 1/2 δ δ -2d/(2β -+2p+d) ,
which was excluded. The first statement is proved.

For the second assertion use from above

D 1/2 δ δ -2d/(2β -+2p+d) for β -∈ [β min , β max ). Taking logarithms, this implies ∀β -∈ [β min , β max ) : 2β -+ 2p + d 2d ≤ lim inf δ→0 log(δ -2 ) log(D δ ) .
Letting β -↑ β max , the result follows.

For statistical inverse problems with λ i ∼ i -p/d we may choose the maximal dimension D δ ∼ δ -2d/(2p+d) without losing in the convergence rate for any sequence space Sobolev ellipsoid of regularity β ≥ 0, see e.g. Cohen el al. [START_REF] Cohen | Adaptive wavelet Galerkin methods for linear inverse problems[END_REF]. In fact, we then have the variance

V D δ = δ 2 D δ i=1 λ -2 i ∼ δ 2 D (2p+d)/d δ ∼ 1 (2.3)
and the estimator with cutoff at the order of D δ will not be consistent anyway. In that case, optimal adaptation is only possible if the squared minimax rate is within the interval [δ, 1], faster adaptive rates up to δ 2 are not feasible. Usually, D δ will be chosen much smaller, assuming some minimal regularity β min . The choice D δ ∼ δ -2d/(2β min +2p+d) ensures that rate optimality is possible for all (sequence space) Sobolev regularities β ≥ β min , when using either oracle (non-adaptive) rules, or adaptive rules that are not stopping times. In contrast, any G-stopping rule can at best adapt over the regularity interval [β min , β max ] with β max = 2β min + p + d/2, keeping the radius R of the Sobolev ball fixed. These adaptation intervals, however, are fundamentally understood only when inspecting the corresponding rate-optimal cutoff indices δ -2d/(2βmax+2p+d) which must at least be of order √ D δ ∼ δ -d/(2β min +2p+d) in order to distinguish a signal in the residual from the pure noise case.

Upper bounds

As announced in the overview section, we will from now on consider families of linear estimators indexed by a continuous parameter t > 0, of the form

µ (t) i = γ (t) i λ -1 i Y i for i = 1, . . . , D.
Recall the basic assumptions on the filter functions:

t → γ (t)
i is a nondecreasing continous function with values in [0, 1], such that γ (0) i = 0, and γ

(t) i ↑ 1 as t → ∞.
For the definition (1.7) of the residual

R 2 t = Y -A µ (t) 2 we introduce the residual-based stopping rule τ = inf t ≥ t 0 : R 2 t ≤ κ from (1.16). Since R 2 t ↓ 0 holds for t ↑ ∞ and t → R 2 t is continuous, we have R 2 τ = κ unless R 2 t 0 < κ already, in which case τ = t 0 . Also, recall the oracle proxy t * = inf t ≥ t 0 : E µ [R 2 t ] ≤ κ , which by the same argument satisfies E µ [R 2 t * ] = E 0 [R 2 t * ]+B 2 t * ,λ (µ) = κ, unless already E µ [R 2 t 0 ] < κ holds, implying t * = t 0 .

Upper bounds in weak norm

3.1 Proposition. The following inequality holds in weak norm:

E µ (τ ) -µ (t * ) 2 A ≤ 2Dδ 4 + 4δ 2 B 2 t * ,λ (µ) 1/2 . (3.1)
This implies the oracle-type inequality

E µ (τ ) -µ A ≤ E µ (t * ) -µ A + 2Dδ 4 + 4δ 2 B 2 t * ,λ (µ) 1/4 . (3.2)
Proof. The main (completely deterministic) argument uses consecutively the definition of the weak norm, the inequality (

A-B) 2 ≤ |A 2 -B 2 | for A, B ≥ 0 and the bounds R 2 τ = κ ≥ E[R 2 t * ] for τ > t * ≥ t 0 and R 2 τ ≤ κ = E[R 2 t * ] for t * > τ ≥ t 0 : µ (t * ) -µ (τ ) 2 A = D i=1 (γ (t * ) i -γ (τ ) i ) 2 Y 2 i ≤ D i=1 |(1 -γ (t * ) i ) 2 -(1 -γ (τ ) i ) 2 |Y 2 i = (R 2 t * -R 2 τ )1(τ > t * ) + (R 2 τ -R 2 t * )1(τ < t * ) ≤ (R 2 t * -E µ [R 2 t * ])1(τ > t * ) + (E µ [R 2 t * ] -R 2 t * )1(τ < t * ) ≤ |R 2 t * -E µ [R 2 t * ]| = D i=1 (1 -γ (t * ) i ) 2 δ 2 (ε 2 i -1) + 2λ i µ i δε i .
Note that the passage from the second to the third line simply follows from the uniform monotonicity of filters, i.e., γ

(t * ) i ≤ γ (τ ) i
for all i if t * ≤ τ and γ

(t * ) i ≥ γ (τ ) i
for all i if t * ≥ τ . By bounding the variance of the first term (applying the Cauchy-Schwarz inequality) and using |1 -γ

(t) i | ≤ 1, Var(ε 2 i ) = 2 and Cov(ε 2 i , ε i ) = 0, this implies: E µ µ (t * ) -µ (τ ) 2 A ≤ 2δ 4 D i=1 (1 -γ (t * ) i ) 4 + 4δ 2 D i=1 (1 -γ (t * ) i ) 4 λ 2 i µ 2 i 1/2 ≤ 2Dδ 4 + 4δ 2 B 2 t * ,λ (µ) 1/2 .
From this first inequality the second follows by the triangle inequality and Jensen's.

Let us point out that Proposition 3.1 continues to hold under minimal assumptions on the noise: the variables ε i need merely be uncorrelated and match the first four Gaussian moments.

The last term in the right-hand side of (3.2) is of the order of the geometric mean of B t * ,λ and δ, and thus asymptotically negligible whenever the oracle proxy risk is of larger order than δ (use Jensen's inequality to argue E[ µ (t * ) -µ A ] ≥ B t * ,λ ). Consequently, the oracle-type inequality (3.2) is asymptotically exact, in the sense that

E µ (τ ) -µ A ≤ 1 + o(1) E µ (t * ) -µ A (3.3)
as δ → 0, whenever the oracle-type risk is of larger order than D 1/4 δ. Our stopping rule thus gives reliable estimators when the weak variance is at least of order D 1/2 δ 2 , and we henceforth choose the initial smoothing step t 0 as

t • = inf{t ≥ 0 : V t,λ = C • D 1/2 δ 2 } for some constant C • ≥ 1. (3.4)
Note that t • is well defined for C • < D 1/2 since V t,λ increases from 0 at t = 0 to Dδ 2 as t ↑ ∞, and that it is easily computable, since V t,λ is obtained as squared norm of the estimation method applied to the data δA1 with 1 = (1, . . . , 1) . Moreover, we find back exactly the critical order from the lower bound.

Remark (Controlling the discretisation error).

For the discrete stopping rule m = inf{m ∈ N : m ≥ t 0 , R 2 m ≤ κ} we obtain, using

(A + B) 2 ≤ 2(A 2 + B 2 ), (A -B) 2 ≤ |A 2 -B 2 | for A, B ≥ 0, filter monotonicity and m ≥ τ : E µ ( m) -µ (τ ) 2 A ≤ 2 E B 2 τ,λ -B 2 m,λ + 2δ 2 E D i=1 γ ( m) i -γ (τ ) i 2 ε 2 i .
By m -1 < τ and the filter monotonicity we further bound the right-hand side by

2 max m=1,...,D B 2 m-1,λ -B 2 m,λ + δ 2 E max i≤D ε 2 i γ (m) -γ (m-1) 2 .
Note that the filter differences are usually not large; for spectral cutoff, for instance, we have γ (m) -γ (m-1) 2 = 1 and for Landweber iteration

γ (m) - γ (m-1) 2 ≤ D i=1 λ 4 i . Because of E[max i≤D ε 2 i ] log D,
the second term is usually of order δ 2 log D and much smaller than the error term in the oracle inequality (3.2). The bias difference term depends on the signal and does not permit a universal bound, but observe that m stops later than τ (or at τ ) and thus µ ( m) incurs less bias in the risk bound than µ (τ ) .

Upper bounds in strong norm

There is no intrinsic way to extend results in weak • A -norm to strong

• -norm. The generic Assumption (A), introduced next, on the filter functions γ (t) i and on the spectrum of A, will enable us to appropriately transfer estimates in weak norm for the bias and the variance terms separately into estimates in strong norm.

Assumption (A) on estimators and spectrum

Let us collect all required properties and discuss conditions under which they are fulfilled.

Assumption (A).

Recall that (γ

(t) i ) 1≤i≤D, t≥0 denotes a filter sequence with γ (t) i ∈ [0, 1], t → γ (t) i is nondecreasing continuous, γ (0) i = 0 and γ (t) i ↑ 1 as t ↑ ∞. Consider t • from (3.4) and set a/0 = ∞ for a ≥ 0. A1. For all t ≥ t ≥ t • , the sequence 1-γ (t ) i 1-γ (t) i i=1,...,D with values in [0, ∞] is nonincreasing in i.
A2. For all i ≤ i and t ≥ t • , we have γ

(t) i ≤ γ (t) i .
A3. For some π ≥ 1 there exists a constant C V,λ ≥ 1 so that for all t ≥ t ≥ t • , we have

V t ≤ C V,λ (V t,λ /V t ,λ ) π V t .
A4. There exists c λ > 0 such that for every k = 1, . . . , D:

1 k k i=1 λ -2 i ≥ c 2 λ λ -2 k .
A5. There exists a constant C 1 , 2 such that for all t ≥ t • we have

D i=1 γ (t) i ≤ C 1 , 2 D i=1 (γ (t) i ) 2 .

Example (Spectral cutoff). Suppose c

A i -p/d ≤ λ i ≤ C A i -p/d for some p ≥ 0, d ∈ N and C A ≥ c A > 0.
Pick the continuous spectral cutoff filter that coincides with 1(i ≤ t) when t is an integer by requiring V t,λ = δ 2 t:

γ (t) i = 1(i ≤ t ) + t -t 1(i = t + 1) for every t ≥ 0. For integers t ≥ t ≥ t • = C • √ D (C • ≥ 1) we have 1-γ (t ) i 1-γ (t) i = 1(i>t ) 1(i>t)
= ∞ when i ≤ t and equal to 1 otherwise. Thus, A1 is satisfied for integers and follows over the real line by interpolation. A2 and A4 are straightforward. For A3, since

V t = δ 2 ( i≤ t λ -2 i + (t -t )λ -2 t +1
), we have for t > t and some constant C p/d depending on p/d only:

V t V t ≤ c -2 A C 2 A C p/d t t 1+2p/d = C V,λ V t,λ V t ,λ π with π = 2p/d + 1 and C V,λ = c -2 A C 2 A C p/d , using V t,λ = δ 2 t. Finally, since γ (t) i = (γ (t) i ) 2 holds for i = t + 1, and t • ≥ √ D, we have A5 with e.g. C 1 , 2 = 1 + D -1/2 .

Generic conditions ensuring Assumption (A).

Most common filter functions used in inverse problems are obtained from spectral regularisation methods of the form

γ (t) i = g(t, λ i ), (3.5)
where g(t, λ) is a regulariser function R + × R + → [0, 1], see for instance Engl et al., Chapter 4 [START_REF] Engl | Regularization of Inverse Problems[END_REF] (with the notation g(t, λ) = λg t -1 (λ 2 ) in terms of their function g α ). In this situation, we give sufficient assumptions that are easier to check and will ensure that Assumption (A) holds. A first set of assumptions concerns the regulariser function:

3.5 Assumption (R).

R1. The function g(t, λ) is nondecreasing in t and λ, continuous in t with g(0, λ) = 0 and lim t→∞ g(t, λ) = 1 for any fixed λ > 0.

R2. For all t ≥ t ≥ t • , the function λ → 1-g(t ,λ) 1-g(t,λ) is nondecreasing.

R3. There exist positive constants ρ, β -, β + such that for all t ≥ t • and λ > 0, we have

β -min (tλ) ρ , 1 ≤ g(t, λ) ≤ min β + (tλ) ρ , 1 . (3.6)
R2 is not needed given R3 if we allow less accurate control in the constants of Lemma 6.1 (see Proposition 3.8 and its proof below). Still, it is usually satisfied. The value ρ should be distinguished from the qualification of a regularisation method, as introduced in Corollary 4.8 below. While the qualification is intended to control the approximation error, the constant ρ introduced in (3.6) guarantees instead the control of E 0 [R 2 t ] and V t , V t,λ for large D, a pure noise property independent of the signal.

Example.

Let us list some commonly used filters (see e.g Engl et al. [START_REF] Engl | Regularization of Inverse Problems[END_REF]) that all can be directly seen to satisfy Assumption (R) with ρ = 2 in R3.

(a) The Landweber filter, as developed in (1.6) of the introduction, is obtained by gradient descent of step size 1 (note λ 1 ≤ 1):

µ (m) = m-1 i=0 (I -A * A) i A * Y = (I -(I -A * A) m )(A * A) -1 A * Y. When interpolating with t = √ m this yields g(t, λ) = 1 -(1 -λ 2 ) t 2 . (b) The Tikhonov filter g(t, λ) = (1 + (tλ) -2 ) -1 is obtained from the min- imisation in µ ∈ R D Y -Aµ 2 + t -2 µ 2 → min µ ! (3.7)
(c) The m-fold iterated Tikhonov estimator µ (α,m) is obtained by minimising iteratively in m the criterion (3.7), but with penalty α 2 µµ (α,m-1) 2 , where µ (α,1) is the standard Tikhonov estimator with t = α -1 . The reparametrisation t = √ m yields the filters

g α (t, λ) = 1 -(1 + α -2 λ 2 ) -t 2 .
(d) Showalter's method or asymptotic regularisation is the general continuous analogue of iterative linear regularisation schemes. Its filter is given by g(t, λ) = 1 -e -t 2 λ 2 .

A second assumption concerns the spectrum.

Assumption (S).

There exist constants ν -, ν + > 0 and L ∈ N such that for all 1 ≤ k ≤ D/L :

0 < L -1/ν -≤ λ Lk λ k ≤ L -1/ν + < 1. (3.8)
The indices ν -and ν + are related to the so-called lower and upper Matuszewska indices of the function F (u) = # {i : λ i ≥ u} in the theory of O-regularly varying functions, see Bingham et al. [START_REF] Bingham | Regular Variation[END_REF], Section 2.1. In classical definitions these indices are defined asymptotically. Since we aim at nonasymptotic results, we require a version holding for all k; to account for possible multiple eigenvalues at the beginning of the sequence, we allow L to be an arbitrary integer (typically L would be larger than the multiplicity of λ 1 ). For connections to inverse and singular value problems in numerical analysis see Djurcic et al. [START_REF] Djurcić | The weak asymptotic equivalence and the generalized inverse[END_REF] or Fleige [START_REF] Fleige | Characterizations of monotone O-regularly varying functions by means of indefinite eigenvalue problems and help type inequalities[END_REF].

3.8 Proposition. Suppose Assumptions (S) and (R) are satisfied with ρ > ν + and the filter functions given by (3.5). Then there exist constants π ≥

1, C V,λ ≥ 1, c λ > 0, C 1 , 2 ≥ 1, depending only on ρ, β -, β + , L, ν -, ν + , such that Assumption (A) is satisfied.
The condition ρ > ν + is often encountered in statistical inverse problems, ensuring, independently of D, a control of the variances of the estimators. The proof of Proposition 3.8 is delayed until Appendix 6.1. In Appendix 6.2 we also present the proof of the following result, which gives the strong-toweak variance order V t ∼ t 2 V t,λ in this framework.

3.9 Lemma. Under Assumptions (R) and (S), we have for all

t ≥ t • V t,λ ≤ C V t -2 V t with C V = L 1+2/ν - L-1 β -2 -.
Under Assumptions (R), (S) with ρ > 1 + ν + /2 we have for all t ≥ t • :

V t,λ ≥ c V t -2 V t , with c V := min 1, C• √ D(1-L 1-2ρ/ν + ) (L-1)β + 1 ρ (1-L 1-(2ρ-2)/ν + )β 2 - L 2(ρ+1)/ν - .

Main result in strong norm

We prove the main bound in strong norm first and provide the necessary technical tools afterwards. The weak-to-strong transfer of error bounds requires at least higher moment bounds, so that we derive immediately results in high probability. From now on, we consider τ = inf{t ≥ t • : R 2 t ≤ κ} with t • from (3.4).

3.10 Theorem. Grant Assumptions A1, A2, A3, A4 with constants π, C V,λ , c λ . Then for x ≥ 1 with probability at least 1 -c 1 e -c 2 x , where c 1 , c 2 > 0 are constants depending on c λ only, we have the oracle-type inequality

µ (τ ) -µ 2 ≤ K E µ (t * ) -µ 2 + 2δ 2 xλ -2 x ∧D , (3.9)
with

K := 4C V,λ 1 + (4 √ D + 12)δ 2 + √ 32δB t * ,λ (µ) 1(t * > t • ) min V t * ,λ , B 2 t * ,λ (µ) + 1(t * = t • )V t•,λ x 1/2 2π
.

Proof. We bound (γ

(τ ) i λ -1 i Y i -µ i ) 2 ≤ 2(1 -γ (τ ) i ) 2 µ 2 i + 2(γ (τ ) i ) 2 λ -2 i δ 2 ε 2
i and we use the fact that any linear function f (w 1 , . . . , w D ) = D i=1 w i z i with z 1 , . . . , z D ∈ R attains its maximum over 1 ≥ w 1 ≥ • • • ≥ w D ≥ 0 at one of the extremal points where w i = 1(i ≤ k), k ∈ {0, . . . , D} (cf. also the proof of Lemma 3.14 below). Under Assumption A2 we thus obtain for ω > 0

µ (τ ) -µ 2 ≤ 2B 2 τ + 2δ 2 D i=1 γ (τ ) i 2 λ -2 i ε 2 i ≤ 2B 2 τ + 2(1 + ω)V τ + 2δ 2 max 1≥w 1 ≥•••≥w D ≥0 D i=1 w i λ -2 i (ε 2 i -1 -ω) = 2B 2 τ + 2(1 + ω)V τ + 2δ 2 max k=0,...,D k i=1 λ -2 i (ε 2 i -1 -ω).
By Lemma 6.5 in Appendix 6.5 below, for ω = 1 the last term is bounded by 2c -2 A x 1+2/ν δ 2 with probability at least 1 -C 1 e -C 2 x with C 1 , C 2 > 0 depending only on c λ from Assumption A4.

For τ < t * (and so t * > t • ) we have V τ ≤ V t * , and the bias transfer bound B 2 τ ≤ (B 2 τ,λ /B 2 t * ,λ )B 2 t * is ensured by Lemma 3.12 below under Assumption A1. In addition, Proposition 3.15 guarantees that the weak bias B 2 τ,λ is with high probability close to the oracle proxy analogue B 2 t * ,λ under Assumption A2. We deduce more precisely that with probability at least 1-3e -x (x ≥ 1):

B 2 τ ≤ 1 + 1(t * > t • ) (4 √ D + 12)δ 2 + √ 32δB t * ,λ B 2 t * ,λ x B 2 t * .
On the other hand, for τ > t * we have B τ ≤ B t * , and we derive, using Assumption A3 on the variance transfer and Proposition 3.16 below on the deviation between V τ,λ and V t * ,λ , that with probability at least 1 -3e -x :

V τ ≤ C V,λ 1 + (4 √ D + 2)δ 2 + √ 8δB t * ,λ V t * ,λ x 1/2 2π V t * .
Observing E µ (t * ) -µ 2 = B 2 t * + V t * , the result follows by taking the maximum of the two previous bounds and simplifying the constants.

A direct consequence of the preceding result is a moment bound, which has the character of an oracle inequality under mild conditions on the weak bias at the oracle proxy t * .

3.11 Corollary. In the setting of Theorem 3.10 assume

C 1 1(t * > t • )V t•,λ ≤ B 2 t * ,λ (µ) ≤ C 2 lim t→∞ V t,λ for some C 1 , C 2 > 0. Further assume that for k = 1, . . . , D it holds δ 2 λ -2 k ≤ C 3 k 2/ν V t• for some C 3 , ν > 0. Then for a constant C τ,t * only depending on C • , C 1 , C 2 , C 3 , ν, c λ , π, C V,λ : E µ (τ ) -µ 2 ≤ C τ,t * E µ (t * ) -µ 2 .
Proof. Noting lim t→∞ V t,λ = Dδ 2 , and on the one hand

V t * ,λ ≥ V t•,λ ≥ C • √ Dδ 2 ≥ C • C -1 2 B t * ,λ (
µ)δ (the last inequality from the assumption of the corollary), on the other hand, B 2 t * ,λ (µ) ≥ C 1 V t•,λ (then further bounded as above) in the case t * > t • , it is simple to check that the factor K in Theorem 3.10 is bounded for x ≥ 1 as K ≤ C * x π , where C * only depends on C • , C 1 , C 2 , C V,λ . For the remainder term in (3.9), note that by the assumed growth condition on λ -2

k δ 2 xλ -2 x ∧D ≤ C 3 x 1+2/ν V t• ≤ C 3 x 1+2/ν V t * , x ≥ 1.
Due to the polynomial increase in x both for K and the remainder term, we can now integrate the bound with respect to c 1 e -c 2 x dx and obtain the announced result.

Intermediate estimates from weak to strong norm

We now set out in detail the ingredients used in the proof of Theorem 3.10.

3.12 Lemma. Under Assumption A1, we have for

t ≥ t ≥ t • that B 2 t ,λ ≤ CB 2 t,λ for some C ≥ 1 implies B 2 t ≤ CB 2 t .
Proof. The assumed decay for the filter ratios implies that there is an index

i 0 ∈ {0, 1, . . . , D} such that 1 -γ (t ) i ≤ C(1 -γ (t) i ) holds for i > i 0 and 1 -γ (t ) i ≥ C(1 -γ (t) i ) for i ≤ i 0 (trivial cases for i 0 = 0, i 0 = D). Then: B 2 t -CB 2 t = D i=1 (1 -γ (t ) i ) 2 -C(1 -γ (t) i ) 2 µ 2 i ≤ λ -2 i 0 i 0 i=1 (1 -γ (t ) i ) 2 -C(1 -γ (t) i ) 2 λ 2 i µ 2 i -λ -2 i 0 D i=i 0 +1 C(1 -γ (t) i ) 2 -(1 -γ (t ) i ) 2 λ 2 i µ 2 i ≤ λ -2 i 0 (B 2 t ,λ -CB 2 t,λ ) ≤ 0,
which implies the assertion.

3.13 Lemma. For any x > 0 we have with probability at least 1 -2e -x

|R 2 t * -E[R 2 t * ]| ≤ 2δ 2 √ D + √ 8δB t * ,λ √ x + 2δ 2 x. Proof. We have R 2 t * -E[R 2 t * ] = D i=1 (1 -γ (t * ) i ) 2 δ 2 (ε 2 i -1) + 2λ i µ i δε i . By Lemma 6.3 in the Appendix, δ 2 D i=1 (ε 2 i -1)
is with probability at least 1 -e -x smaller than δ 2 2 √ Dx + δ 2 2x, while the Gaussian summand is with the same probability smaller than 2δB t * ,λ √ 2x, using (1 -γ

(t * ) i ) 4 ≤ (1 - γ (t * ) i ) 2 .
3.14 Lemma. Under Assumption A2 we have for any z

1 , . . . , z D ∈ R D i=1 (1 -γ (τ ) i ) 2 -(1 -γ (t * ) i ) 2 z i ≤ max k=0,...,D D i=k+1 z i on {τ ≤ t * }, D i=1 (1 -γ (t * ) i ) 2 -(1 -γ (τ ) i ) 2 z i ≤ max k=0,...,D k i=1 (1 -γ (t * ) i ) 2 z i on {τ ≥ t * }.
Proof. For τ ≤ t * introduce the weight space

W ≤ = w ∈ R D : w i ∈ [(1 -γ (t * ) i ) 2 , 1 + (1 -γ (t * ) i ) 2 ], w i increasing in i . Then (1 -γ (τ ) i ) 2
1≤i≤D ∈ W ≤ holds on {τ ≤ t * } by Assumption A2 for the monotonicity in i, and because of γ

(τ ) i ∈ [0, γ (t * ) i ]. The set W ≤ is convex with extremal points w k = (1 -γ (t * ) i ) 2 + 1(i > k) 1≤i≤D , k = 0, 1, . . . , D.
Hence, the linear functional w → i w i z i attains its maximum over W ≤ at some w k . This implies

D i=1 (1 -γ (τ ) i ) 2 z i ≤ max k=0,...,D D i=1 (1 -γ (t * ) i ) 2 z i + D i=k+1 z i on {τ ≤ t * },
which gives the first inequality. For the second inequality consider

W ≥ = w ∈ R D : w i ∈ [0, (1 -γ (t * ) i ) 2 ], w i increasing in i and conclude similarly via D i=1 (1 -γ (τ ) i ) 2 z i ≥ min k D i=k+1 (1 -γ (t * ) i ) 2 z i on {τ ≥ t * }.
Next, we treat the deviation of the weak bias part.

3.15 Proposition. Under Assumption A2, we obtain for any x ≥ 1 that, with probability at least 1 -3e -x :

B 2 τ,λ -B 2 t * ,λ ≤ (4 √ D + 12)δ 2 + √ 32δB t * ,λ x.
Proof. Since t → B 2 t,λ is nonincreasing, only the case τ < t * needs to be considered. By definition of τ , we obtain R 2 τ ≤ κ while E[R 2 t * ] = κ since t * > t ≥ t 0 , and thus, by γ

(τ ) i ≤ γ (t * ) i : B 2 τ,λ -B 2 t * ,λ = R 2 τ -R 2 t * - D i=1 (1 -γ (τ ) i ) 2 -(1 -γ (t * ) i ) 2 δ 2 ε 2 i + 2λ i µ i δε i ≤ E[R 2 t * ] -R 2 t * - D i=1 (1 -γ (τ ) i ) 2 -(1 -γ (t * ) i ) 2 δ 2 ε 2 i + 2λ i µ i δε i ≤ E[R 2 t * ] -R 2 t * + 2δ D i=1 (1 -γ (τ ) i ) 2 -(1 -γ (t * ) i ) 2 (-λ i µ i ε i ).
By Lemma 3.14, for any ω > 0, the last term is bounded as

2δ D i=1 (1 -γ (τ ) i ) 2 -(1 -γ (t * ) i ) 2 (-λ i µ i ε i ) =2δ D i=1 (1 -γ (τ ) i ) 2 -(1 -γ (t * ) i ) 2 -λ i µ i (ε i + ωδ -1 λ i µ i ) + 2ω(B 2 τ,λ -B 2 t * ,λ ) ≤2δ max k=0,...,D D i=k+1 -λ i µ i ε i -ωδ -1 λ 2 i µ 2 i + 2ω(B 2 τ,λ -B 2 t * ,λ ).
Concerning the sum within the maximum, we can identify the term -λ i µ i ε i with an increment of Brownian motion B over a time step λ 2 i µ 2 i . Hence, the maximum is smaller than max t>0 (B t -ωδ -1 t) which is exponentially distributed with parameter 2ωδ -1 , see Problem 3.5.8 in Karatzas and Shreve [START_REF] Karatzas | Brownian motion and stochastic calculus[END_REF]. This term is thus smaller than xδ 2ω with probability at least 1 -e -x . In view of Lemma 3.13 we have with probability at least 1 -3e -x , x ≥ 1,

B 2 τ,λ -B 2 t * ,λ ≤ 2(1 + √ D)δ 2 + √ 8δB t * ,λ + δ 2 ω x + 2ω(B 2 τ,λ -B 2 t * ,λ ).
The choice ω = 1/4 yields the result.

Finally, for the stochastic error, we obtain a comparable deviation result.

3.16 Proposition. Under Assumption A2, we obtain for any x ≥ 1, with probability at least 1 -3e

-x : V 1/2 τ,λ -V 1/2 t * ,λ ≤ δ 2 (4 √ D + 2) + √ 8δB t * ,λ 1/2 √ x. Proof. Since t → V 1/2
t,λ is nondecreasing, we only need to consider the case

τ > t * . Using V 1/2 t,λ = δ γ (t) , the inverse triangle inequality, (A -B) 2 ≤ A 2 -B 2 for A ≥ B ≥ 0, R 2 τ ≥ E[R 2 t * ]
for τ > t * , and Lemma 3.14, we obtain:

δ -2 V 1/2 τ,λ -V 1/2 t * ,λ 2 ≤ γ (τ ) -γ (t * ) 2 ≤ 1 -γ (t * ) 2 -1 -γ (τ ) 2 = δ -2 (R 2 t * -R 2 τ ) + D i=1 (1 -γ (t * ) i ) 2 -(1 -γ (τ ) i ) 2 (1 -δ -2 Y 2 i ) ≤ δ -2 (R 2 t * -E[R 2 t * ]) + max k=0,...,D k i=1 (1 -γ (t * ) i ) 2 (1 -δ -2 Y 2 i ).
Observe next that Y 2 i is stochastically larger under P µ with µ i = 0 than under P µ with µ i = 0, using the unimodality and symmetry of the normal density:

sup µ∈R D P µ (Y 2 i ≤ y) = sup µ i ∈R Φ(-λ i µ i δ -1 + δ -1 √ y) -Φ(-λ i µ i δ -1 -δ -1 √ y) ≤ Φ(δ -1 √ y) -Φ(-δ -1 √ y) = P 0 (Y 2 i ≤ y), y > 0.
By independence of (Y i ), it thus suffices to bound the deviation probability of

δ -2 (R 2 t * -E[R 2 t * ]) + max k=0,1,...,D k i=1 (1 -γ (t * ) i ) 2 (1 -ε 2 i ).
Lemma 6.3 in the Appendix gives that the maximum is smaller than 2 √ Dx with probability at least 1 -e -x , and Lemma 3.13 gives the deviation bound for the first term, so that the result follows by insertion.

Oracle-type property for early stopping

It remains to investigate the relationship of the deterministic oracle proxy t * with the balanced oracles t w , t s , which, of course, depend on the choice of κ > 0 that until now was completely arbitrary. We continue working with t 0 = t • from (3.4).

By definition we have E µ [R 2 t * ] ≤ κ and the weak bias at t * = t * (µ) satisfies

B 2 t * ,λ (µ) ≤ κ -δ 2 D i=1 (1 -γ (t * ) i ) 2 = κ -Dδ 2 -V t * ,λ + 2δ 2 D i=1 γ (t * ) i
with equality if t * > t • . At this stage we exactly need Assumption A5 and obtain

B 2 t * ,λ (µ) -κ -Dδ 2 ≤ (2C 1 , 2 -1)V t * ,λ ; (4.1)
furthermore, we also have (since

γ (t)
i ∈ [0, 1]):

B 2 t * ,λ (µ) -κ -Dδ 2 ≥ -V t * ,λ + 2δ 2 D i=1
(γ

(t * ) i ) 2 = V t * ,λ , if t * > t • . (4.2)
The larger the choice of κ, the smaller t * and thus also V t * ,λ . The control of B 2 t * ,λ (µ) is not clear because in (4.1) the effects in κ and V t * ,λ work in opposite directions. Note that for κ ≤ Dδ 2 , the bias part dominates the variance at t * , in other words t * ≤ t w holds. A natural choice is therefore κ = Dδ 2 ; for spectral cutoff, Example 3.4 and (4.1)-(4.2) imply (whenever

t * > t • ) that B 2 t * ,λ /V t * ,λ ∈ [1, 1 + 2D -1/2
] (the marginal difference between t * and t w is due to the continuous extension in t). For other regularisation methods, other choices could be tailored; moreover, the noise variance δ 2 usually needs to be estimated. For these reasons we shall allow for deviations of the form |κ -

Dδ 2 | ≤ C κ √ Dδ 2 for some C κ > 0. (4.3)
Thanks to the control of E[ µ (τ ) -µ (t * ) 2 A ] in Proposition 3.1, a weakly balanced oracle inequality can be derived.

4.1 Proposition. Grant (4.3) for κ and Assumption A5. Then the following oracle inequality holds in weak norm:

E µ (τ ) -µ 2 A ≤ 2C 1 , 2 E µ (tw) -µ 2 A + 4 2C 1 , 2 + C κ √ Dδ 2 .
Proof. Consider first the case t w > t * . Then B 2 tw,λ = V tw,λ since t w > t • , and we have by monotonicity in t of V t,λ :

E[ µ (tw) -µ 2 A ] = B 2 tw,λ + V tw,λ = 2V tw,λ ≥ 2V t * ,λ .
Moreover, from inequality (4.1) together with (4.3), we have

B 2 t * ,λ ≤ (2C 1 , 2 -1)V t * ,λ + C κ √ Dδ 2 , (4.4)
and bringing together the two last displays yields

B 2 t * ,λ + V t * ,λ ≤ C 1 , 2 E[ µ (tw) -µ 2 A ] + C κ √ Dδ 2 .
In the case t w < t * , since B 2 tw,λ ≤ V tw,λ always holds, by monotonicity in t of B 2 t,λ we have

E[ µ (tw) -µ 2 A ] = B 2 tw,λ + V tw,λ ≥ 2B 2 tw,λ ≥ 2B 2 t * ,λ .
Moreover, from equation (4.2) (which holds since in this case t * > t • ), together with (4.3), we have

V t * ,λ ≤ B 2 t * ,λ + C κ √ Dδ 2 ;
bringing together the two last displays and using C 1 , 2 ≥ 1 yields again

B 2 t * ,λ + V t * ,λ ≤ C 1 , 2 E[ µ (tw) -µ 2 A ] + C κ √ Dδ 2 ,
so that this inequality holds in all cases (including t * = t w in which case the inequality holds trivially since C 1 , 2 ≥ 1). Applying (3.1) and (A + B) 2 ≤ 2A 2 + 2B 2 , we arrive at

E µ (τ ) -µ 2 A ≤ 2 E µ (t * ) -µ 2 A + 2 2Dδ 4 + 4δ 2 B 2 t * ,λ 1/2 ≤ 2C 1 , 2 E[ µ (tw) -µ 2 A ] + 2C κ √ Dδ 2 + 4δ 1 2 Dδ 2 + B 2 t * ,λ 1/2 . Furthermore, 1 2 Dδ 2 + B 2 t * ,λ ≤ (2C 1 , 2 -1 2 )Dδ 2 + C κ √ Dδ 2
follows directly from (4.4) (which holds in all cases) and the trivial bound V t * ,λ ≤ Dδ 2 . It remains to simplify the bound, using C 1 , 2 ≥ 1.

In weak norm, the oracle inequality immediately implies rate-optimal estimation by µ (τ ) whenever the weak oracle risk inf t≥0 E µ (t) -µ 2

A is at least of order √ Dδ 2 . The constants are not optimised, but give a reasonable order of magnitude. For spectral cutoff, an exact asymptotic balanced oracle inequality (i.e., with factor (1 + o( 1)) in front of the balanced oracle risk) can be derived as in (3.3).

In strong norm, the oracle property is more involved. The next result shows, however, that this question is intrinsic: the strong risk at t * can be bounded by the strong risk at the weakly balanced oracle t w , which depends only on the underlying regularisation method and on the spectrum of A, but not on the particular adaptation method. Hence, any empirical risk or cross-validation technique, which is based on a data-fidelity criterion in weak norm, will face the same error estimates.

E µ (t * ) -µ 2 ≤ max 2C 1 , 2 +C κ C -1 • -1, C V,λ (1+C κ C -1 • ) π E µ (tw) -µ 2 .
Proof. For t * < t w , we obtain by (4.1), using V t * ,λ ≤ V tw,λ = B 2 tw,λ (equality due to t w > t • ) as well as

C • √ Dδ 2 ≤ V t•,λ ≤ V tw,λ : B 2 t * ,λ ≤ (2C 1 , 2 + C κ C -1 • -1)B 2 tw,λ .
By Lemma 3.12, we can transfer a weak bias inequality into a strong bias inequality with the same constant and the result follows. In the case t * > t w , we argue in a similiar manner using (4.2) (which holds since t * > t • ):

V t * ,λ ≤ B 2 t * ,λ + C κ √ Dδ 2 ≤ B 2 tw,λ + C κ C -1 • V t•,λ ≤ (1 + C κ C -1 • )V tw,λ ,
followed by the variance transfer guaranteed by Assumption A3.

Next, we turn to the control of the strong bias at the weak oracle t w . Surprisingly, this is quite universally feasible. The following result establishes a particularly clean bound for the spectral cutoff method.

4.3 Theorem. For the spectral cutoff method from Example 3.4 with

c A i -p/d ≤ λ i ≤ C A i -p/d we have E µ (tw) -µ 2 ≤ (1 + (C A /c A ) 2 (1 + p/d)/2) E µ (ts) -µ 2 . For |κ -Dδ 2 | ≤ C κ √ Dδ 2 with C κ ∈ [0, C • )
, we obtain for the early stopping risk an oracle inequality in strong norm, with a constant C s only depending on

C A /c A , C κ /C • , p/d: E µ (τ ) -µ 2 ≤ C s E µ (ts) -µ 2 .
Proof. For spectral cutoff, since γ

(t) i = 0 for i > t + 1, we have B 2 t /B 2 t,λ ≥ λ -2
t +1 , on the other hand since γ

(t) i = 1 for i ≤ t , it holds V 2 t /V 2 t,λ ≤ λ -2 t +1 . Hence, for t w > t • , B 2 tw,λ = V tw,λ implies B 2
tw ≥ V tw , and therefore t w ≤ t s (obviously also true when t w = t • ), whatever µ. Now, for t > t w ,

B 2 tw -B 2 t = (1 -γ (tw) tw+1 ) 2 µ 2 tw+1 + t i= tw+2 µ 2 i + (1 -(1 -γ (t) t+1 ) 2 )µ 2 t+1 ≤ λ -2 t (B 2 tw,λ -B 2 t,λ ) ≤ λ -2 t V tw,λ holds. The singular value bounds imply λ -2 t V t,λ ≤ (C A /c A ) 2 (1 + p/d)V t and thus by V tw,λ ≤ V t,λ , inserting t = t s , B 2 tw ≤ B 2 ts + (C A /c A ) 2 (1 + p/d)V ts .
The first bound therefore follows from

V tw + B 2 tw ≤ (1 + (C A /c A ) 2 (1 + p/d))V ts + B 2
ts and V ts = B 2 ts = 1 2 E[ µ (ts) -µ 2 ] for t s > t • (otherwise t s = t w and the result holds trivially).

For the second part, we check that the conditions of Corollary 3.11 are met. From (4.1) with

C 1 , 2 = 1 + D -1/2 we obtain B 2 t * ,λ ≤ (1 + 2D -1/2 + C κ C -1 • )V t * λ , while (4.2) implies B t * ,λ ≥ (1 -C κ C -1 • )V t•,λ 1(t * > t • ).
Finally, the condition on the spectrum ensures

δ 2 λ -2 i ≤ δ 2 (C A /c A ) 2 i -2p/d λ -2 1 ≤ (C A /c a ) 2 i -2p/d V t• (since t • ≥ 1). Consequently, we can apply Corollary 3.11, yielding E µ (τ ) -µ 2 ≤ C τ,t * E µ (t * ) -µ 2 with C τ,t * depending on C κ /C • , p/d, C A /c A .
Hence, by Proposition 4.2 and by the first inequality established here, the asserted oracle inequality follows.

The spectral cutoff example extends generally to cases where the weakly balanced oracle tends to oversmooth in strong norm, as formalised next.

4.4 Proposition. Grant Assumptions (R) and (S). For all µ with t w (µ) ≤ t s (µ) we have with the constant C V from Lemma 3.9

E µ (tw) -µ 2 ] ≤ (2β + ) 2/ρ C V + 4 E µ (ts) -µ 2 .
Proof. By Assumption R3 we have 4(1 -γ

(t) i ) 2 ≥ 1 if tλ i ≤ c := (2β + ) -1/ρ . Consequently, for t > t w : B 2 tw -4B 2 t = D i=1 (1 -γ (tw) i ) 2 -4(1 -γ (t) i ) 2 µ 2 i ≤ i:λ i >ct -1 (1 -γ (tw) i ) 2 µ 2 i ≤ i:λ i >ct -1 (1 -γ (tw) i ) 2 (c -1 tλ i ) 2 µ 2 i ≤ c -2 t 2 B 2 tw,λ ≤ c -2 t 2 V tw,λ .
From Lemma 3.9 we know

V t,λ ≤ C V t -2 V t . We insert t = t s and use V tw,λ ≤ V ts,λ to conclude B 2 tw ≤ 4B 2 ts + c -2 C V V ts .
Adding V tw ≤ V ts and simplifying the constant yield the result. Section 5.1 below shows for the Landweber method that t w (µ) ≤ t s (µ) or at least V tw(µ) V ts(µ) holds for a certain class of polynomially decaying signals µ. For rapidly decaying signals µ, however, the inverse relationship t w (µ) > t s (µ) may happen:

4.5 Example (Generic counterexample to t w ≤ t s ). Consider the signal µ 1 = 1, µ i = 0 for i ≥ 2 and assume λ 1 = 1, γ (t) 1 < 1 for all t ≥ 0. Then we have B 2 t (µ) = B 2 t,λ (µ) > 0 whereas V t ∼ t 2 V t,λ
holds in the setting of Lemma 3.9. Hence, noting that t w → ∞ as δ → 0, we see that

V tw ∼ t 2 w V tw,λ = t 2 w,λ B 2 tw,λ (µ) = t 2 w B 2 tw (µ) is of larger order than B 2 tw (µ), implying t w /t s → ∞ as δ → 0.
The weakly balanced oracle does not profit from the regularity of µ in strong norm. Notice that this loss of efficiency is intrinsic to the stopping problem: based only on the residual R 2 t we have no possibility to detect in which part of the spectrum the bias concentrates. Still, we are able to control the error by an inflated weak oracle risk.

4.6 Theorem. Suppose Assumptions (R), (S) hold with ρ > 1 + ν + 2 and (4.3) holds for κ with C κ ∈ [0, C • ). Then for all µ with t w (µ) ≤ t s (µ) we have E µ (τ ) -µ 2 ≤ C τ,s E µ (ts) -µ 2 . For all µ with t w (µ) ≥ t s (µ) we obtain

E µ (τ ) -µ 2 ≤ C τ,w t 2 w E µ (tw) -µ 2 A .
The constants C τ,s and C τ,w depend only on ρ, β -, β + , L, ν -, ν + .

Proof. We want to apply Corollary 3.11 (bounding the strong risk of µ (τ ) by that of µ (t * ) ) followed by Proposition 4.2 (from

µ (t * ) to µ (tw) ) in order to bound E[ µ (τ ) -µ 2 ] by C τ,t * max(2C 1 , 2 + C κ C -1 • -1, C V,λ (1 + C κ C -1 • ) π ) E µ (tw) -µ 2 .
For this, note first that Assumption (A) holds by Proposition 3.8. Furthermore, C κ ∈ [0, C • ) implies by the bounds in (4.1)-(4.2) together with

V t * ,λ ≥ V t•,λ = C • √ Dδ 2 that B 2 t * ,λ ∈ [(1 -C κ C -1 • )V t * ,λ 1(t * > t • ), (2C 1 , 2 + C κ C -1 • -1)V t * ,λ ]
, as required for Corollary 3.11. The second assumption for Corollary 3.11 is ensured under (R), (S) by Lemma 6.2 in the Appendix (inequality (6.5)).

For the case t w ≤ t s we can conclude the first inequality by the bound on E[ µ (tw) -µ 2 ] in Proposition 4.4. In the other case, B 2 tw ≤ V tw ≤ c -1 V t w 2 V tw,λ is implied by Lemma 3.9, using ρ > 1 + ν + /2, and the second result follows. It remains to trace back the dependencies of the constants involved.

Let us specify this main result for polynomially decaying singular values λ i . Then we can write an oracle inequality which involves the oracle risks in weak and strong norm instead of the index t w itself.

Corollary. Grant Assumption

(R), (4.3) with C κ ∈ [0, C • ) and c A i -1/ν ≤ λ i ≤ C A i -1/ν for C A ≥ c A > 0 and 0 < ν < 2ρ -2. Then E µ (τ ) -µ 2 ≤ C τ,ws max δ -4/ν E µ (tw) -µ 2 A 1+2/ν , E µ (ts) -µ 2 holds with a constant C τ,ws depending only on ρ, β -, β + , c A , C A . Proof. From δ -2 V tw,λ = D i=1 (γ (tw) i ) 2 we deduce via Assumption R3 δ -2 V tw,λ ≥ β -#{i : λ i ≥ 1/t w } ≥ β -(c A t w ) ν . Because of δ -4/ν E[ µ (tw) -µ 2 A ] 2/ν ≥ (δ -2 V tw,λ ) 2/ν ≥ β 2/ν - (c A t w ) ν 2/ν
the bound follows by combining the two inequalities from Theorem 4.6.

A further consequence is a minimax rate-optimal bound over the Sobolev-type ellipsoids H β d (R) from (2.2). At this stage we need the concept of qualification of the spectral regularisation method, i.e., the filter sequence.

Corollary. Grant Assumption

(R), (4.3) with C κ ∈ [0, C • ), c A i -p/d ≤ λ i ≤ C A i -p/d for C A ≥ c A > 0 and p/d > (2ρ -2) -1 as well as 1 -g(t, λ) ≤ C q (tλ) -2q , t ≥ t • , λ ∈ (0, 1],
for some qualification index q > 0. Then µ (τ ) attains the minimax-optimal rate over H β d (R) sup

µ∈H β d (R) E µ (τ ) -µ 2 R 2 (R -1 δ) 4β/(2β+2p+d) , provided 2q -1 ≥ β/p and (R/δ) 2d/(2β+2p+d) √ D for D → ∞ as δ → 0.
Proof. A qualification q ≥ β/(2p) in combination with Assumption (R) ensures for µ ∈ H β d (R), compare also Thm. 4.3 in Engl et al. [START_REF] Engl | Regularization of Inverse Problems[END_REF]:

B 2 t (µ) ≤ D i=1 C 2 q min (tλ i ) -2q , 1 2 µ 2 i ≤ C 2 q D i=1 (tc A i -p/d ) -2β/p µ 2 i ≤ C 2 q c -2β/p A R 2 t -2β/p .
Similarly, we deduce for 2q -1 ≥ β/p:

t 2 B 2 t,λ (µ) ≤ D i=1 C 2 q min (tλ i ) -2q+1 , tλ i 2 µ 2 i ≤ C 2 q c -2β/p A R 2 t -2β/p .
Under Assumption R3 the weak variance satisfies V t,λ δ 2 i min(β + (tλ i ) 2ρ , 1) δ 2 t d/p provided λ i ∼ i -p/d , p > d/(2ρ). For p > d/(2ρ -2) we obtain in a similar manner V t δ 2 t 2+d/p . An optimal choice of t is thus of order (R/δ) 2p/(2β+2p+d) and gives

inf t≥0 max E[ µ (t) -µ 2 , t 2 E[ µ (t) -µ 2 A R 2 (R -1 δ) 4β/(2β+2p+d) ,
with a constant independent of µ, D and δ. Now note that by assumption for the optimal choice (R/δ) 2p/(2β+2p+d) D 1/2 ∼ t • holds. In view of the narrow sense oracle property (1.17) of t w and equally of t s in strong norm, we thus conclude by applying Theorem 4.6.

For the filters of Example 3.6 we see that Landweber and Showalter's method have any qualification q > 0 while standard Tikhonov regularisation has qualification q = 1. The statement is very much in the spirit of the results for the deterministic discrepancy principle, see e.g. Thm. 4.17 in Engl et al. [START_REF] Engl | Regularization of Inverse Problems[END_REF], when interpreting κ = δ 2 D as the squared noise level, cf. Hansen [START_REF] Hansen | Discrete inverse problems: insight and algorithms, Fundamentals of Algorithms[END_REF]. Note, however, that we do not require a slightly enlarged critical value and that the necessary choice of t • > 0 indicates an intrinsic difference between deterministic and statistical inverse problems.

For the setting of the corollary a conservatively large choice of the dimension would be D ∼ δ -2d/(2p+d) , cf. (2.3). For that choice the corollary applies for all β ∈ (0, p + d/2], assuming R fixed and q sufficiently large. In consequence all squared minimax rates in the range [δ, 1] can be attained, but we cannot converge faster, i.e., the potential range [δ 2 , δ) for high smoothness is not covered (as predicted by the lower bound).

Theorem 4.6 can also serve to deduce bounds on the Bayes risk of µ (τ ) with respect to a prior Π for the signals µ. For concrete methods and general classes of priors Π we can thus obtain Bayesian oracle inequalities similar to Bauer and Reiß [START_REF] Bauer | Regularization independent of the noise level: an analysis of quasi-optimality[END_REF], but in a different setup.

5 Implementing the Landweber method 5.1 A sufficient condition for the oracle property For the concrete example of the Landweber method, let us investigate for which signals µ we have a true oracle inequality in the sense that in Theorem 4.6 the first inequality applies with a universal constant C τ,s > 0. Note first that, under Assumption (S) with L = 2 for simplicity, if we can ensure additionally that V tw ≤ C t V ts for some C t > 1, then Proposition 4.4 yields the more general bound

E µ (tw) -µ 2 ] ≤ max (2β + ) 2/ρ C V + 4, C t E µ (ts) -µ 2 .
(5.1) This is just due to B tw (µ) ≤ B ts (µ) in the case t w > t s .

To establish the additional condition above, let us consider for some c µ > 0 the class of signals µ

C := µ ∈ R D | ∀i : µ 2 2i+1 + µ 2 2i ≥ c µ µ 2 i . (5.2)
From the definition of the Landweber filters in Example 3.6 we obtain

(1 -γ (t) i ) 2 (1 -γ (t) 2i ) 2 = 1 - λ 2 i -λ 2 2i 1 -λ 2 2i 2t 2 ≤ exp -2(1 -2 -2/ν + )t 2 λ 2 i .
By the decay of r → re -(1-2 -2/ν + )r := C r for r ≥ r 0 := (1 -2 -2/ν + ) -1 , we can thus bound for µ ∈ C i:tλ i ≥r 1/2

(1 -γ

(t) i ) 2 (tλ i ) 2 µ 2 i ≤ c -1 µ C 2 r i:tλ i ≥r 1/2 (1 -γ (t) 2i ) 2 µ 2 2i + µ 2 2i+1 . This implies t 2 B 2 t,λ (µ) ≤ (c -1 µ C 2 r + r)B 2 t (µ). Using t 2 V t,λ ≥ C V V t from Lemma 3
.9 and the definition of the balanced oracles, we conclude in the case t w > t s :

V tw ≤ C -1 V t 2 V tw,λ = C -1 V t 2 B 2 tw,λ (µ) ≤ C -1 V (c -1 µ C 2 r + r)B 2 tw (µ) ≤ C -1 V c -1 µ C 2 r + r V ts .
The value of r may be optimised or we just take r = r 0 to define C t . In conclusion, for Landweber iterations under Assumption (S) with L = 2 the inequality (5.1) applies to all signals µ ∈ C. In particular, a strong norm inequality holds whenever µ 2 i ∼ i -ρ for any exponent ρ ≥ 0. The class C in combination with Counterexample 4.5 illustrates that the early stopping rule τ has bad adaptation properties only if the signal has significantly different strength in the lower and higher SVD coefficients.

Numerical examples

As a test bed for a numerical implementation we take the moderately illposed case λ i = i -1/2 with noise level δ = 0.01 and dimension D = 10 000. After 51 Landweber iterations the weak variance attains the level √ 2Dδ 2 , which is the dominating term in (3.2) and corresponds to C • = √ 2 in the choice of t • (by abuse of notation, indices t denote numbers of iterations here). The ratio i γ 2 , defining the constant C 1 , 2 , increases in t and is about 1.05 at t • . In view of the relationship (4.1) we choose κ = 0.95 for Landweber, slightly smaller than Dδ 2 = 1.0. In comparison, we also consider the spectral cutoff method where the weak variance √ 2Dδ 2 is attained at the SVD coefficient (frequency) t • = 141 and where we use κ = Dδ 2 . Nevertheless, in this simulation we compute the stopping rule τ starting at t 0 = 0 to illustrate the effects when very early stopping is recommended.

(t) i / i (γ (t) i )
In Figure 2 (left) we see the SVD representation of three signals: a relatively smooth signal µ(1), a very rough signal µ(2) and a super-smooth signal µ(3), the attributes coming from the interpretation via the decay of Fourier coefficients. Note that due to the oscillations and the rapid decay, respectively, the signals do not lie in the class C from (5.2) above unless c µ > 0 is tiny. The corresponding weakly balanced oracle indices t w are (355, 1074, 42) for Landweber and (512, 1356, 34) for spectral cutoff. So, indeed we stop before t • in the super-smooth case and expect a high variability of τ around t * , especially in the spectral cutoff case. The strong indices t s are (310, 1185, 29) for Landweber, (655, 2379, 37) for spectral cutoff. This confirms t w ≤ t s for spectral cutoff and shows that for Landweber we may also have t w > t s .

For the rough signal µ(1) Figure 1 in the introduction displays squared bias, variance and residuals as a function of m for one realisation and indicates the stopping indices (the strong bias and variance functions are scaled by 0.02 to fit into the picture).

Relative to our target t w , Figure 2 (right) displays box plots (a box representing the inner quartile range, whiskers the total support and a horizontal bar the mean) for the stopping rule τ in 1000 Monte Carlo repetitions. We see that for Landweber τ tends to stop earlier than t w , while for spectral cutoff the ratio τ /t w varies around 1.0, as expected due to t * ≈ t w . As predicted, the (relative) variability in the super-smooth case is much higher.

In Figure 3 the box plots show for the same Monte Carlo run the relative errors

E[ µ (τ ) -µ 2 A ]/ min t≥0 E[ µ (t) -µ 2 A ] (left) and E[ µ (τ ) - µ 2 ]/ min t≥0 E[ µ (t) -µ 2 ]
(right), respectively. In weak norm we observe a loss by a about a factor 1.5 for Landweber, while for spectral cutoff the loss is even smaller, except for the super-smooth case. Interestingly, in strong norm Landweber performs even better which is due to the fact that the oracle proxy t * is closer to the strong than to the weak oracle indices, cf. also Further unreported simulations confirm these findings, in particular the relative error due to adaptive stopping remains small (rarely larger than 2, the maximal factor arising already with the balanced oracle choice). Only for super-smooth signals, where we ought to stop before t • , the variability may become harmful.

As a practical procedure, we propose to run the iterations always until t • (51 iterates in our Landweber case) and if the stopping rule τ tells us not to continue, then a standard model selection procedure like Lepski's can be applied to choose among the t • first iterates. Since in general the lack of a complete oracle inequality in strong norm is due to stopping later than at t s , we could even always apply Lepski's method to select among µ (0) , . . . , µ (τ ) . The performance of this two-step approach needs to be studied further, but seems very promising.

Appendix

Proof of Proposition 3.8

We start with an important result for a nonincreasing sequence satisfying (S). This is related to comparisons between a function and its power integrals, also known as Karamata's one-sided relations. For p > ν + and k ≥ 1 we have

j≥k λ p j kλ p k ≤ L -1 1 -L 1-p/ν + . ( 6.3)
Proof. For inequality (6.2), write:

Lk j=k+1 λ p j ≥ (L -1)kλ p Lk ≥ L -p/ν -(L -1)kλ p k .
We turn to (6.1), for which we write

j≤k λ -p j ≥ k j= k/L λ -p j ≥ k + 1 - k L λ -p k/L ≥ (1 -L -1 )kL -p/ν -λ -p L k/L ≥ L -p/ν -(1 -L -1 )kλ -p k .
Finally, for (6.3), we have

λ Lk λ k ≤ L -1/ν + and j≥k λ p j = ≥0 kL +1 -1 i=kL λ p i ≤ ≥0 kL (L -1)λ p kL ≤ k(L -1)λ p k ≥0 L (1-p/ν + ) = (L-1)kλ p k 1-L 1-p/ν + .
We will need the following auxiliary result:

6.2 Lemma. Suppose Assumptions (S) and (R) are satisfied with 2ρ > ν + , then the constant t • defined via (3.4) is such that

t • ≥ ζλ -1 1 , with ζ := C • √ D(1 -L 1-2ρ/ν + ) (L -1)β + 1/2ρ . ( 6.4)
It follows, for any k = 1, . . . , D:

δ 2 λ -2 k ≤ Ck 2/ν -V t• , with C = β -2 -L 2/ν -(1 ∧ ζ) -2ρ . (6.5)
Proof. Using Assumption R3 and then (6.3) gives

V t,λ = δ 2 D i=1 (γ (t) i ) 2 ≤ δ 2 β + t 2ρ ∞ i=1 λ 2ρ i ≤ δ 2 β + t 2ρ λ 2ρ 1 L -1 1 -L 1-2ρ/ν + .
By definition, V t•,λ = C • D 1/2 δ 2 holds and (6.4) follows. We then have as a consequence

V t• ≥ δ 2 (γ (t•) 1 ) 2 λ -2 1 ≥ β 2 -min(1, ζ) 2ρ δ 2 λ -2 1 . Finally, for any k = 1, . . . , D, put := log k/ log L , then (3.8) entails λ -2 k ≤ λ -2 L ≤ λ -2 1 L 2 /ν -≤ λ -2 1 (Lk) 2/ν -.
Combining the two last displays yields (6.5).

Proof of Proposition 3.8. The monotonicity, continuity and limiting behaviour of g(t, λ) in t = 0, t → ∞ for fixed λ required from R1 ensure the basic requirements on the filter sequence (namely t → γ (t) i continuous, γ (0) i = 0 and γ (t) i ↑ 1 as t → ∞ ). Since the spectral sequence (λ i ) i≥1 is nonincreasing, the monotonicity in λ of g(t, λ) ensures the validity of A2. Similarly, Assumption R2 transparently ensures A1.

We turn to checking A4. For this we use (6.1) with p = 2, yielding

∀k ≥ 1 : j≤k λ -2 j kλ -2 k ≥ L -2/ν -(1 -L -1 ) =: c λ .
We now check A5 for t ≥ t

(t) j ∈ [ζ ρ β -, 1] for all j < j * t , so that D i=1 γ (t) i = j * t -1 i=1 γ (t) i + D i=j * t γ (t) i ≤ ζ -ρ β -1 - j * t -1 i=1 γ (t) i 2 + β + t ρ D i=j * t λ ρ i . (6.6)
To control the second term, we note that, since ρ > ν + , (6.3) yields

j≥k λ ρ j ≤ Ckλ ρ k , where C := L -1 1 -L 1-p/ν + .
We apply this relation to k = j * t . The inequalities λ j * t < ζ/t and j * t ≥ 2 entail

t ρ D i=j * t λ ρ i ≤ Cj * t t ρ λ ρ j * t ≤ 2Cζ ρ (j * t -1) ≤ 2Cζ -ρ β -2 - j * t -1 i=1 (γ (t) i ) 2 .
Plugging this into (6.6) yields A5 with

C 1 , 2 = ζ -ρ (β -1 -+ 2Cβ + β -2 -
). We finally turn to A3. Without loss of generality we can assume β + ≥ 1 in (R3). Because for all A, B > 0

1 2 (A + B) -1 ≤ min(A -1 , B -1 ) ≤ (A + B) -1 , (6.7)
it follows that condition (R3) implies for all t ≥ t • :

β -(1+(tλ) -ρ ) -1 ≤ g(t, λ) ≤ 2(1+β -1 + (tλ) -ρ ) -1 ≤ 2β + (1+(tλ) -ρ ) -1 . (6.8)
Denote h(t) := (1+t -ρ ) -1 ; the above implies together with (3.5) that

γ (t) i h(tλ i ) ∈ [β -, 2β + ]. We infer that for t ≥ t ≥ t • : V t V t = D i=1 (γ (t) i λ -1 i ) 2 D i=1 (γ (t ) i λ -1 i ) 2 ≤ 4β 2 + β 2 - D i=1 λ -1 i h(tλ i ) 2 D i=1 λ -1 i h(t λ i ) 2 =: 4β 2 + β 2 - H(t) H(t ) , while V t,λ V t ,λ = D i=1 (γ (t) i ) 2 D i=1 (γ (t ) i ) 2 ≥ β 2 - 4β 2 + D i=1 h(tλ i ) 2 D i=1 h(t λ i ) 2 =: β 2 - 4β 2 + G(t) G(t ) .
Our next goal is to establish that there exists a constant π such that

H(t)/H(t ) ≤ (G(t)/G(t )) π , (6.9)
which will yield the desired bound A3 with C V,λ := (4β 2 + /β 2 -) 1+π . A sufficient condition for (6.9) is to establish for all t ≥ t • :

d dt log H(t) = H (t) H(t) ≤ π G (t) G(t) = π d dt log G(t), (6.10)
i.e., to check the inequality

D i=1 λ -1 i hh (tλ i ) D i=1 λ -2 i h(tλ i ) 2 = ρt -ρ-1 D i=1 λ -ρ-2 i 1 + (tλ i ) -ρ -3 D i=1 λ -2 i 1 + (tλ i ) -ρ -2 ≤ πt -ρ-1 D i=1 λ -ρ i 1 + (tλ i ) -ρ -3 D i=1 1 + (tλ i ) -ρ -2 = π D i=1 λ i hh (tλ i ) D i=1 h(tλ i ) 2
.

Using (6.7) again, it is sufficient to check the above inequality when replacing everywhere 1 + (tλ i ) -ρ -1 by min(1, (tλ i ) ρ ), and π by π/32. Denoting k * t := inf k ≥ 1 : λ k < t -1 ∧(D+1), we thus have to establish the sufficient condition (for some constant π)

i<k * t λ -ρ-2 i + D i=k * t t 3ρ λ 2ρ-2 i i<k * t λ -2 i + D i=k * t t 2ρ λ 2ρ-2 i ≤ π 32 i<k * t λ -ρ i + D i=k * t t 3ρ λ 2ρ i (k * t -1) + D i=k * t t 2ρ λ 2ρ i . (6.11)
Writing the left fraction as (A 1 + A 2 )/(B 1 + B 2 ) and the right fraction (without π/32) as (A 3 + A 4 )/(B 3 + B 4 ), we check this relation by bounding

A i B j ≤ π 32 A j B i for i = 1, 2, j = 3, 4.
Without loss of generality we assume 1 < k * t ≤ D (otherwise some products are just zero). Let us recall that (6.1) implies (taking p := max(2, ρ) there) that ∀k ≥ 1 : kλ

-max(2,ρ) k ≤ C j≤k λ -max(2,ρ) j , (6.12)
for C := L max(2,ρ)/ν -/(1 -L -1 ). We will also need below a similar bound with λ k replaced by λ k+1 on the left-hand side. For this, notice that by Assumption (S) we have λ k λ k+1 ≤ λ k λ Lk ≤ L 1/ν -, combining with (6.12) we get:

∀k ≥ 1 : kλ -max(2,ρ) k+1 ≤ kL max(2,ρ)/ν -λ -max(2,ρ) k ≤ C j≤k λ -max(2,ρ) j , (6.13) with C := L 2 max(2,ρ)/ν -/(1 -L -1 ).
The first term to handle is now (using (6.12)):

A 1 B 3 = (k * t -1) i<k * t λ -ρ-2 i ≤ (k * t -1)λ -max(2,ρ) k * t -1 i<k * t λ -min(2,ρ) i ≤ C i<k * t λ -2 i i<k * t λ -ρ i = CB 1 A 3 .
For the second term we clearly have A 2 B 4 = A 4 B 2 . The third term (using (6.13) and the definition of k * t ) is bounded as:

B 3 A 2 = (k * t -1) D i=k * t t 3ρ λ 2ρ-2 i ≤ C t ρ λ max(2,ρ) k * t i<k * t λ -max(2,ρ) i D i=k * t t 2ρ λ 2ρ-2 i ≤ C i<k * t t -(2-ρ) + λ -max(2,ρ) i D i=k * t t 2ρ λ 2ρ-2 i ≤ C ( i<k * t λ -ρ i ) D i=k * t t 2ρ λ 2ρ-2 i = C A 3 B 2 .
For the fourth term we bound, using the definition of k * t ,

A 1 B 4 = i<k * t λ -2 i (tλ i ) -ρ D i=k * t t 3ρ λ 2ρ i ≤ D i=k * t t 3ρ λ 2ρ i ( i<k * t λ -2 i ) = A 4 B 1 .
Hence, (6.11) is established if we choose π ≥ 32C .

6.2 Proof of Lemma 3.9

Let us introduce the spectral distribution function F (u) = #{i : λ i ≥ u} for u > 0. Then Assumption (S) gives

F (L 1/ν -u) ≥ k ⇔ λ k ≥ L 1/ν -u ⇒ λ Lk ≥ u ⇔ F (u) ≥ Lk,
so that taking k = F (L 1/ν -u) in the above display yields F (u) ≤ L L-1 (F (u)-F (L 1/ν -u)). Set again k * t := inf{k ≥ 1 : λ k < t -1 } ∧ (D + 1) = F (1/t) + 1. Under Assumption (R) we conclude for t ≥ t

• δ -2 V t,λ = D i=1 (γ (t) i ) 2 ≤ F (1/t) + D i=k * t (tλ i ) -2 (γ (t) i ) 2 ≤ L L -1 i:1/t≤λ i <L 1/ν -/t (L -1/ν -tλ i ) -2 + D i=k * t (tλ i ) -2 (γ (t) i ) 2 ≤ L 1+2/ν - L -1 t -2 D i=1 λ -2 i (γ (t) i /β -) 2
= L 1+2/ν - L-1 β -2 -t -2 δ -2 V t . This establishes the first inequality. In the other direction, denote, as in the proof of Prop. 3.8, j * t := inf{i ≥ 1 : λ i < ζ/t} ∧ (D + 1), where ζ := min( ζ, 1) with ζ from (6.4). Under Assumption R3 we have

t -2 δ -2 V t = t -2 D i=1 λ -2 i (γ (t) i ) 2 ≤ ζ -2 i<j * t (γ (t) i ) 2 + β 2 + t 2ρ-2 D i=j * t λ 2ρ-2 i .
We concentrate on the second term. If D ≥ Lj * t , we use the Karamata relations (6.3), then (6.2), and 2ρ -2 > ν + , to bound

D i=j * t λ 2ρ-2 i ≤ (L -1)j * t λ 2ρ-2 j * t 1 -L 1-(2ρ-2)/ν + ≤ L 2ρ/ν - (1 -L 1-(2ρ-2)/ν + ) λ -2 j * t D i=j * t λ 2ρ i .
If D < Lj * t , then directly using (3.8):

D i=j * t λ 2ρ-2 i ≤ λ -2 Lj * t D i=j * t λ 2ρ i ≤ L 2ρ/ν -λ -2 j * t D i=j * t λ 2ρ i ,
which implies that the inequality derived in the first case still holds. Additionally, since j * t ≥ 2 from Lemma 6.2, we have λ j * t ≥ λ L(j * t -1) ≥ L -1/ν -λ j * t -1 ≥ L -1/ν -ζt -1 , so that Altogether, we obtain the second inequality:

t -2 V t ≤ ζ -2 L 2(ρ+1)/ν - (1-L 1-(2ρ-2)/ν + )β 2 - V t,λ .

Proof of Lemma 2.3

To prove this lemma we first recall a result on the concentration of weighted chi-squared type random variables. Then the following inequalities hold for any x > 0:

P Z > 2 a 2 √
x + 2 a ∞ x) < e -x , (6.14)

P Z < -2 a 2 √
x < e -x (6.15)

and also

P Z > x) < exp - 1 4
x 2 a 2 2 + a ∞ x , P Z < -x < exp -1 4

x 2 a 2 2 . Lemma 6.3 is stated in a slightly more general setting, since the original result of Laurent and Massart [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF], based itself on Lemma 8 in Birgé and Massart [START_REF] Birgé | Minimum contrast estimators on sieves: exponential bounds and rates of convergence[END_REF], has no supremum in k for the definition of Z. The proof, however, is based on the classical Chernov bound argument, which readily carries over with a supremum: indeed, for t ≥ 0 and λ > 0, P (Z ≥ t) = P max Proof of Lemma 2.3. With Z k = k i=1 λ -2 i ε 2 i we obtain

R(µ, τ ) 2 ≥ δ 2 E τ i=1 λ -2 i ε 2 i ≥ δ 2 E 1(τ ≥ k)Z k .
Insert a = (λ -2 1 , . . . , λ -2 k ) and x := log(5/4) in (6.15) so that 2 √ x ≤ 0.95. Then with probability larger than 1 -e -x = 0.2, it holds that

Z k ≥ E [Z k ] -a 2 2 √ x ≥ 1 20 k i=1 λ -2 i =: z k ,
where we used E [Z k ] = D i=1 a i ≥ a 2 (observe that we could tighten the latter inequality significantly under some additional assumptions on the singular value decay). We now have

δ -2 R(µ, τ ) 2 ≥ E [1(τ ≥ k)Z k ] ≥ z k P ({τ ≥ k} ∩ {Z k ≥ z k }) ≥ z k 1 -P (τ < k) -P (Z k < z k ) ≥ z k 0.2 -P (τ < k) .
We deduce from this that z k > 10δ -2 R(µ, τ ) 2 implies P (τ ≥ k) ≤ 0.9.

6.4 A total variation bound for non-central χ 2 -laws 6.4 Lemma. Let ϑ = (ϑ 1 , . . . , ϑ K ) ∈ R K and P ϑ K be the non-central χ 2law of X ϑ = K k=1 (ϑ k + Z k ) 2 with Z k independent and standard Gaussian. Then, for ϑ, θ ∈ R K we have

P ϑ K -P θ K T V ≤ e | ϑ 2 -θ 2 | + 8/π| ϑ -θ | √ πK ,
For ϑ + θ ≥ √ 8e 2π-√ πe ≈ 5.248 this bound simplifies to

P ϑ K -P θ K T V ≤ 2 | ϑ 2 -θ 2 | √ K .
Proof. Writing ϑ = (ϑ k ), Z = (Z k ) ∈ R k we see by orthogonal transformation that X ϑ = ϑ 2 + 2 ϑ, Z + Z 2 equals in law X ϑ = ϑ 2 + 2 ϑ Z 1 + Z 2 with Z 1 , . . . , Z K ∼ N (0, 1) i.i.d. We can therefore first consider the conditional law Q ϑ K (z) of P ϑ K given {Z 1 = z}, which is nothing but the χ 2 (K -1)-distribution translated by ϑ 2 + 2 ϑ z + z 2 .

If f p denotes the χ 2 (p)-density, then we have for any t > 0 that f p (x-t) > f p (x) holds iff x ≥ x t = t 1-e -t/(p-2) . Thus, we obtain x (p-2)/2 e -x/2 dx ≤ 2 (2-p)/2 Γ(p/2) t(p -2) (p-2)/2 e -(p-2)/2 , knowing that x = p -2 is the mode of f p . Stirling's formula guarantees Γ(x) ≥ 2π/x(x/e) x for all x > 0 such that the last expression is always bounded by t(πp) -1/2 e. This yields

Q ϑ K (z) -Q θ K (z) T V ≤ e(πK) -1/2 ϑ 2 -θ 2 + 2( ϑ -θ )z .
Taking expectation with respect to Z 1 ∼ N (0, 1) we conclude

P ϑ K -P θ K T V ≤ e(πK) -1/2 ϑ -θ E ϑ + θ + 2Z 1 .
Using the triangle inequality and E[|Z 1 |] = 2/π, the upper bound follows.

6.5 Maximal inequality for weighted χ 2 -variables with drift 6.5 Lemma. Work under Assumption A4. Then, for every ω > 0 and every x > 0 we have with probability at least 1 -C 1 e -C 2 x , where C 1 , C 2 > 0 only depend on c λ and ω:

max k≥1 k i=1 λ -2 i (ε 2 i -1 -ω) ≤ xλ -2 x ∧D .
Proof. From Lemma 6.3 with a p p (k) = k i=1 |a i | p for p ≥ 1 and the usual modification for p = ∞ as well as λ -2 p (k) ≤ λ -2 ∞ (k) k 1/p for p = 1, 2 and λ -

(r + ωc 2 λ k λ -2 ∞ (k) ) 2 λ -2 2 2 (k) + λ -2 ∞ (k) (r + ωc 2 λ k λ -2 ∞ (k) ) ≤ D k=1 exp - 1 4 (r + ωc 2 λ k λ -2 ∞ (k) ) 2 k λ -2 2 ∞ (k) + λ -2 ∞ (k) (r + ωc 2 λ k λ -2 ∞ (k) ) = D k=1 exp - 1

1 ,

 1 . . . D, and we specify linear estimation procedures by filters (γ(m) i ) i=1,...,D,m≥0 that satisfy γ (m) i ∈ [0, 1], γ (0) i = 0 and γ (m) i ↑ 1 as m → ∞. Typical filters include: spectral cutoff with γ (m) i = 1(i ≤ m), Landweber with γ (m) i = 1 -(1 -λ 2

Figure 1 :

 1 Figure 1: Weak squared bias (dark blue), weak variance (light blue), strong squared bias (red), strong variance (orange), residual (green, dashed) and its expectation (yellow, almost identical) as a function of number m of Landweber iterations; on the abscissa indices τ ≈ t * (for gray choice of κ), t • , t w , t s .

4. 2

 2 Proposition. Grant Assumptions A1, A3 and A5 with constants π, C V,λ , C 1 , 2 . Then for |κ -Dδ 2 | ≤ C κ √ Dδ 2 the oracle proxy t * and the weakly balanced oracle t w satisfy the strong norm bound

Figure 2 :

 2 Figure 2: Left: SVD representation of a smooth (blue), a rough (red) and a super-smooth (olive) signal. Right: Corresponding number of Landweber iterations and spectral cutoffs for τ divided by the weakly balanced oracle numbers.

Figure 3 :

 3 Figure 3: Boxplots of squared Monte Carlo errors for μ(τ) divided by oracle errors in weak (left) and strong (right) norm.

Figure 1 .

 1 Figure 1.Further unreported simulations confirm these findings, in particular the relative error due to adaptive stopping remains small (rarely larger than 2, the maximal factor arising already with the balanced oracle choice). Only for super-smooth signals, where we ought to stop before t • , the variability may become harmful.As a practical procedure, we propose to run the iterations always until t • (51 iterates in our Landweber case) and if the stopping rule τ tells us not to continue, then a standard model selection procedure like Lepski's can be applied to choose among the t • first iterates. Since in general the lack of a complete oracle inequality in strong norm is due to stopping later than at t s , we could even always apply Lepski's method to select among µ (0) , . . . , µ(τ ) . The performance of this two-step approach needs to be studied further, but seems very promising.

6. 1 ≥

 1 Lemma (One-sided Karamata relations). Suppose Assumption (S) is satisfied. Then for any p > 0 and k ≥ 1 we havej≤k λ -p j kλ -p k ≥ L -p/ν -(1 -L -1 (L -1)L -p/ν -.(6.2)

( 2 -

 2 tλ i ) 2ρ ≤ ζ -2 L 2(ρ+1)/ν - (1-L 1-(2ρ-2)/ν + )β

6. 3 D i=1 a 2 i

 32 Lemma (Laurent and Massart, Lemma 1 in[START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF]). Let (Y 1 , . . . , Y D ) be i.i.d. N (0, 1) variables. For nonnegative numbers a 1 , . . . , a D , write a 2 2 = and a ∞ = max 1≤i≤D a i . Set

1≤k≤D e λ k i=1 a i (Y 2 i - 1 ) 2 i - 1 )

 2121 ≥ e λt ≤ e -λt E e λ D i=1 a i (Y 2 i -1)by Doob's maximal inequality applied to the submartingale (e λ k i=1 a i (Y ) 1≤k≤D .

∞ 0 |f 2 ∞ 0 f

 020 p (x -t) -f p (x)| dx = p (x -t) -f p (x) + dx = 2 1-p/2 Γ(p/2) ∞ xt (1 -t/x) p/2-1 e t/2 -1 x p/2-1 e -x/2 dx

2 i - 1 ) 2 ∞

 212 2 1 (k) ≥ c 2 λ kλ -2 k = c 2 λ k λ -2 ∞ (k)by Assumption A4, we obtain for any integer k ≥ 1 > r + ωc 2 λ k λ -

c 4 λ ω 2 /(4+4c 2 λ ω) - 1 exp - c 4 λ ω 2

 42212 k * 4(1 + c 2 λ ω) for any k * . The choice k * = x ∧ D and r = xλ -2 k * yields the asserted deviation bound with suitable constants C 1 , C 2 > 0.

We emphasise in the notation the dependence in µ in the distribution of τ and the Yi by adding the subscript µ when writing the expectation E = Eµ or probability P = Pµ.

Alexander Goldenshluger and Peter Mathé are gratefully acknowledged. This research was supported by the DFG via Research Unit 1735 Structural Inference in Statistics, in particular a six months visit by MH to Humboldt-Universität was made possible.