arXiv:1710.07278v1 [math.ST] 19 Oct 2017

Early stopping for statistical inverse problems
via truncated SVD estimation∗
Gilles Blanchard

Marc Hoffmann

Markus Reiß

Institute of Mathematics
CEREMADE
Institute of Mathematics
Humboldt-Universität zu Berlin
Université Paris-Dauphine
Universität Potsdam
mreiss@math.hu-berlin.de
gilles.blanchard@math. hoffmann@ceremade.dauphine.fr
uni-potsdam.de

October 23, 2017

Abstract
We consider truncated SVD (or spectral cut-off, projection) estimators for a prototypical statistical inverse problem in dimension D.
Since calculating the singular value decomposition (SVD) only for the
largest singular values is much less costly than the full SVD, our aim
is to select a data-driven truncation level m
b ∈ {1, . . . , D} only based
on the knowledge of the first m
b singular values and vectors.
We analyse in detail whether sequential early stopping rules of this
type can preserve statistical optimality. Information-constrained lower
bounds and matching upper bounds for a residual based stopping rule
are provided, which give a clear picture in which situation optimal sequential adaptation is feasible. Finally, a hybrid two-step approach is
proposed which allows for classical oracle inequalities while considerably reducing numerical complexity.

Key words and Phrases: Linear inverse problems. Early stopping. Discrepancy principle. Adaptive estimation. Oracle inequalities.
AMS subject classification: 65J20, 62G07.
∗

Very instructive discussions with Thorsten Hohage, Alexander Goldenshluger and
Peter Mathé 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-Universität was made possible.

1

1
1.1

Introduction and overview of results
Model

A classical model for statistical inverse problems is the observation of
Y = Aµ + δ Ẇ

(1.1)

where A : H1 → H2 is a linear, bounded operator between real Hilbert spaces
H1 , H2 , µ ∈ H1 is the signal of interest, δ > 0 is the noise level and Ẇ is a
Gaussian white noise in H2 , see e.g. [2] and the references therein. In any
concrete situation, the problem is discretized and we can assume H1 = RD ,
H2 = RP with possibly very large D and P . Since the discretisation of µ is
at our choice, we usually take D ≤ P and we assume that A : RD → RP is
one-to-one. We transform (1.1) by the singular value decomposition (SVD)
of A into the Gaussian vector observation model
Yi = λi µi + δεi , i = 1, . . . , D,

(1.2)

where λ1 ≥ λ2 ≥ · · · ≥ λD > 0 are the singular values of A, (µi )1≤i≤D the
coefficients of µ in the orthonormal basis of singular vectors and (εi )1≤i≤D
are independent standard Gaussian random variables.
Working in the SVD representation (1.2), the objective is to recover the
signal µ = (µi )1≤i≤D with best possible accuracy from the data (Yi )1≤i≤D .
A classical method is to use the truncated SVD estimators (also called projection or spectral cut-off estimators) µ
b(m) , 0 ≤ m ≤ D, given by
(m)

µ
bi

= 1(i ≤ m)λ−1
i Yi ,

i = 1, . . . , D,

(1.3)

which are ordered with decreasing bias and increasing variance (w.r.t. m).
Choosing a suitable truncation index m
b = m(Y
b ) from the observed data is
the genuine problem of adaptive model selection. Typical methods use (generalized) cross validation, see e.g. Wahba [18], unbiased risk estimation, see
e.g. Cavalier et al. [6], penalized empirical risk minimisation, see e.g. Cavalier and Golubev [7], or Lepski’s balancing principle for inverse problems,
see e.g. Mathé and Pereverzev [14]. They all share the drawback that the
estimators µ
b(m) have first to be computed for all values of 0 ≤ m ≤ D, and
then be compared to each other in some way.
In this work, we are motivated by constraints due to the obstructive
computational complexity of calculating the full SVD in high dimensions.
Since the calculation of the largest singular value and its corresponding subspace is much less costly, efficient numerical algorithms rely on deflation or
2

locking methods, which achieve the desired accuracy for the larger singular values first and then iteratively achieve the accuracy also for the next
smaller singular values, see the monograph by Saad [16] for a nice exposition
and further references. We investigate the possibility of an approach which
is both statistically efficient and sequential along the SVD in the following
sense: we aim at early stopping methods, in which the truncated SVD estimators µ
b(m) for m = 0, 1, . . . , are computed iteratively, a stopping rule
b is used as the estimator.
decides to stop at some step m
b and then µ
b(m)
More generally, we envision our setting as a first simple model to study
the scope of statistical adaptivity using iterative methods, which are widely
used in computational statistics. A notable feature of these methods is that
not only the numerical, but also the statistical complexity (e.g., measured
by the variance) increases with the number of iterations such that early
stopping is essential from both points of view. It is common to use stopping
rules based on monitoring the residuals because the user has access without
substantial additional cost to the residual norm. The properties of such
rules have been well studied for deterministic inverse problems (e.g. the
discrepancy principle, see Engl et al. [10]). In a statistical setting, minimax
optimality of early stopping rules has been established in different settings
under prior smoothness assumptions, see e.g. Yao et al. [19] for gradient
descent learning, Blanchard and Mathé [3] for conjugate gradients, Raskutti
and Wainwright [15] for kernel learning and Bühlmann and Hothorn [4] for
the application to L2 -boosting. So far, however, an analysis of statistical
adaptation in the absence of prior information lacks.

1.2

Non-asymptotic oracle approach

Our approach is mostly non-asymptotic and concentrates on oracle optimality analysis for individual signals. The oracle approach compares the error
b to the minimal error among (b
of µ
b(m)
µ(m) )m for any signal µ individually,
which entails optimal adaptation in minimax settings, see e.g. Cavalier [5].
The risk (mean integrated squared error) for a fixed truncated SVD
estimator µ
b(m) obeys a standard squared bias-variance decomposition
 (m)

2
E kb
µ
− µk2 = Bm
(µ) + Vm ,
where k•k denotes the Euclidean norm in RD and

 P
2
2
Bm
(µ) := E k E[b
µ(m) ] − µk2 = D
i=m+1 µi ,
 (m)

P
−2
Vm := E kb
µ
− E[b
µ(m) ]k2 = δ 2 m
i=1 λi .
3

(1.4)
(1.5)

In distinction with the weak norm quantities defined below, we call Bm (µ)
strong bias of µ and Vm strong variance.
If we have access to the residual squared norm
2 := kY − Ab
Rm
µ(m) k2 = kY k2 − kAb
µ(m) k2 =

PD

i=1 (Yi

(m) 2
) ,

− λi µ
bi

(1.6)

