Electronic Journal of Statistics
ISSN: 1935-7524

A sharp oracle inequality for
Graph-Slope

arXiv:1706.06977v2 [math.ST] 20 Nov 2017

Pierre C Bellec
Department of Statistics & Biostatistics,
Rutgers, The State University of New Jersey,
501 Hill Center, Busch Campus,
110 Frelinghuysen Road, Piscataway, NJ 08854,
e-mail: pcb71@stat.rutgers.edu
url: http://www.stat.rutgers.edu/home/PCB71/

and
Joseph Salmon∗
LTCI, Télécom ParisTech,
Université Paris-Saclay, 75013, Paris,
e-mail: first.lastname@telecom-paristech.fr
url: http://josephsalmon.eu

and
Samuel Vaiter∗
CNRS & IMB, Université de Bourgogne,
9 avenue Alain Savary, 21000, Dijon,
e-mail: samuel.vaiter@u-bourgogne.fr
url: http://samuelvaiter.com
Abstract:
Following recent success on the analysis of the Slope estimator, we provide a sharp oracle inequality in term of prediction error for Graph-Slope,
a generalization of Slope to signals observed over a graph. In addition to
improving upon best results obtained so far for the Total Variation denoiser (also referred to as Graph-Lasso or Generalized Lasso), we propose
an efficient algorithm to compute Graph-Slope. The proposed algorithm is
obtained by applying the forward-backward method to the dual formulation of the Graph-Slope optimization problem. We also provide experiments
showing the practical applicability of the method.
MSC 2010 subject classifications: Primary 62G08; Secondary 62J07.
Keywords and phrases: denoising, graph signal regularization, oracle
inequality, convex optimization.

Contents
1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Model and notation . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 The Graph-Slope estimator . . . . . . . . . . . . . . . . . . . . .
∗ J.

2
4
5

Salmon and S. Vaiter were supported by the CNRS PE1 “ABS” grant.
1
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

2
3

Theoretical guarantees: sharp oracle inequality .
Numerical experiments . . . . . . . . . . . . . . .
3.1 Algorithm for Graph-Slope . . . . . . . . .
3.2 Synthetic experiments . . . . . . . . . . . .
3.3 Example on real data: Paris roads network .
A Preliminary lemmas . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

2

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

6
11
11
13
15
17
19

1. Introduction
Many inference problems of interest involve signals defined on discrete graphs.
This includes for instance two-dimensional imaging but also more advanced
hyper-spectral imaging scenarios where the signal lives on a regular grid. Two
types of structure arise naturally in such examples: The first type of structures
comes from regularity or smoothness of the signal, which led to the development
of wavelet methods. The second type of structure involves signals with few sharp
discontinuities. For instance in one dimension, piecewise constant signals appear
when transition states are present, the graph being a 1D path. In imaging, where
the underlying graph is a regular 2D grid, occlusions create piece-wise smooth
signals rather than smooth ones.
This paper studies regularizers for signals with sharp discontinuities. A popular choice in imaging is the Total Variation (TV) regularization [24]. For 1D
signals, TV regularization has also long been used in statistics [18]. If an additional `1 regularization is added, this is sometimes referred to as the fused Lasso
[30, 32, 13].
A natural extension of such methods to arbitrary graphs relies on `1 analysis
penalties [15] which involve the incidence matrix of the underlying graph, see
for instance [25] or the Edge Lasso of [26]. Such penalties have the form
pen : β → λkD> βk1 ,
where λ > 0 is a tuning parameter and D> is the (edge-vertex) incidence matrix
of the graph defined below, and β represents the signal to be recovered. This
approach is notably different from contributions in machine learning where `2
penalties, i.e., Laplacian regularization, have been considered for spectral clustering [27, 20] (see also [33] for a review). Theoretical results in favor of the `1
norm instead of the squared `2 norm are studied in [25].
Penalties based on `0 regularization with the graph incidence matrix have
recently been analyzed [16], including an analysis of their approximation algorithm. They are of interest as they do not suffer from the (shrinkage) bias
created by the convex `1 norm. However, such methods present the difficulty
that in the general case they lead to non-convex problems. Note that the 1D
path is an exception since the associated optimization problem can be solve
using dynamic programming [1]. Concerning the bias reduction though, simpler
remedies could be used, including least-squares refitting on the model space
associated, applying for instance the CLEAR method [14].
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

3

Following the introduction of the Slope regularization in the context of high
dimensional regression [10], we propose Graph-Slope, its generalization to contexts where the signal is supported on a graph. In linear regression, Slope [10]
is defined as follows. Given p tuning parameters λ1 ≥ λ2 ≥ · · · ≥ λp ≥ 0 with
at least one strict inequality, define the ordered `1 norm by
kθk[λ] =

p
X

λj |θ|↓j ,

(1.1)

j=1

where for any θ ∈ Rp , we use the notation1 (|θ|↓1 , . . . , |θ|↓p ) for the non-increasing
rearrangement of its amplitudes (|θ1 |, . . . , |θp |). Then, given a design matrix
X ∈ Rn×p and a response vector y ∈ Rn , the Slope estimator is defined as a
solution of the minimization problem
min

b∈Rp

1
ky − Xβk2 + kβk[λ] .
2n

