arXiv: arXiv:1702.01402

SUPPLEMENTARY MATERIAL TO “ESTIMATIONBOUNDS AND SHARP ORACLE INEQUALITIES OFREGULARIZED PROCEDURES WITH LIPSCHITZ LOSSFUNCTIONS”
By Pierre Alquier∗,† and Vincent Cottet∗ and Guillaume
Lecué∗CREST, CNRS, ENSAE, Université Paris Saclay.
Email: pierre.alquier, vincent.cottet,
guillaume.lecue@ensae.fr
The supplementary material is organized as follows.
• Section 6 proposes an alternating direction method of multiplier algorithm for the matrix completion methods proposed in Section 4. Ourestimator is evaluated on simulated and real datasets. Python notebooks can be downloaded: https://sites.google.com/site/vincentcottet/code• Section 7 contains an application of our general results to the casewhere E is a reproducing kernel Hilbert space (RKHS).
• Section 8 contains a complete discussion of the Bernstein condition.
Many examples and sufficient conditions (old and new) are provided.
• Section 9 contains the proofs of the theorems of Section 2.
• Section 10 contains the proofs of the optimality results of Section 4.
• Section 11 contains the proofs of the new results stated in Section 8.
• Finally, Section 12 contains the study of the (non-penalized) ERM. We
also provide an application to shape-constrained logistic regression.
6. Simulation study in matrix completion.
6.1. Algorithm and Simulation Outlines. Since this part provides new
methods and results on matrix completion, we propose an algorithm in order to compute efficiently the RERM using the hinge loss and the quantile
loss. This section explains the structure of the algorithm that is used withspecific loss functions in next sections. Although many algorithms exist for
the least squares matrix completion, to our knowledge many of them treat
only the exact recovery such as in [10] and [30], or at least they all deal with∗

Supported by Labex ECODEC (ANR - 11-LABEX-0047)
Research programme New Challenges for New Data from LCL and GENES, hosted
by the Fondation du Risque
†

1

2

P. ALQUIER AND V. COTTET AND G. LECUÉ

differentiable loss functions, see [22]. On the other hand, the two losses that
we mainly consider here are non differentiable because they are piecewise
linear (in the case of hinge and 0, 5-quantile loss functions): new algorithms
are hence needed. It has been often noted that the RERM with respect to thehinge loss or 0.5-quantile loss can be solved by a semidefinite programming
but the cost is prohibitive for large matrices, say dimensions larger than 100.
It actually works for small matrices as we ran SDP solver in Python in verysmall examples.
We propose here an alternating direction method of multiplier (ADMM)
algorithm. For a clear and self-contained introduction to this class of algorithms, the reader is referred to the very pedagogical introduction [9], andwe do not explain all the details here. When the optimization problem is asum of two parts, the core idea is to split the problem by introducing an
extra variable. In our case, the two following problems are equivalent:
(
)
N
1 X
minimize`( Xi , M , Yi ) + λ kM kS1 ,
M
N
i=1

and
(
minimize
M,L

N

1 X
`( Xi , M , Yi ) + λ kLkS1
N)
subject to M = L

i=1

Below, we use the scaled form and the m × T matrix U is then called thescaled dual variable. Note that the S2 norm is also the Froebenius norm andis thus elementwise. We can now exhibit the augmented Lagrangian:N

Lα (M, L, U ) =1 X
αα`( Xi , M , Yi )+λ kLkS1 + kM − L + U k2S2 − kU k2S2 ,
N
2
2
i=1

where α is a positive constant, called the augmented Lagrange parameter.
The ADMM algorithm [9] is then:
!
N
2
1 X
α
k+1
k
k
(24) M= argmin`( Xi , M , Yi ) +M −L +U
N
2
S2
M
i=1


2
α
(25)
Lk+1 = argmin λ kLkS1 +M k+1 − L + U k
2
S2
LU k+1 = U k + M k+1 − Lk+1
The starting point (M 0 , L0 , U 0 ) uses one random matrix with independent
Gaussian entries for M 0 and two zero matrices for L0 and U 0 . Another choiceREGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

3of starting point is to use a previous estimator with a larger λ. The stopping2
2
criterion is, as explained in [9], M k+1 − M k S2 + U k+1 − U k S2 ≤ ε fora fixed threshold ε. It means that it stops when both (Uk ) and (Mk ) start
converging.
General considerations. The second step (25) is independent of the loss
function. It is well-known that the solution to this problem is Sλ/α (M k+1 +U k ) when Sa (M ) is the soft-thresholding operator with magnitude a applied
to the singular values of the matrix M .It is defined for a rank r matrix M>
with SVD M = U ΣV where Σ = diag (di )1≤i≤r by Sa (M ) = U Sa (Σ)V >
where Sa (Σ) = diag (max(0, di − a))1≤i≤r .
It requires the computation of the SVD of a m×T matrix at each iteration.
This is the main bottleneck of this algorithm (the other main step (24) can be
performed elementwise since the Xi ’s take their values in the canonical basisof Rm×T ; so it needs only at most N operations). Two methods may be used
to speed up the algorithm. First, there are efficient algorithms for computing
the n largest singular values and the associate subspaces, such as the Fortran
PROPACK. It can be plugged in order to solve (25) by computing the nlargest and stop at this stage if the lowest computed singular values is lower
than the threshold. It is obviously more relevant when the target is expected
to have a very small rank. This method has been implemented in Python
and works well in practice even though the parameter n has to be tuned
carefully. Second, one can use an approximate SVD such as in [21].
Moreover, the first step (24) (which may be performed elementwise) has
a closed form solution for hinge and quantile loss: it is a soft-thresholding
applied to a specified quantity.
Simulated observations as well as real-world data (cf. the MovieLens
dataset1 ) are considered in the examples below. Finally note that parameter
λ is tuned by cross-validation.
6.2. Simulation study for RERM “Hinge + S1”. As the hinge loss has
not been often studied in the matrix context, we provide many simulations
in order to show the robustness of our method and the opportunity of using
the hinge loss rather than the logistic loss. We follow the simulations ran
in [14] and compare several methods. An estimator based on the logistic
model, studied in [16], is also challenged2 .
1available in http://grouplens.org/datasets/movielens/
In the followings, the four estimators will be referred to Hinge for estimator givenin (18), Hinge Bayes and Logit Bayes for the two Bayesian estimators from [14] withrespectively hinge and logistic loss functions, and Logit for the estimator from [16]. The
2

4