2 − (D − m)δ 2 gives some bias information due to
then Rm
PD
2 2
2 − (D − m)δ 2 ] = B 2 (µ)
2 (µ) :=
E[Rm
with Bm,λ
i=m+1 λi µi .
m,λ
2 (µ) the weak bias and similarly V
2
We call Bm,λ
m,λ = mδ the weak variance.
They correspond to measuring
error in the weak norm (or prediction
PD the
2 v 2 , which usually (always if λ < 1) is
λ
norm) kvk2λ := kAvk2 =
1
i=1 i i
smaller than the strong Euclidean norm k•k.
The
squared
bias-variance
de (m)

2 (µ) + V
composition for the weak risk then reads E kb
µ − µk2λ = Bm,λ
m,λ .
Our setting is thus a particular instance of the question raised by Lepski
[13] whether adaptation in one loss (here: weak norm) leads to adaptation
in another loss (here: strong norm). Our positive answer for truncated SVD
or spectral cut-off estimation will also extend the results by Chernousova et
al. [8].
Intrinsic to the sequential analysis is the fact that at truncation index m
we cannot say anything about the way the bias decreases for larger indices:
it may drop to zero at m + 1 or even stay constant until D − 1. Even if we
knew the exact value of the bias until index m, we could not minimise the
sum of squared bias and variance sequentially. Instead, we should wait until
the squared bias is sufficiently small to equal (approximately) the variance.
This leads to the notion of the strongly balanced oracle
2
ms = ms (µ) := min{m ∈ {0, . . . , D} | Vm ≥ Bm
(µ)},

(1.7)

whose risk is always upper bounded by the classical oracle risk
min0≤m≤D E[kb
µ(m) − µk2 ], up to a factor depending mildly on the spectrum.

1.3

Setting for asymptotic considerations

Risk estimates over classes of signals and asymptotics for vanishing noise
level δ → 0 often help to reveal main features. This way, we can also provide
lower bounds for sequential estimation procedures and compare them directly to classical minimax convergence rates. In our setting, the magnitude
of the discretisation dimension D plays a central role, so that it is sensible

4

to assume in an asymptotic view that D = Dδ → ∞ as δ → 0. As classes of
signals, we will consider the Sobolev-type ellipsoids
P
2β 2
2
H β (R, D) := {µ ∈ RD | D
(1.8)
i=1 i µi ≤ R }, β ≥ 0, R > 0
and we shall use the following polynomial spectral decay assumption
−1 −p
CA
i ≤ λi ≤ CA i−p ,

1 ≤ i ≤ D,

(PSD(p, CA ))

for p ≥ 0, CA ≥ 1. The spectrum is allowed to change with D and δ, but
p, CA are considered as fixed constants. Under these assumptions, standard
computations yield for µ ∈ H β (R, D), 1 ≤ m ≤ D:
−2 2 2p+1
δ m
.
Vm ≤ CA

2
Bm
(µ) ≤ R2 m−2β ;

Balance between these squared bias and variance bounds is obtained for m
of the order of the minimax truncation index
tβ,p,R (δ) := (R−1 δ)−2/(2β+2p+1) ,

(1.9)

provided the condition D ≥ tβ,p,R (δ) holds. This gives rise to the risk rate
R∗β,p,R (δ) := R(R−1 δ)2β/(2β+2p+1) ,
which coincides with the optimal minimax rate in the standard Gaussian
sequence model (i.e. D = ∞). On the other hand, for D . tβ,p,R (δ) the
choice m = D is optimal on H β (R, D) and the rate degenerates to Dδ 2 . This
situation is indicative of an insufficient discretisation and will be excluded
in the asymptotic considerations.

1.4

Overview of results

Our results consist of lower and upper bounds for sequentially adaptive stopping rules. The stopping rules permitted are most conveniently described in
terms of stopping times with respect to an appropriate filtration. Introduce
the frequency filtration


Fm := σ µ
b(1) , . . . , µ
b(m) = σ Y1 , . . . , Ym .
(1.10)
Stopping rules with respect to the filtration F = (Fm )0≤m≤D must decide
whether to halt and output µ
b(m) based only on the information of the first m
estimators. Statistical adaptation will turn out to be essentially impossible
for such stopping rules (Section 2.1). If the residual (1.6) is available at
5

no substantial computational cost, taking this information into account, we
define the residual filtration

2
Gm := Fm ∨ σ(R02 , . . . , Rm
) = Fm ∨ σ kY k2 ,
(1.11)
which is the filtration Fm enlarged by the residuals up to index m, or equivalently by kY k2 only.
Pushing some technical details aside, the main message conveyed by our
lower bounds is that oracle statistical adaptation with respect to the residual
filtration √
is impossible for signals µ such that the strongly balanced oracle
ms (µ) . D (Section 2.2). On the other hand, we establish in Section 3 that
this statement is sharp, in the sense that the simple residual-based stopping
rule

2
τ = min m ≥ m0 | Rm
≤κ ,
(1.12)
with a proper √
choice of κ and m0 is statistically adaptive for signals µ such
that ms (µ) & D.
Finally, in Section 4 we introduce a √
hybrid two-step approach consisting
of the above stopping rule with m0 ∼ D log D, followed by a traditional
(non-sequential) model selection procedure over m ≤ m0 , in the case where
τ = m0 (immediate stop hinting at an optimal index smaller than m0 ).
This procedure enjoys full oracle adaptivity
at a computational cost of cal√
culating on average the first O(max( D log D, ms (µ))) singular values, to
be compared to the full SVD in non-sequential adaptation. Some numerical
simulations illustrate the theoretical analysis. Technical proofs are gathered
in an appendix.

2
2.1

Lower bounds
The frequency filtration

Let τ be an F-stopping time, where F is the frequency filtration defined in
(1.10) and let1
R(µ, τ )2 := Eµ [kb
µ(τ ) − µk2 ].
By Wald’s identity, we obtain the simple formula
 PD

 2

Pτ
−2 2 2
2
R(µ, τ )2 = Eµ
i=τ +1 µi +
i=1 λi δ εi = Eµ Bτ (µ) + Vτ ,

(2.1)

1
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µ .

6

2 (µ) and V
with Bm
m from (1.4), (1.5). This implies in particular that an
oracle stopping time, i.e., an optimal F-stopping time constructed using the
2 (µ) +
knowledge
of µ, coincides with the deterministic oracle argminm Bm

Vm almost surely.

2.1 Proposition. For µ, µ̄ ∈ RD with µi = µ̄i for all i ≤ i0 with some
i0 ∈ {1, . . . , D − 1} any F-stopping rule τ satisfies

R(µ, τ )2 
R(µ̄, τ )2 ≥ Bi20 (µ̄) 1 −
.
Vi0 +1
Suppose R(µ, τ )2 ≤ CR(µ, ms )2 for the balanced oracle ms in (1.7) and
some C ≥ 1. Then for any µ̄ ∈ RD with µ̄i = µi for i ≤ 3Cms we obtain
2
R(µ̄, τ )2 ≥ 31 Bb3Cm
(µ̄).
sc

Proof. We use the fact that (Yi )1≤i≤i0 has the same law under Pµ and Pµ̄
and so has 1(τ ≤ i0 ) by the stopping time property of τ . Moreover, thanks
to the monotonicity of m 7→ Vm , Markov inequality and identity (2.1)
R(µ̄, τ )2 ≥ Eµ̄ [Bτ2 (µ̄)1(τ ≤ i0 )]
= Eµ [Bτ2 (µ̄)1(τ ≤ i0 )]
≥ Bi20 (µ̄)Pµ (τ ≤ i0 )
≥ Bi20 (µ̄)(1 − Pµ (Vτ ≥ Vi0 +1 ))

Eµ [Vτ ] 
≥ Bi20 (µ̄) 1 −
Vi0 +1

R(µ, τ )2 
≥ Bi20 (µ̄) 1 −
.
Vi0 +1
The second assertion follows by inserting i0 = b3Cms c and R(µ, τ )2 ≤
2CVms together with Vms /Vi0 +1 ≤ ms /(i0 + 1) since the singular values λi
are non-increasing.
The last statement clarifies that if the stopping time τ yields a squared
risk comparable to the optimally balanced risk for a given signal µ, then
this signal can be changed arbitrarily to µ̄ after the index b3Cms (µ)c, while
the risk for the rule τ always stays larger than the squared bias of that
part. In Appendix 5.1 we use this proposition to provide a result suitable
for asymptotic interpretation:

7

2.2 Corollary. Assume (PSD(p, CA )) and let τ be any F-stopping rule.
If there exists µ ∈ H β (R, D) with R(µ, τ ) ≤ Cµ R∗β,p,R (δ), then for any
α ∈ [0, β], R̄ ≥ 2R, there exists µ̄ ∈ H α (R̄, D) such that
R(µ̄, τ ) ≥ c1 R̄(R−1 δ)2α/(2β+2p+1) ,
provided D ≥ c2 tβ,p,R (δ). The constants c1 , c2 > 0 only depend on Cµ and
CA .
The conclusion for impossible rate-optimal adaptation is a direct consequence of Corollary 2.2: since for any α < β the rate δ 2α/(2β+2p+1) is
suboptimal, no F-stopping rule can adapt over Sobolev classes with different regularities. 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 β (R, D),
so that the lower bound is in fact a sharp no adaptation result.

2.2

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 5.2.

2.3 Lemma. Let τ = τ (Yi )1≤i≤D ∈ {0, . . . , D} be an arbitrary (measurable) data-dependent index. Then for any m ∈ {1, . . . , D} the following
implication holds true:
Vm ≥ 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. Consider µ ∈ RD
and i0 ∈ {1, . . . , D} such that Vi0 +1 ≥ 200R(µ, τ )2 . Then
R(µ̄, τ )2 ≥ 0.05Bi20 (µ̄)
holds for any µ̄ ∈ RD that satisfies
(a) µi = µ̄i for all i ≤ i0 ,
(b) the weak bias bound |Bi20 ,λ (µ̄) − Bi20 ,λ (µ)| ≤ 0.05
(c) Bi0 ,λ (µ) + Bi0 ,λ (µ̄) ≥ 5.25δ.
8

√

D−i0 2
δ
2

and

Suppose that R(µ, τ )2 ≤ Cµ R(µ, ms )2 holds with some Cµ ≥ 1. Then any
i0 ≥ 400Cµ ms will satisfy the initial requirement.
Proof. First, we lower bound the risk of µ̄ by its bias on {τ ≤ i0 } and then
transfer to the law of τ under Pµ , using the total variation distance on Gi0 :
R(µ̄, τ )2 ≥ Eµ̄ [Bτ2 (µ̄)1(τ ≤ i0 )]
≥ Bi20 (µ̄)Pµ̄ (τ ≤ i0 )

≥ Bi20 (µ̄) Pµ (τ ≤ i0 ) − kPµ − Pµ̄ kT V (Gi0 ) .
By Lemma 2.3 we infer Pµ (τ ≤ i0 ) ≥ 0.1. Denote Wi0 = (Y1 , . . . , Yi0 ). Since
the law of Wi0 is identical under Pµ and Pµ̄ , and Wi0 is independent of
Ri20 for both measures, the total variation distance between Pµ and Pµ̄ on
Gi0 equals the total variation distance between the respective laws of the
scaled residual δ −2 Ri20 . For ϑ ∈ RD , let PϑK be the non-central χ2 -law of
P
2
Xϑ = K
k=1 (ϑk + Zk ) with Zk independent and standard Gaussian. With
−1
K = D − i0 , ϑk = δ λi0 +k µi0 +k , ϑ̄k = δ −1 λi0 +k µ̄i0 +k the total variation
distance between the respective laws of the scaled residual δ −2 Ri20 exactly
equals k PϑK − Pϑ̄K kT V . By Lemma 5.2 in the Appendix, taking account of
kϑk = δ −1 Bi0 ,λ (µ) and similarly for kϑ̄k, we infer from (c) the simplified
bound
2|Bi20 ,λ (µ̄) − Bi20 ,λ (µ)|
√
kPµ − Pµ̄ kT V (Gi0 ) ≤
.
δ 2 D − i0
Under our assumption on µ̄, this is at most 0.05, and the inequality follows.
From R(µ, τ )2 ≤ 2Cµ Vms and Vi0 +1 /Vms ≥ (i0 + 1)/ms , the last statement
follows.
In comparison with the frequency filtration, the main new hypothesis is
that at i0 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 µ√allowed by (b), so that (c) is always satisfied in the interesting
cases where D − i0 is not small.
Considering the behaviour over Sobolev-type ellipsoids, we obtain in Appendix 5.4 a lower bound result comparable to Corollary 2.2 for the frequency filtration.

9

2.5 Corollary. Assume (PSD(p, CA )) and let τ be any G-stopping time.
If there exists µ ∈ H β (R, D) with R(µ, τ ) ≤ Cµ R∗β,p,R (δ), then for any
α ∈ [0, β] and R̄ ≥ 2R, there exists µ̄ ∈ H α (R̄, D) such that


2α/(2α+2p)
, (R−1 δ)2α/(2β+2p+1) ,
R(µ̄, τ ) ≥ c1 R̄ min R̄−1 δD1/4
provided R−1 δ ≤ c2 and D ≥ c3 tα− 1 ,p,R̄ (δ) . The constants c1 , c3 > 0, and
4
c2 ∈ (0, 1] depend only on Cµ , CA , α, p.
The form of the lower bound is transparent: as in the case of the frequency filtration, the sub-obtimal rate R̄(R−1 δ)2α/(2β+2p+1) is attained by a
deterministic rule that stops at the oracle frequency for H β (R, D), whereas
2α/(2α+2p)
R̄ R̄−1 δD1/4
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 δD1/4 , which is exactly the critical signal strength in nonparametric testing, see Ingster and Suslina [11],
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.
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. In this setting, a stopping rule τ is to be understood as a
family of stopping rules that depend on the knowledge of D and δ.
2.6 Corollary. Assume (PSD(p, CA )). Let β+ > β− ≥ 0, R+ , R− > 0.
Suppose that there exists a G-stopping rule τ such that R(µ, τ ) ≤ CR∗β,p,R (δ)
holds for some C > 0, all δ > 0 small enough, and for every µ ∈ H β (R, Dδ ),
simultaneously for (β, R) ∈ {(β− , R− ), (β+ , R+ )}.
√ Then the rate-optimal
β
−
truncation index for H (R− , Dδ ) must satisfy Dδ = O(tβ− ,p,R− (δ)) as
δ → 0 (all other parameters being fixed).
In particular, if a G-stopping rule τ is rate-optimal over H β (R, Dδ ) for
β ∈ [βmin , βmax ], βmax > βmin ≥ 0, and some R > 0, then we necessarily
δ −2
must have βmax ≤ lim inf δ→0 log
log Dδ − p − 1/2.
Proof. In this proof we denote by ’.’, ’&’ inequalities holding up to factors
depending on CA , p, β+ , β− , R− , R+ . We apply Corollary 2.5 with β = β+ ,
α = β− and R̄ = R− , R = min(R+ , R̄/2). Because of δ −2/(2β− +2p+1/2) ≤
δ −4/(2β− +2p+1) = o(Dδ ), the conditions are fulfilled for sufficiently small
δ > 0 and we conclude (R+ , R− are fixed)


1/4 2β− /(2β− +2p)
∃µ̄ ∈ H β− (R− , D) : R(µ̄, τ ) & min δDδ
, δ 2β− /(2β+ +2p+1) .
10

By assumption, that rate must be O(δ 2β− /(2β− +2p+1) ). Since the second term in the above minimum is of larger order than this, this
√
1/4
must imply (δDδ )2β− /(2β− +2p) . δ 2β− /(2β− +2p+1) , and further Dδ .
δ −2/(2β− +2p+1) . tβ− ,p,R− (δ). The first statement is proved.
For the second assertion, we proceed by contradiction and assume
δ −2
βmax and
βmax > βlim := lim inf δ→0 log
log Dδ − p − 1/2. Choose β+ = p
β− ∈ (βlim , βmax ). Then β− > βlim implies tβ− ,p,R− (δk ) = o( Dδk ) for
some sequence δk → 0, contradicting the first part of the corollary.
For statistical inverse problems with singular values satisfying the polynomial decay (PSD(p, CA )) we may choose the maximal dimension Dδ ∼
δ −2/(2p+1) without losing in the convergence rate for a Sobolev ellipsoid of
any regularity β ≥ 0, see e.g. Cohen el al. [9]. In fact, we then have the
variance
Dδ
X
2 2p+1
∼ 1,
(2.2)
VDδ = δ 2
λ−2
i ∼ δ Dδ
i=1

and the estimator with truncation at the order of Dδ will not be consistent anyway; the oracle index is always of order o(Dδ ) whatever the signal
regularity. For this choice of Dδ , optimal adaptation is only possible if the
squared minimax rate is within the interval [δ, 1], faster adaptive rates up
to δ 2 cannot be attained.
Usually, Dδ will be chosen much smaller, assuming some minimal a priori
regularity βmin . The choice Dδ ∼ δ −2/(2βmin +2p+1) 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 + 1/2 (keeping
the radius R of the Sobolev ball fixed). These adaptation intervals, however, are fundamentally understood only when inspecting the corresponding
rate-optimal
truncation indices tβ,p,R (δ), which must at least be of order
√
Dδ ∼ δ −1/(2βmin +2p+1) in order to distinguish a signal in the residual from
the pure noise case.

3

Upper bounds


2 ≤ κ from
Consider the residual-based stopping rule τ = min m ≥ m0 | Rm
2
2
(1.12). Since Rm is decreasing with RD = 0, the minimum is attained and
we have Rτ2 ≤ κ.

11

In order to have clearer oracle inequalities, let us introduce a continuous
oracle-proxy index t∗ ∈ [m0 , D] via
t∗ = inf{t ≥ m0 | Eµ [Rt2 ] ≤ κ}

p
2 2 P
with Rt2 = 1− t − btc Ydte
+ i=dte+1 Yi2 .

Then by continuity E[Rt2∗ ] = κ holds in the case t∗ > m0 . The oracle-proxy
∗
estimator is consistently given by µ
b(t ) where for real t ∈ [0, D],


p
(t)
i = 1, . . . , D.
µ
bi := 1(i ≤ btc) + t − btc1(i = dte) λ−1
i Yi ,
We also define for t ∈ [0, D]:
p
2
P
2
Bt2 = 1 − t − btc µ2dte + D
i=dte+1 µi ,
2 Pbtc −2
Vt = (t − btc)δ 2 λ−2
i=1 λi ,
dte + δ
2
2 Pbtc −2 2
St = (t − btc)δ 2 λ−2
i=1 λi εi .
dte εdte + δ
We thus obtain the following decompositions in a bias and a stochastic error
term:
p

kb
µ(t) − µk2 = Bt2 (µ) + St + 2 t − btc − t − btc λ−1
(3.1)
dte µi εi ,
 (t)





E kb
µ − µk2 = Bt2 (µ) + Vt , E kb
µ(τ ) − µk2 = E Bτ2 (µ) + Sτ , (3.2)
noting that the last term in (3.1) has expectation zero for deterministic t
and vanishes for the integer-valued random time τ . Analogously, the linear
interpolations for bias and variance in weak norm are defined.
Let us define the weakly and strongly balanced oracles tw and ts in a
continuous manner:
2
tw = tw (µ) = inf{t ≥ m0 | Bt,λ
(µ) ≤ Vt,λ } ∈ [m0 , D],

ts = ts (µ) = inf{t ≥ m0 | Bt2 (µ) ≤ Vt } ∈ [m0 , D].
While the balanced oracles are the natural oracle quantities we try to mimic
by early stopping, they should be compared to the classical oracles. Since
t 7→ Bt2 (µ) is decreasing and t 7→ Vt is increasing, we derive
 (t)

 (ts )

inf E kb
µ − µk2 ≥ inf max(Bt2 (µ), Vt ) ≥ Vts ≥ 21 E kb
µ − µk2 ,
t∈[m0 ,D]

t∈[m0 ,D]

(3.3)
noting Bt2s (µ) = Vts for ts > m0 , and inf t∈[m0 ,D] Vt ≥ Vts ≥ Bt2s (µ) in case
ts = m0 .
12

3.1

Upper bounds in weak norm

3.1 Proposition. The balanced oracle inequality in weak norm
 (τ )
 √
∗
E kb
µ −µ
b(t ) k2λ ≤ 2Dδ 2 + 2δBt∗ ,λ (µ) + ∆τ (µ)2

(3.4)

holds with the discretisation error
q
√
∆τ (µ) = max |λi µi | + 4δ log( 2D).
i≥dt∗ e

Proof. The main (completely deterministic) argument p
uses consecutively the
∗
∗
definition of the weak norm, t − bt c ≤ 1 − (1 − t∗ − bt∗ c)2 and the
2
2
∗
2
2
bounds R(τ
−1)∨bt∗ c ≥ κ ≥ E[Rt∗ ] for τ > t ≥ m0 and Rτ ≤ κ = E[Rt∗ ] for
∗
t > τ ≥ m0 :
∗

kb
µ(t ) − µ
b(τ ) k2λ
D 
2
X
p
=
1(i ≤ bt∗ c) + t∗ − bt∗ c1(i = dt∗ e) − 1(i ≤ τ ) Yi2
≤
≤

i=1
(Rt2∗ − Rτ2 )1(τ > t∗ ) + (Rτ2 − Rt2∗ )1(τ < t∗ )
2
2
∗
|Rt2∗ − E[Rt2∗ ]| + (R(τ
−1)∨bt∗ c − Rτ )1(τ > t )
D
X

≤

γi δ 2 (ε2i − 1) + 2λi µi δεi

i=dt∗ e



+ max Yi2
i≥dt∗ e

p
2
with γi = 1 for i > dt∗ e and γi = (1− t∗ − bt∗ c for i = dt∗ e. The maximal
inequality in Corollary 1.3 of [17] implies
q
2
h
i 
√
E max Yi2 ≤ max |λi µi | + 4δ log( 2(D − dt∗ e + 1)) ≤ ∆τ (µ)2 .
i≥dt∗ e

i≥dt∗ e

By bounding the variance of the main term (applying the Cauchy-Schwarz
inequality), using Var(ε2i ) = 2, Cov(ε2i , εi ) = 0, this gives
1/2
 (t∗ )
 
+ ∆τ (µ)2
Eµ kb
µ
−µ
b(τ ) k2λ ≤ 2(D − t∗ )δ 4 + 4δ 2 Bt2∗ ,λ (µ)
and thus by

√

A+B ≤

√

A+

√

B, A, B ≥ 0, the asserted inequality.

So far, it is not clear for which values of κ the oracle proxy t∗ yields good
results. For t∗ > m0 ,
κ = E[Rt2∗ ] = Bt2∗ ,λ (µ) + (D − t∗ )δ 2 = Dδ 2 + Bt2∗ ,λ (µ) − Vt∗ ,λ
13

(3.5)

implies that the choice κ = Dδ 2 balances weak squared bias and variance
exactly such that t∗ = tw . In practice, however, we might have to estimate
the noise level δ 2 , or prefer a larger threshold κ to reduce numerical complexity. Therefore, precise bounds for general κ between the oracle-proxy
and the weakly balanced errors in weak norm are useful.
3.2 Lemma. We have
(Bt2∗ ,λ (µ) − Bt2w ,λ (µ))+ ≤ (κ − Dδ 2 )+ ,
so that

(Vt∗ ,λ − Vtw ,λ )+ ≤ (Dδ 2 − κ)+ ,

∗

µ(tw ) − µk2λ ] + |κ − Dδ 2 |.
E[kb
µ(t ) − µk2λ ] ≤ E[kb
Proof. Suppose tw > t∗ ≥ m0 . Then Vt∗ ,λ < Vtw ,λ and from κ ≥ E[Rt2∗ ] =
Bt2∗ ,λ (µ) + Dδ 2 − Vt∗ ,λ , Vtw ,λ = Bt2w ,λ (µ) we deduce
Bt2∗ ,λ (µ) ≤ Vt∗ ,λ + κ − Dδ 2 < Vtw ,λ + κ − Dδ 2 = Bt2w ,λ (µ) + κ − Dδ 2 .
Conversely, for t∗ > tw ≥ m0 we have Bt2∗ ,λ (µ) ≤ Bt2w ,λ (µ) as well as κ =
E[Rt2∗ ] = Bt2∗ ,λ (µ) + Dδ 2 − Vt∗ ,λ and Vtw ,λ ≥ Bt2w ,λ (µ), so that
Vt∗ ,λ = Bt2∗ ,λ (µ) − κ + Dδ 2 ≤ Bt2w ,λ (µ) − κ + Dδ 2 ≤ Vtw ,λ − κ + Dδ 2 .
This gives the result.
(t∗

Remark that the weak variance control of Lemma 3.2 implies directly
2
− tw )+ ≤ (D − κδ −2 )+ . From the inequalities Bt2 (µ) ≥ λ−2
btc Bt,λ (µ) and

Vt ≤ λ−2
btc Vt,λ we infer further tw ≤ ts such that always
t∗ − (D − κδ −2 )+ ≤ tw ≤ ts .

(3.6)

As a consequence of the preceding two results, we √
obtain directly a weakly
balanced oracle inequality with error terms of order Dδ 2 , provided |κ−Dδ|2
is at most of that order:
3.3 Theorem. We have
 

 (τ )


E kb
µ − µk2λ ≤ C E kb
µ(tw ) − µk2λ + |κ − Dδ 2 |


 (t)

≤ C 2 min E kb
µ − µk2λ + |κ − Dδ 2 |
t∈[m0 ,D]

holds with a numerical constant C > 0.
14

Proof. For the first bound use
 (τ )

 (tw )

 (τ )

E kb
µ − µk2λ ≤ 2 E kb
µ
− µk2λ + 2 E kb
µ −µ
b(tw ) k2λ
and apply Proposition 3.1 and Lemma
2δBt∗ ,λ (µ) ≤
√ 2 3.2 2with the estimates
2
2
2
2
2
δ +Bt∗ ,λ (µ), ∆τ (µ) . Bt∗ ,λ (µ)+ Dδ , Bt∗ ,λ (µ) ≤ Btw ,λ (µ)+|κ−Dδ 2 | (’.’
denotes an inequality up to a numerical factor). The second bound follows
exactly as (3.3).
In weak norm, we have thus obtained a completely general oracle inequality for our early
√ stopping rule. In view of the lower bounds, the ”residual
term” of order Dδ 2 , which is much larger than the usual parametric order
δ 2 , is unavoidable. This will be developed further in the strong norm error
analysis.

3.2

Upper bounds in strong norm

2 ≤ κ), m < t∗ , in
In Appendix 5.5 we derive exponential bounds for P (Rm
terms of the weak bias and deduce by partial summation the following weak
bias deviation inequality:

3.4 Proposition. We have
√
 2


E (Bτ,λ
(µ) − Bt2∗ ,λ (µ))+ ≤ 17 D + 64 δ 2 + Bt2∗ ,λ (µ)D−1/2 .
This is the probabilistic basis for the main bias oracle inequality.
3.5 Proposition. We have the balanced oracle inequality for the strong bias


√
2
−2
t
+
δ
E[(Bτ2 (µ) − Bt2s (µ))+ ] ≤ 81λ−2
D
+
(κδ
−
D)
.
+
s
dts e
Proof. On the event {τ ≥ ts } we have Bτ2 (µ) ≤ Bt2s (µ). On {τ < ts } we have
2
2
Bτ2 (µ) − Bt2s (µ) ≤ λ−2
dts e (Bτ,λ (µ) − Bts ,λ (µ)),

using the fact that only coefficients up to index dts e enter into the bias
differences. From the weak bias control given by Proposition 3.4 it follows
that
E[(Bτ2 (µ) − Bt2s (µ))+ ]


2
2
2
2
≤ λ−2
E[(B
(µ)
−
B
(µ))
]
+
(B
(µ)
−
B
(µ))
+
+
τ,λ
t∗ ,λ
t∗ ,λ
ts ,λ
dts e
 √

2
−1/2
)Bt2∗ ,λ (µ)
≤ λ−2
dts e (17 D + 64)δ + (1 + D
15

 √

2
∗
−2
≤ λ−2
δ
81
D
+
2(t
+
κδ
−
D)
,
dts e
where in the last line we used κ ≥ E[Rt2∗ ] = Bt2∗ ,λ (µ) + Dδ 2 − Vt∗ ,λ and
Vt∗ ,λ = t∗ δ 2 . By (3.6) we see t∗ ≤ ts +(D−κδ −2 )+ and the result follows.
To assess the size of the bias bound, let us assume the polynomial decay
(PSD(p, CA )). Then a Riemann sum approximation yields for any t ∈ [1, D]
δ

−2

Vt =

btc
X

λ−2
i

+ (t −

btc)λ−2
dte

≥

−2
CA

i=1

Z
0

t

−2
x2p dx = CA
(2p + 1)−1 t2p+1 .

2
2p+1 ≤ C 2 (2t)2p+1 , we thus obtain
Noting tλ−2
A
dte ≤ CA dte
2
2p+1 4
λ−2
CA Vt .
dte tδ ≤ (1 + 2p)2

(3.7)

Consequently, we can estimate E[(Bτ2 (µ) − Bt2s (µ))+ ] . Vts in the case ts &
√
max( D, κδ −2 − D).
Let us see by a counterexample that (Bt2∗ (µ) − Bt2s (µ))+ can be of the
same order as the strongly balanced risk itself, meaning that the bound of
Proposition 3.5 is not too pessimistic in general. Suppose κ = Dδ 2 (such
that t∗ = tw ), µD 6= 0 and δ, D such that ts = D − 3/4. This gives µ2D /4 =
2
Bt2s (µ) = Vts . In weak norm we have BD−1,λ
(µ) = λ2D µ2D , VD−1,λ = δ 2 (D−1)
and consequently tw ≤ D − 1 if λ2D µ2D ≤ δ 2 (D − 1). In that case, Bt2∗ (µ) ≥
µ2D = 4Bt2s (µ) holds and we must indeed pay a positive factor for using the
weak oracle in strong norm. We can meet the bound λ2D µ2D ≤ δ 2 (D − 1)
PD−1 −2
under the constraint µ2D /4 = VD−3/4 = δ 2 (λ−2
i=1 λi ) for instance
D /4 +
−p
for λi = i with p > 3/2 and D sufficiently large.
For the stochastic error we use in Appendix 5.6 exponential inequalities
2
for P (Rm−1
> κ), m > t∗ , to obtain the following bound:
3.6 Proposition. We have the oracle-proxy inequality for the strong norm
stochastic error
2

E[(Sτ − St∗ )+ ] ≤ rV,τ δ with rV,τ

D
 √ X

(m−1−t∗ )2
+
−2 − 16D+32κδ−2
:= min 2 3
λm e
,D .
m=dt∗ e

If the polynomial decay condition (PSD(p, CA )) is satisfied, then


 √D D(p+1/2)∧1  V ∗
√
t
2
∗ 2p
p+1/2
0 4
rV,τ ≤ Cp CA (t )
D+D
+
∧ D ≤ Cp CA
t∗
(t∗ )2p+1
δ2
(3.8)
0
holds with constants Cp , Cp , only depending on p.
16

3.7 Corollary. We have the balanced oracle inequality for the stochastic
error


−2
2
E[(Sτ − Sts )+ ] ≤ rV,τ + λ−2
(D
−
κδ
)
+ δ .
dt∗ e
Proof. By the monotonicity of St and Vt in t we bound
E[(Sτ −Sts )+ ] ≤ E[(Sτ −St∗ )+ ]+E[(St∗ −Sts )+ ] = E[(Sτ −St∗ )+ ]+(Vt∗ −Vts )+ .
2
In view of Proposition 3.6 it suffices to prove (Vt∗ − Vts )+ ≤ λ−2
dt∗ e (Dδ − κ)+ .
∗
By definition of the variances, (Vt∗ − Vtw )+ ≤ λ−2
dt∗ e (Vt ,λ − Vtw ,λ )+ holds. We
apply Lemma 3.2 and note Vtw ≤ Vts by (3.6) to conclude.

Everything is prepared to prove our main strong norm result.
√
3.8 Theorem. Assume |κ − Dδ 2 | ≤ Cκ Dδ 2 . Then the following balanced
oracle inequality holds in strong norm
 (τ )

 (ts )

E kb
µ − µk2 ≤ E kb
µ − µk2


√ 
√
+ 81λ−2
ts + (1 + Cκ ) D + rV,τ δ 2 .
dts +Cκ De

If in addition the polynomial decay condition (PSD(p, CA )) is satisfied, then
there is a constant C > 0, only depending on p, CA , Cκ , so that
 (τ )

 (ts ∨√D)

E kb
µ − µk2 ≤ C E kb
µ
− µk2 .
(3.9)
Proof. By (3.2) we have
i
h
h

 i
E kb
µ(τ ) − µk2 − kb
µ(ts ) − µk2 ≤ E Bτ2 (µ) − Bt2s (µ) + + Sτ − Sts + .
Combining Proposition 3.5 and Corollary 3.7 we thus obtain
 (τ )

 (ts )

E kb
µ − µk2 ≤ E kb
µ − µk2 ,
√

2
−2
+ 81λ−2
δ
t
+
D
+
|κδ
−
D|
+ rV,τ δ 2 .
s
?
dts ∨t e
By (3.6) we have t∗ ≤ ts + (D − κδ −2 )+ and the first inequality
follows.
√
∗
Under (PSD(p, CA )) we use (3.8) and t ≤ ts + Cκ D to further bound
√
rV,τ . t2p
D + Dp+1/2
s
with a factor depending on p, CA , Cκ . Finally, note
√

E[kb
µ(ts ) − µk2 ] ≤ 2Vts ≤ 2Vts ∨√D ≤ 2 E[kb
µ(ts ∨ D) − µk2 ]
√ 2p+1 2
Vts ∨√D ∼ (ts ∨ D)
δ
√
√
and apply λ−2
. (ts ∨ D)2p to deduce the second bound.
dts +Cκ De

17

Let us derive from Theorem 3.8 an asymptotic minimax upper bound
over the Sobolev-type ellipsoids
H β (R, D), matching the lower bound of
√
Corollary 2.6. For m0 = d De the bound (3.9) gives
 (τ )

 (ts )

E kb
µ − µk2 ≤ C E kb
µ − µk2
√
because of ts ≥ m0 ≥ D. Now, ts (µ) . tβ,p,R (δ) holds for µ ∈ H β (R, D)
and E[kb
µ(ts ) − µk2 ] . R∗β,p,R (δ) is true for tβ,p,R (δ) ∈ [m0 , D] as in (3.6) so
that we obtain the following adaptive upper bound:
√ 2
2| ≤ C
3.9 Corollary.
Assume
(PSD(p,
C
)),
|κ
−
Dδ
Dδ and choose
κ
A
√
m0 = d De. Then there is a constant C > 0,√depending only on p, CA and
Cκ , such that for all (β, R) with tβ,p,R (δ) ∈ [ D, D]
sup
µ∈H β (R,D)

4
4.1

 (τ )

Eµ kb
µ − µk2 ≤ CR∗β,p,R (δ).

An adaptive two-step procedure
Construction and results

The lower bounds show that, in general, there is no hope for an early stopping rule attaining the order
√of the oracle risk if the strongly balanced oracle
ts is of smaller order than
D. We can therefore always start the stopping
√
rule τ at some m0 & D. If, however, immediate stopping τ = m0 occurs,
we might have stopped too late in the sense that ts  m0 . To avoid this overfitting, we propose to run a second model selection step on {b
µ(0) , . . . , µ
b(m0 ) }
in the event τ = m0 .
Below, we shall formalise this procedure and prove that this combined
model selection indeed achieves adaptivity, that is, its risk is controlled by an
oracle inequality. While violating the initial stopping rule prescription, we
still gain substantially in terms of numerical complexity. At the heart of this
twofold model selection procedure is a simple observation of independence.
4.1 Lemma. The stopping rule τ is independent of the estimators
µ
b(0) , . . . µ
b(m0 ) .
Proof. By construction, τ is measurable with respect to the σ-algebra
2 , . . . , R2 ) = σ(Y 2
2
σ(Rm
b(m) is σ(Y1 , . . . , Ym )-measurable.
m0 +1 , . . . , YD ) and µ
D
0
By the independence of (Y1 , . . . , Ym0 ) and (Ym0 +1 , . . . , YD ) the claim follows.

18

For the second step, we suppose that m
b ∈ {0, . . . , m0 } is obtained from
any model selection procedure among {b
µ(0) , . . . , µ
b(m0 ) } that satisfies with a
constant C2 ≥ 1, for any signal µ, the oracle inequality


b
E[kb
µ(m)
− µk2 ] ≤ C2
min
E[kb
µ(m) − µk2 ] + δ 2 .
(4.1)
m∈{0,...,m0 }

Such an oracle inequality holds for standard procedures, for instance the
AIC-criterion
m
b ∈ argminm∈{0,...,m0 }



−

m
X
i=1

2
λ−2
i Yi

+ 2δ

2

m
X


λ−2
.
i

i=1

We refer to Section 2.3 in Cavalier and Golubev [7] for the corresponding
result and further discussion. If we are interested in a weak norm oracle
inequality, the AIC-criterion
takes the weak empirical risk and reduces to the
P
2 + 2mδ 2 , which is classical. Based on the lemma
Y
minimisation of − m
i=1 i
and the tools developed in the previous section, we prove in Appendix 5.7
the following oracle inequality in an asymptotic setting.
√ 2
2| ≤ C
Dδ
4.2 Proposition. Assume
D
≥
3,
(PSD(p,
C
)),
|κ
−
Dδ
κ
A
√
and set m0 = d128 log(D) De. Suppose the model selector m
b satisfies (4.1)
with C2 ≥ 1. Then there is a constant C > 0, depending only on p, CA , Cκ
and C2 , such that uniformly over all signals µ the estimator
(
b ,
µ
b(m)
if τ = m0 ,
(ρ)
µ
b =
(τ
)
µ
b ,
if τ > m0
satisfies

 (ρ)

E kb
µ − µk2 ≤ C

4.2

min
m∈{0,...,D}


 (m)

E kb
µ
− µk2 + δ 2 .

Numerical illustration

Let us exemplify the procedure by some Monte Carlo results. As a test bed
we take the moderately ill-posed case λi = i−1/2 with noise level δ = 0.01 and
dimension D = 10 000. We consider early stopping at τ with κ = Dδ 2 = 1.
In Figure 1 (left), we see the SVD representation of three signals: a
very smooth signal µ(1), a relatively smooth signal µ(2) and a rough signal µ(3), the attributes coming from the interpretation via the decay of
Fourier coefficients. The corresponding weakly balanced oracle indices tw are
19

Figure 1: Left: SVD representation of a super-smooth (blue), a smooth (red)
and a rough (olive) signal. Right: Relative efficiency for early stopping with
m0 = 0.
(34, 316, 1356). The classical oracle indices in strong norm are (43, 504, 1331).
Figure 1 (right) shows box-plots of the relative efficiency of early stopping in
1000 Monte Carlo replications defined as minm E[kb
µ(m) − µk2 ]1/2 /kb
µ(τ ) − µk,
both for strong and weak norm. Ideally, the relative efficiency should concentrate around one. This is well achieved for the smooth and rough signals.
The super-smooth case with its very small oracle risk suffers from the variability within the residual and attains on average an efficiency of about 0.5,
meaning that its root mean squared error is about twice as large as the
oracle error.
This leads us to consider the two-step procedure. According to√Proposition 4.2 we have to choose an initial index somewhat larger than D. The
factor in the choice there is very conservative due to non-tight concentration
bounds. For the implementation we choose m0 such that for a zero signal
2 > κ} is about 0.01, when apµ = 0 the probability of {τ > m0 } = {Rm
0
√
plying a normal approximation, that is m0 = dq0.99 2De = 329 with the
99%-percentile q0.99 of N (0, 1). In Figure 2(left) we see that with this choice
for the super-smooth signal, 6 out of 1 000 MC realisations lead to τ > m0 ,
for the others we apply the second model selection step. The truncation for
the smooth signal varies around m0 , and the second step is applied to about
50% of the realisations. In the rough case, τ > m0 was always satisfied and
no second model selection step was applied.
As model selection procedure we apply the AIC-criterion, based on the
weak and strong empirical norm for the weak and strong norm criterion,
respectively. The results are shown in Figure 2(right). We see that the efficiency for the super-smooth signal improves significantly (with the 6 outliers

20

Figure 2: Left: truncation levels for √
early stopping with m0 = 0 and the
two-step procedures with m0 = dq0.99 2De = 329, AIC in weak and strong
norm. Right: Relative efficiencies for the two-step procedure.
not being affected). The variability is still considerably higher than for the
other two signals. This phenomenon is well known for unbiased risk estimation. Especially for more strongly ill-posed problems, one should penalise
stronger, see the comparison with the risk hull approach in Cavalier and
Golubev [7]. Here let us rather emphasize that a pure AIC-minimisation for
the super-smooth signal gives exactly the same result, apart from the 6 outliers, but requires to calculate the AIC-criterion for D = 10 000 indices in
1 000 MC iterations. The two-step procedure, even for known SVD, is about
30 times faster.

5
5.1

Appendix
Proof of Corollary 2.2

Proof. For i0 = b(2Cµ2 CA )1/(2p+1) (R−1 δ)−2/(2β+2p+1) c, we can choose c2 (in
dependence of Cµ , CA ) big enough so that our assumptions imply i0 ≤ D
and
!1+2p
R(µ, τ )2
(R−1 δ)−2/(2β+2p+1)
1
2
1−
≥ 1 − Cµ CA
≥ .
Vi0 +1
i0 + 1
2
Put µ̄i = µi for i 6= i0 + 1 and µ̄i0 +1 = 21 R̄(i0 + 1)−α . Then µ̄ ∈ H α (R̄, D)
follows from µ ∈ H β (R, D) ⊆ H α (R, D) and R̄ ≥ 2R. The bias bound
Bi20 (µ̄) ≥ 41 R̄2 (i0 + 1)−2α inserted in Proposition 2.1 yields the result.

21

5.2

Proof of Lemma 2.3

To prove this lemma we first recall a result on the concentration of weighted
chi-squared type random variables.
5.1 Lemma (Laurent and Massart, Lemma 1 in [12]). Let (ε1 , . . . , εD ) be
2
i.i.d.
PD N2(0, 1) variables. For nonnegative numbers a1 , . . . , aD , recall kak =
i=1 ai and denote kak∞ = max1≤i≤D ai . Set
k
X

Z = max

1≤k≤D

ai (ε2i − 1).

i=1

Then the following inequalities hold for any x > 0:
√
P Z > 2kak x + 2kak∞ x) < e−x ,
√ 
P Z < −2kak x < e−x

(5.1)
(5.2)

and also

 1 x2 
 1

x2
,
P
Z
<
−x
<
exp
−
.
P Z > x) < exp −
4 kak2 + kak∞ x
4 kak2
Lemma 5.1 is stated in a slightly more general setting, since the original
result of Laurent and Massart [12], based itself on Lemma 8 in Birgé and
Massart [1], has no maximum in k for the definition of Z. The proof, however,
is based on the classical Chernov bound argument, which readily carries over
with a maximum: indeed, for t ≥ 0 and λ > 0,


Pk
 PD

2
2
P (Z ≥ t) = P max eλ i=1 ai (εi −1) ≥ eλt ≤ e−λt E eλ i=1 ai (εi −1)
1≤k≤D

by P Doob’s maximal
k
2
(eλ i=1 ai (εi −1) )1≤k≤D .

inequality

Proof of Lemma 2.3. With Sm = δ 2

applied
−2 2
i=1 λi εi

Pm

to

the

submartingale

we obtain

τ
h X
i
h
i
2
R(µ, τ )2 ≥ E δ 2
λ−2
ε
≥
E
1(τ
≥
m)S
.
m
i
i
i=1

√
−2
Insert a = δ 2 (λ−2
1 , . . . , λm ) and x := log(5/4) in (5.2) so that 2 x ≤ 0.95.
Then with probability larger than 1 − e−x = 0.2, it holds that
Sm

m

δ 2 X −2 Vm
≥ E [Sm ] − 2kak x ≥
λi =
,
20
20
√

i=1

22

P
where we used kak ≤ m
i=1 ai = E [Sm ] = Vm (observe that we could tighten
the latter inequality significantly under some additional assumptions on the
singular value decay). We now have
R(µ, τ )2 ≥ E [1(τ ≥ m)Sm ]
≥ Vm P ({τ ≥ m} ∩ {Sm ≥ Vm /20})/20

≥ Vm 1 − P (τ < m) − P (Sm < Vm /20) /20

≥ Vm 0.2 − P (τ < m) /20.
We deduce from this that Vm ≥ 200R(µ, τ )2 implies P (τ ≥ m) ≤ 0.9.

A total variation bound for non-central χ2 -laws

5.3

5.2 Lemma.PLet ϑ = (ϑ1 , . . . , ϑK ) ∈ RK and PϑK be the non-central χ2 2
law of Xϑ = K
k=1 (ϑk + Zk ) with Zk independent and standard Gaussian.
K
Then, for ϑ, ϑ̄ ∈ R we have
p
|kϑk2 − kϑ̄k2 | + 8/π|kϑk − kϑ̄k|
ϑ
ϑ̄
√
kPK − PK kT V ≤ e
,
πK
√

For kϑk + kϑ̄k ≥

8e
√
2π− πe

≈ 5.248 this bound simplifies to

kPϑK − Pϑ̄K kT V ≤ 2

|kϑk2 − kϑ̄k2 |
√
.
K

Proof. Writing ϑ = (ϑk ), Z = (Zk ) ∈ Rk we see by orthogonal transformation that Xϑ = kϑk2 + 2hϑ, Zi + kZk2 equals in law Xϑ0 = kϑk2 + 2kϑkZ10 +
0 ∼ N (0, 1) i.i.d. We can therefore first consider the
kZ 0 k2 with Z10 , . . . , ZK
conditional law QϑK (z) of PϑK given {Z10 = z}, which is nothing but the
χ2 (K − 1)-distribution translated by kϑk2 + 2kϑkz + z 2 .
If fp denotes the χ2 (p)-density, then we have for any t > 0 that fp (x−t) >
t
fp (x) holds iff x ≥ xt = 1−e−t/(p−2)
. Thus, we obtain
Z

∞

|fp (x − t) − fp (x)| dx
0

23

Z

∞


fp (x − t) − fp (x) + dx
0
Z ∞
1−p/2

2
=
(1 − t/x)p/2−1 et/2 − 1 xp/2−1 e−x/2 dx
Γ(p/2) xt
Z
21−p/2 xt (p−2)/2 −x/2
x
e
dx
=
Γ(p/2) xt −t
=2

≤

2(2−p)/2
t(p − 2)(p−2)/2 e−(p−2)/2 ,
Γ(p/2)

knowingpthat x = p − 2 is the mode of fp . 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
kQϑK (z) − Qϑ̄K (z)kT V ≤ e(πK)−1/2 kϑk2 − kϑ̄k2 + 2(kϑk − kϑ̄k)z .
Taking expectation with respect to Z10 ∼ N (0, 1) we conclude


kPϑK − Pϑ̄K kT V ≤ e(πK)−1/2 kϑk − kϑ̄k E kϑk + kϑ̄k + 2Z10 .
Using the triangle inequality and E[|Z10 |] =

5.4

p

2/π, the upper bound follows.

Proof of Corollary 2.5

Proof. Set µ̄i = µi for i 6= i0 +1 and µ̄2i0 +1 = µ2i0 +1 + 14 R̄2 (i0 +1)−2α for some
i0 ∈ {1, . . . , D}, so that µ̄ ∈ H α (R̄, D) and condition (a) of Proposition 2.4
is satisfied. If
p
C2
(b’): 4A R̄2 (i0 + 1)−2(α+p) ≤ 0.025δ 2 D − i0
holds, then condition (b) of Proposition 2.4 is ensured, whereas
2
(c’): R̄2 (i0 + 1)−2(α+p) ≥ 2CA
5.252 δ 2

implies condition (c) of Proposition 2.4. Finally, for
2 2 1/(2p+1)
(d’): i0 ≥ b(200(1 + 2p)CA
Cµ )
(R2 δ −2 )1/(2β+2p+1) c,

we have Vi0 +1 ≥ 200R(µ, τ )2 . Hence, by Proposition 2.4, (b’)-(c’)-(d’) imply
R(µ̄, τ )2 ≥ 0.05Bi20 (µ̄) ≥
24

0.05 2
4 R̄ (i0

+ 1)−2α .

√


For i0 = C0 max (R̄2 δ −2 / D)1/(2α+2p) , (R2 δ −2 )1/(2β+2p+1) with some
suitably large constant C0 > 0, depending only on Cµ , CA , p, and for
D ≥ 2i0 , conditions (b’) and (d’) are satisfied. To check condition (c’), a suf2 ))1/(2α+2p) . The first term in the
ficient condition is i0 + 1 ≤ (R̄2 δ −2 /(56CA
maximum defining i0 satisfies this condition (here again using D ≥ 2i0 ) provided R−1 δ is smaller than a suitable constant c02 depending on CA , Cµ , α, p.
The second term in the maximum defining i0 satisfies the sufficient condition
2 1/(2α+2p)
C0 (R2 δ −2 )1/(2β+2p+1) ≤ C0 (R̄2 δ −2 )1/(2α+2p+1) ≤ (R̄2 δ −2 /(56CA
))
,

again as soon as R−1 δ is smaller than a suitable constant c002 depending on the
same parameters as c02 . Finally, putting c2 = min(c02 , c002 , 1) and unwrapping
the condition D ≥ 2i0 , yields (using Rδ −1 ≥ 1) the sufficient condition
D ≥ c03 (R̄2 δ −2 )1/(2α+2p+1/2) , which is equivalent to the assumption D ≥
c3 tα− 1 ,p,R̄ (δ) postulated in the statement, for suitable c03 , c3 depending on
4
Cµ , CA , α, p. This yields the result.

5.5

Proof of Proposition 3.4

2 (µ) > B 2 (µ) ⇒ τ ≤ bt∗ c by partial summaProof. We deduce from Bτ,λ
t∗ ,λ
tion
∗

2
(µ) − Bt2∗ ,λ (µ))+ ] =
E[(Bτ,λ

bt c
X

2
(µ) − Bt2∗ ,λ (µ))P (τ = m)
(Bm,λ

m=m0
∗

=

bt c
X

2
2
(µ) − B(m+1)∧t
(Bm,λ
∗ ,λ (µ))P (τ ≤ m).

m=m0

In the case t∗ = m0 all expressions evaluate to zero because of τ ≥ t∗ and we
suppose t∗ > m0 from now on, so that E[Rt2∗ ] = κ holds. For m0 ≤ m < t∗
2 ≤ κ}, E[R2 ] ≥ κ and by Lemma 5.1 together with
we have {τ ≤ m} = {Rm
m
2
2
P (Z < −x) ≤ e−x /(2σ ) for Z ∼ N (0, σ 2 ), x ≥ 0 we obtain the bound
2
P (Rm
≤ κ) = P

D
 X



2
δ 2 (ε2i − 1) + 2λi µi δεi ≤ −(E[Rm
] − κ)

i=m+1
D
 X

D
 X
2 ] − κ
2 ] − κ
E[Rm
E[Rm
+P
λi µi δεi ≤ −
2
4
i=m+1
i=m+1
 (E[R2 ] − κ)2 
 (E[R2 ] − κ)2 
m
m
≤ exp −
+
exp
−
2 (µ)
16δ 4 (D − m)
32δ 2 Bm,λ

≤P

δ 2 (ε2i − 1) ≤ −

25

2
≤ F (Bm,λ
(µ) − Bt2∗ ,λ (µ)),
2 ] − κ = E[R2 − R2 ] ≥ B 2 (µ) − B 2 (µ) for m < t∗
where we use E[Rm
m
t∗
m,λ
t∗ ,λ
(see (3.5)), and put


F (z) := exp −



z2
z2 
,
+
exp
−
16δ 4 D
32δ 2 (Bt2∗ ,λ (µ) + z)

z ≥ 0.

2 (µ) and F via a Riemann-Stieltjes sum
We conclude by monotonicity of B•,λ
approximation:
 2
 
E Bτ,λ
(µ) − Bt2∗ ,λ (µ) +
∗

bt c
X

≤

2
2
2
2
(µ) − B(m+1)∧t
(Bm,λ
∗ ,λ (µ))F (Bm,λ (µ) − Bt∗ ,λ (µ))

m=m0
2
Bm

Z
≤

0 ,λ

(µ)

Bt2∗ ,λ (µ)
Z ∞

≤

F (y − Bt2∗ ,λ (µ)) dy

F (z) dz
0

≤

√

4πδ 4 D +

Z
0

Bt2∗ ,λ (µ)


exp −


z2
dz +
64δ 2 Bt2∗ ,λ (µ)

q
√
≤ 4πδ 4 D + 16πδ 2 Bt2∗ ,λ (µ) + 64δ 2
√

≤ 17 D + 64 δ 2 + Bt2∗ ,λ (µ)D−1/2 ,

Z

∞


exp −

Bt2∗ ,λ (µ)

z 
dz
64δ 2

√
√
using 4 πδBt∗ ,λ (µ) ≤ 4π Dδ 2 + D−1/2 Bt2∗ ,λ (µ) by the binomial identity
√
and 4π + 4π ≤ 17 in the last line.

5.6

Proof of Proposition 3.6

Proof. By the Cauchy-Schwarz inequality and E[ε4m ]1/2 =
h
i
E (Sτ − Sdt∗ e )+ = δ 2

D
X

√

3, we have

2
λ−2
m E[εm 1(τ ≥ m)]

m=dt∗ e+1
D
X

√
≤ 3δ 2

m=dt∗ e+1

26

1/2
λ−2
.
m P (τ ≥ m)

2
2
For m ≥ t∗ + 1 ≥ m0 + 1 we have {τ ≥ m} = {Rm−1
> κ}, E[Rm−1
]≤κ
2
2
−x
/(2σ
)
and by Lemma 5.1 together with P (Z > x) ≤ e
for Z ∼ N (0, σ 2 ),
x ≥ 0, we obtain the bound

2
P (Rm−1
> κ) = P

D
X



2
δ 2 (ε2i − 1) + 2λi µi δεi > κ − E[Rm−1
]

i=m
D
X

D
X
2
2
κ − E[Rm−1
]
κ − E[Rm−1
]
+P
λi µi δεi ≥
2
4
i=m
i=m


 (κ − E[R2 ])2 
2
(κ − E[Rm−1
])2
m−1
≤ exp −
+
exp
−
.
2
2
16δ 4 (D − m + 1) + 4δ 2 (κ − E[Rm−1
])
32δ 2 Bm−1,λ
(µ)

≤P

δ 2 (ε2i − 1) ≥

For the numerator, we use the lower bound
2
κ − E[Rm−1
] ≥ κ − E[Rt2∗ ] + δ 2 (m − 1 − t∗ ) ≥ δ 2 (m − 1 − t∗ ).
2
]) ≤ 16δ 4 D+
For the denominators, we use 16δ 4 (D−m+1)+4δ 2 (κ−E[Rm−1
2
2
2
2
2
4δ κ for the first term and 32δ Bm−1,λ (µ) ≤ 32δ Bt∗ ,λ (µ) ≤ 32δ 2 κ for the
second term. We arrive at

h

E (Sτ − Sdt∗ e )+

i

D
X

√
≤ 2 3δ 2

m=dt∗ e+1


(m − 1 − t∗ )2 
λ−2
.
m exp −
16D + 32κδ −2

√
Adding E[(Sdt∗ e −St∗ )+ ] ≤ 2 3δ 2 λ−2
dt∗ e gives the first inequality, when noting
(Sτ − St∗ )+ ≤ SD which gives the trivial bound E[SD ] = Dδ 2 .
Turning to the polynomial eigenvalue decay, we obtain the bound

X
√ 2
2
rV,τ ≤ 2 3CA
1+
(t∗ + 1 + k)2p e−k /(48D) ∧ D.
k≥0

In the sequel ’.’, ’&’ denote inequalities up to a factor only depending on
p. A Riemann sum approximation shows
Z ∞
X
√
2
−k2 /(48D)
e
≤1+
e−x /(48D) dx . D.
0

k≥0

Similarly, we obtain
X
k≥0

2p −k2 /(48D)

k e

Z
≤

∞

(1 + x)2p e−x

0

27

2 /(48D)

dx . Dp+1/2 .

This yields



√
2
rVτ . CA
(t∗ )2p D + Dp+1/2 ∧ D.

On the other hand, we have
Vt∗ = δ

2

bt∗ c
X


−2
∗
∗
2 −2 ∗ 2p+1
λ−2
+
(t
−
bt
c)λ
,
∗
m
bt c+1 & δ CA (t )

m=1

implying the result with a suitable constant Cp .

5.7

Proof of Proposition 4.2

Proof. In this proof ’.’ denotes an inequality holding up to factors depending only on p, CA , Cκ and C2 ; similarly, ’∼’ denotes a two-sided inequality
holding up to factors depending on these parameters. In the case ts > m0
we use the independence of τ from µ
b(0) , . . . µ
b(m0 ) by Lemma 4.1 to obtain
b
E[kb
µ(ρ) − µk2 1(τ = m0 )] = E[kb
µ(m)
− µk2 ]P (τ = m0 )


≤ C2 E[kb
µ(m0 ) − µk2 ] + δ 2 P (τ = m0 )


= C2 E[kb
µ(τ ) − µk2 1(τ = m0 )] + δ 2 P (τ = m0 ) .

On {τ > m0 } we have ρ = τ and we apply Theorem 3.8 with ts ≥ m0 >
to get

√

D

E[kb
µ(ρ) − µk2 1(τ > m0 )] ≤ E[kb
µ(τ ) − µk2 ] . E[kb
µ(ts ) − µk2 ].
Because of ts > m0 we have E[kb
µ(ts ) −µk2 ] ≤ 2 mint∈[0,D] E[kb
µ(t) −µk2 ]. This
gives the result in this case.
2 (µ) ≤ V
Next, consider the case ts = m0 where Bm
m0 . Then the estima0
(m
)
s
tor µ
b
with ms ∈ {0, 1, . . . , m0 } from (1.7) satisfies
 (ms )

λ2
E kb
µ
− µk2 ≤ 2 max 2 i
i λi+1

min
m∈{0,...,D}

 (m)

E kb
µ
− µk2 ,

noting that the factor maxi λ2i /λ2i+1 comes from the discretisation ms of
4 22p . 1. Given the independence
the balanced oracle and is bounded by CA
(0)
(m
)
of τ from {b
µ ,...,µ
b 0 } by Lemma 4.1 and the properties of the model
selector m,
b we have


E[kb
µ(ρ) − µk2 1(τ = m0 )] ≤ C2 E[kb
µ(ms ) − µk2 ] + δ 2
28

.

min
m∈{0,...,D}

E[kb
µ(m) − µk2 ] + δ 2 .

For ms ∈ [m0 /2, m0 ]
2
µ(ms ) − µk2 ]
E[kb
µ(m0 ) − µk2 ] ≤ Bm
(µ) + Vm0 . E[kb
s

∼ Vms . By Theorem 3.8 with ts = m0 this gives
follows from Vm0 ∼ δ 2 m2p+1
0
E[kb
µ(ρ) − µk2 1(τ > m0 )] . E[kb
µ(m0 ) − µk2 ] . E[kb
µ(ms ) − µk2 ]
.

min
m∈{0,...,D}

E[kb
µ(m) − µk2 ].

2 > κ}, S ≤ S , B 2 (µ) ≤
For ms < m0 /2 we obtain by {τ > m0 } = {Rm
τ
D
τ
0
2
Bm0 (µ) and Cauchy-Schwarz inequality
2
2
E[kb
µ(ρ) − µk2 1(τ > m0 )] ≤ E[(Bm
(µ) + SD )1(Rm
> κ)]
0
0
2
2
2 1/2
2
≤ Bm
(µ)P (Rm
> κ) + E[SD
] P (Rm
> κ)1/2 .
0
0
0
2 (µ) ≤ B 2 (µ) ≤ V and E[S 2 ]1/2 . E[S ] = V (by compariWe have Bm
D
D
D
ms
D
0
son of Gaussian moments), so that
2
2
E[kb
µ(ρ) − µk2 1(τ > m0 )] . VD P (Rm
> κ)1/2 ∼ δ 2 DP (Rm
> κ)1/2 .
0
0
2 (µ) ≤ V
Observing mw := min{m ≥ 0 | Bm,λ
m,λ } ≤ ms < m0 /2 we obtain
2
2
2
(µ) − m0 δ 2 ≤ −(m0 /2)δ 2 .
E[Rm
(µ) − Vm0 ,λ ≤ Bm
] − κ = Bm
w ,λ
0
0 ,λ

As in the proof of Proposition 3.6 we therefore find

2
P (Rm
>
κ)
≤
exp
−
0




m20
m20 δ 2
+ exp −
.
2
64(D − m0 ) + 8m0
128Bm
(µ)
0 ,λ

2
2
By the choice of m0 and Bm
(µ) ≤ Bm
(µ) ≤ (m0 /2)δ 2 , using D ≥
0 ,λ
0 /2,λ
3 ⇒ log D ≥ 1, we deduce

2
P (Rm
> κ) ≤ 2 exp − 2 log D = 2D−2 .
0

Insertion of this bound yields E[kb
µ(ρ) − µk2 1(τ > m0 )] . δ 2 , which accomplishes the proof for the case ts = m0 and ms ≤ m0 /2.

29

References
[1] L. Birgé and P. Massart. Minimum contrast estimators on sieves: exponential bounds and rates of convergence. Bernoulli, 4(3):329–375,
1998.
[2] N. Bissantz, T. Hohage, A. Munk, and F. Ruymgaart. Convergence
rates of general regularization methods for statistical inverse problems
and applications. SIAM Journal on Numerical Analysis, 45:2610–2636,
2007.
[3] G. Blanchard and P. Mathé. Discrepancy principle for statistical inverse problems with application to conjugate gradient iteration. Inverse
Problems, 28:pp. 115011, 2012.
[4] P. Bühlmann and T. Hothorn. Boosting algorithms: Regularization,
prediction and model fitting. Statistical Science, pages 477–505, 2007.
[5] L. Cavalier. Inverse problems in statistics. In Inverse problems and
high-dimensional estimation, pages 3–96. Lecture Notes in Statistics
203, Springer, 2011.
[6] L. Cavalier, G.K. Golubev D. Picard, and A.B. Tsybakov. Oracle inequalities for inverse problems. Annals of Statistics, 30:843–874, 2002.
[7] L. Cavalier and Y. Golubev. Risk hull method and regularization by
projections of ill-posed inverse problems. Annals of Statistics, 34:1653–
1677, 2006.
[8] E. Chernousova, Y. Golubev, and E. Krymova. Ordered smoothers
with exponential weighting. Electronic Journal of Statistics, 7:2395–
2419, 2013.
[9] A. Cohen, M. Hoffmann, and M. Reiß. Adaptive wavelet Galerkin methods for linear inverse problems. SIAM Journal on Numerical Analysis,
42(4):1479–1501, 2004.
[10] H. Engl, M. Hanke, and A. Neubauer. Regularization of Inverse Problems. Kluwer Academic Publishers, London, 1996.
[11] Y. Ingster and I. Suslina. Nonparametric goodness-of-fit testing under
Gaussian models. Lecture Notes in Statistics 169, Springer, 2012.

30

[12] B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28:1302–1338, 2000.
[13] O. Lepski.
Some new ideas in
arXiv:1603.03934, 2016.

nonparametric

estimation.

[14] P. Mathé and S. V. Pereverzev. Geometry of linear ill-posed problems
in variable hilbert scales. Inverse problems, 19(3):789, 2003.
[15] G. Raskutti and M.J. Wainwright. Early stopping and non-parametric
regression: An optimal data-dependent stopping rule. Journal of Machine Learning Research, 15:335–366, 2014.
[16] Y. Saad. Numerical Methods for Large Eigenvalue Problems: Revised
Edition. Society for Industrial and Applied Mathematics (SIAM), 2011.
[17] A. B. Tsybakov. Introduction to nonparametric estimation. Springer
Series in Statistics. Springer, New York, 2009.
[18] G. Wahba. Practical approximate solutions to linear operator equations when the data are noisy. SIAM Journal on Numerical Analysis,
14(4):651–667, 1977.
[19] Y. Yao, L. Rosasco, and A. Caponnetto. On early stopping in gradient
descent learning. Constructive Approximation, 26(2):289–315, 2007.

31