If the parameters λ1 , . . . , λp are all equal, then Slope is equal to the Lasso with
tuning parameter λ1 .
Slope presents several advantages compared to Lasso in sparse linear regression. First, Slope provably controls the False Discovery Rate (FDR) for orthogonal design matrices [10] and experiments show that this property is also
satisfied for some non-orthogonal design matrices [10]. Second, it appears that
Slope has more power than Lasso in the sense that Slope will discover more
nonzero coefficients of the unknown target vector [10]. An interpretation of this
phenomenon is that Lasso shrinks small coefficients too heavily and may thus
miss the smallest nonzero coefficients of the target vector. On the other hand,
the Slope penalty induces less shrinkage on small coefficients, leading to more
power. Third, while Lasso with the universal parameter is known to achieve the
rate of estimation of order (s/n) log(p) (where s is the sparsity of the unknown
target vector, n the number of measurements and p the number of covariates),
Slope achieves the optimal rate of estimation of order (s/n) log(p/s) [28, 4].
We propose a theoretical and experimental analysis of Graph-Slope, the counterpart estimator of Slope for signals defined on graphs. Graph-Slope is defined
in the next section. Our theoretical contribution for Graph-Slope borrows some
technical details recently introduced in [17] to control the Mean Squared Error
(MSE) for the Generalized Lasso.
Last but not least, we provide an efficient solver to compute the Graph-Slope
estimator. It relies on accelerated proximal gradient descent to solve the dual
formulation [3, 12, 22]. To obtain an efficient solver, we leverage the seminal
contribution made in [36] showing the link between ordered `1 norm (1.1) and
isotonic regression. Hence, we can use fast implementations of the PAVA algorithm (for Pool Adjacent Violators Algorithm, see for instance [6]), available for
instance in scikit-learn [23] for this purpose. Numerical experiments illustrate the benefit of Graph-Slope, in particular in terms of True Discovery Rate
(TDR) performance.
1 following

the notation considered in [7]
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

4

A high level interpretation of our simulation results is as follows. In the
model considered in this paper, a sharp discontinuity of the signal corresponds
to an edge of the graph with nonzero coefficient. Since Graph-Lasso uses an
`1 -penalty, the penalty level is uniform across all edges of the graph. Edges with
small coefficients are too heavily penalized with Graph-Lasso. Using GraphSlope lets us reduce the penalty level on the edges with small coefficients. This
leads to the discovery of more discontinuities of the true signal as compared to
Graph-Lasso.
1.1. Model and notation
Let G = (V, E) be an undirected and connected graph on n vertices, V = [n],
and p edges, E = [p]. This graph can be represented by its edge-vertex incidence
p×n
matrix D> = D>
(we drop the reference to G when no ambiguity is
G ∈ R
possible) defined as


+1, if v = min(i, j)
(D> )e,v = −1, if v = max(i, j) ,


0,
otherwise
where e = {i, j}. The matrix L = DD> is the so-called graph Laplacian of G.
The Laplacian L is invariant under a change of orientation of the graph.
For any u ∈ Rp , we denote by kuk0 the pseudo `0 norm of u : kuk0 = |{j ∈
[p] : uj 6= 0}|, and for any matrix A, we denote by A† its Moore-Penrose
pseudo-inverse. The canonical basis of Rp is denoted (e1 , . . . , ep ).
For any norm k · k on Rn , the associated dual norm k · k∗ reads at v ∈ Rn
kvk∗ = sup hv, βi .
kβk61

As a consequence, for every (β, v) ∈ Rn × Rn , one has hβ, vi 6 kβkkvk∗ .
In this work, we consider the following denoising problem for a signal over
a graph. Assume that each vertex i ∈ [n] of the graph carries a signal βi? . For
each vertex i ∈ [n] of the graph, one observes yi , a noisy perturbation of βi? . In
vector form, one observes the vector y ∈ Rn and aims to estimate β ? ∈ Rn , i.e.,
y = β? + ε ,
where ε ∼ N (0, σ 2 Idn ) is a noise vector. We will say that an edge e = {i, j} of
the graph carries the signal (D> β ? )e . In particular, if two vertices i and j are
neighbours and if they carry the same value of the signal, i.e., βi? = βj? , then
the corresponding edge e = {i, j} carries the constant signal. The focus of the
present paper is on signals β ? that have few discontinuities. A signal β ? ∈ Rn
has few discontinuities if D> β ? has few nonzero coefficients, i.e., kD> β ? k0 is
small, or equivalently if most edges of the graph carry the constant signal. In
particular, if kD> β ? k0 = s, we say that β ? is a vector of D> -sparsity s.
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

5

1.2. The Graph-Slope estimator
We consider in this paper the so-called Graph-Slope variational scheme:
β̂ := β̂ GS ∈ argmin
β∈Rp

1
ky − βk2 + kD> βk[λ] ,
2n

where
>

kD βk[λ] =

p
X

(1.2)

λj |D> β|↓j ,

j=1
p

with λ = (λ1 , . . . , λp ) ∈ R satisfying λ1 > λ2 > · · · > λp ≥ 0, and using for any
vector θ ∈ Rp the notation2 (|θ|↓1 , . . . , |θ|↓p ) for the non-increasing rearrangement
of its amplitudes (|θ1 |, . . . , |θp |). According to [10], k · k[λ] is a norm over Rp if
and only if λ1 > λ2 > · · · > λp ≥ 0 with at least one strict inequality. This
is a consequence of the observation that if λ1 > λ2 > · · · > λp ≥ 0 then one
can rewrite the Slope-norm of θ as thePmaximum over all τ ∈ Sp (the set of
p
permutations over [p]), of the quantity i=1 λj |θτ (j) |:
kθk[λ] = max

τ ∈Sp

p
X
j=1

λj |θτ (j) | =

p
X

λj |θ|↓j .

j=1

The Generalized Lasso (also sometimes referred to as TV denoiser) relies on
`1 regularization. It was recently investigated in [17, 25], and can be defined as
β̂ GL ∈ argmin
β∈Rp

1
ky − βk2 + λ1 kD> βk1 ,
2n

(1.3)

