Motivation
Oracle inequalities
Applications

Regularization with Lipschitz Loss
Pierre Alquier

Sequential, structured, and/or statistical learning
IHES - May 17, 2017
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Motivation : user ratings

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

8
8

10
3

7
9
6

8

4
9

10

3
9

4
6

10

10

8
10
7

10

8

2
7

9
3

Pierre Alquier

4

8Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Motivation : user ratings

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

8
8

10
3

7
9
6

8

4
9

10

3
9

4
6

10

10

8
10
7

10

8

2
7

???

4

8

9
3

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Motivation : user ratings

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

8
8

10
3

7
9
6

8

4
9

10

3
9

4
6

10

10

8
10
7

10

8

2
7

7

4

8

9
3

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

A possible model
Notation : hA, BiF = Tr(AT B). Let Ej,k be the matrix withzeros everywhere except the (j, k)-th entry equal to 1.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

A possible model
Notation : hA, BiF = Tr(AT B). Let Ej,k be the matrix withzeros everywhere except the (j, k)-th entry equal to 1.
Observations :Yi = hM ∗ , Xi iF + εi ,E(εi ) = 0

Xi takes values in the set of matrices {Ej,k }.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

A possible model
Notation : hA, BiF = Tr(AT B). Let Ej,k be the matrix withzeros everywhere except the (j, k)-th entry equal to 1.
Observations :Yi = hM ∗ , Xi iF + εi ,E(εi ) = 0

Xi takes values in the set of matrices {Ej,k }.
Idea : M ∗ is (approximately) low-rank.
E. Candès & T. Tao (2009). The power of convex relaxation : Near-optimal matrix completion.
IEEE Trans. Info. Theory.
E. Candès & Y. Plan (2010). Matrix completion with noise. Proceedings of the IEEE.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Penalized ERM
First idea :(M̂ ∈ arg min

N
1 X

N i=1

)
(Yi − hM, Xi iF )2 + λ.rank(M)but the rank is not convex...

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Penalized ERM
First idea :(M̂ ∈ arg min

N
1 X

N i=1

)
(Yi − hM, Xi iF )2 + λ.rank(M)but the rank is not convex...
(
)
N
1 X
2
M̂ ∈ arg min(Yi − hM, Xi iF ) + λkMk∗
N i=1
Minimax rates of convergence derived inV. Koltchinskii, K. Lounici, & A. Tsybakov (2011) Nuclear-norm penalization and optimal rates
for noisy low-rank matrix completion. Annals of Statistics.
O. Klopp (2014). Noisy low-rank matrix completion with general sampling distribution. Bernoulli.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Is the quadratic loss always a good idea ?

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

8
8

10
3

7
9
6

8

4
9

10

3
9

4
6

10

10

8
10
7

10

8

2
7

9
3

Pierre Alquier

4

8Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Is the quadratic loss always a good idea ?

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

8
8

10
3

7
9
6

8

4
9

10

3
9

4
6

10

10

8
10
7

10

8

2
7

???

4

8

9
3

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Is the quadratic loss always a good idea ?

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

8
8

10
3

7
9
6

8

4
9

10

3
9

4
6

10

10

8
10
7

10

8

2
7

[6,8]

4

8

9
3

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

The quantile loss... suggests to replace the quadratic loss by the quantile loss`τ (f (x), y ) = (y − f (x))[τ − 1(y − f (x) ≤ 0)].

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

The quantile loss... suggests to replace the quadratic loss by the quantile loss`τ (f (x), y ) = (y − f (x))[τ − 1(y − f (x) ≤ 0)].