P. ALQUIER AND V. COTTET AND G. LECUÉA first set of simulations. The simulations are all based on a low-rank 200×
200 matrix M ? from which the data are generated and which is the target
for the predictions. M ? is also a minimizer of R0/1 so the error criterion that
we will report for a matrix M is the difference of the predictions between
M ? and M , which is P[sign( M ? , X ) 6= sign( M, X )]. The Xi ’s correspondto 20% ofso the misclassification rate is also
P the entries randomly picked? )}.
(1/mT ) p,q I{sign(Mp,q ) 6= sign(Mp,q
Two different scenarios are tested: the first one (called A), involves amatrix M ? with only entries in {−1, +1} so the Bayes classifier is low rank
and favors the hinge loss. The second test (called B) involves a matrix M ? =LR> where L, R have i.i.d. Gaussian entries and the rank is the number ofcolumns. In this case, the Bayes matrix contains the signs of a low-rankmatrix, but it is not itself low rank in general. We also test the impact ofseveral noise structures on the performance of the estimators:
1. (noiseless) Yi = sign( M ? , Xi )2. (logistic) Yi = sign( M ? , Xi + Zi ), where Zi follows a logistic distribution
3. (switch) Yi = i sign( M ? , Xi ) where i = (1 − p)δ1 + pδ−1Finally, we run all the simulations on rank 3 and rank 5 matrices and λ istuned by cross validation. All the simulations are run one time.
Model
Hinge
Logit
Hinge Bayes
Logit Bayes
Hinge
Logit
Hinge Bayes
Logit Bayes

A1
0
0
0
0
0
0
0
0

A2 (p = .1)
A3
B1
B2 (p = .1)
B3
0
14.5
6.7
10.9
21.0
0.5
17.3
5.1
10.7
19.8
Rank 3
0.1
8.5
5.3
10.8
22.1
0.5
16.0
4.1
10.1
16.0
0.8
29.0 11.7
19.3
23.3
3.1
30.1
9.0
18.3
22.1
Rank 5
0.5
27
9.4
17.9
24.4
4.4
32.5
7.8
17.3
21.5
Table 1
Misclassification error rates on simulated matrices in various cases. Model∈ {A, B}{1, 2, 3} refers to scenario ∈ {A, B} and noise structure ∈ {1, 2, 3}. For thenoise-free Model = A0, the 0 column shows the exact reconstruction property of allprocedures.

The results are very similar among the methods, see Table 1. The logistic
loss performs better for matrices of type B and especially for high level ofnoise in the logistic data generation as expected. For type A matrices, thehinge loss performs slightly better. The Bayesian estimators performs as wellas the frequentist estimators even though the program solved is not convex.
Bayesian estimators use the Gammma prior distribution.

5

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

Impact of the noise level. The second experiment is a focus on the switch
noise and matrices that are well separated (as A2 in the previous example).
The noise lies between p = 0 and almost full noise (p = .4). The performanceof the RERM with the hinge loss is slightly worse than the Bayesian estimator with hinge loss but always better than the RERM with the logistic
loss, see Figure 6.2.
Model
Hinge

0.4

Misclassification Rate

Hinge Bayes
Logit
0.3

0.2

0.1

0.0
0.00

0.05

0.10

0.15

0.20

0.25

0.30

0.35

0.40

Level of noise

Fig 1. Misclassification error rates for a large range of switch noise (noise structure
number 3).

Real dataset. We finally run the hinge loss estimator on the MovieLens
dataset. The ratings, that lie in {1, 2, 3, 4, 5}, are split between good ratings(4, 5) and bad ratings (others). The goal is therefore to predict whether theuser will like a movie or not. On a test set that contains 20% of the data, themisclassification rate in prediction are almost the same for all the methods(Table 2).
Hinge Bayes Logit Hinge
.28
.27
.28
Table 2
Misclassification Rate on MovieLens 100K dataset

Model
misclassification rate

6.3. Simulation study for quantile matrix completion. The goal of thissection is to challenge the regularized least squares estimator by the RERM
with 0.5-quantile loss. The quantile used here is therefore the median. The
main conclusion of our study is that median based estimators are morerobust to outliers and noise than mean based estimators. We first test themon simulated datasets and then turn to use a real dataset.

6

P. ALQUIER AND V. COTTET AND G. LECUÉ

Simulated matrices. The observations come from a base matrix M ? which
is a 200 × 200 low rank matrix. It is built by M ? = LR> where the entries of
L, R are i.i.d. gaussian and L, R have 3 columns (and therefore, the rank of
M ? is 3). The Xi ’s correspond to 20% randomly picked entries. The
P criterion? −that we retain is the l1 reconstruction of M ? that is: (1/mT ) p,q |Mp,q
Mp,q |.
The observations are made according to this flexible model:
Yi = M ? , X + zi + oζi .
zi is the noise, o is the magnitude of outliers and ζi is the outlier indicatorparametrized by the share p such that ζi = p/2δ−1 + (1 − p)δ0 + p/2δ1 . The
different parameters for the different scenarios are summarized in Table 3.
On the first experiment, p is fixed to 10% and the magnitude o increases.
As expected for least squares, the results are better for low magnitude ofoutliers (it corresponds to the penalized maximum likelihood estimator), see
Figure 2. Quickly, the performance of the least squares estimator is getting
worse and when the outliers are large enough, the best least squares predictor
is a matrix with null entries. In opposite to this estimator, the median of the
distribution is almost not affected by outliers and it is completely in line withthe results: the performances are strictly the same for mid-range to highrange magnitude of outliers. The robustness of the quantile reconstruction
is totally independent to the magnitude of the outliers.
zioζiFigure 2
N (0, 1/4)
o = 0..30
p = 0.1
Figure 3
N (0, 1/4)
10
p = 0.025
Figure 4 tα , α = 1..100p=0tα : t-distribution with α degrees of freedom.
Table 3
Parameters and distributions of the simulations

In a second experiment, we fixed the magnitude of outliers but we increase
their proportion within the dataset (see Figure 3). The median completionis, as expected, more robust and the results deteriorate less than the ones
from least squares. When the outliers ratio is greater than 20%, the leastsquares estimator completely fails while the median completion still works.
The third simulation involves non gaussian noise without outliers: we use
the t-distribution, that has heavy tails. In this challenge, a lower degree of
freedom involves heavier tails and the worst case is for Student distribution
with degree 1. We can see that the least squares is inadequate for small
degrees of freedom (1 to 2) and behaves better than the median completion
for larger degrees of freedom, see Figure 4.

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

7

1.25

methodLeast Squares
Median loss

L1 Risk

1.00

0.75

0.50

0

10

20

30

Outliers Magnitude

Fig 2. l1 reconstruction for different magnitude of outliers
methodLeast Squares

L1 Risk

1.00

Median loss

0.75

0.50

0

5

10

15

20

25

Outliers Ratio (%)

Fig 3. l1 reconstruction for different percentage of outliers
1.25

methodLeast Squares
Median loss

L1 Risk

1.00

0.75

0.50

1

2

5

10

Student DF

Fig 4. l1 reconstruction for student noise with various magnitude degrees of freedom

Real dataset. The last experiment involves the MovieLens dataset. We keep
one fifth of the sample for test set to check the prediction accuracy. Even
though the least squares estimator remains very efficient in the standard
case, see Table 4, the results are quite similar for the MAE criterion. In asecond step, we add artificial outliers. In order to do that, we change 20% of
5 ratings to 1 ratings. It can be seen as malicious users that change ratingsin order to distort the perception of some movies. As expected, it depreciates

8

P. ALQUIER AND V. COTTET AND G. LECUÉMSE MAE
Raw Data, LS
0.89
0.75
Raw Data, Median
0.93
0.75
Outliers, LS
1.04
0.84
Outliers, Median
0.96
0.78
Table 4
Prediction power of Least Squares and Median Loss on MovieLens 100K dataset

the least squares estimator performance but the median estimator returns
almost as good performances as in the standard case.
7. Kernel methods via the hinge loss and a RKHS-norm regularization. In this section, we consider regularization methods in some
general Reproducing Kernel Hilbert Space (RKHS) (cf. [15], Chapter 4 in[38] or Chapter 3 of [44] for general references on RKHS). Note that RKHS
is a vast class of functions space which include non-parametric spaces suchas Sobolev spaces (see [38]).
Unlike the previous examples, the regularization norm here, which is thenorm k·kHK of a RKHS HK , is not associated with some ”hidden” conceptof sparsity. In particular, RKHS norms have no singularity (except at 0)
since they are differentiable at any point except in 0. As a consequence
the sparsity parameter ∆(ρ) cannot be larger than 4ρ/5, i.e. ρ does notsatisfy the sparsity equation, unless the set Γf ∗ (ρ) contains 0 that is for ρ ≥20 kf ∗ kHK . Indeed, one key observation is that norms are non differentiable
at 0 and that its subdifferential at 0 is somehow extremal:(26)∂ k·k (0) = B∗ := {f : kf k∗ ≤ 1},

where k·k∗ is the dual norm.
As a consequence, the rates obtained in this section do not depend onsome hidden sparsity parameter associated with the oracle f ∗ but on the
RKHS norm at f ∗ , that is kf ∗ kHK (such error rates are refer as “complexity
bounds” in [28]). The aim of this section is therefore to show that our main
results apply beyond “sparsity inducing regularization methods” by showingthat “classic” regularization method, inducing smoothness for instance, mayalso be analyzed the same way and fall into the scope of Theorem 2.1 andTheorem 2.2. This section also shows an explicit expression for the Gaussian
mean-width with localization as used in Definition 9.1 (a sharper way tomeasure statistical complexity via a local r(·) function provided below).
Mathematical background. In this setup, the data are still N i.i.d. pairs(Xi , Yi )N
i=1 where the Xi ’s take their values in some set X and Yi ∈ {−1, +1}.

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

9A ”similarity measure” is provided over the set X by means of a kernel
K : X × X → R so that x1 , x2 ∈ X are ”similar” when K(x1 , x2 ) is small.
One can think, for instance, of X as the set of all DNA sequences (that is
finite words over the alphabet {A, T, C, G}) and K(w1 , w2 ) is the minimal
number of changes like insertion, deletion and mutation needed to transformword w1 ∈ X into word w2 ∈ X .
The core idea behind kernel methods is to transport the design data Xi ’sfrom X to a Hilbert space via the application x → K(x, ·) and then constructstatistical procedures based on the ”transported” dataset (K(Xi , ·), Yi )N
i=1 .
The advantage of doing so is that the space where the K(Xi , ·)’s belong
have much structure than the initial set X which may have no algebraic
structure at all. The first thing to set is to define somehow the ”smallest”
Hilbert space containing all the functions x → K(x, ·). We recall now oneclassic way of doing so that will be used later to define the objects that need
to be considered in order to construct RERM in this setup and to derive theirestimation rates via Theorem 2.1 and Theorem 2.2. Note that even though,we derive estimation rates only in the bounded case (because the subgaussian
assumption is not natural for RKHS), we provide a computation of the twocomplexity parameters since their analysis is identical and they yield an
example where the two Gaussian width and Rademacher complexities areequal.
Recall that if K : X × X → R is a positive definite kernel such thatkKkL2 < ∞, then by Mercer’s theorem, there is anPorthogonal basis (φi )i∈N0of L2 such that µ ⊗ µ-almost surely, K(x, x0 ) = ∞i=1 λi φi (x)φi (x ) where(λi )i∈N is the sequence of eigenvalues of the positive self-adjoint integral
operator TK (arranged in a non-increasing order) defined for every f ∈ L2
and µ-almost every x ∈ X byZ
(TK f )(x) =K(x, x0 )f (x0 )dµ(x0 ).
x0 ∈XIn particular, for all i ∈ N, φi is an eigenvector of TK corresponding to theeigenvalue λi ; and (φi )i is an orthonormal system in L2 (µ).
The reproducing kernel Hilbert space HK is the set of all function seriesP∞
i=1 ai K(xi , ·) converging in L2 endowed with the inner productXXX
ai K(xi , ·),bj K(x0j , ·) =ai bj K(xi , x0j )i,jwhere ai , bj ’s are any real numbers and the xi ’s and x0j ’s are any points inX.

10

P. ALQUIER AND V. COTTET AND G. LECUÉ

Estimator. The RKHS HK is therefore a class of functions from X to R
that can be used as a learning model and the norm naturally associatedto its Hilbert structure can be used as a regularization function. Given a
Lipschitz loss function `, the oracle is defined asf ∗ ∈ argmin E`f (X, Y )f ∈HK

and it is believed that kf ∗ kHK is small which justified the use of the RERM
with regularization function given by the RKHS norm k·kHK :Nfˆ ∈ argmin
f ∈HK

1 X
`f (Xi , Yi ) + λ kf kHK
N

!

i=1

Statistical properties of this RERM may be obtained from Theorem 2.1
in the subgaussian case and from Theorem 2.2 in the bounded case. To
that end, we only have to compute the Gaussian mean width and/or the
Rademacher complexities of BHK . In this example, we rather compute thelocalized version of those quantities because it is possible to derive explicit
formula. They are obtained by intersecting the ball with rE. In order not to
induce any confusion, we still use the global ones in estimation bounds.
Localized complexity parameter. The goal is to compute w(ρBHK ∩ rE) andRad(ρBHK ∩ rE) for all ρ, r > 0 where BHK = {f ∈ HK : kf kHK ≤ 1} isthe unit ball of the RKHS and E = {f ∈ HK : Ef (X)2 ≤ 1} is the ellipsoidassociated with X. In the following, we embed the two sets BHK and E in
l2 = l2 (N) so that we simply have to compute the Gaussian mean width andthe Rademacher complexities of the intersection of two ellipsoids sharing thesame coordinates structures.
The unit ball of HK can be constructed from the eigenvalue decomposition √of TK by considering the feature map Φ : X → l2 defined by
Φ(x) =λi φi (x) i∈N and then the unit ball of HK is just
BHK = fβ (·) = β, Φ(·) : kβkl2 ≤ 1 .
One can use the feature map Φ to show that there is an isometry between theP 2 1/2
βi /λi.
two Hilbert spaces HK and l2 endowed with the norm kβkK =The unit ball of l2 endowed with the norm k·kK is an ellipsoid denoted by
EK .
Let us now determine the ellipsoid in l2 associated with the design X
obtained via this natural isomorphism β ∈ l2 → fβ (·) = β, Φ(·) ∈ HK between l2 and HK . Since (φi )i is an orthonormal system in L2 , the covarianceREGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

11

operator of Φ(X) in l2 is simply the diagonal operator with diagonal elements (λi )i . As a consequence the ellipsoid associated with X is isomorphic2
to Ẽ = {β ∈ l2 : E β, Φ(X) ≤ 1}; it has the same coordinate structure asP
the canonical one in l2 endowed with k·kK : Ẽ = {β ∈ l2 :λi βi2 ≤ 1}. So
that, we obtain

(27)


1/2
X
w(Kρ (f ∗ ) ∩ rEf ∗ ) = w(ρEK ∩ rẼ) ∼  (ρ2 λj ) ∧ r2 jwhere the last inequality follows from Proposition 2.2.1 in [39] (note that
we defined the Gaussian mean widths in Definition (2.4) depending on thecovariance of X). We also get from Theorem 2.1 in [32] that

(28)


1/2
X
Rad(Kρ (f ∗ ) ∩ rEf ∗ ) ∼  (ρ2 λj ) ∧ r2  .
jNote that unlike the previous examples, we do not have to assume isotropicity of the design. Indeed, in the RKHS case, the unit ball of the regularization
function is isomorphic to the ellipsoid EK . Since E is also an ellipsoid having
the same coordinates structure as EK (cf. paragraph above), for all ρ, r > 0,
the intersection ρBHK ∩rE is equivalent to an ellipsoid, meaning that, it contains an ellipsoid and is contained in a multiple of this ellipsoid. Therefore,
the Gaussian mean width and the Rademacher complexity of ρBHK ∩rE has
been computed without assuming isotropicity (thanks to general results on
the complexity of Ellipsoids from Proposition 2.2.1 in [39] and Theorem 2.1
in [32]).
It follows from (27) and (28) that the Gaussian mean width and theRademacher complexities are equal. Therefore, up to constant (L in the subgaussian case and b in the bounded case), the two subgaussian and bounded
setups may be analyzed at the same time. Nevertheless, since we will only
consider in this setting the hinge loss and that the Bernstein condition (cf.
Assumption 2.1) with respect to the hinge loss has been studied in Proposition 8.3 only in the bounded case, we continue the analysis only for thebounded framework. Moreover, the subgaussian assumption is not naturalfor RKHS.
We are now able to identify the complexity parameter of the problem. We
actually do not use the localization in this and rather use only the global

12

P. ALQUIER AND V. COTTET AND G. LECUÉ

complexity parameter as defined in Definition 2.7: for all ρ > 0:


(29)

 Cρ
r(ρ) = 

P

j λj

√

1
1/2  2κN

where κ ≥ 1 is the Bernstein parameter.
Results in the bounded setting. Finally, let us discuss about the boundedness assumption. It is known (cf., for instance, Lemma 4.23 in [38]) that if
the kernel K is bounded then the functions in the RKHS HK arepbounded:
for any f ∈ HK , kf kL∞ ≤ kKk∞ kf kHK where kKk∞ := supx∈X K(x, x).
As a consequence, if one restricts the search space of the RERM to a RKHS
ball of radius R, one has F := RBHK ⊂ R kKk∞ BL∞ and therefore theboundedness assumption is satisfied by F . However, note that a refinementof the proof of Theorem 9.2 using a boundedness parameter b dependingon the radius of the RKHS balls used while performing the peeling device
yields statistical properties for the RERM with no search space constraint.
For the sake of shortness, we do not provide this analysis here.
We are now in a position to provide estimation and prediction results for
the RERM


P
1/2
N
C
j λj
1 X

√
(30)
fˆ ∈ argmin (1 − Yi f (Xi ))+ +kf kHK N
Nf ∈RBHK
i=1
where the choice of the regularization parameter λ follows from Theorem (2.2)
and (28) (for r = +∞). Note that unlike the examples in the previous sections, we do not have to find some radius ρ∗ satisfying the sparsity equation (3) to apply Theorem 2.2 since we simply take ρ∗ = 20 kf ∗ kHK to insurethat 0 ∈ Γf ∗ (ρ∗ ).
Theorem 7.1. Let X be some space, K : X × X → R be a boundedkernel and denote by HK the associated RKHS. Denote by (λi )i the sequenceof eigenvalues associated to HK in L2 . Assume that the Bayes rule f from(35) belongs to RBHK and that the margin assumption (36) is satisfied forsome κ ≥ 1.
Then the RERM defined in (30) satisfies with probability larger than
1/2 (2κ−1)/κX
1/2κ , 
1 − C exp 
−CN
f
λ


j


HK
j

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

13

that
P
1/2 1/2κ
P
1/2
f
f
λ
λ
j j
j j
HK
HK


√
√
and Ehinge (fˆ) ≤ C
fˆ − f
≤ C

L2
N
N


where Ehinge (fˆ) is the excess hinge risk of fˆ.
Note that classic procedures in the literature on RKHS are mostly developed in the classification framework. They are usually based on the hinge
loss and the regularization function is the square of the RKHS norm. For
such procedures, oracle inequalities have been obtained in Chapter 7 from[38] under the margin assumption (cf. [40]). A result that is close to the one
obtained in Theorem 7.1 is Corollary 4.12 in [34]. Assuming that kY k∞ ≤ C,
X ⊂ Rd , kKk∞ ≤ 1, that the eigenvalues of the integral operator satisfies
λi ≤ ci−1/p(31)

for some 0 < p < 1 and that the eigenvectors (φi ) are such that kφi k∞ ≤ A
for any i and some constant A then the RERM f˜ over the entire RKHS
space, w.r.t. the quadratic loss and for a regularization function of the orderof (up to logarithmic terms)!
2p/(1+p)
kf kH
kf k2H(32)
f 7→ ρ(kf kH ) := max,N
N 1/(1+p)satisfies with large probability an oracle inequality like


2
2
˜
E(Y − f (X)) ≤ inf
inf E(Y − f (X)) + Cρ(r) .
r≥1

kf kH ≤r

In particular, an error bound (up to log factors) follows from this result:with high probability,!
∗ k2p/(1+p)
∗ k2
2
kf
kf
H
H
(33)
f˜ − f ∗≤ Cρ(kf ∗ kH ) = C max,.
N
L2
N 1/(1+p)
One may compare this result to the one from Theorem 7.1 under assumption (31) even though the two procedures f˜ and fˆ use different loss functions,
regularization function and different search space. If assumption (31) holds
P
1/2

√ 1/(2κ)
andthen≤ c and so, one can take r(ρ) = Ccρ/(θ N )
j λj

14

P. ALQUIER AND V. COTTET AND G. LECUÉp
λ = C C/N . For such a choice of regularization parameter, Theorem 7.1
provides an error bound of the order of
"
#1/κ
f H C
2
√ K
(34)
f˜ − f≤C
L2 (µ)
N
which is almost the same as the one obtained in (33) when κ = 1 and p isclose to 1. But our result is worse when κ > 1 and p is far from 1. This is
the price that we pay by using the hinge loss – note that the quadratic loss
satisfies the Bernstein condition with κ = 1 – and by fixing a regularization
function which is the norm k·kHK instead of fitting the regularization function in a “complexity dependent way” as in (32). In the last case, our procedure fˆ does not benefit from the “real complexity” of the problem which is
localized Rademacher complexities – note that we used global Rademacher
complexities to fit λ and construct the complexity function r(·).
8. A review of the Bernstein and margin conditions. In order
to apply the main results from Theorem 2.1 and Theorem 2.2, one has
to check the Bernstein condition. This section is devoted to the study ofthis condition for three loss functions: the hinge loss, the quantile loss andthe logistic loss. This condition has been extensively studied in Learningtheory (cf. [2, 46, 33, 4, 43, 18]). We can identify mainly two approaches
to study this condition: when the class F is convex and the loss function` is “strongly convex”, then the risk function inherits this property andautomatically satisfies the Bernstein condition (cf. [2]). On the other hand,for loss functions like the hinge or quantile loss, that are affine by parts, one
has to use a different path. In such cases, one may go back to a statisticalframework and try to check the margin assumption. As a consequence, in thelatter case, the Bernstein condition is usually more restrictive and requires
strong assumptions on the distribution of the observations.
8.1. Logistic loss. In this section, we study the Bernstein condition of
the logistic loss function which is defined for every f : X → R, x ∈ X ,y ∈ {−1, 1} and u ∈ R by
˜ (x)) where `(u)˜ = log(1 + exp(−u)).
`f (x, y) = `(yf
Function `˜ is strongly convex on every compact interval in R. As it was firstobserved in [2, 3], one may use this property to check the Bernstein condition
for the loss function `. This approach was extended to the bounded regression
problem with respect to Lp loss functions (1 < p < ∞) in [31] and to nonconvex classes in [33].

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

15

In the bounded scenario, [3] proved that the logistic loss function satisfies
the Bernstein condition for κ = 1. One may therefore use that result toapply Theorem 2.2. The analysis is pretty straightforward in the boundedcase. It becomes more delicate in the subgaussian scenario as considered in
Theorem 2.1.
Proposition 8.1 ([2]). Let F be a convex class of functions from X to
R. Assume that for every f ∈ F , kf kL∞ ≤ b. Then the class F satisfies theBernstein condition (for the logistic loss) with Bernstein parameter κ = 1
and constant A = 4 exp(2b).
The proof is given in Section 11. This result solves the problem of theBernstein condition with respect to the logistic loss function over a convex
class F of functions as long as all functions in F are uniformly boundedby some constant b. We will therefore use this result only in the boundedframework, for instance, when F is a class of linear functionals indexed bya bounded set of vectors and X takes values in the canonical basis – like in
Section 4 where we assumed that X ∈ {E1,1 , · · · , Em,T }, the canonical basisof Rm×T .
In the subgaussian framework, one may proceed as in [43] and assume thata statistical model holds. In that case, the Bernstein condition is reduced tothe study of the margin assumption since, in that case, the “Bayes rule” f(which is called the log-odds ratio in the case of the logistic loss function)is assumed to belong to the class F and so f ∗ = f . The margin assumption
with respect to the logistic loss function has been studied in Example 1 from[43] but for a slightly different definition of the margin assumption. Indeed,in [43] only functions f in a L∞ neighborhood of f need to satisfy the margin
assumption whereas in Assumption 2.1 it has to be satisfied at least in the
non-bounded set C (see Remark 2.1).
From our perspective, we do not want to make no “statistical modelingassumption”. In particular, we do not want to assume that f belongs to F .
We therefore have to prove the Bernstein condition when f¯ may not belong
to F . We used this result in Section 3 in order to obtain statistical bounds
for the logistic LASSO and logistic SLOPE procedures. In those cases, F
is a class of linear functionals. We now state that the Bernstein conditionis satisfied for a class of linear functional when X is a standard Gaussian
vector (the proof has been postponed to Section 11).
Proposition 8.2. Let F = { ·, t : t ∈ RBl2 } be a class of linear
functionals indexed by RBl2 for some radius R ≥ 1. Let X be a standard
Gaussian vector in Rd and let Y be a {−1, 1} random variable. For every

16

P. ALQUIER AND V. COTTET AND G. LECUÉ

f ∈ F , the excess logistic risk of f , denoted by P Lf , satisfies
Elogistic (f ) = P Lf ≥c0
kf − f ∗ k2L2
R3

where c0 is some absolute constant.
8.2. Hinge loss. Unlike the logistic loss function (on a bounded support),
both the hinge loss and the quantile losses do not enjoy a strong convexity
property. Therefore, one has to turn to a different approach as the one usedin the previous section to check the Bernstein condition for those two loss
functions.
For the hinge loss function, Bernstein condition is more stringent and isconnected to the margin condition in classification. So, let us first introduce
some notations specific to classification. In this setup, one is given N labeledpairs (Xi , Yi ), i = 1, . . . , N where Xi takes its values in X and Yi is a label
taking values in {−1, +1}. The aim is to predict the label Y associatedwith X from the data when (X, Y ) is distributed like the (Xi , Yi )’s. The
classical loss function considered in this setup is the 0 − 1 loss function`f (x, y) = I(y 6= f (x)) defined for any f : X → {−1, +1}. The 0 − 1 loss
function is not convex, this may result in some computational issues when
dealing with it. A classic approach is to use a “ convex relaxation function”
as a surrogate to the 0 − 1 loss function: note that this is a way to motivate
the introduction of the hinge loss `f (x, y) = max(1 − yf (x), 0). It is wellknown that the Bayes rules minimizes both the standard 0 − 1 risk as wellas the hinge risk: put η(x) := E[Y |X = x] for all x ∈ X and define the Bayes
rule as(35)

f (x) = sgn(η(x)),

then f minimizes f → P `f over all measurable functions from X to R when
`f is the hinge loss of f .
Let F be a class of functions from X to [−1, 1]. Assume that f ∈ F
so that f is an oracle in F and thus (using the notations from Section 2)
f ∗ = f . In this situation, the margin assumption with respect to the hinge
loss (cf. [40, 25]) restricted to the class F and Bernstein condition (cf. Assumption 2.1) coincide. Therefore, Assumption 2.1 holds when the margin
assumption w.r.t. the hinge loss holds. According to Proposition 1 in [25],the margin assumption with respect to the hinge loss is equivalent the margin assumption with respect to the 0 − 1 loss for a class F of functions withvalues in [−1, 1]. Then, according to Proposition 1 in [40] and [8] the margin

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

17

assumption with respect to the 0 − 1 loss with parameter κ is equivalent to(1
P(|η(X)| ≤ t) ≤ ct κ−1 , ∀0 ≤ t ≤ 1 when κ > 1(36)|η(X)| ≥ τ a.s. for some τ > 0
when κ = 1.
As a consequence, one can state the following result on the Bernstein condition for the hinge loss in the bounded case scenario.
Proposition 8.3 (Proposition 1, [25]). Let F be a class of functions
from X to [−1, 1]. Define η(x) = E[Y |X = x] for all x ∈ X and assume thatthe Bayes rule (35) belongs to F . If (36) is satisfied for some κ ≥ 1 thenAssumption 2.1 holds with parameter κ for the hinge loss, and A dependingon c, κ and τ (which is explicitly given in the mentioned references). In thespecial case when κ = 1 then A = 1/(2τ ).
Note that up to a modification of the constant A, the same result holds
for functions with values in [−b, b] for b > 0, a fact we used in Section 7.
8.3. Quantile loss. In this section, we study the Bernstein parameterof the quantile loss in the bounded regression model, that is when for allf ∈ F, kf kL∞ ≤ b a.s.. Let τ ∈ (0, 1) and, for all x ∈ X , define f (x) as
the quantile of order τ of Y |X = x and assume that f¯ belongs to F , inthat case, f = f ∗ and Bernstein condition and margin assumption are thesame. Therefore one may follow the study of the margin assumption for thequantile loss in [18] to obtain the following result.
Proposition 8.4 ([18]). Assume that for any x ∈ X , it is possible
to define a density fx w.r.t the Lebesgue measure for Y |X = x such thatfx (u) ≥ 1/C for some C > 0 for all u ∈ R with |u − f ∗ (x)| ≤ 2b. Then thequantile loss satisfies Bernstein’s assumption with κ = 1 and A = 2C overF.
9. Proof of Theorem 2.1 and Theorem 2.2.
9.1. More general statements: Theorems 9.2 and 9.1. First, we state twotheorems: Theorem 9.1 in the subgaussian setting, and Theorem 9.2 in thebounded setting. These two theorems rely on localized versions of the complexity function r(·) that will be defined first. Note that the localized versionof r(·) can always be upper bounded by the simpler version used in the coreof the paper. Thus, Theorem 2.1 is a direct corollary of Theorem 9.1, andTheorem 2.2 is a direct corollary of Theorem 9.2.

18

P. ALQUIER AND V. COTTET AND G. LECUÉSo let us start with a localized complexity parameters. The ”statisticalsize” of the family of ”sub-models” (ρB)ρ>0 is now measured by local Gaussian mean-widths in the subgaussian framework.
Definition 9.1. Let θ > 0. The complexity parameter is a nondecreasing function r(·) such that for every ρ ≥ 0,√
CLw (ρB ∩ r(ρ)BL2 ) ≤ θr(ρ)2κ N
where κ is the Bernstein parameter from Assumption 2.1.
In the boundedness case, it is written as follows.
Definition 9.2. Let θ > 0. The complexity parameter is a nondecreasing function r(·) such that for every ρ ≥ 0,√
48Rad(ρB ∩ r(ρ)BL2 ) ≤ θr(ρ)2κ N
where κ is the Bernstein parameter from Assumption 2.1.
To obtain the complexity functions from Definition 2.5 and 2.7, we use thefact that w (ρB ∩ r(ρ)BL2 ) ≤ w(ρB) and Rad(ρB ∩ r(ρ)BL2 ) ≤ Rad(ρB):
it indeed does not use the localization. We also set θ = 7/40A in thosedefinitions because it is the largest value allowed in the following theorems.
Theorem 9.1. Assume that Assumption 1.1, Assumption 2.1 and Assumption 2.2 hold. Let r(·) be a function as in Definition 9.1 for some θsuch that 40Aθ ≤ 7 and assume that ρ → r(2ρ)/ρ is non-increasing. Let theregularization parameter λ be chosen such that10θr(2ρ)2κr(2ρ)2κ
<λ<
,
7ρ
2Aρ

(37)

∀ρ ≥ ρ∗where ρ∗ satisfies (3). Then, with probability larger than
(38)

1−

∞ X
X
j=0 i∈Ij

θ2 N (2(i−1)∨0 r(2j ρ∗ ))4κ−2
exp −4C 2 L2!

where for all j ∈ N, Ij = {1} ∪ {i ∈ N∗ : 2i−1 r(2j ρ∗ ) ≤ 2j ρ∗ dL2 (B)}, wehavefˆ − f ∗ ≤ ρ∗ ,fˆ − f ∗L2≤ r(2ρ∗ ) and E(fˆ) ≤ r(2ρ∗ )2κ /A.

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

19

Proof of Theorem 2.1: Let r(·) be chosen as in Definition 2.5. For thischoice, one can check that the regularization parameter used for the construction of the RERM satisfies (37) with an adequate choice of constants.
Moreover, for this choice of function r(·) it is straightforward to lower boundthe sum in the probability estimate in (38). The bounded case is in the same spirit.
Theorem 9.2. Assume that Assumption 1.1, Assumption 2.1 and Assumption 2.3 hold. Let r(·) be a function as in Definition 9.2 for some θsuch that 40Aθ ≤ 7 and assume that ρ → r(2ρ)/ρ is non-increasing. Let theregularization parameter λ be chosen such that(39)

10θr(2ρ)2κr(2ρ)2κ
<λ<
,
7ρ
2Aρ

∀ρ ≥ ρ∗where ρ∗ satisfies (3). Then, with probability larger than
(40)

1−2

∞ X
X

exp −c0 θ2 N (2i r(2j+1 ρ∗ ))4κ−2



j=0 i∈Ij
where c0 = 1/ max 48, 207θb2κ−1 and for all j ∈ N, Ij := {1} ∪ {i ∈ N∗ :2i−1 r(2j ρ∗ ) ≤ min(2j ρ∗ dL2 (B), b)}, we havefˆ − f ∗ ≤ ρ∗ ,fˆ − f ∗L2≤ r(2ρ∗ ) and E(fˆ) ≤ r(2ρ∗ )2κ /A.

The proof of Theorem 2.2 is straightforward consequence of Theorem 9.2.
It is identical to the one of Theorem 2.1 and we do not reproduce it here.
9.2. Proofs of Theorems 9.2 and 9.1. Proof of Theorem 9.1 and andTheorem 9.2 follow the same strategy. They are split into two parts. First,
we identify an event onto which the statistical behavior of the regularized
estimator fˆ can be controlled using only deterministic arguments. Then, we
prove that this event holds with a probability at least as large as the one in(38) in the case of Theorem 9.1 and as in (40) in the case of Theorem 9.2.
We first introduce this event which is common to the subgaussian and thebounded setups:)(
for allf ∈ FΩ0 :=(P − PN )Lf ≤ θ max r(2 max(kf − f ∗ k , ρ∗ ))2κ , kf − f ∗ k2κ
L2
where θ is a parameter appearing in the definition of r(·) in Definition 9.1
and Definition 9.2, κ ≥ 1 is the Bernstein parameter from Definition 2.1 andρ∗ is a radius satisfying the sparsity Equation (3).

20

P. ALQUIER AND V. COTTET AND G. LECUÉ

Proposition 9.1. Let λ be as in (37) (or equivalently as in (39)) andlet ρ∗ satisfy (3), on the event Ω0 , one hasfˆ − f ∗ ≤ ρ∗ ,fˆ − f ∗L2≤ r(2ρ∗ ) and E(fˆ) ≤ θr(2ρ∗ )2κ .

Proof. Denote ρ̂ = fˆ − f ∗ . We first prove that ρ̂ < ρ∗ . To that end, we
assume that the reverse inequality holds and show some contradiction. Assume that ρ̂ ≥ ρ∗ . Since ρ → r(2ρ)/ρ is non-increasing then by Lemma A.1,
ρ → ∆(ρ)/ρ is non-decreasing and so we have∆(ρ̂)∆(ρ∗ )
4
≥
≥ .
∗
ρ̂
ρ
5
Now, we consider two cases: either fˆ − f ∗r(2ρ̂).
First assume that fˆ − f ∗L2

L2≤ r(2ρ̂) or fˆ − f ∗L2>≤ r(2ρ̂). Since ∆(ρ̂) ≥ 4ρ̂/5 and h = fˆ −f ∗ ∈ ρ̂S ∩ r(2ρ̂)BL2 , it follows from the definition of the sparsity parameter∆(ρ̂) that there exists some f ∈ F such that kf − f ∗ k ≤ ρ̂/20 and for which
kf + hk − kf k ≥

4ρ̂
.
5

It follows that7ρ̂4ρ̂ ρ̂
−=.
fˆ −kf ∗ k = kf ∗ + hk−kf ∗ k ≥ kf + hk−kf k−2 kf − f ∗ k ≥5 10
10
Let us now introduce the excess regularized loss: for all f ∈ F ,Lλf = Lf + λ(kf k − kf ∗ k) = (`f + λ kf k) − (`f ∗ + λ kf ∗ k) .
On the event Ω0 , we havePN Lλfˆ = PN Lfˆ + λ fˆ − kf ∗ k ≥ (PN − P )Lfˆ + λ fˆ − kf ∗ k


2κ
7λρ̂
7λρ̂
∗
2κ
ˆ
+
≥ −θ max r(2ρ̂) , f − f= −θr(2ρ̂)2κ +
>0
10
10
L2
because by definition of λ, 7λρ̂ > 10θr(2ρ̂)2κ . Therefore, PN Lλfˆ > 0. But, byconstruction, one has PN Lλfˆ ≤ 0.
Then, assume that fˆ − f ∗L2> r(2ρ̂). In particular, fˆ ∈ C where C is theset introduced in Equation (2) from Remark 2.1 . By definition of fˆ we have

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

21

PN Lλfˆ ≤ 0 so it follows from the Bernstein condition (cf. Assumption 2.1)
that
h

i
2κ
≤ AP Lfˆ = A (P − PN )Lfˆ + PN Lλfˆ + λ kf ∗ k − fˆfˆ − f ∗
L2

(41)


≤ Aθ max r(2ρ̂) , fˆ − f ∗
2κ

2κ



L2

+ Aλ fˆ − f ∗ = Aθ fˆ − f ∗2κ
L2+ Aλρ̂.

Hence, if Aθ ≤ 1/2 thenr(2ρ̂)2κ ≤ fˆ − f ∗2κ
L2≤ 2Aλρ̂.

But, by definition of λ one has r(2ρ̂)2κ > 2Aλρ̂.
Therefore, none of the two cases is possible when one assumes that ρ̂ ≥ ρ∗and so we necessarily have ρ̂ < ρ∗ .
Now, assuming that fˆ − f ∗> r(2ρ∗ ) and following (41) step by stepL2

also leads to a contradiction, so fˆ − f ∗L2≤ r(2ρ∗ ). p Next, we prove theresult for the excess risk. One hasPN Lλfˆ = PN Lfˆ + λ fˆ − kf ∗ k = (PN − P )Lfˆ + P Lfˆ + λ fˆ − kf ∗ k


2κ
∗ 2κ
∗
ˆ
≥ −θ max r(2ρ ) , f − f+ P Lfˆ − λρ̂ ≥ −θr(2ρ∗ )2κ − λρ∗ + P LfˆL2−r(2ρ∗ )2κ1
r(2ρ∗ )2κ + P Lfˆ ≥+ P Lfˆ.
≥− θ+
2AA
In particular, if P Lfˆ > r(2ρ∗ )2κ /A then PN Lλfˆ > 0 which is not possible byconstruction of fˆ so we necessarily have P L ˆ ≤ r(2ρ∗ )2κ /A. fProposition 9.1 shows that fˆ satisfies some estimation and prediction
properties on the event Ω0 . Next, we prove that Ω0 holds with large probability in both subgaussian and bounded frameworks. We start with thesubgaussian framework. To that end, we introduce several tools.
Recall that the ψ2 -norm of a real valued random variable Z is defined bykZkψ2 = inf {c > 0 : Eψ2 (|Z|/c) ≤ ψ2 (1)}where ψ2 (u) = exp(u2 )−1 for all u ≥ 0. The space Lψ2 of all real valued random variables with finite ψ2 -norm is called the Orlicz space of subgaussianvariables. We refer the reader to [36, 37] for more details on Orlicz spaces.

22

P. ALQUIER AND V. COTTET AND G. LECUÉWe recall several facts on the ψ2 -norm and subgaussian processes. First,
it follows from Theorem 1.1.5 from [11] that kZkψ2 ≤ max(K0 , K1 ) if
E exp(λ|Z|) ≤ exp λ2 K12 ,(42)∀λ ≥ 1/K0 .

It follows from Lemma 1.2.2 from [11] that, if Z is a centered ψ2 randomvariable then, for all λ > 0,

(43)
E exp (λZ) ≤ exp eλ2 kZk2ψ2 .
Then, it follows from Theorem 1.2.1 from [11] that if Z1 , . . . , ZN are independent centered real valued random variables then
N
X

(44)

i=1

≤ 16

Zi
ψ2

N
X

!1/2
kZi k2ψ2.

i=1

Finally, let us turn to some properties of subgaussian processes. Let (T, d)be a pseudo-metric space. Let (Xt )t∈T be a random process in Lψ2 such thatfor all s, t ∈ T , kXt − Xs kψ2 ≤ d(s, t). It follows from the comment below
Theorem 11.2 p.300 in [29] that for all measurable set A and all s, t ∈ T ,


Z
1
−1
.
|Xs − Xt |dP ≤ d(s, t)P(A)ψ2
P(A)
A
Therefore, it follows from equation (11.14) in [29] that for every u > 0,
!
(45)

P

sup |Xs − Xt | > c0 (γ2 + Du)≤ ψ2 (u)−1s,t∈Twhere D is the diameter of (T, d), c0 is an absolute constant and γ2 is the
majorizing measure integral γ(T, d; ψ2 ) (cf. Chapter 11 in [29]). When T is asubset of L2 and d is the natural metric of L2 it follows from the majorizing
measure theorem that γ2 ≤ c1 w(T ) (cf. Chapter 1 in [39]).
Lemma 9.1.

Assume that Assumption 1.1 and Assumption 2.2 hold. Let

F 0 ⊂ F then for every u > 0, with probability at least 1 − 2 exp(−u2 )c0 L
sup |(P − PN )(Lf − Lg )| ≤ √w(F 0 ) + udL2 (F 0 )N
f,g∈F 0where d is the L2 metric and dL2 (F 0 ) is the diameter of (F 0 , d).

23

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONSProof. To prove Lemma 9.1, it is enough to show that ((P − PN )Lf )f ∈F 0√
has (L/ N )-subgaussian increments and then to apply (45) where γ2 ∼w(F 0 ) in this case.
Let us prove that for some absolute constant c0 : for all f, g ∈ F 0 ,√k(P − PN )(Lf − Lg )kψ2 ≤ c0 (L/ N ) kf − gkL2
It follows from (44) thatk(P − PN )(Lf − Lg )kψ2 ≤ 16

N
X
k(Lf − Lg )(Xi , Yi ) − E(Lf − Lg )k2ψ

!1/2

2

i=1

N2

16
= √ kζf,g kψ2 .
Nwhere ζf,g = (Lf − Lg )(X, Y ) − E(Lf − Lg ). Therefore, it only remains toshow that kζf,g kψ2 ≤ c1 L kf − gkL2 .
It follows from (42), that the last inequality holds if one proves that forall λ ≥ c1 /(L kf − gkL2 ),(46)

E exp (λ|ζf,g |) ≤ exp(c2 λ2 L2 kf − gk2L2 )for some absolute constants c1 and c2 . To that end, it is enough to provethat, for some absolute constant c3 – depending only on c1 and c2 – and all
λ > 0,
E exp (λ|ζf,g |) ≤ 2 exp(c3 λ2 L2 kf − gk2L2 ).
Note that if Z is a real valued random variable and  is a Rademacher
variable independent of Z then E exp(|Z|) ≤ 2E exp(Z). Hence, it follows
from a symmetrization argument (cf. Lemma 6.3 in [29]), (a simple versionof) the contraction principle (cf. Theorem 4.4 in [29]) and (43) that, for all
λ > 0,
E exp (λ|ζf,g |) ≤ 2E exp(λζf,g ) ≤ 2E exp (2λ(Lf − Lg )(X, Y ))
≤ 2E exp (2λ(f − g)(X)) ≤ 2E exp c4 λ2 L2 kf − gk2ψ2
where  is a Rademacher variable independent of (X, Y ) and where we usedin the last but one inequality that |Lf (X, Y ) − Lg (X, Y )| ≤ |f (X) − g(X)|a.s.. Proposition 9.2. We assume that Assumption 1.1, 2.2 and 2.1 hold.
Then the probability measure of Ω0 is at least as large as the one in (38).

24

P. ALQUIER AND V. COTTET AND G. LECUÉ

Proof. The proof is based on a peeling argument (cf. [42]) with respect tothe two distances naturally associated with this problem: the regularization
norm k·k and the L2 -norm k·kL2 associated with the design X. The peelingaccording to k·k is performed along the radii ρj = 2j ρ∗ for j ∈ N and thepeeling according to k·kL2 is performed within the class {f ∈ F : kf − f ∗ k ≤ρj } := f ∗ + ρj B along the radii 2i r(ρj ) for all i = 0, 1, 2, · · · up to a radiussuch that 2i r(ρj ) becomes larger than the radius of f ∗ + ρj B in L2 , that isfor all i ∈ Ij .
We introduce the following partition of the class F . We first introduce the”true model”, i.e. the subset of F where we want to show that fˆ belongs towith high probability:F0,0 = f ∈ F : kf − f ∗ k ≤ ρ0 and kf − f ∗ kL2 ≤ r(ρ0 )(note that ρ0 = ρ∗ ). Then we peel the remaining set F \F0,0 according to
the two norms: for every i ∈ I0 ,
F0,i = f ∈ F : kf − f ∗ k ≤ ρ0 and 2i−1 r(ρ0 ) < kf − f ∗ kL2 ≤ 2i r(ρ0 ) ,for all j ≥ 1 ,
Fj,0 = f ∈ F : ρj−1 < kf − f ∗ k ≤ ρj and kf − f ∗ kL2 ≤ r(ρj )and for every integer i ∈ Ij ,
Fj,i = f ∈ F : ρj−1 < kf − f ∗ k ≤ ρj and 2i−1 r(ρj ) < kf − f ∗ kL2 ≤ 2i r(ρj ) .
∗ = ρ B ∩ (2i r(ρ ))B
We also consider the sets Fj,ijj
L2 for all integers i and j.
Let j and i ∈ Ij be two integers. It follows from Lemma 9.1 that for anyu > 0, with probability larger than 1 − 2 exp(−u2 ),sup |(P − PN )Lf | ≤f ∈Fj,i(47)

sup∗ +f ∗
f,g∈Fj,i|(P − PN )(Lf − Lg )|


c0 L
∗
∗
≤√
w(Fj,i) + udL2 (Fj,i)
N∗ ) ≤ 2i+1 r(ρ ).
where dL2 (Fj,ijNote that for any ρ > 0, h : r → w(ρB ∩ rBL2 )/r is non-increasing(cf. Lemma A.2 in the Appendix) and√ note that, by definition of r(ρ) (cf.
Definition 9.1), h(r(ρ)) ≤ θr(ρ)2κ−1 N /(CL). Since h(·) is non-increasing,√∗ )/(2i r(ρ )) ≤ h(2i r(ρ )) ≤ h(r(ρ )) ≤ θr(ρ )2κ−1 N /(CL)we have w(Fj,i
j
j
j
j
√
∗ ) ≤ θ2i r(ρ )2κ N /(CL). Therefore, it follows from (47) forand so w(Fj,ij

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

25√
u = θ N (2(i−1)∨0 r(ρj ))2κ−1 /(2CL), if C ≥ 4c0 then, with probability at
least


(48)
1 − 2 exp −θ2 N (2(i−1)∨0 r(ρj ))4κ−2 /(4C 2 L2 ) ,for every f ∈ Fj,i ,|(P − PN )Lf | ≤ θ(2(i−1)∨0 r(ρj ))2κ
≤ θ max r(2 max(kf − f ∗ k , ρ∗ ))2κ , kf − f ∗ k2κ
L2 .
The result follows from a union bound. 
Now we turn to the proof of Theorem 9.1 under the boundedness assumption. The proof follows the same strategy as in the ”subgaussian case”: wefirst use Proposition 9.1 and then show (under the boundedness assumption)that event Ω0 holds with probability at least as large as the one in (40).
Similar to Proposition 9.2, we prove the following result under the boundedness assumption.
Proposition 9.3. We assume that Assumption 1.1, 2.3 and 2.1 hold.
Then the probability measure of Ω0 is at least as large as the one in (40).
Proof. Using the same notation as in the proof of Proposition 9.2, wehave for any integer j and i such that 2i r(ρj ) ≤ b that by Talagrand’sconcentration inequality: for any x > 0, with probability larger than 1−2e−x ,r
8x 69 LFj,i ∞ x(49)
Zj,i ≤ 2EZj,i + σ(LFj,i )
+
N
2N
where
Zj,i = sup |(P −PN )Lf |,f ∈Fj,iqσ(LFj,i ) = supEL2f andf ∈Fj,i

LFj,i ∞ = sup kLf k∞ .
f ∈Fj,iBy the Lipschitz assumption, one hasσ(LFj,i ) ≤ 2i+1 r(ρj ) and

LFj,i ∞ ≤ 2b.

Therefore, it only remains to upper bound the expectation EZj,i . Let 1 , . . . , Nbe a N i.i.d. Rademacher variables independent of the (Xi , Yi )’s. For all function f , we set
N
1 X
PN, f =i f (Xi )
N
i=1

26

P. ALQUIER AND V. COTTET AND G. LECUÉ

It follows from a symmetrization and a contraction argument (cf. Chapter 4
in [29]) that
EZj,i ≤ 4E sup |PN, (f −f ∗ )| ≤f ∈Fj,i4Rad(ρj B ∩ (2i r(ρj ))BL2 )√≤ (θ/12)2i r(ρj )2κ .
N

Now, we take x = c2 θ2 N (2i−1 r(ρj ))4κ−2 in (49) and note that 2i r(ρj ) ≤ b
and κ ≥ 1: with probability larger than(50)

1 − 2 exp(−c2 θN (2i r(ρj ))4κ−2 ),for any f ∈ Fj,i ,2κ√+ 69c2 θ2 b(2i−1 r(ρj ))4κ−2|(P − PN )Lf | ≤ θ2i−1 r(ρj )2κ /3 + 2 8c2 θ 2i−1 r(ρj )2κ  1√
≤ θ 2(i−1)∨0 r(ρj )+ 2 8c2 + 69c2 θb(2i r(ρj ))2κ−232κ  1√2κ−1(i−1)∨0≤θ 2
r(ρj )+ 2 8c2 + 69c2 θb3≤ θ max r(2 max(kf − f ∗ k , ρ∗ ))2κ , kf − f ∗ k2κ
L2
if c2 is defined by(51)c2 = min1
1,
48 207θb2κ−1.

We conclude with a union bound. 
Remark 9.1 (Technical comments). The machinery we used here toprove Theorems 9.2 and 9.1 is inspired by the technique from [28, 27]. In thelatter papers, estimation properties of regularized ERM are also obtained but
for the square loss. Here, we extend those results to Lipschitz loss functions.
Going from the square loss to Lipschitz loss functions is not straightforward.
It requires another machinery given that the homogeneity argument used in[28, 27] do not apply here. In a nutshell, this argument shows that if PN Lλf >0 (where Lλf is the regularized excess loss of f ) for all f ∈ F ∩ (f ∗ + r∗ SL2 )then it is also the case for all f such that kf − f ∗ kL2 ≥ r∗ (and therefore
the RERM is in f ∗ + r∗ BL2 ). This argument cannot be used for Lipschitz
loss function because there is no homogeneity between Lf and Lg when f −f ∗ = λ(g − f ∗ ) for some λ > 0. As a consequence, one needs to control
the oscillation of the process f → (PN − P )Lf on every shelves Fi,j in the
Lipschitz case. This requires a (double) peeling argument. Peeling arguments

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

27(see [42]) work only if one can sum all the deviation probabilities of the events
where the empirical process is controlled on each shell. This is an infinite sum
and therefore, one needs enough concentration to make this sum converging.
That is the reason why we assumed subgaussianity or boundedness in order tomake the peeling argument work. The weak stochastic framework consideredin [28, 27] would not be enough here because of this approach based on apeeling argument.
10. Proof of the optimality results in Section 4.
10.1. Proof of Theorem 4.3. For the sake of simplicity, assume that m ≥T so max(m, T ) = m. Fix r ∈ {1, . . . , T }. Fix x > 0 such that exp(x)/[1 +exp(x)] ≤ b, we define the set of matricesCx = A ∈ Rm×r : ∀(p, q), Ap,q ∈ {0, x}
andMx = {A ∈ Rm×T : A = (B| . . . |B|O), B ∈ Cx }where the block B is repeated bT /rc times (this construction is taken from [24]).
Varshamov-Gilbert bound (Lemma 2.9 in [41]) implies that there is a finite
subset M0x ⊂ Mx with card(M0x ) ≥ 2rm/8 + 1 with 0 ∈ M0x , and for any
distinct A, B ∈ M0x ,kA − Bk2S2 ≥and somrbT /rc 2 mT 2
x ≥
x
8
16

1
x2
kA − Bk2S2 ≥.
mT
16Then, for M ∈ M0x \ {0},




m T 
1 + exp(Mi,j )1 + exp(Mi,j )n XX 1
1
K(P0 , PM ) =
log
+ log
mT
2
2 exp(Mi,j )22
i=1 j=1




m T 
1 + exp(Mi,j )
n XX
1
=
log
− Mi,jmT2
2
i=1 j=1 
1 + exp(x)1≤ n log− x22≤ c(b)nx2

28

P. ALQUIER AND V. COTTET AND G. LECUÉ

where c(b) > 0 is a constant that depends only on b. So:
X
1
K(P0 , PA ) ≤ c(b)nx2 ≤ c(b) log(card(M0x ) − 1)card(M0x ) − 1
0A∈Mx

as soon as we chooserx≤log(card(M0x ) − 1)≤nrrm log(2)8n(note that the condition n ≥ rm log(2)/(8b2 ) implies that exp(x)/[1 +exp(x)] ≤ b). Then, Theorem 2.5 in [41] leads to the existence of β, c > 0such that


1 c
mr
inf sup PA
kM − Ak2S2 ≥ c
≥ β.
mT
N
c A∈M0Mx
10.2. Proof of Theorem 4.5. For the sake of simplicity, assume that m ≥T so max(m, T ) = m. Fix r ∈ {2, . . . , T } and assume that rT ≤ N ≤ mT .
We recall that {Ep,q : 1 ≤ p ≤ m, 1 ≤ p ≤ T } is the canonical basis of
Rm×T . We consider the following “blocks of coordinates”: for every 1 ≤ k ≤r − 1 and 1 ≤ l ≤ T ,(k − 1)mT
kmT
Bkl = Ep,l :
+1≤p<
+1
N
N
(note that (r − 1)mT /N + 1 ≤ m when rT ≤ N ≤ mT ). We also introduce
the “blocks” of “remaining” coordinates:(r − 1)mT
B0 = Ep,q :+ 1 ≤ p, 1 ≤ q ≤ T
NFor every σ = (σkl ) ∈ {0, 1}(r−1)×T , we denote by Pσ the probability
distribution of a pair (X, Y ) taking its values in Rm×T × {−1, 1} where X
is uniformly distributed over the basis {Ep,q : 1 ≤ p ≤ m, 1 ≤ p ≤ T } andfor every (p, q) ∈ {1, . . . , m} × {1, . . . , T },
σkl if Ep,q ∈ Bkl
Pσ [Y = 1|X = Ep,q ] =1otherwise.
We also introduce ησ (Ep,q ) = E[Y = 1|X = Ep,q ] = 2Pσ [Y = 1|X = Ep,q ]−1.
It follows from [46] that the Bayes rules minimizes the Hinge risk, that isfσ∗ ∈ argminf Eσ (Y − f (X))+ , where the minimum runs over all measurable

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

29

functions and Eσ denotes the expectation w.r.t. (X, Y ) when (X, Y ) ∼ Pσ ,is achieved by fσ∗ = sgn(ησ (·)). Therefore, fσ∗ (·) = Mσ∗ , · where for every(p, q) ∈ {1, . . . , m} × {1, . . . , T },

2σkl − 1 if Ep,q ∈ Bkl(Mσ∗ )pq == ησ (Ep,q ).
1otherwise.
In particular, Mσ∗ has a rank at most equal to r.
0 ) be in {0, 1}(r−1)T . We denote by ρ(σ, σ 0 ) theLet σ = (σp,q ), σ 0 = (σpq
Hamming distance between σ and σ 0 (i.e. the number of times the coordinates of σ and σ 0 are different). We denote by H(Pσ , Pσ0 ) the Hellinger
distance between the probability measures Pσ and Pσ0 . We haveZ p
2 2ρ(σ, σ 0 )pdPσ − dPσ0 =.
H(Pσ , Pσ0 ) =N
Then, if ρ(σ, σ 0 ) = 1, it follows that (cf. Section 2.4 in [41]), !
2 (P , P 0 ) NHσσ⊗N
H 2 (P⊗N
σ , Pσ 0 ) = 2 1 − 1 −
2
 !

1 N
=2 1− 1−
≤ 2(1 − e−2 ) := α.
NNow, it follows from Theorem 2.12 in [41], that
(52)

inf

max

σ̂ σ∈{0,1}(r−1)TE⊗Nσ kσ̂ − σkl1 ≥p(r − 1)T 
1 − α(1 − α/4)8where the infimum inf σ̂ runs over all measurable functions σ̂ of the data
(Xi , Yi )N
i=1 with values in R (note that Theorem 2.12 in [41] is stated forfunctions σ̂ taking values in {0, 1}(r−1)T but its is straightforward to extend
this result to any σ̂ valued in R) and E⊗Ndenotes the expectation w.r.t.
σ⊗N
those data distributed according to Pσ .
Now, we lower bound the excess risk of any estimator. Let fˆ be an estimator with values in R. Using a truncation argument it is not hard to seethat one can restrict the values of fˆ to [−1, 1]. In that case, We havehiEhinge (fˆ) = E |2ησ (X) − 1||fˆ(X) − fσ∗ (X)| = E|fˆ(X) − fσ∗ (X)|X=
|fˆ(Ep,q ) − fσ∗ (Ep,q )|P[X = Ep,q ]
p,q

X 1
≥
mT
kl

X
Ep,q ∈Bkl|fˆ(Ep,q ) − (2σpq − 1)| ≥2 X|σ̂kl − σpq |
N
kl

30

P. ALQUIER AND V. COTTET AND G. LECUÉ

where σ̂kl is the mean of {(fˆ(Ep,q ) + 1)/2 : Ep,q ∈ Bkl }. Then we obtain,
2
ˆ
E⊗N
inf
max
E⊗N kσ̂ − σkl1
σ Ehinge (f ) ≥N σ̂ σ∈{0,1}(r−1)T σ
fˆ σ∈{0,1}(r−1)T

inf

sup

and, using (52), we get
inf

sup

fˆ σ∈{0,1}(r−1)TˆE⊗Nσ Ehinge (f ) ≥ c0

rT
N



p
for c0 = 1 − α(1 − α/4) /4.

11. Proofs of Section 8. The proof of Proposition 8.1 may be foundin several papers (cf., for instance, [2]). Let us recall this argument since wewill be using it at a starting point to prove the Bernstein condition in thesubgaussian case.
Proof of Proposition 8.1. The logistic risk of a function f : X → R canbe written as P `f = E[g(X, f (X))] where for all x, a ∈ R, g(x, a) :=((1 + η(x))/2) log (1 + e−a )+((1 − η(x))/2) log (1 + ea ) and η(x) = E[Y |X =x] is the conditional expectation of Y given X = x.
Since f ∗ minimizes f → P `f over the convex class F , one has by the
first order condition that for every f ∈ F , E∂2 g(X, f ∗ (X))(f − f ∗ )(X) ≥ 0.
Therefore, it follows from a second order Taylor expansion that the excess
logistic loss of every f ∈ F is such that(53)

Elogistic (f ) = P Lf
Z 1
(1 − u)δ(f ∗ (X) + u(f − f ∗ )(X))du≥ E (f (X) − f ∗ (X))20

where δ(u) = ∂22 g(x, u) = eu /(1 + eu )2 for every u ∈ R.
Since |f ∗ (X)|, |f (X)| ≤ b a.s. then for every u ∈ [0, 1], |f ∗ (X) + u(f −f ∗ )(X)| ≤ 2b, a.s. and since δ(v) ≥ δ(2b) ≥ exp(−2b)/4 for every |v| ≤ 2b,
it follows from (53) that P Lf ≥ δ(2b) kf − f ∗ k2L2 . 
Proof of Proposition 8.2. Let t∗ ∈ RBl2 be such that f ∗ = ·, t∗ , wheref ∗ is an oracle in F = { ·, t : t ∈ RBl2 } w.r.t. the logistic loss risk. Let
f = ·, t ∈ F for some t ∈ RBl2 . It follows from (53) that the excess logistic
risk of f satisfies
Z 1 h
i
2
P Lf ≥E X, t∗ − t δ X, t∗ + u(t − t∗ )du.
0

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

31

The result will follow if one proves that for every t0 , t ∈ Rd ,
−1 !

q
2
2
min π, π kt0 k2 2π + kt0 k2
h
i
ktk22
2
q
√ .
(54) E X, t δ X, t0≥
8 2π
2π + kt0 k22 + (π − 1) kt0 k2⊥
Let us now prove (54). We write t = t⊥
0 + λt0 where t0 is a vector orthogonal to t0 and λ ∈ R. Since X, t⊥
and X, t0 are independent random0variables, we havehi2
E X, t δ X, t0
h
i 
h

i
2
2
2
E
,
= E X, t⊥
δ
X,
t
+
λ
E
X,
t
δ
X,
t
0
0
0
0

= t⊥
0

2
2

Eδ(kt0 k2 g) + λ2 kt0 k22 Eg 2 δ(kt0 k2 g)

where g ∼ N (0, 1) is standard Gaussian variable and we recall that δ(v) =ev /(1 + ev )2 for all v ∈ R. Now, it remains to lower bound Eδ(σg) andEg 2 δ(σg) for every σ > 0.
Since δ(v) ≥ exp(−|v|)/4 for all v ∈ R, one has for all σ > 0,Eδ(σg) ≥ E exp(−σ|g|)/4 = exp(σ 2 /2)P[g ≥ σ]/2
andEg 2 δ(σg) ≥ Eg 2 exp(−σ|g|)/4

σ exp(−σ 2 /2)
22√= (1/2) exp(σ /2) (1 + σ )P[g ≥ σ] −.
2πTherefore, for σ = kt0 k2 ,h2i2
E X, t δ X, t0≥ exp(σ 2 /2)P[g ≥ σ] t⊥
0
2


2 /2)

σ
exp(−σ2222√+ 2λ kt0 k2 exp(σ /2) 1 + σ P[g ≥ σ] −
2π
2

2
2
and since ktk22 = t⊥
0 2 + λ kt0 k2 , one has,
(55)





h
i
ktk22
1 − Φ(σ)
1 − Φ(σ)
22≥ √ min, (1 + σ )−σ
E X, t δ X, t0
φ(σ)
φ(σ)
2π

where φ and Φ denote the standard Gaussian density and distribution functions, respectively.

32

P. ALQUIER AND V. COTTET AND G. LECUÉWe lower bound the right-hand side of (55) using estimates on the Mills
ratio (1 − Φ)/φ that follows from Equation (10) in [17]: for every σ > 0,
1 − Φ(σ)
π
.
>√
2
φ(σ)
2π + σ + (π − 1)σ
Proof of Proposition 8.4. We follow a proof from [18]. We have
P Lf = E[ρτ (Y − f (X)) − ρτ (Y − f ∗ (X))]
no= E E[ρτ (Y − f (X)) − ρτ (Y − f ∗ (X))|X] .
For all x ∈ X , denote by Fx the c.d.f. associated with fx . We haveE[ρτ (Y − f (X))|X = x]
ZZ
= (τ − 1)(y − f (x))Fx (dy) + τ(y − f (x))Fx (dy)y<f (x)y≥f (x)ZZ=(y − f (x))Fx (dy) + (τ − 1) (y − f (x))Fx (dy)y≥f (x)RZ
Z=(1 − Fx (y))dy + (τ − 1)
yFx (dy) − f (x)y≥f (x)RZ= g(x, f (x)) + (τ − 1) yFx (dy)Rwhere g(x, a) = y≥a (1 − Fx (y))dy + (1 − τ )a. Note that ∂2 g(x, f ∗ (x)) = 0(can be checked by calculations but also obvious from the definition). SoR

E[ρτ (Y − f (X)) − ρτ (Y − f ∗ (X))|X = x]
Z f (x)∗= g(x, f (x)) − g(x, f (x)) =(f (x) − u)∂22 g(x, u)duf ∗ (x)Z f (x)1=(f (x) − u)fx (u)du ≥
C
∗
f (x)

Z f (x)(f (x) − u)du =f ∗ (x)(f (x) − f ∗ (x))2.
2C 2

It follows that
Equantile (f ) = P Lf ≥ E
(f (X) − f ∗ (X))2
2C


=

1
kf − f ∗ k2L2 .
2C

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

33

12. Empirical risk minimization with Lipschitz loss function. In
this section, we consider the case where we have no a priori knowledge on theoracle f ∗ such as “low dimensional structure” or “smoothness”. In that case,there is no reason to force some structure on the estimators and therefore
a natural procedure is the one minimizing the empirical risk itself (without
regularization):
!
N
X
1
(56)
f˜ ∈ argmin`f (Xi , Yi )
N
f ∈F
i=1

where ` is a Lipschitz loss function as considered in the previous sections
and F is a convex class of functions.
The aim of this section is to obtain estimation and prediction bounds for˜
f in the two subgaussian and bounded settings as introduced in Section 2.
As in the regularized case, the statistical performances of f˜ are driven by
fixed points, one for each of the two setups.
Definition 12.1. Let θ > 0. The complexity parameter in the subgaussian case r∗ is any point satisfying√
Lw (F ∩ (f ∗ + r∗ BL2 )) ≤ θr∗2κ N
where κ is the Bernstein parameter from Assumption 2.1.
In the bounded case, it is written as follows.
Definition 12.2. Let θ > 0. The complexity parameter in thebounded case r∗ is any point satisfying√
48Rad(F ∩ (f ∗ + r∗ BL2 )) ≤ θr∗2κ N
where κ is the Bernstein parameter from Assumption 2.1.
Explicit computations of r∗ in both subgaussian and bounded cases areavailable in the literature for various classes F (see, for instance, [19, 5, 26,
27, 32, 1, 6, 20]). An example in shape constrained regression is provided
below. Let us now state the main results of this section (we treat both cases
at the same time since they are identical in nature).
Theorem 12.1. Assume that Assumption 1.1, Assumption 2.1 and Assumption 2.2 (resp. Assumption 2.3) hold. Let r∗ be as in Definition 12.1
(resp. Definition 12.2) for some θ such that Aθ < 1. There exists a constant

34

P. ALQUIER AND V. COTTET AND G. LECUÉ

c0 depending only on L (resp. on b) such that, with probability larger than1 − exp(−c0 θ2 N r∗4κ−2 ), the ERM (56) f˜ satisfiesf˜ − f ∗L2≤ r∗ and E(f˜) ≤ θr∗2κ .

Proof of Theorem 12.1: As in Section 9, we introduce an event (whichis common to the subgaussian and the bounded setups) on which we canderive the statistical performances of f˜ using only deterministic arguments:onΩ00 := for all f ∈ F, (P − PN )Lf ≤ θ max r∗2κ , kf − f ∗ k2κ
L2
where θ is a parameter appearing in the definition of r∗ in Definition 12.1 andDefinition 12.2 and κ ≥ 1 is the Bernstein parameter from Definition 2.1.
Let us place ourselves on the event Ω00 . Let f ∈ F be a function in F suchthat kf − f ∗ kL2 > r∗ . We have
∗ 2κPN Lf = (PN − P )Lf + P Lf ≥ −θ kf − f ∗ k2κ
L2 + (1/A) kf − f kL2 > 0.

Since PN Lf˜ ≤ 0, we have f˜ − f ∗L2≤ r∗ on the event Ω00 . Let us now

prove the sharp oracle inequality. It follows from0 ≥ PN Lf˜ = (PN − P )Lf˜ + P Lf˜


2κ
2κ
∗
˜
≥ −θ max r∗ , f − f+ P Lf˜ = −θr∗2κ + P Lf˜
L2that θr∗2κ ≥ P Lf˜.
Let us prove that Ω00 holds at least with the exponential probability from
Theorem 12.1. The proof uses a peeling argument of the class F along the
shelvesnoFk = f ∈ F : 2k−1 r∗ < kf − f ∗ kL2 ≤ 2k r∗
for all integer k ≥ 1 and F0 = F ∩ (f ∗ + r∗ BL2 ). The peeling argument usedhere is similar to the one from Proposition 9.2 and 9.3 but it is simpler since
we do not have to peel simultaneously along the values of the distance to f ∗of the regularization norm.
Let us first consider the subgaussian case. It follows from Lemma 9.1 thatfor all k ∈ N and u > 0, with probability larger than 1 − 2 exp(−u2 ),c0 L
sup |(P − PN )(Lf − Lg )| ≤ √ (w(Fk ) + udL2 (Fk ))N
f,g∈FkREGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

35

where dL2 (Fk ) ≤ 2k+1 r∗ . Finally the result in the subgaussian case follows
from a union bound and the same arguments as in the proof of Proposition 9.2. The result in the bounded case is similar except that we use Talagrand’s concentration inequality instead of Lemma 9.1 and the argumentsfrom the proof of Proposition 9.3.
As a proof of concept we apply Theorem 12.1 to the isotonic regression
which is an example of a shape constrained regression problem [35, 12, 45,
13, 7, 23]. Unlike the majority of works on shape constrained regression,
we consider the classification problem with {−1, 1}-valued outputs where
one wants to fit a logistic function ft : x ∈ Rp → σ( x, t ) (where σ(u) =eu /(1 + eu ), ∀u ∈ R) with a constraint on the shape of the weights t. Notethat we do not assume that the log-odds ratio has a particular structure
satisfying a shape constraint since we do not make any assumption of the
distribution of Y |X but we want to predict Y by the best logistic functionft∗ having weights t∗ satisfying a constraint.

We consider the class of linear functionals F = ft (·) = ·, t : t ∈ I
indexed by isotonic vectors:(57)

I = {t = (tj )p1 ∈ Rp : t1 ≤ t2 ≤ · · · ≤ tp } .

We are given a dataset made of N i.i.d. pairs of random variables (Xi , Yi )N
i=1
distributed like (X, Y ) where the outputs Yi ’s take their values in {−1, 1}
and the Xi ’s take their values in Rp . Let R ≥ 1 and the ERM
!
N

1 X
(58)
t̃ ∈ argmin
log 1 + exp Xi , t.
t∈I,ktk2 ≤R N
i=1

Let us assume that the Xi ’s are distributed according to a standard Gaussian variable. In that case, it follows from Proposition 8.2 that the Bernsteincondition is satisfied with parameter κ = 1 and the subgaussian Assumption 2.2 is satisfied. Therefore, in order to apply Theorem 12.1, it only remains to compute the complexity parameter r∗ in the Gaussian case. To
that end, we need to upper bound the local Gaussian mean width of I. This
follows from [1, (D.12)] thatw(I ∩ rB`2 ) ≤ r log(ed)√and so one can take r∗ = log(ed)/(θ N ) in Definition 12.1 given that κ = 1.
We can therefore apply Theorem 12.1 and obtain the following result.