where k · k1 is the standard `1 norm, and λ1 > 0 is a tuning parameter.
If λ1 = λ2 = · · · = λp then kθk[λ] = λ1 kθk1 for all θ ∈ Rp , so that the
minimization problems (1.3) and (1.2) are the same. On the other hand, if
λj > λj+1 for some j = 1, . . . , p − 1, then the optimization problems (1.3) and
(1.2) differ. For instance, if λ1 > λ2 > 0, all coefficients of D> β are equally
penalized in the Graph-Lasso (1.3), while coefficients of D> β are not uniformly
penalized in the Graph-Slope optimization problem (1.2). Indeed, in the GraphSlope optimization problem (1.2), the largest coefficient of D> β is penalized
as in (1.3) but smaller coefficients of D> β receive a smaller penalization. The
Graph-Slope optimization problem (1.2) is more flexible than (1.3) as it allows
the smaller coefficients of D> β to be less penalized than its larger coefficients.
We will see in the next sections that this flexibility brings advantages to both
the theoretical properties of β̂ GS as well as its performance in simulations, as
compared to β̂ GL .
2 following

the notation from [7].

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

6

2. Theoretical guarantees: sharp oracle inequality
We can now state the main theoretical result of the paper, a sharp oracle inequality for the Graph-Slope. For any integer s and weights λ = (λ1 , . . . , λp ),
define
s
X
1/2
Λ(λ, s) =
.
(2.1)
λ2j
j=1

Theorem 2.1. Assume that the Graph-Slope weights λ1 ≥ · · · ≥ λp ≥ 0 are
such that the event
1
(2.2)
kD† εk∗[λ] ≤ 1/2
n
has probability at least 1/2. Then, for any δ ∈ (0, 1), we have with probability at
least 1 − 2δ


!2
p
1
1 3nΛ(λ, s) σ + 2σ 2 log(1/δ) 
1

√
kβ̂−β ? k2 ≤ inf  infn
kβ − β ? k2 +
+
 ,
β∈R
n
n
2n
2κ(s)
n
s∈[p]
kD> βk0 ≤s

(2.3)
where Λ(·, ·) is defined in (2.1) and the compatibility factor κ(s) is defined as


kvk
κ(s) ,
inf P
.
(2.4)
> ↓
kD> vk2
v∈Rn :3Λ(λ,s)kD> vk2 > p
j=s+1 λj |D v|j
Proof. Let β be a minimizer of the right hand side of (2.3) and let s = kD> βk0 .
Define the function f (·) by


p
X
↓
e> v + nΛ(λ, s)kD> vk2 − n
λj |D> v|j  .
f (e) =
sup
v∈Rn :kvk=1

j=s+1

Let also w = (β̂ − β)/(kβ̂ − βk). By Lemma A.3 and Lemma A.1 with α = 0,
for any z ∈ Rp , we have
1
(kβ̂−zk2 − kβ − zk2 + kβ̂ − βk2 )
2
≤ε> (β̂ − β) + nkD> βk[λ] − nkD> β̂k[λ] ,
≤ε> (β̂ − β) + nΛ(λ, s)kD> (β̂ − β)k2 − n

p
X

λj |D> (β̂ − β)|↓j ,

j=s+1
p


X
=kβ̂ − βk ε> w + nΛ(λ, s)kD> wk2 − n
λj |D> w|↓j ,
j=s+1

1
1
≤kβ̂ − βkf (ε) ≤ f (ε)2 + kβ̂ − βk2 ,
2
2
where for the last inequality we used the elementary inequality 2ab ≤ a2 + b2 .
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

7

By Lemma A.4 we have Idn = (Idn − Π) + Π with Idn − Π = (D> )† D> and
where Π is the orthogonal projection onto ker(D> ). Furthermore, ker(D> ) has
dimension 1 so that kΠεk22 /σ 2 is a χ2 random variable with 1 degree of freedom.
Thus for any v ∈ Rn with kvk = 1 we have
ε> v = ε> Πv + ε> (Idn − Π)v ≤ kΠεk2 + ε> (Idn − Π)v.
Let us define the function g(·) by

g(e) =

>

sup
v∈Rn :kvk=1

>

e (Idn − Π)v + nΛ(λ, s)kD vk2 − n

p
X

(2.5)


λj |D

>

v|↓j  .

j=s+1

Then, by the definition of f, g and (2.5), we have almost surely f (ε) ≤ kΠεk2 +
2
g(ε). By a standard bound
p on χ random variable with 1 degree of freedom, we
have P(kΠεk2 ≤ σ + σ 2 log(1/δ)) ≥ 1 − δ. Furthermore, the function g is is
1-Lipschitz and ε ∼ N (0, σ 2 Idn ). By the Gaussian concentration theorem [11,
Theorem 10.17], we have


p
P g(ε) ≤ Med[g(ε)] + σ 2 log(1/δ) ≥ 1 − δ ,
where Med[g(ε)] is the median of the random variable g(ε). Combining these
two probability
bounds with the union bound, we obtain f (ε) ≤ Med[g(ε)] +
p
σ + 2σ 2 log(1/δ) with probability at least 1 − 2δ.
To complete the proof, it remains to show that
Med[g(ε)] ≤ (3n/2)Λ(λ, s)/κ(s) .

(2.6)

By definition of the median, it is enough to show that
P(g(ε) ≤ (3n/2)Λ(λ, s)/κ(s)) ≥ 1/2.

(2.7)

By Lemma A.4 and the fact that Idn − Π = (D> )† D> , we obtain that for all v,
ε> (Idn − Π)v = ε> (D> )† D> v
≤ k((D> )† )> εk∗[λ] kD> vk[λ] = kD† εk∗[λ] kD> vk[λ] ,
where we used the duality between k · k∗[λ] and k · k[λ] for the second term and the
fact that the transpose and the Moore-Penrose pseudo-inverse commute, which
†
implies (D† )> = D> .
We now bound g(ε) from above on the event (2.2). On the event (2.2),


p
X
n
 kD> vk[λ] + nΛ(λ, s)kD> vk2 − n
λj |D> v|↓j 
g(ε) ≤
sup
v∈Rn :kvk=1 2
j=s+1


p
s
X
X
n
n

≤
sup
λj |D> v|↓j + nΛ(λ, s)kD> vk2 −
λj |D> v|↓j 
2 j=s+1
v∈Rn :kvk=1 2 j=1


p
X
n
3Λ(λ, s)kD> vk2 −
≤
sup
λj |D> v|↓j  .
2 v∈Rn :kvk=1
j=s+1
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

8

Pp
Consider v ∈ Rn such that kvk = 1 and 3Λ(λ, s)kD> vk2 > j=s+1 λj |D> v|↓j .
Then, by the definition of κ(s) given in defined in (2.4) we have
p
X

3Λ(λ, s)kD> vk2 −

λj |D> v|↓j ≤ 3Λ(λ, s)kvk/κ(s) = 3Λ(λ, s)/κ(s).

j=s+1

Consider v ∈ Rn such that kvk = 1 and 3Λ(λ, s)kD> vk2 ≤
then we have trivially
p
X

>

3Λ(λ, s)kD vk2 −

Pp

j=s+1

λj |D> v|↓j ,

λj |D> v|↓j ≤ 0 ≤ 3Λ(λ, s)/κ(s) .

j=s+1

Thus, we have proved that on the event (2.2) that has probability at least 1/2,
(2.7) holds. This implies (2.6) by definition of the median.
The constant κ(s) is sometimes referred to as the compatibility factor of D> .
Bounds on the compatibility factor are obtained for a large class of random and
deterministic graphs [17]. For instance, for graphs with bounded degree, the
compatibility factor is bounded from below (see for instance [17, Lemma 3]). In
linear regression, constants that measure the correlations of the design matrix
have been proposed to study the Lasso and the Dantzig selector: [8] defined the
Restricted Eigenvalue constant, [31] defined the Compatibility constant, [35]
defined the Cone Invertibility factors and [13] defined the Compatibility factor,
to name a few. The Weighted Restricted Eigenvalue constant was also defined
in [4] to study the Slope estimator. These constants are the linear regression
analogs of κ(s) defined in (2.4).
Theorem 2.1 does not provide an explicit choice for the weights λ1 ≥ · · · ≥ λp .
These weights should be large enough so that the event (2.2) has probability at
least 1/2. These weights should also be as small as possible in order to minimize
the right hand side of (2.3). Define g1 , . . . , gp by
†
gj = e>
j D ε,

for all j = 1, . . . , p .

(2.8)

and let |g|↓1 ≥ · · · ≥ |g|↓p be a nondecreasing rearrangement of (|g1 |, . . . , |gp |).
Inequality (2.10) below reads


(1/n)kD† εk∗[λ] ≤ max |g|↓j / (nλj ) .
j=1,...,p

Thus, if the event
max

j=1,...,p




|g|↓j / (nλj ) ≤ 1/2 ,

has probability greater than 1/2, then the event (2.2) has probability greater
than 1/2 as well, and the conclusion of Theorem 2.1 holds. This observation can
be used to justify the following heuristics for the choice of the tuning parameters
λ1 ≥ · · · ≥ λp . This heuristics can be implemented provided that the MoorePenrose pseudo-inverse D† and the probability distribution of the noise random
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

9

vector ε are both known. These heuristics go as follows. Assume that one has
generated N independent copies of the random vector ε, and denote by P̃N the
empirical probability distribution with respect to these independent copies of ε,
and F̃Nj the empirical cumulative distribution function (cdf) of |g|↓j . Next, define
λj as the (1 − 1/(3p))th quantile of 2|g|↓j , so that
P̃N (2|g|↓j ≤ nλj ) = 1 − 1/3p .
As N → +∞, by the Glivenko-Cantelli theorem, F̃Nj (t) converges to the cdf
of |g|↓j at t uniformly in t ∈ R, j ∈ [p]. Hence if N is large enough, then for
all j = 1, ..., p we have P(2|g|↓j ≤ nλj ) ≥ 1 − 1/2p . By the union bound over
j = 1, . . . , p,




↓
P max |g|j / (nλj ) ≤ 1/2 ≥ 1/2 ,
j=1,...,p

thus the event (2.2) has probability greater than 1/2 with respect to the probability distribution P of ε. This simple scheme provides a computational heuristic
to choose the weights λ1 , . . . , λp .
The following corollaries propose a theoretical choice for the weights. To state
these corollaries, let us write
ρ(G) = max k(D> )† ej k ,
j∈[p]

following the notation in [17].
Corollary 1. Assume that the Graph-Slope weights λ1 ≥ · · · ≥ λp ≥ 0 satisfy
for any j ∈ [p]
p
nλj ≥ 8σρ(G) log(2p/j) .
(2.9)
Then, for any δ ∈ (0, 1), the oracle inequality (2.3) holds with probability at least
1 − 2δ.
Note that if λ1 = · · · = λp = λ, then the event (2.2) reduces to k(D> )† εk∞ ≤
nλ/2. The random variable k(D> )† εk∞ is the maximum of p correlated Gaussian
random variables with variance at most σ 2 ρ(G)2 , √
so that (2.2) has probability
at least 1/2 provided that λ is of order (ρ(G)σ/n) log p.
Proof of Corollary 1. It is enough to show that if the weights λ1 , . . . , λp satisfy
(2.9) then the event (2.2) has probability at least 1/2.
Define g1 , . . . , gp by (2.8) and let |g|↓1 ≥ · · · ≥ |g|↓p be a nondecreasing rearrangement of (|g1 |, . . . , |gp |). For each j, the random variable gj is a centered
Gaussian random variable with variance at most σ 2 kD† ej k2 ≤ σ 2 ρ(G)2 . By

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

10

definition of the dual norm, and [7, Corrolary II.4.3], we have
a> D† ε
1
sup
kD† εk∗[λ] =
n
n
a∈Rp :kak[λ] =1
≤

sup

p
X

a∈Rp :kak[λ] =1 j=1

λj |a|↓j ·

|g|↓j
nλj

|g|↓j
j=1,...,p nλj

≤ max

(2.10)

|g|↓j
p
,
j=1,...,p 8 V log(2p/j)

≤ max
†

where V = σ 2 maxj=1,...,p kD> ej k2 . Thus, by Lemma A.5 below, the event
(2.2) has probability at least 1/2.
Under an explicit choice of tuning parameters, Corollary 1 yields the following
result.
Corollary 2. Under p
the same hypothesis as Theorem 2.1 but with the special
choice nλj = 8σρ(G) log(2p/j) for any j ∈ [p], then for any δ ∈ (0, 1), we
have with probability at least 1 − 2δ


2


2
1
1
2ep
? 2
? 2
σ 2 48ρ (G)s
kβ̂ − β k ≤ inf n
kβ − β k + n
log s
+ σn (2 + 16 log 1δ ) .
2
n
n
κ (s)
s∈[p],β∈R
kD> βk0 ≤s

Proof. We apply Lemma A.2 with the choice C = 8σρ(G)/n
When the true signal satisfies kD> β ? k0 = s? , the previous bound reduces to
σ2
1
kβ̂ − β ? k2 ≤
n
n



48ρ(G)2 s?
log
κ(s? )2



2ep
s?


+ 2 + 16 log

 
1
.
δ

Corollary 2 is an improvement w.r.t. the bound provided in [17, Theorem 2] for
the TV denoiser (also sometimes referred to as the Generalized Lasso) relying
on `1 regularization defined in Eq. (1.3).
Indeed, the contribution of the second term in Corollary 2 is reduced from
log(ep/δ) (in [17, Theorem 2]) to log(2ep/s). Thus the dependence of the right
hand side of the oracle inequality in the confidence level δ is significantly reduced
compared to the result of [17, Theorem 2].
A similar bound as in Corollary 2 could be obtained for `1 regularization
adapting the proof from [4, Theorem 4.3]. However such a better bound would
be obtained for a choice of regularization parameter relying on the D> -sparsity
of the signal. The Graph-Slope does not rely on such a quantity, and thus
Graph-Slope is adaptive to the unknown D> -sparsity of the signal.

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

11

Remark 1. The optimal theoretical choice of parameter requires the knowledge
of the noise level σ from the practitioner. Whenever the noise level σ is not
known, the practitioner can use the corresponding Concomitant estimator to
alleviate this issue [21, 5, 29], see also [19] for efficient algorithms to compute
such scale-free estimators.
3. Numerical experiments
3.1. Algorithm for Graph-Slope
In this section, we propose an algorithm to compute a solution of the highly
structured optimization problem (1.2). The data fidelity term f : β 7→ ky −
βk22 /2 is a convex smooth function with 1-Lipschitz gradient, and the map β 7→
kD> βk[λ] is the pre-composition by a linear operator of the norm k · k[λ] whose
proximal operator can be easily computed [36, 10]. Thus, the use of a dual or
primal-dual proximal scheme can be advocated.
Problem (1.2) can be rewritten as
min f (β) + g(D> β) ,

β∈Rn

where f is a smooth, 1-Lipschitz strictly convex function and g = k · k[λ] is a
convex, proper, lower semicontinuous function (see for instance [2, p. 275]). Its
dual problem reads
minp f ? (Dθ) + g ? (−θ) ,
θ∈R

?

where f is the convex conjugate of f , i.e., for any x ∈ Rn
f ? (x) = suphx, zi − f (z) .
z

Classical computations leads to the following dual problem
min

θ∈Rp

1
1
kDθ − yk22 − kyk22
2
2

subject to kθk∗[λ] 6 1 .

(3.1)

The dual formulation (3.1) can be rewritten as an unconstrained problem, using
for any set C ⊂ Rn , and any θ ∈ Rn , the notation
(
0,
if θ ∈ C
ιC (θ) =
.
+∞, otherwise
The quadratic term in y is constant and can be dropped. Thus the optimization problem (3.1) is equivalent to
min

θ∈Rp

1
kDθ − yk22 + ι{k·k∗[λ] 61} (θ).
2

(3.2)

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

12

Algorithm 1 FISTA on dual formulation
Require: (β 0 , θ0 ) initial guess, L = kDk2 , t0 = 1, ε duality gap tolerance
k←0
while ∆(β k , θk ) > ε do

1
(D> (Dθ̄k − y))
. forward-backward step
θk+1 ← Π 1 B∗ θ̄k − L
L

β k+1 ← y −
Dθk+1
q
1+

. necessary to compute ∆

1+4t2
k

tk+1 ←
2
θ̄k+1 ← θk+1 +
k ←k+1
end while

tk −1 k+1
(θ
tk+1

. FISTA rule
. non-convex over-relaxation

− θk )

The formulation in (3.2) is now well suited to apply an accelerated version of
the forward-backward algorithm such as FISTA [3]. As a stopping criterion, we
use a duality gap criterion: ∆(β, θ) 6 ε, where
∆(β, θ) =

1
1
1
ky − βk22 + kD> βk[λ] + kDθ − yk22 − kyk22 ,
2
2
2

for a feasible pair (β, θ) and by ∆(β, θ) = +∞ for an unfeasible pair. In practice
we set ε = 10−2 as a default value. Algorithm 1 summarizes the dual FISTA
algorithm applied to the Graph-Slope minimization problem.
We recall that the proximity operator of a convex, proper, lower semicontinuous function f is given as the unique solution of the optimization problem
Proxλf (β) = argmin
z∈Rn

1
kβ − zk22 + λf (z) .
2

To compute the proximity operator of ι{k·k∗[λ] 61} , we use the Moreau’s decomposition [22, p. 65] which links it to the proximity operator of the dual Slope-norm,
 
θ
θ = Proxτ ιk·k∗ 61 (θ) + τ Prox τ1 k·k[λ]
[λ]
τ
 
θ
= Π τ1 B∗ (θ) + τ Prox τ1 k·k[λ]
,
τ
where Π τ1 B∗ is the projection onto the unit ball B∗ associated to the dual
norm k · k∗ scaled by a factor 1/τ . The proximity operator of k · k[λ] can be
obtained obtained in several ways [36, 10]. In our numerical experiments, we
use the connection between this operator and the isotonic regression following
[36], which can be computed in linear time. Under the assumption that the
quantity (ui − λi ) is positive, non-increasing (which is obtained by sorting |u|
and restoring the signs and ordering afterwards, see details in [36, Eq. (24)]),
computing Proxk·k[λ] (u) is equivalent to solving the problem
argmin
θ∈Rp

1
ku − λ − θk22
2

subject to θ1 > θ2 > · · · > θp > 0 .

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

13

We have relied on the fast implementation implementation of the PAVA algorithm (for Pool Adjacent Violators Algorithm, see for instance [6]), available in
scikit-learn [23] to solve this inner problem.
The source code used for our numerical experiments is freely available at
http://github.com/svaiter/gslope_oracle_inequality.
3.2. Synthetic experiments
To illustrate the behavior of Graph-Slope, we first propose two synthetic experiments in moderate dimension. The first one is concerned with the so-called
“Caveman” graph and the second one with the 1D path graph.
For these two scenarios, we analyze the performance following the same protocol. For a given noise level σ, we use the bounds derived in Theorem 2.1 (we
dropped the constant term 8) and in [17], i.e.,
r
r
2 log(p)
2 log(p/j)
and (λGS )j = ρ(G)σ
∀j ∈ [p] . (3.3)
λGL = ρ(G)σ
n
n
For every n0 between 0 and p, we generate 1000 signals as follows. We draw
J uniformly at random among all the subsets of [p] of size n0 . Then, we let
ΠJ be the projection onto Ker D>
J and generate a vector g ∼ N (0, Idn ). We
then construct β ? = c(Id − ΠJ )g where c is a given constant (here c = 8). This
constrains the signal β ? to be of D> -sparsity at most p − n0 .
We corrupt the signals by adding a zero mean Gaussian noise with variance
σ 2 , and run both the Graph-Lasso estimator and the Graph-Slope estimator. We
then compute the mean of the mean-squared error (MSE), the false detection
rate (FDR) and the true detection rate (TDR). To clarify our vocabulary, given
an estimator β̂ and a ground truth β ? , the MSE reads (1/n)kβ ? − β̂k2 , while
the FDR and TDR read, respectively,

 |{j∈[p] : j∈supp(D> β̂) and j6∈supp(D> β ? )}|
if D> β̂ 6= 0
?
| supp(D> β̂)|
FDR(β̂, β ) =
0
if D> β̂ = 0,
and
( | j∈[p] : j∈supp(D> β̂) and j∈supp(D> β ? ) |
{
}
TDR(β̂, β ? ) =

| supp(D> β ? )|

0,

, if D> β ? 6= 0,
if D> β ? = 0,

where for any z ∈ Rp , supp(z) = {j ∈ [p] : zj 6= 0}.
Example on Caveman The caveman model was introduced in [34] to model
small-world phenomenon in sociology. Here we consider its relaxed version,
which is a graph formed by l cliques of size k (hence n = lk), such that with
probability q ∈ [0, 1], an edge of a clique is linked to a different clique. In our
experiment, we set l = 4, k = 10 (n = 40) and q = 0.1. We provide a visualisation of such a graph in Figure 1a. For this realization, we have p = 180. The
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

14

0.35
0.30
0.25
0.20

Graph-Lasso
Graph-Slope
Graph-Slope (MC)

0.15
0.10
0.05
0.00
0

25

(a)
Realization of a caveman
graph
2.00

Graph-Lasso
Graph-Slope
Graph-Slope (MC)

1.75
1.50

75

0.50
0.00
25

50

75

100

D -sparsity

125

150

175

(c) Mean-square error
(MSE)

0.4
0.2

0.0
0

175

0.6

0.4
0.2

0.25

150

Graph-Lasso
Graph-Slope
Graph-Slope (MC)

0.8

TDR

FDR

0.75

125

1.0

Graph-Lasso
Graph-Slope
Graph-Slope (MC)

0.6

1.00

100

(b) Weights

0.8

1.25

MSE

50

0

25

50

75

100

D -sparsity

125

150

175

0.0

0

25

50

75

100

D -sparsity

125

150

175

(d) False Detection Rate (e) True Detection Rate
(FDR)
(TDR)

Fig 1: Relaxed caveman denoising

rewired edges are indicated in blue in Figure 1a whereas the edges similar to the
complete graph on 10 nodes are in black. The signals are generated as random
vectors of given D> -sparsity with a noise level of σ = 0.2. Figure 1b shows the
weights decay.
Figures 1c–1e represent the evolution of the MSE and TDR in function of
the level of D> -sparsity. We observe that while the MSE is close between the
Graph-Lasso and the Graph-Slope estimator at low level of sparsity, the TDR
is vastly improved in the case of Graph-Slope, with a small price concerning the
FDR (a bit more for the Monte Carlo choice of the weights). Hence empirically,
Graph-Slope will make more discoveries than Graph-Lasso without impacting
the overall FDR/MSE, and even improving it.
Example on a path: 1D–Total Variation The classical 1D–Total Variation
corresponds to the Graph-Lasso estimator β̂ GL when G is the path graph over
n vertices, hence with p = n − 1 edges. In our experiments, we take n = 100,
σ = 0.6 and a very sparse gradient (s = 4). According to these values, and taking
a random amplitude for each step, we generate a piecewise-constant signal. We
display a typical realization of such a signal in Figure 2a. Figure 2b shows the
weights decay. Note that in this case, the Monte–Carlo weights shape differs
from the one in the previous experiment. Indeed, they are adapated to the

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

Graph-Lasso
Graph-Slope
Graph-Slope (MC)
True signal
Noisy signal

4
2

10
8
6

0

4

2

2

4

0
0

20

40

60

80

100

Graph-Lasso
Graph-Slope
Graph-Slope (MC)
0

20

(a) Example of signal
20.0

Graph-Lasso
Graph-Slope
Graph-Slope (MC)

17.5
15.0

5.0

0.0
40

60

D -sparsity

80

100

(c) Mean-square error
(MSE)

Graph-Lasso
Graph-Slope
Graph-Slope (MC)

0.4
0.2

2.5
20

100

0.6

0.4
0.2

0.0

80

0.8

TDR

7.5

60

1.0

Graph-Lasso
Graph-Slope
Graph-Slope (MC)

0.6

10.0

FDR

MSE

40

(b) Weights

0.8

12.5

0

15

0

20

40

60

D -sparsity

80

100

0.0

0

20

40

60

D -sparsity

80

100

(d) False Detection Rate (e) True Detection Rate
(FDR)
(TDR)

Fig 2: TV1D

underlying graph, contrary to the theoretical weights λGS which depend only
on the size of the graph. Figures 2c–2e represent the evolution of the MSE and
TDR in function of the level of D> -sparsity. Here, Graph-Slope does not improve
the MSE significantly. However, as for the caveman experiments, Graph-Slope
is more likely to make more discoveries than Graph-Lasso for a small price
concerning the FDR.
3.3. Example on real data: Paris roads network
To conclude our numerical experiments, we present our result on a real-life
graph, the road network of Paris, France. Thanks to the Python module osmnx [9],
which downloads and simplifies OpenStreetMap data, we run our experiments
on p = 20108 streets (edges) and n = 10205 intersections (vertices).
The ground truth signal is constructed as in [16] as follows. Starting from
30 infection sources, each infected intersections has probability 0.75 to infect
each of its neighbors. We let the infection process run for 8 iterations. The
resulting graph signal β ? is represented in Figure 3a with D> -sparsity 1586. We
then corrupt this signal by a zero mean Gaussian noise with standard-deviation
σ = 0.8, leading to the observations y represented in Figure 3b.
Instead of using the parameters given in (3.3), we have computed the oracle
parameters for the Graph-Lasso and Graph-Slope estimators by evaluating for

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

(a) True signal β ?

(b) Noisy signal y

(c) Graph-Lasso β̂ GL
MSE=0.070,FDR=83.4%,
TDR=52.1%

120

(e) True signal close-up

0

2000

16

(d) Graph-Slope β̂ GS
MSE=0.074,FDR=88.6%,
TDR=73.5%

(f) Graph-Lasso close-up

4000

6000

(g) Graph-Slope close-up

8000

10000

0.50 0.25 0.00 0.25 0.50 0.75 1.00 1.25
Fig 3: Paris road network. Comparison of oracle choice for the tuning parameter
between Graph-Lasso and Graph-Slope.

100 parameters of the form
r
2 log(p)
λGL = ασ
and
n

r
(λGS )j = ασ

2 log(p/j)
n

∀j ∈ [p] ,

where α lives on a geometric grid inside [10−5 , 101.5 ]. The best one in terms of
MSE (i.e., in term of (1/n)kβ̂ − β ? k2 ) is refered to as the oracle parameter.
The results are illustrated in Figure 3c for Graph-Lasso and in Figure 3d for
Graph-Slope. We can see the benefit of Graph-Slope, for instance in the center
of Paris where the sources of infections are better identified as shown in the
close-up, see Figures 3e–3g.

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

17

Appendix A: Preliminary lemmas
Lemma A.1. Let s ∈ [p]. For any two β, β̂ ∈ Rn such that kD> βk0 6 s we
have
kD> βk[λ] − kD> β̂k[λ] 6

s
X

λj |u|↓j −

j=1

p
X

λj |u|↓j , ≤ Λ(λ, s)kuk2 −

j=s+1

where u = D> (β̂ − β) and Λ(λ, s) =

P

s
j=1

p
X

λj |u|↓j ,

j=s+1

λ2j

1/2

.

Proof. This is a consequence of [4, Lemma A.1]. We provide a proof here for completeness. The second
of the Cauchy-Schwarz
Ps
Ps
Psinequality is simple
Ps consequence
inequality. Indeed, ( j=1 λj |u|↓j )2 ≤ ( j=1 λ2j )( j=1 (|u|↓j )2 ) ≤ kuk22 ( j=1 λ2j ).
Let v = D> β and w =P
D> β̂ and note that u = w −v. Let ϕ be a permutation
s
of [p] such that kvk[λ] = j=1 λj |v|ϕ(j) . The first inequality can be rewritten as
kvk[λ] − kwk[λ] = kvk[λ] − sup
τ

p
X

λj |w|τ (j) 6

j=1

s
X

λj |u|↓j

j=1

−

p
X

λj |u|↓j , (A.1)

j=s+1

where the supremum is taken over all permutations τ of [p]. We now prove (A.1).
Let τ be a permutation of [p] such that ϕ(j) = τ (j) for all j = 1, . . . , s. Then
by the triangle inequality, we have
|v|ϕ(j) − |w|ϕ(j) = |v|ϕ(j) − |w|τ (j) ≤ |u|τ (j)
for each j = 1, . . . , s since u = w − v. Furthermore, for each j > s, it holds that
vτ (j) = 0 so that wτ (j) = uτ (j) . Thus,
kvk[λ] − kwk[λ] ≤

s
X
j=1

λj |v|ϕ(j) −

p
X
j=1

λj |w|τ (j) ≤

s
X
j=1

λj |u|τ (j) −

p
X

λj |u|τ (j) .

j=s+1

Ps
Ps
It is clear that j=1 λj |u|τ (j) ≤ j=1 λj |u|↓j . Finally, notice that it is always
possible to find a permutation τ such that (|u|τ (j) )j>s is non-decreasing. For
Pp
Pp
such choice of τ we have − j=s+1 λj |u|τ (j) ≤ − j=s+1 λj |u|↓j .
p
Lemma A.2. For the choice of weights: ∀j ∈ [p], λj = C log(2p/j), the following inequalities hold true
p
p
C s log(2p/s) 6 Λ(λ, s) 6 C s log(2ep/s) .
Proof. Reminding Stirling’s formula s log(s/e) 6 log(s!) 6 s log(s), one can
check that
 


  X
s
2p
2p
2ep
s log
6
log
6 s log(2p) − log(s!) = log
.
s
j
s
j=1

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

18

Lemma A.3. Let z, ε ∈ Rn , y = z + ε, and β̂ a solution of Problem (1.2).
Then, for all β ∈ Rn ,

1
kβ̂ − zk2 − kβ − zk2 + kβ̂ − βk2 6 ε> (β̂ − β) + nkD> βk[λ] − nkD> β̂k[λ] .
2
Proof. The objective function of the minimization problem (1.2) is the sum of
1
two convex functions. The first term, i.e., the function β → 2n
ky − βk2 , is
(1/n)-strongly convex with respect to the Euclidean norm k · k. The sum of a
1-strongly convex function and a convex function is 1-strongly convex, and thus
by multiplying by n we have
1
1
1
kβ̂ − yk2 + nkD> β̂k[λ] ≤ ndT (β̂ − β) + kβ − yk2 + nkD> βk[λ] − kβ − β̂k2
2
2
2
for all β ∈ Rn and for any d in the subdifferential of the objective function (1.2)
at β̂. Since β̂ is a minimizer of (1.2), we can choose d = 0 in the above display.
For d = 0, the previous display is equivalent to the claim of the Lemma.
Lemma A.4. Let us suppose that the graph G has K connected components
C1 , . . . , CK . Then,
ker(D> ) = span(1C1 ) ⊕ · · · ⊕ span(1CK ),
where for any k ∈ [K], the vectors 1Ck ∈ Rn are defined by
(
1 if i ∈ Ck
(1Ck )i =
, for i = 1, · · · , |V | .
0 otherwise
Moreover, the orthogonal projection over ker(D> ) is denoted by Π and is the
component-wise averaging given by
(Π(β))i =

1 X
βi , where k is such that Ck 3 i, for i = 1, . . . , n.
|Ck |
i∈Ck

Furthermore, if G is a connected graph then ker(Π) = span(1n ).
Proof. The proof can be done for the simple case of a connected graph (i.e., K =
1), and the result can be generalized by tensorization of graph for K > 1 components. Hence, we assume that K = 1. For any β ∈ ker(D> ), the definition of the
incidence matrix yields that for all (i, j) ∈ E, βi = βj . Since all vertices are connected, by recursion all the βj ’s are identical, and β ∈ span(1n ) = span(1C1 ).
The converse is proved in the same way.
Lemma A.5 (Proposition E.2 in [4]). Let g1 , . . . , gp be centered Gaussian random variables (not necessarily independent) with variance at most V > 0. Then,
!
|g|↓j
P
max p
≤ 4 ≥ 1/2 .
j=1,...,p
V log(2p/j)
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

19

References
[1] I. E. Auger and C. E. Lawrence. Algorithms for the optimal identification
of segment neighborhoods. Bull. Math. Biol., 51(1):39–54, 1989.
[2] H. H. Bauschke and P. L. Combettes. Convex analysis and monotone operator theory in Hilbert spaces. Springer, New York, 2011.
[3] A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm
for linear inverse problems. SIAM J. Imaging Sci., 2(1):183–202, 2009.
[4] P. C Bellec, G. Lecué, and A. B. Tsybakov. Slope meets lasso: improved
oracle bounds and optimality. arXiv preprint arXiv:1605.08651, 2016.
[5] A. Belloni, V. Chernozhukov, and L. Wang. Square-root Lasso: pivotal
recovery of sparse signals via conic programming. Biometrika, 98(4):791–
806, 2011.
[6] M. J. Best and N. Chakravarti. Active set algorithms for isotonic regression;
a unifying framework. Math. Program., 47(1-3):425–439, 1990.
[7] R. Bhatia. Matrix analysis, volume 169 of Graduate Texts in Mathematics.
Springer-Verlag, New York, 1997.
[8] P. J. Bickel, Y. Ritov, and A. B. Tsybakov. Simultaneous analysis of lasso
and dantzig selector. Ann. Statist., 37(4):1705–1732, 08 2009.
[9] G. Boeing. OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks.
ArXiv e-prints
ArXiv:1611.01890, 2016.
[10] M. Bogdan, E. van den Berg, C. Sabatti, W. Su, and E. J. Candès. SLOPEadaptive variable selection via convex optimization. Ann. Appl. Stat.,
9(3):1103, 2015.
[11] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A
nonasymptotic theory of independence. Oxford University Press, 2013.
[12] P. L. Combettes and J.-C. Pesquet. Proximal splitting methods in signal
processing. In Fixed-point algorithms for inverse problems in science and
engineering, volume 49 of Springer Optim. Appl., pages 185–212. Springer,
New York, 2011.
[13] A. S. Dalalyan, M. Hebiri, and J. Lederer. On the prediction performance
of the Lasso. Bernoulli, 23(1):552–581, 2017.
[14] C.-A. Deledalle, N. Papadakis, J. Salmon, and S. Vaiter. CLEAR: Covariant
LEAst-square Re-fitting with applications to image restoration. SIAM J.
Imaging Sci., 10(1):243–284, 2017.
[15] M. Elad, P. Milanfar, and R. Rubinstein. Analysis versus synthesis in signal
priors. Inverse problems, 23(3):947–968, 2007.
[16] Z. Fan and L. Guan. `0 -estimation of piecewise-constant signals on graphs.
ArXiv e-prints ArXiv:1703.01421, 2017.
[17] J.-C. Hütter and P. Rigollet. Optimal rates for total variation denoising.
ArXiv e-prints ArXiv:1603.09388, 2016.
[18] E. Mammen and S. van de Geer. Locally adaptive regression splines. Ann.
Statist., 25(1):387–413, 1997.
[19] E. Ndiaye, O. Fercoq, A. Gramfort, V. Leclère, and J. Salmon. Efficient
smoothed concomitant lasso estimation for high dimensional regression. In
imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