(M̂ ∈ arg minN

1 X`τ (hM, Xi iF , Yi ) + λkMk∗
N i=1

)

Source : http ://www.lokad.com/
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

1-bit matrix completion

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

1-bit matrix completion

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

???

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

1-bit matrix completion

Stan
Pierre
Zoe
Bob
Oscar
Léa
Tony

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

1-bit matrix completion(M̂ ∈ arg min

N

1 X
1(sign(hM, Xi iF ) 6= Yi ) + λkMk∗
N i=1

Pierre Alquier)

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

1-bit matrix completion(M̂ ∈ arg min

N

1 X
1(sign(hM, Xi iF ) 6= Yi ) + λkMk∗
N i=1

)

Problem : the indicator function is not convex.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

1-bit matrix completion(M̂ ∈ arg min

N

1 X
1(sign(hM, Xi iF ) 6= Yi ) + λkMk∗
N i=1

)

Problem : the indicator function is not convex.
(
)
N
1 X
M̂ ∈ arg min`(hM, Xi iF , Yi ) + λkMk∗
N i=1
logistic loss `(y 0 , y ) = log(1 + exp(−y 0 y ))J. Laffond, O. Klopp, E. Moulines & J. Salmon (2014). Probabilistic low-rank matrix
completion on finite alphabets. NIPS.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

1-bit matrix completion(M̂ ∈ arg min

N

1 X
1(sign(hM, Xi iF ) 6= Yi ) + λkMk∗
N i=1

)

Problem : the indicator function is not convex.
(
)
N
1 X
M̂ ∈ arg min`(hM, Xi iF , Yi ) + λkMk∗
N i=1
logistic loss `(y 0 , y ) = log(1 + exp(−y 0 y ))J. Laffond, O. Klopp, E. Moulines & J. Salmon (2014). Probabilistic low-rank matrix
completion on finite alphabets. NIPS.

hinge loss `(y 0 , y ) = (1 − y 0 y )+ etc.
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Lipschitz losses

All the aforementionned losses :hinge,
logistic,quantile
are Lipschitz. And so are other popular losses :Huber,...

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

Outline of the talk1

Motivation
Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

2

Oracle inequalities
Notations and overview
The main ingredients
Sharp oracle inequality

3

Applications
Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

Outline of the talk1

Motivation
Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

2

Oracle inequalities
Notations and overview
The main ingredients
Sharp oracle inequality

3

Applications
Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

NotationsPairs (X1 , Y1 ), . . . , (XN , YN ) in X × R i.i.d from P.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

NotationsPairs (X1 , Y1 ), . . . , (XN , YN ) in X × R i.i.d from P.
A space E ⊆ L2 (P) of functions f : X → R equippedwith a norm k · k, generally different from k · kL2 . A
convex F ⊆ E .

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

NotationsPairs (X1 , Y1 ), . . . , (XN , YN ) in X × R i.i.d from P.
F ⊆ E ⊆ L2 (P), (E , k · k).
A loss function ` that is 1-Lipschitz :|`(f1 (x), y ) − `(f2 (x), y )| ≤ |f1 (x) − f2 (x)|.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

NotationsPairs (X1 , Y1 ), . . . , (XN , YN ) in X × R i.i.d from P.
F ⊆ E ⊆ L2 (P), (E , k · k).
A loss function `oraclef ∗ ∈ arg min EP [`(f (X ), Y )] .
{z}f ∈F |=R(f )

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

NotationsPairs (X1 , Y1 ), . . . , (XN , YN ) in X × R i.i.d from P.
F ⊆ E ⊆ L2 (P), (E , k · k).
A loss function `oracle f ∗ ∈ arg minf ∈F R(f ).
estimator :Penalized ERM
"

#
N
X
1
fˆ ∈ arg min`(f (Xi ), Yi ) + λkf k .
f ∈F
N i=1

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

Three main ingredients to study fˆ
The Bernstein condition with parameters A and κ
quantifies the “identifiability” of f ∗ .

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

Three main ingredients to study fˆ
The Bernstein condition with parameters A and κ .
The complexity parameter comp(B) measures the “size”
or “complexity” of (the unit ball B of) E . Allows to define
the complexity function
1
ρAcomp(B) 2κ
√r (ρ) =.
N

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

Three main ingredients to study fˆ
The Bernstein condition with parameters A and κ .
The complexity function
1
ρAcomp(B) 2κ
√.
r (ρ) =N
The sparsity function ∆(·) measures the size of the
sub-differential of k · k in a ρ-neighborhood of f ∗ . Find asolution ρ∗ to the sparsity equation∆(ρ∗ ) ≥ (4/5)ρ∗ .

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

Three main ingredients to study fˆ
The Bernstein condition with parameters A and κ .
The complexity function
1
ρAcomp(B) 2κ
√.
r (ρ) =
N
Find a solution ρ∗ to the sparsity equation∆(ρ∗ ) ≥ (4/5)ρ∗ .
Then with high probability,kfˆ − f ∗ k ≤ ρ∗ , kfˆ − f ∗ kL2 ≤ r (2ρ∗ ),R(fˆ) − R(f ∗ ) . [r (2ρ∗ )]2κ .
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition

The Bernstein condition
There is κ ≥ 1 and A > 0 such that∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and strongly convex losses∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and strongly convex losses∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

P. Bartlett, M. Jordan & J. McAuliffe (2006). Convexity, classification and risk bounds. JASA.

Theorem` is strongly convex ⇒ condition satisfied with κ = 1.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and strongly convex losses∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

P. Bartlett, M. Jordan & J. McAuliffe (2006). Convexity, classification and risk bounds. JASA.

Theorem` is strongly convex ⇒ condition satisfied with κ = 1.
Proof :

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and strongly convex losses∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

P. Bartlett, M. Jordan & J. McAuliffe (2006). Convexity, classification and risk bounds. JASA.

Theorem` is strongly convex ⇒ condition satisfied with κ = 1.
Proof :`(f (X ), Y ) + `(f ∗ (X ), Y )2−`f (X ) + f ∗ (X )Pierre Alquier

2

!
,Y

∗

2

≥ α[f (X ) − f (X )] .

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and strongly convex losses∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

P. Bartlett, M. Jordan & J. McAuliffe (2006). Convexity, classification and risk bounds. JASA.

Theorem` is strongly convex ⇒ condition satisfied with κ = 1.
Proof :`(f (X ), Y ) + `(f ∗ (X ), Y )2R(f ) + R(f ∗ )2−`

f (X ) + f ∗ (X )−R|

Pierre Alquier

2
f +f∗

!

2
{z

}

!
,Y

∗

2

≥ α[f (X ) − f (X )] .

∗ 2

≥ αkf − f kL .
2

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and strongly convex losses∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

P. Bartlett, M. Jordan & J. McAuliffe (2006). Convexity, classification and risk bounds. JASA.

Theorem` is strongly convex ⇒ condition satisfied with κ = 1.
Proof :`(f (X ), Y ) + `(f ∗ (X ), Y )2R(f ) + R(f ∗ )2−`

f (X ) + f ∗ (X )
2

−R
|

f +f∗

!

2
{z

}

∗

2

≥ α[f (X ) − f (X )] .

∗ 2

≥ αkf − f kL .
2

≥R(f ∗ )Pierre Alquier!
,Y

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and strongly convex losses∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

P. Bartlett, M. Jordan & J. McAuliffe (2006). Convexity, classification and risk bounds. JASA.

Theorem` is strongly convex ⇒ condition satisfied with κ = 1.
Proof :`(f (X ), Y ) + `(f ∗ (X ), Y )2R(f ) + R(f ∗ )2−`

f (X ) + f ∗ (X )
2

−R
|

f +f∗

!

2
{z

}

∗

2

≥ α[f (X ) − f (X )] .

∗ 2

≥ αkf − f kL .
2

≥R(f ∗ )
∗

!
,Y

∗ 2

R(f ) − R(f ) ≥ 2αkf − f kL .
2

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and the hinge loss
∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and the hinge loss
∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

G. Lecué (2006). Optimal Rates of Aggregation in Classification Under Low Noise Assumption.
PhD Thesis.

TheoremY ∈ {−1, 1}, η(x) := E(Y |X = x) and f ∗ (x) = sign(η(x)).
|η(X )| ≥ τ > 0 a.s. ⇒ Bernstein condition with κ ≥ 1.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The Bernstein condition and the hinge loss
∀f ∈ F ,∗kf − f ∗ k2κ
L2 ≤ A[R(f ) − R(f )].

G. Lecué (2006). Optimal Rates of Aggregation in Classification Under Low Noise Assumption.
PhD Thesis.

TheoremY ∈ {−1, 1}, η(x) := E(Y |X = x) and f ∗ (x) = sign(η(x)).
|η(X )| ≥ τ > 0 a.s. ⇒ Bernstein condition with κ ≥ 1.
1

P(|η(X )| ≤ t) ≤ ct κ−1 with κ > 1 ⇒ Bernstein.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The complexity parameter 1 - the bounded caseLet us assume that supf ∈F kf k∞ ≤ b.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The complexity parameter 1 - the bounded caseLet us assume that supf ∈F kf k∞ ≤ b.
Ex : matrix completion case, Xi ∈ {Ej,k } and
F = hM, ·iF , sup |Mi,j | ≤ b .
i,jPierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The complexity parameter 1 - the bounded caseLet us assume that supf ∈F kf k∞ ≤ b.
Ex : matrix completion case, Xi ∈ {Ej,k } and
F = hM, ·iF , sup |Mi,j | ≤ b .
i,jRademacher complexity
In this case we define, for B the unit ball in E ,N

1 X
comp(B) = E sup √i f (Xi ) , (i ) i.i.d Rademacher.
N i=1
f ∈B
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The complexity parameter 2 - subgaussian case
Put H = {f − g , (f , g ) ∈ F 2 }. Assume that ∀h ∈ H, ∀λ,|h(X )|
E exp λ≤ exp λ2 L2 .
khkL2

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The complexity parameter 2 - subgaussian case
Put H = {f − g , (f , g ) ∈ F 2 }. Assume that ∀h ∈ H, ∀λ,|h(X )|
E exp λ≤ exp λ2 L2 .
khkL2
Ex : X is Gaussian and
F = {ht, ·i , t ∈ Rp } .

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The complexity parameter 2 - subgaussian case
Put H = {f − g , (f , g ) ∈ F 2 }. Assume that ∀h ∈ H, ∀λ,|h(X )|
E exp λ≤ exp λ2 L2 .
khkL2
Ex : X is Gaussian and
F = {ht, ·i , t ∈ Rp } .
Gaussian mean width(Gh )h∈E canonical Gaussian process,comp(B) = E sup Gh .
h∈B
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The complexity function

The complexity function
Aρcomp(B)√r (ρ) :=
N

Pierre Alquier

 2κ1
.

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The sparsity equation
Example : the k · k1 penalty.

Idea : t ∗ sparse (easier to estimate) ↔ ∂k · k(t ∗ ) is a large set.
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The sparsity equation
The sparsity parameter∆(ρ) :=infsuph∈ρS∩r (2ρ)BL2 f ∈∂k·k(f ∗ )hh, f iwhere BL2 is the unit ball in L2 and S is the unit sphere in E .

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

The sparsity equation
The sparsity parameter∆(ρ) :=infsuph∈ρS∩r (2ρ)BL2 f ∈∂k·k(f ∗ )hh, f iwhere BL2 is the unit ball in L2 and S is the unit sphere in E .
The sparsity equation
Find (the smallest possible) ρ∗ such that∆(ρ∗ ) ≥ (4/5)ρ∗Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Notations and overview
The main ingredients
Sharp oracle inequality

Sharp oracle inequality
C stands for a constant that depends on A, κ, ... and maychange from line to line.
Theorem√Take λ = 720comp(B)/(7 N). Then with probability at least
h
i
2κ−1
1
1 − C exp −CN 2κ (ρ∗ comp(B)) κ
we have simultaneouslykfˆ − f ∗ k ≤ ρ∗ , kfˆ − f ∗ kL2 ≤ r (2ρ∗ ),R(fˆ) − R(f ∗ ) ≤ C [r (2ρ∗ )]2κ .
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Outline of the talk1

Motivation
Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

2

Oracle inequalities
Notations and overview
The main ingredients
Sharp oracle inequality

3

Applications
Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Outline of the talk1

Motivation
Matrix completion : the L2 point of view
Matrix completion : Lipschitz losses ?

2

Oracle inequalities
Notations and overview
The main ingredients
Sharp oracle inequality

3

Applications
Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : context

E = F = {ht, ·i , t ∈ Rp } equipped with k · k = k · k1 .
Logistic LASSO
"

#
N
X
1
log(1 − exp(−Yi f (Xi ))) + λkf k1 .
fˆ ∈ arg min
f ∈F
N i=1

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : Bernstein & complexity
Assume that X ∼ N (0, Ip ).

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : Bernstein & complexity
Assume that X ∼ N (0, Ip ).
Bernstein condition satisfied with κ = 1.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : Bernstein & complexity
Assume that X ∼ N (0, Ip ).
Bernstein condition satisfied with κ = 1.
comp(B) = E sup ht, X i = EkX k∞ ∼plog(p).

ktk1 ≤1

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : Bernstein & complexity
Assume that X ∼ N (0, Ip ).
Bernstein condition satisfied with κ = 1.
comp(B) = E sup ht, X i = EkX k∞ ∼plog(p).

ktk1 ≤1r (ρ) =

ρAcomp(B)√N

Pierre Alquier

 2κ1
∼

! 21
p
ρ log(p)√.
N

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : sparsity
Sparsity parameter∆(ρ) =infsuph∈ρS∩r (2ρ)BL2 f ∈∂k·k1 (f ∗ )Pierre Alquierhh, f i

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : sparsity
Sparsity parameter∆(ρ) =infsuph∈ρS∩r (2ρ)BL2 f ∈∂k·k1 (f ∗ )∗f ∈ ∂k · k1 (f ) ⇔hh, f i∗ fj = +1 when fj > 0,
fj = −1 when fj∗ < 0,
 f ∈ [−1, +1] when f ∗ = 0.
jj

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : sparsity
Sparsity parameter∆(ρ) =infsuph∈ρS∩r (2ρ)BL2 f ∈∂k·k1 (f ∗ )∗f ∈ ∂k · k1 (f ) ⇔hh, f i∗ fj = +1 when fj > 0,
fj = −1 when fj∗ < 0,
 f ∈ [−1, +1] when f ∗ = 0.
jjChoose h and define P as the projector on the sparsity pattern of f ∗ . Let s denote the sparsity of f ∗ .
hh, f i = h(I − P)h, f i + hPh, f i ≥ k(I − P)hk1 − kPhk1 = khk1 − 2kPhk1 = ρ − 2kPhk1|{z}f well chosen

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : sparsity
Sparsity parameter∆(ρ) =infsuph∈ρS∩r (2ρ)BL2 f ∈∂k·k1 (f ∗ )∗f ∈ ∂k · k1 (f ) ⇔hh, f i∗ fj = +1 when fj > 0,
fj = −1 when fj∗ < 0,
 f ∈ [−1, +1] when f ∗ = 0.
jjChoose h and define P as the projector on the sparsity pattern of f ∗ . Let s denote the sparsity of f ∗ .
hh, f i = h(I − P)h, f i + hPh, f i ≥ k(I − P)hk1 − kPhk1 = khk1 − 2kPhk1 = ρ − 2kPhk1|{z}f well chosen√√√
kPhk1 ≤ skPhk2 ≤ skhk2 ≤ sr (2ρ)

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : sparsity
Sparsity parameter∆(ρ) =infsuph∈ρS∩r (2ρ)BL2 f ∈∂k·k1 (f ∗ )∗f ∈ ∂k · k1 (f ) ⇔hh, f i∗ fj = +1 when fj > 0,
fj = −1 when fj∗ < 0,
 f ∈ [−1, +1] when f ∗ = 0.
jjChoose h and define P as the projector on the sparsity pattern of f ∗ . Let s denote the sparsity of f ∗ .
hh, f i = h(I − P)h, f i + hPh, f i ≥ k(I − P)hk1 − kPhk1 = khk1 − 2kPhk1 = ρ − 2kPhk1|{z}f well chosen√√√
kPhk1 ≤ skPhk2 ≤ skhk2 ≤ sr (2ρ)

Sparsity equation∆(ρ) ≥ (4/5)ρ ⇔ ρ such that
Pierre Alquier√ρ≥ C s.
r (2ρ)

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : solving the sparsity equation! 12plog(p)√.
r (ρ) ∼
N
!
√
√
ρ
ρ N
C s≤
∼ p
.
r (2ρ)log(p)
ρ

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : solving the sparsity equation! 12plog(p)√.
r (ρ) ∼
N
!
√
√
ρ
ρ N
C s≤
∼ p
.
r (2ρ)log(p)rlog(p)ρ∗ ∼ s.
N
ρ

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : solving the sparsity equation! 12plog(p)√.
r (ρ) ∼
N
!
√
√
ρ
ρ N
C s≤
∼ p
.
r (2ρ)log(p)rlog(p)ρ∗ ∼ s.
Nr
s log(p)∗r (ρ ) ∼.
N
ρ

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic LASSO : conclusion
TheoremTake λ ∼plog(p)/N. Then with probability at least
1 − C exp [−Cs log(p)]we have simultaneouslyrkfˆ − f ∗ k1 ≤ Cslog(p),
Nrs log(p),Ns log(p)R(fˆ) − R(f ∗ ) ≤ C.
Nkfˆ − f ∗ k2 ≤ C

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

The SLOPE penalty

ktk
comp(B)ρ∗r (ρ∗ )

LASSO
Pp
|ti |
pi=1
log p
p
s
√
log p
N
s
log p
N

SLOPE

Pp q
log epi |t(i) |
i=1
1
ep
s
√ log
s
N
s
ep
log
N
s

where |t(1) | ≥ · · · ≥ |t(p) |.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Logistic SLOPE : conclusion
Theorem√Take λ ∼ 1/ N. Then with probability at least
1 − C exp [−Cs log(ep/s)]
we have simultaneouslyrkfˆ − f ∗ k1 ≤ Cslog(ep/s),Nrs log(ep/s),Ns log(ep/s)
R(fˆ) − R(f ∗ ) ≤ C.
Nkfˆ − f ∗ k2 ≤ C

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Matrix completion : context

E = F = {hM, ·iF , M ∈ [−1, +1]m×p } with k · k = k · k∗ .
Matrix completion via hinge loss + nuclear norm
"
#
N
X
1
fˆ ∈ arg min(1 − Yi f (Xi ))+ + λkf k∗ .
f ∈F
N i=1

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Matrix completion : context

E = F = {hM, ·iF , M ∈ [−1, +1]m×p } with k · k = k · k∗ .
Matrix completion via hinge loss + nuclear norm
"
#
N
X
1
fˆ ∈ arg min(1 − Yi f (Xi ))+ + λkf k∗ .
f ∈F
N i=1
Assume that X is uniformly distributed on {Ej,k }.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Matrix completion : Bernstein and complexity
Obvious that f ∗ (Ej,k ) = sign(hEj,k , M ∗ i) = sign(η(Ej,k )). As
soon as |η(Ej,k )| ≥ β > 0 then Bernstein satisfied with κ = 1.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Matrix completion : Bernstein and complexity
Obvious that f ∗ (Ej,k ) = sign(hEj,k , M ∗ i) = sign(η(Ej,k )). As
soon as |η(Ej,k )| ≥ β > 0 then Bernstein satisfied with κ = 1.
comp(B) = E

=E

N
1 X
i hM, Xi i = E
sup√N
kMk∗ ≤1
kMk∗ ≤1
i =1

sup

N
1 X
i Xi
√
N i =1

s
∼

*

N
1 X
M, √
i Xi
N i =1+log(m + p)min(m, p)op

thanks to “matrix Bernstein” inequality.

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Matrix completion : Bernstein and complexity
Obvious that f ∗ (Ej,k ) = sign(hEj,k , M ∗ i) = sign(η(Ej,k )). As
soon as |η(Ej,k )| ≥ β > 0 then Bernstein satisfied with κ = 1.
comp(B) = E

=E

N
1 X
i hM, Xi i = E
sup√N
kMk∗ ≤1
kMk∗ ≤1
i =1

sup

N
1 X
i Xi
√
N i =1

s
∼

*

N
1 X
M, √
i Xi
N i =1+log(m + p)min(m, p)op

thanks to “matrix Bernstein” inequality.

sr (ρ) ∼

ρlog(m + p)
N min(m, p)

Pierre Alquier!1/2.

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Matrix completion : sparsity

Sparsity equation∆(ρ) ≥ (4/5)ρ ⇔ ρ such thatpρ
≥ C rank(M ∗ )mp.
r (2ρ)

Put r = rank(M ∗ ).

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

Matrix completion : conclusion
TheoremTake λ ∼at leastplog(m + p)/[N min(m, p)]. Then with probability
1 − C exp [−Cr (m + p) log(m + p)]

we have simultaneouslyskfˆ − f ∗ k∗ ≤ Cr

log(m + p),
N min(m, p)rr max(m, p) log(m + p),Nr max(m, p) log(m + p)
R(fˆ) − R(f ∗ ) ≤ C.
Nkfˆ − f ∗ kF ≤ C

Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions

Motivation
Oracle inequalities
Applications

Logistic LASSO
Logistic SLOPE
Matrix completion with hinge loss

P. Alquier, V. Cottet & G. Lecué (2017). Estimation Bounds and Sharp Oracle Inequalities ofRegularized Procedures with Lipschitz Loss Functions. Preprint arxiv :1702.01402.

Jupyter notebooks :https://sites.google.com/site/vincentcottet/code
Thank you !
Pierre Alquier

Regularized Procedures with Lipschitz Loss Functions