36

P. ALQUIER AND V. COTTET AND G. LECUÉ

Theorem 12.2. Assume that X is a standard Gaussian
vector in Rp .

2
With probability larger than 1 − C exp −C log (ep) , the isotonic logistic
regression estimator t̃ defined in (58) satisfiest̃ − t∗ 2 ≤log2 (ed)log(ed)√and Elogistic (t̃) = R(t̃) − R(t∗ ) ≤Nθ N

where t∗ ∈ argmint∈I,ktk2 ≤R E log(1 + exp( X, t )).
Note that other examples of applications of Theorem 12.1 in shape constrained regression can be obtained using the same strategy for other typeof constraints such as convex regression or unimodal regression by using theresults on the Gaussian mean widths from [6].
APPENDIX A: TECHNICAL LEMMAS
Lemma A.1.
decreasing.

If ρ → r(2ρ)/ρ is non-increasing then ρ → ∆(ρ)/ρ is non-

Proof. We have for all ρ > 0
∆(ρ)
=
inf
sup
H, G .
ρ
H∈S∩(r(2ρ)/ρ)BL2 G∈∂k·k(M ∗ )The result follows since ρ → S ∩ (r(2ρ)/ρ)BL2 is non-increasing. Lemma A.2.
non-increasing.

Let ρ > 0. The function h : r > 0 → w(ρB ∩ rBL2 )/r is