Bellec et al./A sharp oracle inequality for Graph-Slope

20

NCMIP, 2017.
[20] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and
an algorithm. In NIPS, volume 14, pages 849–856, 2001.
[21] A. B. Owen. A robust hybrid of lasso and ridge regression. Contemporary
Mathematics, 443:59–72, 2007.
[22] N. Parikh, S. Boyd, E. Chu, B. Peleato, and J. Eckstein. Proximal algorithms. Foundations and Trends in Machine Learning, 1(3):1–108, 2013.
[23] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel,
M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn:
Machine learning in Python. J. Mach. Learn. Res., 12:2825–2830, 2011.
[24] L. I. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise
removal algorithms. Phys. D, 60(1-4):259–268, 1992.
[25] V. Sadhanala, Y.-X. Wang, and R. J. Tibshirani. Total variation classes
beyond 1d: Minimax rates, and the limitations of linear smoothers. In
NIPS, pages 3513–3521, 2016.
[26] J. Sharpnack, A. Singh, and A. Rinaldo. Sparsistency of the edge lasso over
graphs. In AISTATS, volume 22, pages 1028–1036, 2012.
[27] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans.
Pattern Anal. Mach. Intell., 22(8):888–905, 2000.
[28] W. Su and E. J. Candès. Slope is adaptive to unknown sparsity and asymptotically minimax. Ann. Statist., 44(3):1038–1068, 2016.
[29] T. Sun and C.-H. Zhang. Scaled sparse linear regression. Biometrika,
99(4):879–898, 2012.
[30] R. Tibshirani, M. A. Saunders, S. Rosset, J. Zhu, and K. Knight. Sparsity and smoothness via the fused LASSO. J. R. Stat. Soc. Ser. B Stat.
Methodol., 67(1):91–108, 2005.
[31] S. van de Geer and P. Bühlmann. On the conditions used to prove oracle
results for the Lasso. 3:1360–1392, 2009.
[32] V. Viallon, S. Lambert-Lacroix, H. Hoefling, and F. Picard. On the robustness of the generalized fused lasso to prior specifications. Statistics
and Computing, 26(1-2):285–301, 2016.
[33] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing,
17(4):395–416, 2007.
[34] D. J. Watts. Networks, dynamics, and the small-world phenomenon. American Journal of Sociology, 105(2):493–527, 1999.
[35] F. Ye and C.-H. Zhang. Rate minimaxity of the lasso and dantzig selector
for the lq loss in lr balls. J. Mach. Learn. Res., 11(Dec):3519–3540, 2010.
[36] X. Zeng and M. A. T. Figueiredo. The Ordered Weighted `1 Norm:
Atomic Formulation, Projections, and Algorithms.
ArXiv e-prints
arXiv:1409.4271, 2014.

imsart-ejs ver. 2014/10/16 file: ejs_bsv.tex date: November 22, 2017