Proof. Let r1 ≥ r2 . By convexity of B and BL2 , we have(59) (ρB ∩r1 BL2 )/r1 = (ρ/r1 )B ∩BL2 ⊂ (ρ/r2 )B ∩BL2 = (ρB ∩r2 BL2 )/r2 .

REFERENCES[1] Dennis Amelunxen, Martin Lotz, Michael B. McCoy, and Joel A. Tropp. Living on
the edge: phase transitions in convex programs with random data. Inf. Inference,3(3):224–294, 2014.
[2] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Large margin classifiers:
Convex loss, low noise, and convergence rates. In NIPS, pages 1173–1180, 2003.
[3] Peter L Bartlett, Michael I Jordan, and Jon D McAuliffe. Convexity, classification,and risk bounds. Journal of the American Statistical Association, 101(473):138–156,
2006.

REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

37[4] Peter L. Bartlett and Shahar Mendelson. Empirical minimization. Probab. Theory
Related Fields, 135(3):311–334, 2006.
[5] Pierre Bellec. Localized gaussian width of m-convex hulls with applications to lasso
and convex aggregation. Technical report, Rutgers University, 2017.
[6] Pierre Bellec. Sharp oracle inequalities for least squares estimators in shape restricted
regression. Technical report, ENSAE, 2017. To appear in the annals of statistics.
[7] Pierre C. Bellec and Alexandre B. Tsybakov. Sharp oracle bounds for monotone andconvex regression through aggregation. J. Mach. Learn. Res., 16:1879–1892, 2015.
[8] Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification:a survey of some recent advances. ESAIM Probab. Stat., 9:323–375, 2005.
[9] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method ofmultipliers. Foundations and Trends R in Machine Learning, 3(1):1–122, 2011.
[10] Jian-Feng Cai, Emmanuel J Candès, and Zuowei Shen. A singular value thresholding
algorithm for matrix completion. SIAM Journal on Optimization, 20(4):1956–1982,
2010.
[11] Djalil Chafaı̈, Olivier Guédon, Guillaume Lecué, and Alain Pajor. Interactions between compressed sensing random matrices and high dimensional geometry, volume 37
of Panoramas et Synthèses [Panoramas and Syntheses]. Société Mathématique deFrance, Paris, 2012.
[12] Sabyasachi Chatterjee, Adityanand Guntuboyina, and Bodhisattva Sen. On riskbounds in isotonic and other shape restricted regression problems. Ann. Statist.,
43(4):1774–1800, 2015.
[13] Sourav Chatterjee. A new perspective on least squares under convex constraint. Ann.
Statist., 42(6):2340–2381, 2014.
[14] V. Cottet and P. Alquier. 1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation. preprint arXiv:1604.04191, to appear in Machine Learning,
2016.
[15] Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bull.
Amer. Math. Soc. (N.S.), 39(1):1–49 (electronic), 2002.
[16] Mark A Davenport, Yaniv Plan, Ewout van den Berg, and Mary Wootters. 1-bit
matrix completion. Information and Inference, 3(3):189–223, 2014.
[17] Lutz Dümbgen. Bounding standard gaussian tail probabilities. Technical report,
University of Bern, 2010.
[18] Andreas Elsener and Sara van de Geer. Robust low-rank matrix estimation. arXiv
preprint arXiv:1603.09071, 2016.
[19] Y. Gordon, A. E. Litvak, S. Mendelson, and A. Pajor. Gaussian averages of interpolated bodies and applications to approximate reconstruction. J. Approx. Theory,
149(1):59–73, 2007.
[20] Adityanand Guntuboyina and Bodhisattva Sen. Global risk bounds and adaptationin univariate convex regression. Probab. Theory Related Fields, 163(1-2):379–411,
2015.
[21] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure withrandomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):217–288, 2011.
[22] Cho-Jui Hsieh and Peder A Olsen. Nuclear norm minimization via active subspace
selection. In ICML, pages 575–583, 2014.
[23] Arlene K. H. Kim and Richard J. Samworth. Global rates of convergence in logconcave density estimation. Ann. Statist., 44(6):2756–2779, 2016.
[24] Vladimir Koltchinskii, Karim Lounici, Alexandre B Tsybakov, et al. Nuclear-norm

38

P. ALQUIER AND V. COTTET AND G. LECUÉ

penalization and optimal rates for noisy low-rank matrix completion. The Annals of
Statistics, 39(5):2302–2329, 2011.
[25] Guillaume Lecué. Optimal rates of aggregation in classification under low noise
assumption. Bernoulli, 13(4):1000–1022, 2007.
[26] Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes: Upper andminimax bounds. Technical report, CNRS, Ecole polytechnique and Technion - to appear in Topics in Learning Theory - Societe Mathématique de France, (S. Boucheron
and N. Vayatis Eds.), 2013.
[27] Guillaume Lecué and Shahar Mendelson. Regularization and the small-ball method
I: sparse recovery. Technical report, CNRS, Ecole Polytechnique and Technion - toappear in the Annals of Statistics, 2015.
[28] Guillaume Lecué and Shahar Mendelson. Regularization and the small-ball method
II: complexity dependent error rates. Technical report, CNRS, Ecole Polytechniqueand Technion - to appear in Journal of Machine Learnint Research, 2015.
[29] Michel Ledoux and Michel Talagrand. Probability in Banach spaces, volume 23 ofErgebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics andRelated Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and processes.
[30] Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of machine learning research,
11(Aug):2287–2322, 2010.
[31] Shahar Mendelson. Improving the sample complexity using global data. IEEE transactions on Information Theory, 48(7):1977–1991, 2002.
[32] Shahar Mendelson. On the performance of kernel classes. J. Mach. Learn. Res.,
4(5):759–771, 2004.
[33] Shahar Mendelson. Obtaining fast error rates in nonconvex situations. J. Complexity,
24(3):380–397, 2008.
[34] Shahar Mendelson and Joseph Neeman. Regularization in kernel learning. Ann.
Statist., 38(1):526–565, 2010.
[35] Mary Meyer and Michael Woodroofe. On the degrees of freedom in shape-restricted
regression. Ann. Statist., 28(4):1083–1104, 2000.
[36] M. M. Rao and Z. D. Ren. Theory of Orlicz spaces, volume 146 of Monographs andTextbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York, 1991.
[37] M. M. Rao and Z. D. Ren. Applications of Orlicz spaces, volume 250 of Monographs
and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York,
2002.
[38] Ingo Steinwart and Andreas Christmann. Support vector machines. Information
Science and Statistics. Springer, New York, 2008.
[39] Michel Talagrand. The generic chaining. Springer Monographs in Mathematics.
Springer-Verlag, Berlin, 2005. Upper and lower bounds of stochastic processes.
[40] Alexandre B. Tsybakov. Optimal aggregation of classifiers in statistical learning.
Ann. Statist., 32(1):135–166, 2004.
[41] Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Seriesin Statistics, 2009.
[42] Sara A. van de Geer. Applications of empirical process theory, volume 6 of Cambridge
Series in Statistical and Probabilistic Mathematics. Cambridge University Press,
Cambridge, 2000.
[43] Sara A Van de Geer. High-dimensional generalized linear models and the lasso. The
Annals of Statistics, pages 614–645, 2008.
[44] Vladimir N. Vapnik. Statistical learning theory. Adaptive and Learning Systems for
Signal Processing, Communications, and Control. John Wiley & Sons Inc., New York,REGULARIZED PROCEDURES WITH LIPSCHITZ LOSS FUNCTIONS

39

1998. A Wiley-Interscience Publication.
[45] Cun-Hui Zhang. Risk bounds in isotonic regression. Ann. Statist., 30(2):528–555,
2002.
[46] Tong Zhang. Statistical behavior and consistency of classification methods based onconvex risk minimization. Annals of Statistics, pages 56–85, 2004.
ENSAE, 3, avenue Pierre Larousse,92245 MALAKOFF. France.