# The folded concave Laplacian spectral penalty learns block diagonal sparsity
patterns with the strong oracle property

Iain<EMAIL_ADDRESS>
###### Abstract

Structured sparsity is an important part of the modern statistical toolkit. We
say set of model parameters has block diagonal sparsity up to permutations if
its elements can be viewed as the edges of a graph that has multiple connected
components. For example, a block diagonal correlation matrix with $K$ blocks
of variables corresponds to a graph with $K$ connected components whose nodes
are the variables and whose edges are the correlations. This type of sparsity
captures clusters of model parameters. To learn block diagonal sparsity
patterns we develop folded concave Laplacian spectral penalty and provide a
majorization-minimization algorithm for the resulting non-convex problem. We
show this algorithm has the appealing computational and statistical guarantee
of converging to the oracle estimator after two steps with high probability,
even in high-dimensional settings. The theory is then demonstrated in several
classical problems including covariance estimation, linear regression, and
logistic regression.

Keywords: Structured sparsity; spectral graph theory; non-convex optimization;
majorization-minimization; strong oracle property; high-dimensions

###### Contents

  1. 1 Introduction
    1. 1.1 Contributions and outline
    2. 1.2 Related literature
    3. 1.3 Network constructions and notation
    4. 1.4 Notation
  2. 2 Block diagonal sparsity with Laplacian spectral regularization
    1. 2.1 Folded concave Laplacian spectral penalty
    2. 2.2 Local linear approximation algorithm
  3. 3 Oracle properties of the FCLS penalty
    1. 3.1 When the oracle is a stationary point
    2. 3.2 When the LLA algorithm converges to the block oracle in two steps
  4. 4 Block diagonal shrinkage
    1. 4.1 Stationary point for independent, unbiased, sub-Gaussian residuals
    2. 4.2 Two step convergence
  5. 5 Block sparse regression
    1. 5.1 Linear regression
    2. 5.2 Logistic regression
  6. 6 Simulations
    1. 6.1 Gaussian sequence model
    2. 6.2 Covariance estimation
    3. 6.3 Linear regression
    4. 6.4 Logistic regression
  7. 7 Discussion
  8. A Block-diagonal rectangular matrices and multi-arrays
    1. A.1 Rectangular matrices and the bipartite FCLS penalty
    2. A.2 Multi-arrays and the hypergraph FCLS penalty
  9. B Specifying the largest value for the FCLS tuning parameter
  10. C Laplacian spectral bounds
    1. C.1 Spectra of some important binary graphs
    2. C.2 Laplacian vs. adjacency matrix norms
    3. C.3 Laplacian coefficient comparison
  11. D Proofs for Sections 2 and 3
    1. D.1 Proofs for Section 2.2
    2. D.2 Proofs for Section 3
  12. E Proofs for Section 4
    1. E.1 Preliminary results
    2. E.2 Proofs for main results
    3. E.3 Proofs for preliminary results
  13. F Proofs for Section 5
    1. F.1 Preliminary facts for Section 5.1
    2. F.2 Proofs for Section 5.1
    3. F.3 Preliminary facts for Section 5.2
    4. F.4 Proofs for Section 5.2
  14. G Proofs for Appendices
    1. G.1 Proofs for Appendix C
    2. G.2 Proofs for Appendix A
    3. G.3 Proofs for Appendix B

##  1 Introduction

Sparsity plays a crucial role in statistics and machine learning (Hastie et
al.,, 2015). Estimators that incorporate sparsity help the data analyst obtain
interpretable results and the theoretician establish favorable estimation
properties. Some problems have additional structure beyond entrywise sparsity.
For example, in the group sparse setting the analyst knows that predefined
groups of variables should be included or excluded together (Yuan and Lin,,
2006). There is a growing literature on structured sparsity inducing penalties
including: the group lasso (Yuan and Lin,, 2006), fused lasso/total
variation/edge lasso (Tibshirani et al.,, 2005; Sharpnack et al.,, 2012),
graph total variation (Li et al.,, 2020), and generalized Lasso (Tibshirani et
al.,, 2011). Many of these established sparsity inducing penalties – and their
concave extensions – come with appealing statistical and computational
guarantees (Negahban et al.,, 2012; Fan et al.,, 2020). This paper adds a new
structured sparsity inducing penalty to this list that aims to discover
groupings of variables.

We say a vector, $\beta$, has block diagonal sparsity up to permutations if
$\beta$ can be viewed as the edges of a graph and this graph has multiple
connected components. This is made precise below. For example,
$\beta\in\mathbb{R}^{{d\choose 2}}$ might be the upper-triangular elements of
a block diagonal correlation matrix for $d$ variables. Our goal is to learn
the parameters of a statistical model when these parameters have an unknown
block diagonal sparsity structure. Since the blocks are not known ahead of
time, learning the block structure amounts to learning clusters of model
parameters. This setting is reminiscent of community detection (Porter et
al.,, 2009) in networks, but we simultaneously learn both the (real valued)
edges of the network and the underlying communities, which are perfectly
separated.

(a) Block diagonal hollow symmetric matrix.

(b) Block diagonal rectangular matrix.

(c) A 3 dimensional block diagonal multi-array.

Figure 1:  Examples of block diagonal arrays. Each corresponds to a graph that
has 4 connected components, one of which is an isolated vertex. Permuting the
rows/columns of the matrices in Figures 1(a)/1(b) (or the axes in Figure 1(c))
results in graphs with the same number of connected components.

Block diagonal sparsity arises in several settings that are illustrated in
Figure 1.

  1. 1.

Hollow symmetric matrices (0s on the diagonal) in $\mathbb{R}^{d\times d}$;
the entries of $\beta\in\mathbb{R}^{{d\choose 2}}$ parameterize the edges of
the adjacency matrix of a graph with $d$ nodes. For example, $\beta$ might be
the upper-triangular elements of a $d\times d$ dimensional correlation matrix.

  2. 2.

Rectangular matrices in $\mathbb{R}^{m\times d}$; the entries
$\beta\in\mathbb{R}^{m\cdot d}$ parameterize the edges of a bipartite graph
whose vertex sets are the rows and columns of the matrix. For example, $\beta$
might be the regression coefficient matrix for a multiple response regression
problem with $m$ responses and $d$ covariates.

  3. 3.

Multi-arrays in $\mathbb{R}^{d^{(1)}\times\dots\times d^{(V)}}$; the entries
of $\beta\in\mathbb{R}^{\prod_{v=1}^{V}d^{(v)}}$ parameterize the hyperedges
of a hypergraph (Berge,, 1984; Zhou et al.,, 2006). See Appendix A.

There is a growing literature on block diagonal estimation including:
covariance matrix and graphical model estimation (Marlin and Murphy,, 2009;
Pavlenko et al.,, 2012; Tan et al.,, 2015; Hyodo et al.,, 2015; Sun et al.,,
2015; Egilmez et al.,, 2017; Devijver and Gallopin,, 2018; Kumar et al.,,
2019; Broto et al.,, 2019), community detection (Nie et al.,, 2016), co-
clustering (Han et al.,, 2017; Nie et al.,, 2017), subspace clustering (Feng
et al.,, 2014; Lu et al.,, 2018), principal components analysis (Asteris et
al.,, 2015), bipartite cross-correlation clustering (Dewaskar et al.,, 2020),
neural network regularization (Tam and Dunson,, 2020), and multi-view
clustering (Carmichael,, 2020).

A variety of approaches are used to estimate block diagonally structured
parameters. Some methods exploit the structure of particular statistical
models (Asteris et al.,, 2015; Tan et al.,, 2015; Devijver and Gallopin,,
2018). Bayesian approaches to block diagonal estimation are based on priors
that promote block diagonal structure (Mansinghka et al.,, 2006; Marlin and
Murphy,, 2009). Constrained optimization approaches have been developed that
constrain the eigenvalues of the graph Laplacian (Nie et al.,, 2016, 2017;
Egilmez et al.,, 2017; Kumar et al.,, 2019) or the symmetric, normalized graph
Laplacian (Carmichael,, 2020). We follow a similar optimization strategy by
developing estimators that penalize Laplacian eigenvalues; see Problem (3)
below.

###  1.1 Contributions and outline

Inspired by the success of folded concave penalties for sparse vector
estimation (Fan and Li,, 2001; Zou and Li,, 2008; Zhang et al.,, 2012; Loh and
Wainwright,, 2015; Liu et al.,, 2017) – especially (Fan et al.,, 2014) – we
develop the folded concave Laplacian spectral (FCLS) penalty for block
sparsity estimation (Section 2). While this penalty is non-convex, we show it
can be majorized by a (positively) weighted $L_{1}$ penalty. Section 2.2
develops a majorization-minimization algorithm for this penalty, which we call
a local linear approximation algorithm (LLA) in the spirit of (Zou and Li,,
2008).

By making use of concave penalties such as the smoothly clipped absolute
deviation (SCAD) penalty, Section 3 shows the output after two steps of the
LLA algorithm obeys the strong oracle property, as long as we have a “good
enough” initializer. In addition to being an appealing statistical guarantee,
this result has the computational implication that we may only need to take a
few (e.g. 2) steps of the LLA algorithm.

Sections 4 and 5 illustrate the theory in several settings, including block
diagonal shrinkage, linear regression and logistic regression. These sections
provided strong non-asymptotic guarantees that often apply in ultra-high
dimensional settings when $\log(d)=O(n^{\alpha})$ for some $\alpha\in(0,1)$.
Section 6 shows empirically that our proposed estimator outperforms competing
entrywise penalties (Fan et al.,, 2014).

Additional details such as proofs, technical results and additional
computational details are provided in the appendix. While the focus of this
paper is on symmetric block diagonal matrices (Figure 1(a)), our methodology
extends naturally to rectangular matrices (Figure 1(b)) and multi-arrays
(Figure 1(c)). These extensions are sketched in Appendix A. Section A python
package implementing the methods in this paper is provided at
https://github.com/idc9/fclsp and code to reproduce the simulations in Section
6 is available at https://github.com/idc9/repro_lap_reg.

###  1.2 Related literature

To our knowledge, we provide the first general purpose framework for block
diagonal estimation that comes with strong statistical and computational
guarantees. Some existing bespoke methods for particular problems (Tan et
al.,, 2015; Asteris et al.,, 2015; Devijver and Gallopin,, 2018) come with
strong guarantees, but these methods do not naturally extend to other
statistical models. The existing literature on Laplacian spectral constraints
typically provides weak computational guarantees (e.g. eventual convergence to
a stationary point), but no statistical guarantees (Nie et al.,, 2016; Egilmez
et al.,, 2017; Nie et al.,, 2017; Kumar et al.,, 2019; Carmichael,, 2020). The
recent work of Tam and Dunson, (2020) proposes a Laplacian spectral penalty
for neural network regularization that is a special case of the FCLS penalty
for a single Laplacian eigenvalue.

The FCLS penalty should not be confused with other penalties that make use of
graph information (Smola and Kondor,, 2003; Ando and Zhang,, 2007; Sharpnack
et al.,, 2012; Jiang et al.,, 2013; Li et al.,, 2020). In these approaches a
fixed graph known ahead of time and is used to incorporate prior graph
structural information. In our setting the graph is learned and the Laplacian
is used to uncover unknown graph structure.

###  1.3 Network constructions and notation

Suppose $A\in\mathbb{R}^{d\times d}$ is the adjacency matrix of a graph with
real valued edges and no self-loops (equivalently $A$ is a hollow symmetric
matrix). Let $\mathcal{S}\left(A\right)\in\\{0,1\\}^{d\times d}$ be the
support of $A$ i.e. $\mathcal{S}\left(A\right)_{ij}=\mathbf{1}\left(A_{ij}\neq
0\right)$. We say the connected components of $A$ are the connected components
of $\mathcal{S}\left(A\right)$. In this case, the rows/columns $A$ can be
permuted to form a block diagonal matrix. We therefore refer to the blocks of
$A$ as these connected components. Note the number of connected components of
$A$ is equal to the number of (non-zero) blocks plus the number of zero rows.
We will need the following notion of block support i.e. the superset of the
support that includes all within-block edges.

######  Definition 1.1.

For a hollow symmetric matrix $A\in\mathbb{R}^{d\times d}$ the block support
matrix $\mathcal{BS}\left(A\right)\in\mathbb{R}^{d\times d}$ is the hollow
symmetric matrix such that

$\mathcal{BS}\left(A\right)_{ij}=\mathbf{1}\left(\text{nodes }i\text{ and
}j\text{ are in the same connected component of
}\mathcal{S}\left(A\right)\right).$

We next review a few basic facts about the graph Laplacian that can be found
in (Von Luxburg,, 2007). For a symmetric matrix $A\in\mathbb{R}^{d\times d}$
let

$L(A):=\text{diag}(A\mathbf{1}_{d})-A,$

be the Laplacian matrix. For a weighted graph with positive edges whose
adjacency matrix is given by $A\in\mathbb{R}^{d\times d}_{+}$, the number of
zero eigenvalues of $L(A)$ is equal to the number of connected components of
$A$. Furthermore, the indicator vectors (i.e. the vectors in $\\{0,1\\}^{d}$
such that there is a 1 in the $j$th entry of the $k$ eigenvector if the $j$th
node is a member of the $k$th connected component) of these connected
components form an orthonormal basis for the kernel of $L(A)$.

For a vector $x\in\mathbb{R}^{{d\choose 2}}$, let
$\mathcal{A}(x)\in\mathbb{R}^{d\times d}$ be the hollow symmetric matrix whose
upper triangular elements are given by $x$. We will also write
$\mathcal{L}(x):=L(\mathcal{A}(x))\in\mathbb{R}^{d\times d}$. To lighten
notation, we will often write $x_{(ij)}:=\mathcal{A}(x)_{ij}$ and
$D:={d\choose 2}$. To index the edges we will write either
$\\{x_{\ell}|\ell\in[D]\\}$ or $\\{x_{(ij)}|(ij)\in[D]\\}$ i.e. $(ij)$ refers
to the unique entry of $x$ corresponding to the edge between nodes $i$ and
$j$.

###  1.4 Notation

Let $[n]:=\\{1,\dots,n\\}$ and let $\mathbf{1}\left(\cdot\right)$ be the
indicator function i.e. it is 1 if $\cdot$ is true and 0 otherwise. Let
$\mathbf{1}_{d}\in\mathbb{R}^{d}$ be the vector of ones. For a vector $x$,
$||x||_{q}$ refers to the usual $L_{q}$ norm. We write $||x||_{\text{max}}$
and $||x||_{\text{min}}$ for the maximal (minimal) entry in absolute value.

For a symmetric matrix $A\in\mathbb{R}^{d\times d}$ let
$\lambda(A)\in\mathbb{R}^{d}$ be the vector of eigenvalues of $A$. We will
write $\lambda_{j}$ for the $j$th largest eigenvalue and $\lambda_{(j)}$ for
the $j$th smallest eigenvalue. For the largest and smallest eigenvalues we
will also use the notation $\lambda_{\text{max}}$ and $\lambda_{\text{min}}$.
For a matrix $A\in\mathbb{R}^{R\times C}$, the $(\kappa\to\rho)$ operator norm
is

$||A||_{(\kappa\to\rho)}:=\sup_{0\neq
x\in\mathbb{R}^{C}}\frac{||Ax||_{\rho}}{||x||_{\kappa}}$

We will write $||A||_{\text{op}}:=||A||_{(2\to 2)}$ for the standard operator
norm (i.e. the largest singular value) and $||A||_{\text{op}-1}:=||A||_{(1\to
1)}=\max_{r\in[R]}\sum_{c=1}^{C}|X_{rc}|$ for the operator one norm.

For a matrix $X\in\mathbb{R}^{n\times d}$, $X(i,:)\in\mathbb{R}^{d}$ denotes
the $i$th row and $X_{j}\in\mathbb{R}^{n}$ the $j$th column. For a subset
$A\subseteq[d]$ we let $X_{A}\in\mathbb{R}^{n\times|A|}$ be the sub-matrix of
the columns in $A$. When $x\in\mathbb{R}^{d}$ is a vector and
$f:\mathbb{R}\to\mathbb{R}$ is a function we will overload notation and write
$f(x)\in\mathbb{R}^{d}$ for $f$ applied element-wise to $x$ e.g.
$|x|\in\mathbb{R}^{d}$ means the entrywise absolute value of $x$.

We say a random variable $X$ has a $\sigma$ sub-Gaussian distribution if
$\mathcal{P}\left(|X|\geq t\right)\leq 2\exp(-\frac{t}{2\sigma^{2}})$ for all
$t>0$ e.g. see (Vershynin,, 2018). We say an event $E$ occurs with
overwhelming probability if there exist positive constants $N,c,C$ such that
$\mathcal{P}\left(E\right)\geq 1-Ce^{-cn}$ for all $n\geq N$ where $n$ is
typically the sample size. We will use $c,C,c_{i}$ to refer to absolute
constants that may change from line to line.

##  2 Block diagonal sparsity with Laplacian spectral regularization

Consider estimating a model parameter, $\beta\in\mathbb{R}^{D}$, by minimizing
some loss function $\ell\left(\beta\right)$. Throughout the body of the paper
we assume the model parameter can be viewed as the edges of an adjacency
matrix, $\mathcal{A}(\beta)\in\mathbb{R}^{d\times d}$ where $D={d\choose 2}$.
Suppose we know a priori that the target model parameter has a block diagonal
sparsity structure. We would then like to solve the following block diagonally
constrained problem,

$\displaystyle\underset{\beta\in\mathbb{R}^{D}}{\textup{minimize}}$
$\displaystyle\ell(\beta)$ (1) subject to
$\displaystyle\mathcal{A}(|\beta|)\text{ has at least K connected
components},$

where $K$ is a tuning parameter. This constraint set is non-convex and, even
worse, seems combinatorial.

Problem (1) can be made amenable to continuous optimization approaches by
recalling that the number of zero eigenvalues of the Laplacian count the
number of connected components of a graph. Thus the (combinatorial) sparsity
constraint of (1) is equivalent to the (continuous) spectral constraint,
$\lambda_{(K)}(\mathcal{L}(|\beta|))=0$ (Nie et al.,, 2016, 2017; Kumar et
al.,, 2019; Carmichael,, 2020). Instead of solving such a constrained problem,
we develop a related penalized approach that leads to an efficient algorithm
with strong statistical and computational guarantees.

###  2.1 Folded concave Laplacian spectral penalty

For a function $g_{\tau}:\mathbb{R}\to\mathbb{R}$ and matrix
$X\in\mathbb{R}^{d\times d}$ we write
$g_{\tau}\circ\lambda(X)=\sum_{i=1}^{d}g_{\tau}(\lambda_{i}(X))$.

######  Definition 2.1.

For a vector $\beta\in\mathbb{R}^{{d\choose 2}}$ and concave increasing
function $g_{\tau}:\mathbb{R}\to\mathbb{R}$, the folded concave Laplacian
spectral (FCLS) penalty is given by

$s_{\tau}\left(\beta\right):=\frac{1}{2}g_{\tau}\circ\lambda(\mathcal{L}(|\beta|))=:\frac{1}{2}t_{\tau}\left(|\beta|\right).$
(2)

######  Remark 2.1.

We can check that $t_{\tau}\left(\beta\right)$ is concave when $g_{\tau}$ is
concave e.g. by Theorem 7.17 of Beck, 2017. Therefore $s_{\tau}(\cdot)$ is
concave in $|\beta|$ hence the name “folded concave”. Note that if $g_{\tau}$
is the identity then $s_{\tau}\left(\beta\right)=||\beta||_{1}$ i.e. the FCLS
penalty reduces to the LASSO.

The FCLS penalty encourages sparsity in the Laplacian eigenvalues thus
encouraging $\mathcal{A}(\beta)$ to have multiple connected components. We
therefore consider the following penalized problem

$\underset{\beta\in\mathbb{R}^{D}}{\textup{minimize}}\;\;\ell(\beta)+\frac{1}{2}g_{\tau}\circ\lambda(\mathcal{L}(|\beta|)).$
(3)

Informally, the penalized Problem (3) is to the constrained Problem (1) as
Lasso/SCAD penalized problems are to $L_{0}$ constrained problems.

###  2.2 Local linear approximation algorithm

We next derive a majorization-minimization (MM) algorithm for Problem (3)
(Lange et al.,, 2000; Sun et al.,, 2016). The key observation is that
$s_{\tau}$ can be majorized by (positively) weighted Lasso function.

######  Definition 2.2.

We say a surrogate function $Q(x|y)$ majorizes $f(x)$ if

$f(x)=Q(x|x)\text{ for all }x\text{ and }f(x)\leq Q(x|y)\text{ for all }x,y.$

Since $t_{\tau}(\cdot)$ is concave we can construct a surrogate function via a
standard linearization approach i.e. $\overline{Q}(\beta|b):=\nabla
t_{\tau}\left(b\right)^{T}(\beta-b)+t_{\tau}\left(b\right)=\nabla
t_{\tau}\left(b\right)^{T}\beta+\text{constants}(b)$ is a surrogate for
$t_{\tau}(\cdot)$. The composition of this surrogate function with the
absolute value function, $Q(\beta|b):=\overline{Q}(|\beta|\Big{|}|b|)$, then
gives a surrogate for $s_{\tau}(\cdot)$.

Next we give an explicit form for the gradient, $\nabla
t_{\tau}\left(b\right)$. For $w\in\mathbb{R}^{K}$ and $V\in\mathbb{R}^{d\times
K}$ let $\mathcal{M}(V,w)\in\mathbb{R}_{+}^{D}$ be the vector such that

$\mathcal{M}(V,w)_{(ij)}=||V(i,:)-V(j,:)||_{2,w}^{2},$ (4)

where $||y||_{2,w}^{2}:=y^{T}\text{diag}(w)y$. We call this vector the
Laplacian coefficient. We can check that

$\nabla
t_{\tau}\left(b\right)=\mathcal{M}(V^{b},g^{\prime}_{\tau}(\lambda^{b})),$ (5)

where $V^{b}\in\mathbb{R}^{D\times D}$ is any orthonormal matrix of
eigenvectors of $\mathcal{L}(b)$ with corresponding eigenvalues
$\lambda^{b}\in\mathbb{R}^{D}_{+}$ and $g^{\prime}_{\tau}$ denotes any super-
gradient. Thus the surrogate function for $s_{\tau}$ at $b$ is given by

$Q(\beta|b)=\sum_{\ell=1}^{D}\mathcal{M}(V^{|b|},g^{\prime}_{\tau}(\lambda^{|b|}))_{\ell}\;\cdot|\beta_{\ell}|+\text{constants}(b),$
(6)

where $V^{|b|},\lambda^{|b|}$ are eigenvectors/values of $\mathcal{L}(|b|)$.

######  Proposition 2.1.

$Q(\cdot|b)$ is convex and majorizes $s_{\tau}(\cdot)$ at $b$. The quantity
$\mathcal{M}(V^{|b|},g^{\prime}_{\tau}(\lambda^{|b|}))$ does not depend on the
choice of eigenvectors, $V^{|b|}$. Majorizing at $0$ leaves a Lasso i.e.
$Q(\beta|0)=g^{\prime}_{\tau}(0)||\beta||_{1}$. Additionally, any fixed point
of the below MM algorithm is a stationary point of Problem (3).

Equipped with our weighted $L_{1}$ surrogate function we can use the following
MM algorithm to hunt for stationary points of the penalized Problem (3).
Similar reweighted $L_{1}$ algorithms appear elsewhere in the literature
(Krishnapuram et al.,, 2005; Zou and Li,, 2008; Gasso et al.,, 2009; Candes et
al.,, 2008; Fan et al.,, 2014).

1

Input: Tuning parameter value $\tau\geq 0$ and initializer
$\beta^{(0)}\in\mathbb{R}^{D}$

2 for  _s=0, 1, 2, …_ do

3

4 $V^{(s)},\lambda^{(s)}\leftarrow$ eigenvectors and eigenvalues of
$\mathcal{L}\left(|\beta^{(s)}|\right)$

$M^{(s)}\leftarrow\mathcal{M}(V^{(s)},g_{\tau}^{\prime}(\lambda^{(s)}))$

// Obtain weights for Lasso surrogate using (4)

5

6
$\beta^{(s+1)}=\underset{\beta\in\mathbb{R}^{D}}{\textup{argmin}}\;\;\ell(\beta)+\frac{1}{2}|\beta|^{T}M^{(s)}$
(7)

Algorithm 1 Local linear approximation algorithm for FCLS penalized Problem
(3)

Each loop of Algorithm 1 requires computing an eigen-decomposition and a
solution to a (weighted) Lasso penalized problem. The theory in Section 3
shows we may only need a few (e.g. 2) LLA iterations. Additional computational
details of Algorithm 1 are discussed in Appendix B.

A key insight into this algorithm is the following. Suppose a point $b$ is
such that $\mathcal{A}(b)$ has exactly $K$ connected components. Further
suppose the $K+1$st smallest eigenvalue is large enough and $g_{\tau}$ is such
that $g^{\prime}_{\tau}(\lambda_{(K+1)}(\mathcal{L}(|b|)))=0$ (think of
penalties such as SCAD that are eventually flat). In this case we can check
that up to additive constants

$Q(\beta|b)=\frac{1}{2}g^{\prime}_{\tau}(0)\sum_{(ij)\in[D]}\left(\frac{1}{|C(i)|}+\frac{1}{|C(j)|}\right)\cdot\mathbf{1}\left(i\text{
and }j\text{ are in different connected components}\right)\cdot|\beta_{(ij)}|$

where $|C(i)|$ denotes the number of vertices in the connected component that
node $i$ belongs to. In other words $Q(\beta|b)$ puts a Lasso penalty on all
the edges that go between connected components in $\mathcal{A}(b)$, but does
not penalize any edge within a in connected component. Thus if Algorithm 1
reaches a point with $K$ connected components, then the FCLS penalty may force
the next iteration to have the same connected components (see Theorem 3.1).
Similar behavior occurs when $b$ is close to a graph that has $K$ connected
components (see Theorem 3.2).

##  3 Oracle properties of the FCLS penalty

This section studies two questions:

  1. 1.

When is the block oracle solution (made precise below) a stationary point of
the FCLS penalized Problem (3)?

  2. 2.

When does the LLA algorithm find the block oracle solution after exactly two
steps?

Section 3.1 answers the first question, thus providing theoretical guarantees
for a theoretical estimator that we are by no means guaranteed to find.
Section 3.2 answers the second question, thus providing theoretical guarantees
for estimators actually used in practice. Recall that similar guarantees for
an entrywise folded concave concave penalty require only one LLA step (Fan et
al.,, 2014). Sections 3.1 and 3.2 provide deterministic conditions under which
their claims follow. Applying these results requires verifying these
conditions hold with high-probability for particular statistical models, which
is the topic of the following Sections 4 and 5.

###  3.1 When the oracle is a stationary point

Our goal is to estimate some “target” parameter, $\beta^{*}\in\mathbb{R}^{D}$
where $D={d\choose 2}$. For example, $\beta^{*}$ might be the upper triangular
entries of a correlation matrix for a $d$ dimensional random vector.

The results below depend on the following graph quantities. Let
$\mathcal{G}^{*}$ be the binary graph whose adjacency matrix is given by the
support graph, $\mathcal{S}\left(\mathcal{A}(\beta^{*})\right)$. Let
$\mathcal{S}^{*}$ be the connected component support set i.e.
$\mathcal{S}^{*}=\\{(i,j):\mathcal{BS}\left(\mathcal{A}(\beta^{*})\right)_{ij}=1,i<j\\}$;
this is the support set we will attempt to estimate. Also let
$K_{\text{cc}}^{*}$ be the number of connected components of
$\mathcal{G}^{*}$, let $d^{*}_{\text{max}}$ be the largest number of nodes in
a connected component and let $d^{*}_{\text{min}}$ be the smallest size of a
connected component that is not an isolated vertex.

A block oracle estimator, $\widehat{\beta}^{\text{oracle}}$, is a solution to
the following constrained problem

$\displaystyle\underset{\beta\in\mathbb{R}^{D}}{\textup{minimize}}$
$\displaystyle\ell(\beta)$ (8) subject to
$\displaystyle\beta_{\mathcal{S}^{*^{C}}}=0.$

In other worlds, a block oracle knows the true between block edges for the
target parameter. Note this estimator is unaware of any within block edges
that are zero. For simplicity we assume Problem (8) has a unique solution,
$\widehat{\beta}^{\text{oracle}}$, which satisfies the first order necessary
conditions $\nabla_{\mathcal{S}^{*}}\ell(\widehat{\beta}^{\text{oracle}})=0$.

We next define two sets specifying the values of $\beta$ that satisfy
regularity conditions. Let

$\mathcal{B}^{\text{nice grad}}_{t}:=\left\\{\beta\text{ s.t.
}||\nabla_{\mathcal{S}^{*^{C}}}\ell(|\beta|)||_{\text{max}}<t\right\\},$ (9)

be the set of points whose gradients are small for the between block edges
$\mathcal{S}^{*^{C}}$. Let
$\mathcal{C}^{*}_{1},\dots,\mathcal{C}^{*}_{K_{\text{cc,
nz}}^{*}}\subseteq\mathcal{S}^{*}$ be the indices of the $K_{\text{cc,
nz}}^{*}\leq K_{\text{cc}}^{*}$ non-zero connected components of
$\mathcal{G}^{*}$ (recall isolated vertices correspond to zero rows of
$\mathcal{A}(\beta^{*})$). Let

$\mathcal{B}^{\text{big eval, component-wise}}_{t}:=\left\\{\beta\text{ s.t.
}\min_{k\in[K_{\text{cc,
nz}}^{*}]}\lambda_{(2)}\left(\mathcal{L}(|\beta_{\mathcal{C}^{*}_{k}}|)\right)\geq
t\right\\},$ (10)

be the set of points with a large spectral gap.

The theory in this section applies to a class of concave penalties defined in
(Fan et al.,, 2014).

######  Definition 3.1.

Let $a_{0}\geq a_{1}>0$ and $b_{2}>b_{1}>0$. A SCAD-like concave penalty
function, $g_{\tau}:\mathbb{R}_{+}\to\mathbb{R}$, satisfies the following

  1. 1.

$g_{\tau}(t)$ is increasing and concave for $t\in[0,\infty)$ and
$g_{\tau}(0)=0$,

  2. 2.

$g_{\tau}(t)$ is differentiable for $t\in(0,\infty]$ with
$g_{\tau}^{\prime}(0):=g_{\tau}^{\prime}(0+)=a_{0}\tau$,

  3. 3.

$g_{\tau}^{\prime}(t)\geq a_{1}\tau$ for $t\in(0,b_{1}\tau]$,

  4. 4.

$g_{\tau}^{\prime}(t)=0$ for $t\in[b_{2}\tau,\infty)$.

For example, if $g_{\tau}(\cdot)$ is the SCAD penalty where

$g_{\tau}^{\prime}(t)=\tau\mathbf{1}\left(t\leq\tau\right)+\frac{[a\tau-t]_{+}}{a-1}\mathbf{1}\left(t>\tau\right),\qquad\text{
for some }a>2$

then $a_{0}=a_{1}=1$, $b_{1}=1$, $b_{2}=a$. Other penalties satisfying this
definition include the MCP and hard-thresholding penalty, see222Beware our
notation is slightly different. (Fan et al.,, 2014).

Throughout our analysis we make the following basic assumption333We can relax
this uniqueness assumption by checking the regularity conditions hold for any
solution to Problem (8).

######  Assumption 3.1.

The loss function $\ell(\cdot)$ in Problem (3) is convex, $g_{\tau}(\cdot)$
satisfies Definition 3.1, $\widehat{\beta}^{\text{oracle}}$ is the unique
solution to Problem (8), and $\mathcal{A}(\beta^{*})$ has $K_{\text{cc}}^{*}$
connected components as above.

######  Theorem 3.1.

Suppose Assumption 3.1 is satisfied. If
$\widehat{\beta}^{(0)}\in\mathbb{R}^{D}$ is any point whose block support is a
subset of $\beta^{*}$’s block support, i.e.
$\mathcal{BS}\left(\mathcal{A}(\widehat{\beta}^{(0)})\right)\subseteq\mathcal{BS}\left(\mathcal{A}(\beta^{*})\right)$,
and satisfies

$\widehat{\beta}^{(0)}\in\mathcal{B}^{\text{big eval, component-
wise}}_{b_{2}\tau}$ (11)

and the block oracle satisfies

$\widehat{\beta}^{\text{oracle}}\in\mathcal{B}^{\text{nice
grad}}_{\frac{a_{0}\tau}{d^{*}_{\text{max}}}}$ (12)

then taking one LLA step from $\widehat{\beta}^{(0)}$ results in
$\widehat{\beta}^{\text{oracle}}$. In particular, if

$\widehat{\beta}^{\text{oracle}}\in\mathcal{B}^{\text{big eval, component-
wise}}_{b_{2}\tau}\cap\mathcal{B}^{\text{nice
grad}}_{\frac{a_{0}\tau}{d^{*}_{\text{max}}}},$ (13)

then $\widehat{\beta}^{\text{oracle}}$ is fixed point of the LLA algorithm and
therefore is a stationary point of Problem (3).

Let us unpack the conditions of this theorem. The block support assumption on
$\widehat{\beta}^{\text{oracle}}$ guarantees the connected components of
$\mathcal{A}(\widehat{\beta}^{\text{oracle}})$ are a subset of the target’s
connected components. Combining this with the assumption
$\widehat{\beta}^{\text{oracle}}\in\mathcal{B}^{\text{big eval, component-
wise}}_{b_{2}\tau}$ guarantees these connected components are exactly the
target’s connected components.444E.g. this rules out the case that one
connected component is zeroed out while another connected component is split
into two components. This assumption – in conjunction with the spectral
properties of the Laplacian and form of $g_{\tau}$ – guarantee the Laplacian
coefficient, $\mathcal{M}(V^{\text{orc}},w^{\text{orc}})$, computed at the
oracle puts zero penalty on the within block edges and a large penalty on the
between block edges (recall Section 2.2). Finally, the condition
$\widehat{\beta}^{\text{oracle}}\in\mathcal{B}^{\text{nice grad}}_{a_{0}\tau}$
guarantees the between block edges are killable by the latter Lasso terms.

Next we give a sufficient condition to verify elements of
$\mathcal{B}^{\text{big eval, component-wise}}_{t}$. Let

$\triangle^{*}:=\lambda_{(K_{\text{cc}}^{*}+1)}\left(\mathcal{L}(|\beta^{*}|)\right)=\min_{k\in[K_{\text{cc,
nz}}^{*}]}\lambda_{(2)}\left(\mathcal{L}(|\beta^{*}_{\mathcal{C}^{*}_{k}}|)\right).$
(14)

be the target spectral gap, which quantifies the minimal signal strength of
the target graph.555This quantity is the analog of
$||\beta^{*}_{s^{*}}||_{\text{min}}$ from (Fan et al.,, 2014). This quantity
depends on the magnitude of the (smallest) entries of $\beta^{*}$ as well as
on the topology of the binary graph $\mathcal{G}^{*}$. For binary graphs,
finding lower bounds on the second smallest Laplacian eigenvalue – also called
the algebraic connectivity or Fiedler value – is an active area of research
(Fiedler,, 1973; Lu et al.,, 2007; De Abreu,, 2007; Rad et al.,, 2011). For
some important special cases we can give lower bounds on $\triangle^{*}$. When
the non-zero connected components of $\mathcal{G}^{*}$ are fully connected we
have666We have used the elementary Fact D.1 stated in Appendix D.

$\triangle^{*}\geq
d^{*}_{\text{min}}||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}},$ (15)

which shows the more nodes in a connected component, the larger the signal
strength. We can relax the fully connected assumption for (15) e.g. zeroing
out several edges should not dramatically change $\triangle^{*}$. See Appendix
C.1 for additional details.

We next give the non-asymptotic probability that
$\widehat{\beta}^{\text{oracle}}$ is a stationary point. 777We use Weyl’s
inequality and the fact that the operator norm of a block diagonal matrix is
the largest operator norm of the blocks thus
$\beta_{\mathcal{S}^{*^{C}}}=0\text{ and
}||\mathcal{L}(|\beta|-|\beta^{*}|)||_{\text{op}}\leq\triangle^{*}-t\implies\beta\in\mathcal{B}^{\text{big
eval, component-wise}}_{t}$ Let

$\delta^{\text{nice
grad}}_{\text{orc}}:=\mathcal{P}\left(||\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})||_{\text{max}}>\frac{a_{0}\tau}{d^{*}_{\text{max}}}\right),\qquad\delta^{\text{small
lap
resid}}_{\text{orc}}:=\mathcal{P}\left(||\mathcal{L}(|\widehat{\beta}^{\text{oracle}}|-|\beta^{*}|)||_{\text{op}}\geq\triangle^{*}-b_{2}\tau\right).$
(16)

######  Corollary 3.1.

Suppose Assumption 3.1 is satisfied. Then $\widehat{\beta}^{\text{oracle}}$ is
a stationary point of Problem (3) with probability at least
$1-\delta^{\text{nice grad}}_{\text{orc}}-\delta^{\text{small lap
resid}}_{\text{orc}}$.

###  3.2 When the LLA algorithm converges to the block oracle in two steps

We first make a few constructions that capture regularity conditions needed
below. The following set captures the set of points with a large Laplacian
spectral gap

$\mathcal{B}^{\text{gap}}_{s,t}:=\left\\{\beta\text{ s.t.
}\lambda_{(K_{\text{cc}}^{*})}\left(\mathcal{L}(|\beta|)\right)\leq s\text{
and }\lambda_{(K_{\text{cc}}^{*}+1)}\left(\mathcal{L}(|\beta|)\right)\geq
t\right\\}.$ (17)

For a weight vector $w\in\mathbb{R}^{D}_{+}$ with $w_{\mathcal{S}^{*^{C}}}=0$
consider the following Lasso block oracle problem

$\displaystyle\underset{\beta\in\mathbb{R}^{D}}{\textup{minimize}}$
$\displaystyle\ell(\beta)+\frac{1}{2}\sum_{(ij)\in\mathcal{S}^{*}}w_{(ij)}|\beta_{(ij)}|$
(18) subject to $\displaystyle\beta_{\mathcal{S}^{*^{C}}}=0.$

This problem reduces to the block oracle Problem (8) when $w=0$. The following
are two sets of block oracle solutions with “small” Lasso penalties,

$\displaystyle\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
op}}:=\Big{\\{}\beta\in\mathbb{R}^{D}|$ $\displaystyle\beta\text{ is a
minimizer of }\eqref{prob:weighted_lasso_oracle}\text{ for
}w\in\mathbb{R}^{D}_{+},\text{ s.t. }w_{\mathcal{S}^{*^{C}}}=0\text{ and
}||w||_{\text{max}}\leq 2^{5}a_{0}\tau\rho^{2}\Big{\\}}.$ (19)

and

$\displaystyle\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
frob}}:=\Big{\\{}\beta\in\mathbb{R}^{D}|$ $\displaystyle\beta\text{ is a
minimizer of }\eqref{prob:weighted_lasso_oracle}\text{ for
}w\in\mathbb{R}^{D}_{+},\text{ s.t. }w_{\mathcal{S}^{*^{C}}}=0\text{ and}$
(20) $\displaystyle||w||_{\text{max}}\leq
2^{5}a_{0}\tau\rho^{2},\;||w||_{2}\leq
2^{9/2}d^{*^{1/2}}_{\text{max}}a_{0}\tau\rho^{2},\text{ and }||w||_{1}\leq
2^{4}d^{*}_{\text{max}}a_{0}\tau\rho^{2}\Big{\\}}.$

######  Theorem 3.2.

Suppose Assumption 3.1 is satisfied and Lasso oracle Problem (18) has a unique
solution for any weight vector. Fix $\rho\geq 0$. Let
$\widehat{\beta}^{(1)},\widehat{\beta}^{(2)}$ be the result of taking the
first and second LLA steps from $\widehat{\beta}^{(0)}$. If

$\widehat{\beta}^{(0)}\in\mathcal{B}^{\text{gap}}_{b_{1}\tau,b_{2}\tau}$ (21)
$\frac{||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{\text{op}}}{\triangle^{*}}\leq\rho\wedge\frac{1}{2^{6}}\sqrt{\frac{a_{1}}{a_{0}d^{*}_{\text{max}}}},$
(22) $\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
op}}\subseteq\mathcal{B}^{\text{nice
grad}}_{\frac{a_{1}\tau}{4d^{*}_{\text{max}}}},$ (23)

then $\widehat{\beta}^{(1)}\in\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$.
If additionally

$\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}\subseteq\mathcal{B}^{\text{big
eval, component-wise}}_{b_{2}\tau}$ (24)

then $\widehat{\beta}^{(2)}=\widehat{\beta}^{\text{oracle}}$. Furthermore,
taking an additional LLA step from $\widehat{\beta}^{(2)}$ results in the same
estimate i.e. the LLA algorithm has converged to the block oracle estimate.

Furthermore, if (22) is replaced with

$\min\left(||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{F},K_{\text{cc}}^{*^{1/2}}||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{\text{op}}\right)\leq\triangle^{*}\cdot\left(\rho\wedge\frac{1}{2^{6}}\sqrt{\frac{a_{1}}{a_{0}d^{*}_{\text{max}}}}\right),$
(25)

then the above statements hold with $\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
frob}}$ in place of $\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$.

Figure 2 gives a visual depiction of the two step convergence in Theorem 3.2.
Let us unpack the conditions of this theorem. Condition (21) ensures
$g_{\tau}$ only penalizes the smallest $K_{\text{cc}}^{*}$ Laplacian
eigenvalues of the initializer and not the larger ones. Condition (22) says
the initializer must be close enough to the target parameter such their
Laplacian eigenvectors look similar. Condition (23) guarantees the between
block edges are killable by the Lasso penalty that comes from the Laplacian
coefficient of the initializer. Under these assumptions, taking one LLA step
from $\widehat{\beta}^{(0)}$ ends up in $\mathcal{B}_{\rho,\tau}^{\text{lasso
orc}}$. Assumption (24) guarantees taking an LLA step from any element of
$\mathcal{B}_{\rho,\tau}^{\text{lasso orc}}$ lands at the block oracle (by
Theorem 3.1). The parameter $\rho$ is introduced because making the set
$\mathcal{B}_{\rho,\tau}^{\text{lasso orc}}$ small enough so that the
conditions hold with high probability requires a model specific analysis.

Figure 2:  Two step convergence of the LLA algorithm where the target graph is
given in Figure 1(a). The columns show the initializer and the output of the
first two LLA steps. The first row show the matrices
$\mathcal{A}(|\beta^{(s)}|)$ at each step, $s=0,1,2$. The second row shows the
spectrum of the Laplacian, $\mathcal{L}(|\beta^{(s)}|)$. In Theorem 3.2 the
estimate, $\widehat{\beta}^{(1)}$, after the first LLA step is close to the
block oracle i.e. all between block edges are zero but the within block edges
are not exactly the block oracle. The estimate, $\widehat{\beta}^{(2)}$, after
the second LLA step is exactly the block oracle. Note some edges in the block
oracle may be incorrectly identified as non-zero e.g. edge $(1,4)$ in the
third column.

We next give a non-asymptotic probability bound that the LLA algorithm
converges to the block oracle after two steps. Let

$\displaystyle C_{\rho}$
$\displaystyle:=\min\left(\rho,\frac{1}{2^{6}}\sqrt{\frac{a_{1}}{a_{0}d^{*}_{\text{max}}}},\frac{b_{1}}{b_{1}+b_{2}}\right)(b_{1}+b_{2})$
(26) $\displaystyle\delta^{\text{good init, op}}$
$\displaystyle:=\mathcal{P}\left(||\mathcal{L}(|\widehat{\beta}^{\text{initial}}|-|\beta^{*}|)||_{\text{op}}\geq
C_{\rho}\tau\right)$ $\displaystyle\delta^{\text{nice grad, op}}$
$\displaystyle:=\mathcal{P}\left(\sup_{\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso
orc,
op}}}||\nabla_{\mathcal{S}^{*^{C}}}\ell(\beta)||_{\text{max}}>\frac{a_{1}\tau}{4d^{*}_{\text{max}}}\right)$
$\displaystyle\delta^{\text{small lap resid, op}}$
$\displaystyle:=\mathcal{P}\left(\sup_{\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso
orc, op}}}||\mathcal{L}(|\beta|-|\beta^{*}|)||_{\text{op}}\geq
b_{1}\tau\right).$

We also define $\delta^{\text{good init, frob}}$ similarly to
$\delta^{\text{good init, op}}$, but with the left hand side of (25) in place
of the operator norm. Also let $\delta^{\text{nice grad, frob}}$ be the
quantity $\delta^{\text{small lap resid, op}}$ but with
$\mathcal{B}_{\rho,\tau}^{\text{lasso orc, frob}}$ in place if
$\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$ (similarly for
$\delta^{\text{small lap resid, frob}}$).

######  Corollary 3.2.

Suppose Assumption 3.1 is satisfied, the Lasso oracle Problem (18) has a
unique solution for any weight vector and

$\triangle^{*}\geq(b_{1}+b_{2})\tau.$ (27)

Then the LLA algorithm initialized from $\widehat{\beta}^{\text{initial}}$
will converge to $\widehat{\beta}^{\text{oracle}}$ in two steps with
probability at least $1-\delta^{\text{good init, op}}-\delta^{\text{nice grad,
op}}-\delta^{\text{small lap resid, op}}$. This statement also holds with
probability at least $1-\delta^{\text{good init, frob}}-\delta^{\text{nice
grad, frob}}-\delta^{\text{small lap resid, frob}}$.

To apply this corollary have to verify regularity conditions hold for every
element of $\mathcal{B}_{\rho,\tau}^{\text{lasso orc}}$. If the loss function,
$\ell(\cdot)$ is strongly convex when restricted to $\mathcal{S}^{*}$, then we
can reduce these conditions to statements about
$\widehat{\beta}^{\text{oracle}}$ (see Corollary F.1 in Appendix F.2) , which
can then be controlled using standard concentration inequalities. The logistic
regression example in Section 5.2 uses a more involved fixed point argument
due to the lack of strong convexity.

##  4 Block diagonal shrinkage

This section shows how the theory from Section 3 applies when $\ell(\cdot)$ is
the squared loss. Suppose $\widehat{\beta}^{\text{ok}}$ is an “ok” estimate
(e.g. the sample covariance matrix) for a target parameter $\beta^{*}$ (e.g.
the population covariance matrix). We can obtain an better estimator by
shrinking $\widehat{\beta}^{\text{ok}}$ towards a block diagonal matrix by
computing proximal operator of the FCLS penalty,

$\displaystyle\underset{\beta\in\mathbb{R}^{{d\choose 2}}}{\textup{minimize}}$
$\displaystyle\frac{1}{2}||\widehat{\beta}^{\text{ok}}-\beta||_{2}^{2}+s_{\tau}\left(\beta\right).$
(28)

This “shrink an ok estimator” idea is used for classical sparse estimation
problems such as sparse covariance estimation (Bickel et al.,, 2008; Rothman
et al.,, 2009). Instead of solving this problem exactly, we can use the LLA
algorithm to approximate its solution. Below we show that as long as
$\widehat{\beta}^{\text{ok}}$ is an “ok” estimate of $\beta^{*}$ and a “good
enough” initializer, $\widehat{\beta}^{\text{initial}}$, is used then the LLA
algorithm obeys the strong oracle property after two steps.

The results of this section are directly applicable to many statistical models
including covariance estimation (Ravikumar et al.,, 2011), correlation matrix
estimation for non-paranormal copula models (Liu et al.,, 2012), and multi-
layer community detection. While our results can be applied immediately to
these settings, we will not state these extensions explicitly for the sake of
brevity.

Throughout this section we will assume Assumption 3.1 is satisfied. The
results below will depend on the target parameter $\beta^{*}$ via: the
spectral gap $\triangle^{*}$, the block sparsity support size
$s^{*}:=|\mathcal{S}^{*}|$, the number of connected components,
$K_{\text{cc}}^{*}$, and the number of nodes in the largest connected
component $d^{*}_{\text{max}}$. We will also need the following quantities
based on the binary target graph $\mathcal{G}^{*}$ : the number of non-zero
connected components, $K_{\text{cc, nz}}^{*}$ the number of non-isolated
vertices $d_{\text{non-iso}}$, and the largest node degree, $\mathscr{d}^{*}$.

Recall $c,C,c_{i}$ denote absolute constants that may change from line to
line.

###  4.1 Stationary point for independent, unbiased, sub-Gaussian residuals

In this section we work under the following assumption.

######  Assumption 4.1.

Assume the entries of $\widehat{\beta}^{\text{ok}}$ are independent,
$\mathbb{E}\left[\widehat{\beta}^{\text{ok}}\right]=\beta^{*}$ and have sub-
Gaussian tails with variance proxy $\frac{\sigma^{2}}{n}$. That is
$\mathcal{P}\left(|\widehat{\beta}^{\text{ok}}_{\ell}-\beta^{*}_{\ell}|>t\right)\leq
2\exp\left(\frac{-nt^{2}}{2\sigma^{2}}\right)$ for each $\ell\in[D]$.

While this setting is meant to illustrate the theory in the nicest statistical
setting it is also motivated by the following multi-layer, weighted network
community detection model (similar models are studied in Levin et al.,
(2019)). Suppose we observe $n$ independent networks with real valued edges
$\\{\mathcal{A}(x_{i})\\}_{i=1}^{n}$, where each $x_{i}\in\mathbb{R}^{D}$.
Assume an additive noise model $x_{i}=\beta^{*}+e_{i}$ where
$e_{i}\in\mathbb{R}^{D}$ $i=1,\dots,n$ are independent, mean zero noise
vectors whose entries follow sub-Gaussian distributions with variance proxy
$\sigma^{2}$. Let
$\widehat{\beta}^{\text{ok}}=\frac{1}{n}\sum_{i=1}^{n}x_{i}$. Note
$\widehat{\beta}^{\text{ok}}=\beta^{*}+\epsilon$ where the entries of
$\epsilon$ are independent, mean 0 and follow sub-Gaussian distributions with
variance proxy $\frac{\sigma^{2}}{n}$.

######  Theorem 4.1.

Suppose Assumption 4.1 holds, $\triangle^{*}\geq 2b_{2}\tau$ and

$4b_{2}\tau\geq
c_{1}d^{*}_{\text{max}}\left(\frac{\sigma}{\sqrt{n}}+||\beta^{*}||_{\text{max}}\right)\exp\left(-\frac{c_{2}n||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}^{2}}{\sigma^{2}}\right)+c_{3}\sigma\sqrt{\frac{d^{*}_{\text{max}}}{n}}.$
(29)

Then $\widehat{\beta}^{\text{oracle}}$ is a stationary point of Problem (28)
with probability $1-\delta^{\text{nice grad}}_{\text{orc}}-\delta^{\text{small
lap resid}}_{\text{orc}}$, where

$\delta^{\text{small lap resid}}_{\text{orc}}=d_{\text{non-
iso}}\exp\left(-\frac{nc_{4}b_{2}^{2}\tau^{2}}{8d^{*}_{\text{max}}\sigma^{2}}\right)+K_{\text{cc,
nz}}^{*}4\exp\left(-\frac{nc_{5}b_{2}^{2}\tau^{2}}{16\sigma^{2}}\right)$ (30)

and

$\delta^{\text{nice
grad}}_{\text{orc}}=2(D-s^{*})\exp\left(-\frac{na_{0}^{2}\tau^{2}}{2d^{*^{2}}_{\text{max}}\sigma^{2}}\right).$

Condition (29) can easily be weakened (e.g. allowing within block zeros), but
we state it as above for the sake of exposition.888This assumption requires
$||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}>0$ (i.e. the target graph should
be fully connected) and $||\beta^{*}||_{\text{max}}$ to be not too large. Both
of these requirements can be significantly weakened by modifying (87) in the
proof of Theorem 4.1. In the setting of this theorem we see there exists a
value of $\tau$ such that $\beta^{*}$ is a stationary point with overwhelming
probability if $\triangle^{*}\geq
c\sigma\sqrt{\max\left(d^{*}_{\text{max}}\log d_{\text{non-
iso}},d^{*^{2}}_{\text{max}}\log(D-s^{*})\right)}$.

######  Remark 4.1.

Suppose the non-empty connected components of the target graph all have
$q^{*}$ nodes; for this topology $\triangle^{*}\geq
q^{*}||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}$. We will refer to this as
the basic target graph in the sequel.

For the basic target graph, the spectral gap requirement translates to
$||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}\geq
c\sigma\sqrt{\log(D-s^{*})}$. This is the same condition for the hard
thresholding estimator to succeed with overwhelming probability, see Appendix
E. Next consider the noisy within block edge setting where the elements of
$\mathcal{S}^{*}$ have sub-Gaussian parameter $\omega>>\sigma$. In this case
we can check the target gap requirement becomes
$||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}\geq
c\sqrt{\max\left(\frac{\omega^{2}}{q^{*}}\log d_{\text{non-
iso}},\sigma^{2}\log(D-s^{*})\right)}$. Hard-thresholding on the other hand
requires $||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}\geq
c\sqrt{\max\left(\omega^{2}\log d_{\text{non-
iso}},\sigma^{2}\log(D-s^{*})\right)}$. In this case $\omega$ can be up to
$\sqrt{q^{*}}$ times larger than $\sigma$ before these two conditions are
equal.

###  4.2 Two step convergence

This section considers more general conditions on
$\widehat{\beta}^{\text{ok}}$ by relaxing Assumption 4.1 e.g. we do not assume
unbiasedness or independence. We measure the quality of
$\widehat{\beta}^{\text{ok}}$ via an entrywise residual tail condition by
borrowing the following definition from (Ravikumar et al.,, 2011).

######  Definition 4.1.

Let $f:\mathbb{N}\times\mathbb{R}_{+}\to\mathbb{R}_{+}$ be monotonically
decreasing in both arguments and let $v_{*}\in[0,\infty)$. We say an estimator
$\widehat{\beta}^{\text{ok}}\in\mathbb{R}^{D}$ satisfies a
$\mathcal{T}(f,v_{*})$ residual tail condition if for each $\ell\in[D]$,

$\mathcal{P}\left(|\widehat{\beta}^{\text{ok}}_{\ell}-\beta^{*}_{\ell}|>t\right)\leq
f(n,t),\qquad\text{for all }t\in(0,1/v_{*}],$ (31)

where $1/0:=+\infty$ by convention (i.e. if $v_{*}=0$ the bound is valid for
all $t>0$). We assume $f(n,t)=1$ for $t\in(0,1/v_{*}]^{C}$.

For example, in Lemma 1 of (Ravikumar et al.,, 2011) the empirical covariance
matrix from $n$ samples satisfies a $\mathcal{T}(f,v_{*})$ residual tail
condition for some $v_{*}$ and $f(n,t)=4\exp\left(-cnt^{2}\right)$ for some
constant $c$.

######  Theorem 4.2.

Assume $\widehat{\beta}^{\text{ok}}$ is an estimator satisfying a
$\mathcal{T}(f,v_{*})$ residual tail condition and
$\triangle^{*}\geq(b_{1}+b_{2})\tau$. Suppose $\rho$ satisfies

$\rho\leq\sqrt{\frac{b_{1}}{2^{7}a_{0}d^{*}_{\text{max}}}}$ (32)

and
$\max(\frac{a_{1}\tau}{4},\frac{b_{1}\tau}{4d^{*}_{\text{max}}})\leq\frac{1}{v_{*}}$.
Then the LLA algorithm initialized by $\widehat{\beta}^{\text{initial}}$
converges to $\widehat{\beta}^{\text{oracle}}$ after two steps with
probability at least $1-\delta^{\text{good init, op}}-\delta^{\text{nice grad,
op}}-\delta^{\text{small lap resid, op}}$, where

$\delta^{\text{nice grad,
op}}:=(D-s^{*})f\left(n,\frac{a_{1}\tau}{4d^{*}_{\text{max}}}\right),$ (33)

and

$\delta^{\text{small lap resid,
op}}:=s^{*}f\left(n,\frac{b_{1}\tau}{4d^{*}_{\text{max}}}\right).$ (34)

Next we turn our attention to the initializer. For very high dimensional
settings when $d>>n$, $\widehat{\beta}^{\text{ok}}$ may not be a sufficiently
good initializer. Fortunately by thresholding $\widehat{\beta}^{\text{ok}}$ we
can obtain a good enough initializer for high-dimensional settings. Note the
following definition, borrowed from (Rothman et al.,, 2009), encompasses many
common thresholding operators including hard-thresholding, soft-thresholding,
etc.

######  Definition 4.2.

A generalized thresholding operator is a function
$T_{\gamma}\left(\cdot\right):\mathbb{R}\to\mathbb{R}$ satisfying

$1.\;|T_{\gamma}\left(z\right)|\leq|z|\qquad
2.\;T_{\gamma}\left(z\right)=0,\text{ if }|z|\leq\tau\qquad
3.\;|T_{\gamma}\left(z\right)-z|\leq\tau,$

for all $z\in\mathbb{R}$ and $\gamma\geq 0$.

The following corollary puts Theorem 4.2 together with three choices of the
initializer; $\widehat{\beta}^{\text{ok}}$,
$T_{\gamma}\left(\widehat{\beta}^{\text{ok}}\right)$, and $0$. Recall that if
we initialize from 0, the first step of the LLA algorithm is equivalent to a
Lasso penalty with parameter $a_{0}\tau$ (by Proposition 2.1 and Definition
3.1).

######  Corollary 4.1.

Suppose the assumptions of Theorem 4.2 hold. If the LLA algorithm is
initialized by $\widehat{\beta}^{\text{ok}}$ then

$\delta^{\text{good init, op}}=Df\left(n,\frac{C_{\rho}\tau}{2d}\right).$ (35)

Let $T_{\gamma}\left(\cdot\right)$ be any generalized thresholding operator
satisfying Definition 4.2. Assume $\rho$ satisfies (32) and recall $C_{\rho}$
from (26). If

$\gamma\leq\frac{C_{\rho}\tau}{12\mathscr{d}^{*}}$ (36)

and the LLA algorithm is initialized by
$T_{\gamma}\left(\widehat{\beta}^{\text{ok}}\right)$ then

$\delta^{\text{good init,
op}}=2\mathscr{s}^{*}f\left(n,\gamma\right)+2Df\left(n,\frac{1}{2}\gamma\right).$
(37)

Furthermore, if $a_{0}\leq\frac{C_{\rho}}{12\mathscr{d}^{*}}$ and the LLA
algorithm is initialized at 0 then

$\delta^{\text{good init,
op}}=2\mathscr{s}^{*}f\left(n,\tau\right)+2Df\left(n,\frac{1}{2}\tau\right).$
(38)

A similar statement using $\delta^{\text{good init, frob}}$ is possible (see
the proof of Corollary 4.1). In the independent, sub-Gaussian setting of the
previous section we can improve upon the direct applications of Theorem 4.2
and Corollary 4.1.

######  Remark 4.2.

If $\widehat{\beta}^{\text{ok}}$ satisfies Assumption 4.1 and $8b_{1}\tau$ is
at least the right hand size of (29) then

$\delta^{\text{small lap resid, op}}=d_{\text{non-
iso}}\exp\left(-\frac{nc_{1}b_{1}^{2}\tau^{2}}{d^{*}_{\text{max}}\sigma^{2}}\right)+4K_{\text{cc,
nz}}^{*}\exp\left(-\frac{nc_{2}b_{1}^{2}\tau^{2}}{\sigma^{2}}\right).$

Similarly, if the LLA algorithm is initialized by
$\widehat{\beta}^{\text{ok}}$ and $8C_{\rho}\tau$ is at least (29) then

$\delta^{\text{good init, op}}=d_{\text{non-
iso}}\exp\left(-\frac{nc_{3}C_{\rho}^{2}\tau^{2}}{d^{*}_{\text{max}}\sigma^{2}}\right)+4K_{\text{cc,
nz}}^{*}\exp\left(-\frac{nc_{4}C_{\rho}^{2}\tau^{2}}{\sigma^{2}}\right)+2d\exp\left(-\frac{nc_{5}C_{\rho}^{2}\tau^{2}}{d\sigma^{2}}\right).$

These two claims follow from technical lemmas provided in the appendix.

Next we put these results into context by working under the independent, sub-
Gaussian setting of Assumption 4.1. In this case, if we use
$\widehat{\beta}^{\text{ok}}$ as the initializer we need $\triangle^{*}\geq
c\sigma\sqrt{d^{*}_{\text{max}}d\log d}$ for there to be a value of $\tau$
such that the LLA algorithm converges to the oracle in two steps with
overwhelming probability. On the other hand if we initialize with an
appropriately chosen thresholded initializer we need $\triangle^{*}\geq
c\sigma\sqrt{d^{*}_{\text{max}}\mathscr{d}^{*^{2}}\log d}$. Without the
independence/unbiasedness of Assumption 4.1 these become slightly worse. If we
assume the basic target graph topology from the previous section then these
conditions translate to $||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}\geq
c\sigma\sqrt{\frac{d\log d}{q^{*}}}$ and
$||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}\geq c\sigma\sqrt{q^{*}\log d}$
respectively.999For this graph topology note $\frac{d}{q^{*}}=K_{\text{cc,
nz}}^{*}+\frac{\mathscr{i}^{*}}{q^{*}}$ is linear in $K_{\text{cc, nz}}^{*}$,
not in $q^{*}$. These rates are worse than those required for stationary point
conditions and hard thresholding estimator discussed in the previous section.
The empirical evidence from Section 6 suggests these rates can be improved.

##  5 Block sparse regression

This section studies the FCLS penalty LLA algorithm for linear and logistic
regression. As in the previous section we assume Assumption 3.1 is satisfied
throughout this section. The setup in this section closely follows the
examples of Fan et al., (2014).

###  5.1 Linear regression

Consider the least squares objective function with the FCLS penalty,

$\displaystyle\underset{\beta\in\mathbb{R}^{{d\choose 2}}}{\textup{minimize}}$
$\displaystyle\frac{1}{2n}||y-X\beta||_{2}^{2}+s_{\tau}\left(\beta\right)$
(39)

where $y\in\mathbb{R}^{n}$ is the response vector and $X\in\mathbb{R}^{n\times
D}$ is the covariate matrix.

Let $\beta^{*}\in\mathbb{R}^{D}$ be the true parameter vector in the linear
regression model $y=X\beta^{*}+\epsilon$. We assume then entries of
$\epsilon\in\mathbb{R}^{n}$ are $i.i.d$ mean zero $\sigma$ sub-Gaussian. For
linear regression the oracle estimator has a closed form,

$\widehat{\beta}^{\text{oracle}}=(\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*}},0),\text{
where
}\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*}}=(X^{T}_{\mathcal{S}^{*}}X_{\mathcal{S}^{*}})^{-1}X^{T}_{\mathcal{S}^{*}}y.$

We will need the following quantities:
$\lambda_{\text{min},\mathcal{S}^{*}}:=\lambda_{\text{min}}\left(\frac{1}{n}X_{\mathcal{S}^{*}}^{T}X_{\mathcal{S}^{*}}\right)$,
$\lambda_{\text{max}}:=\lambda_{\text{max}}\left(\frac{1}{n}X^{T}X\right)$,
$M:=\frac{1}{n}\max_{j\in[D]}||X_{j}||_{2}^{2}$ (which is often normalized to
be 1).

######  Theorem 5.1.

Assume $\triangle^{*}\geq(b_{1}+b_{2})\tau$ and let

$\rho\leq\sqrt{\frac{a_{1}\lambda_{\text{min},\mathcal{S}^{*}}}{a_{0}\sqrt{2^{11}d^{*}_{\text{max}}M\lambda_{\text{max}}}}}\wedge\sqrt{\frac{b_{1}\lambda_{\text{min},\mathcal{S}^{*}}}{64a_{0}d^{*}_{\text{max}}}}.$
(40)

Then the LLA algorithm initialized by $\widehat{\beta}^{\text{initial}}$
converges to $\widehat{\beta}^{\text{oracle}}$ in two steps with probability
at least $1-\delta^{\text{good init, frob}}-\delta^{\text{nice grad,
frob}}-\delta^{\text{small lap resid, frob}}$, where

$\delta^{\text{nice grad,
frob}}=2(D-s^{*})\exp\left(\frac{-na_{1}^{2}\tau^{2}}{32d^{*^{2}}_{\text{max}}\sigma^{2}M}\right)$
(41)

and

$\delta^{\text{small lap resid,
frob}}=2s^{*}\exp\left(\frac{-n\lambda_{\text{min},\mathcal{S}^{*}}b_{1}^{2}\tau^{2}}{32d^{*^{2}}_{\text{max}}\sigma^{2}}\right).$
(42)

We complement Theorem 5.1 by showing that the LLA algorithm can be initialized
by a Lasso estimate as in Fan et al., (2014). We use Theorem 7.13 of
Wainwright, (2019) to bound the Lasso error under the assumption that $X$
satisfies the $(\kappa_{\text{linear}},3)$ restricted eigenvalue condition
stated in (7.22) of Wainwright, (2019). Under the sub-Gaussian error
assumptions of this section the Lasso solution,
$\widehat{\beta}^{\text{lasso}}$, with penalty parameter $\gamma$ satisfies

$||\widehat{\beta}^{\text{lasso}}-\beta^{*}||_{1}\leq\frac{12\mathscr{s}^{*}\gamma}{\kappa_{\text{linear}}}$

with probability at least $1-2\exp(-\frac{n\gamma^{2}}{8\sigma^{2}M^{2}})$.

######  Corollary 5.1.

Suppose the assumptions of Theorem 5.1 hold and

$\frac{12\mathscr{s}^{*}\gamma}{\kappa_{\text{linear}}}\leq\frac{C_{\rho}\tau}{4},$

where $\rho$ is given in (40) and $C_{\rho}$ is given in (26). Then the two
step convergence claim of Theorem 5.1 holds when the LLA algorithm is
initialized by $\widehat{\beta}^{\text{lasso}}$ where

$\delta^{\text{good init,
frob}}=2\exp(-\frac{n\gamma^{2}}{8\sigma^{2}M^{2}}).$

Furthermore, if
$\frac{12\mathscr{s}^{*}a_{0}}{\kappa_{\text{linear}}}\leq\frac{C_{\rho}}{4}$
then the LLA algorithm initialized by 0 converges to
$\widehat{\beta}^{\text{oracle}}$ after three steps with probability at least
$1-2\exp(-\frac{n\tau^{2}}{8\sigma^{2}M^{2}})-\delta^{\text{nice grad,
frob}}-\delta^{\text{small lap resid, frob}}$.

Assume the target graph has the basic topology discussed in the previous
section. In this case there exists a value of $\tau$ such that the LLA
algorithm initialized from an appropriately selected Lasso initializer
converges to $\beta^{*}$ in two steps with overwhelming probability if
$||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}\geq c\sigma K_{\text{cc,
nz}}^{*}q^{*^{3/2}}\sqrt{\log d}$. Section 6 suggests this rate may be
improvable.

###  5.2 Logistic regression

This section considers logistic regression when the true coefficient vector is
block sparse. Suppose we observe a covariate matrix $X\in\mathbb{R}^{n\times
D}$ and a random binary response vector $y\in\\{0,1\\}^{n}$. We assume the
standard logistic regression setup

$y_{i}|X(i,:)\sim\text{Bernoulli}\left(\frac{e^{X(i,:)^{T}\beta^{*}}}{1+e^{X(i,:)^{T}\beta^{*}}}\right),i=1,\dots,n\text{,
independently},$ (43)

where $\beta^{*}\in\mathbb{R}^{D}$ is the true coefficient vector. The FCLS
penalized logistic regression problem is then given by

$\displaystyle\underset{\beta\in\mathbb{R}^{D}}{\textup{minimize}}$
$\displaystyle\frac{1}{n}\sum_{i=1}\left(-y_{i}X(i,:)^{T}\beta+\psi\left(X(i,:)^{T}\beta\right)\right)+s_{\tau}\left(\beta\right),$
(44)

where $\psi\left(t\right)=\log(1+e^{t})$ is the canonical link function.

To ease notation we make a few definitions. Let
$M:=\max_{j\in[D]}\frac{||X_{j}||_{2}^{2}}{n}$ and $m:=||X||_{\text{max}}$.
Let $h\left(\cdot\right):\mathbb{R}^{D}\to\mathbb{R}^{n}$ be the function
given by
$h\left(\beta\right)_{i}=\psi^{\prime\prime}\left(X(i,:)^{T}\beta\right),i=1,\dots,n$.
Let
$Q_{1}:=\max_{j\in[D]}\lambda_{\text{max}}\left(\frac{1}{n}X_{\mathcal{S}^{*}}^{T}\text{diag}(|X_{j}|)X_{\mathcal{S}^{*}}\right)$,
$Q_{2}:=||\frac{1}{n}X_{\mathcal{S}^{*^{C}}}^{T}\text{diag}(h\left(\beta^{*}\right)))X_{\mathcal{S}^{*}}||_{\text{max}}$,
and
$Q_{3}:=||\left(\frac{1}{n}X_{\mathcal{S}^{*}}^{T}\text{diag}(h_{\mathcal{S}^{*}}\left(\beta^{*}\right))X_{\mathcal{S}^{*}}\right)^{-1}||_{(\infty\to\infty)}$.

######  Theorem 5.2.

Assume $\triangle^{*}\geq(b_{1}+b_{2})\tau$, the columns of
$X_{\mathcal{S}^{*}}$ are linearly independent and let

$\rho\leq\sqrt{\frac{1}{2^{7}a_{0}Q_{3}}\min\left(\frac{b_{1}}{2d^{*}_{\text{max}}},\frac{a_{1}}{8d^{*}_{\text{max}}\left(s^{*}Q_{2}+\frac{\sqrt{s^{*}}Q_{1}}{8}\right)}\right)}$
(45)

and assume

$\tau\leq\frac{4}{s^{*}Q_{1}Q_{3}}\min\left(\frac{d^{*}_{\text{max}}}{2b_{1}},\frac{8d^{*}_{\text{max}}\left(s^{*}Q_{2}+\frac{\sqrt{s^{*}}Q_{1}}{8}\right)}{a_{1}}\right).$
(46)

Then the LLA algorithm initialized by $\widehat{\beta}^{\text{initial}}$
converges to $\widehat{\beta}^{\text{oracle}}$ in two steps with probability
at least $1-\delta^{\text{good init, op}}-\delta^{\text{nice grad,
op}}-\delta^{\text{small lap resid, op}}$, where

$\delta^{\text{nice grad,
op}}=2s^{*}\exp\left(-\frac{n}{M}\left(\frac{a_{1}}{8d^{*}_{\text{max}}\left(s^{*}Q_{2}+\frac{\sqrt{s^{*}}Q_{1}}{8}\right)}\right)^{2}\tau^{2}\right)+(D-s^{*})\exp\left(\frac{-na_{1}^{2}\tau^{2}}{64d^{*^{2}}_{\text{max}}M}\right)$
(47)

and

$\delta^{\text{small lap resid,
op}}=2s^{*}\exp\left(-\frac{n}{M}\frac{b_{1}^{2}\tau^{2}}{4d^{*^{2}}_{\text{max}}}\right)$
(48)

As in the previous section, Lasso penalized logistic regression gives a “good
enough” initial estimator assuming an appropriate restricted eigenvalue
condition. In the following theorem $\widehat{\beta}^{\text{lasso}}$ is the
Lasso solution with tuning parameter $\gamma$ and we assume a restricted
eigenvalue condition (108) is satisfied with parameter
$\kappa_{\text{logistic}}$. See Appendix F.3 for details.

######  Corollary 5.2.

Suppose the assumptions of Theorem 5.2 hold and

$\frac{20\mathscr{s}^{*}}{\kappa_{\text{logistic}}}\gamma\leq\frac{C_{\rho}\tau}{4}$

where $\rho$ is given in (45). Then the two step convergence claim of Theorem
5.2 holds when the LLA algorithm is initialized by
$\widehat{\beta}^{\text{lasso}}$ where

$\delta^{\text{nice grad, op}}=\delta^{\text{nice grad,
frob}}=2D\exp(-\frac{n}{2M}\gamma^{2}).$

Furthermore if
$\frac{20\mathscr{s}^{*}a_{0}}{\kappa_{\text{logistic}}}\leq\frac{C_{\rho}}{4}$
then the LLA algorithm initialized by 0 converges to
$\widehat{\beta}^{\text{oracle}}$ after three steps with probability at least
$1-2D\exp(-\frac{n}{2M}\tau^{2})-\delta^{\text{nice grad,
op}}-\delta^{\text{small lap resid, op}}$.

##  6 Simulations

This section studies several FCLS penalized models discussed in previous
sections through simulations. The block diagonal shrinkage algorithm from
Section 4 is examined for a Gaussian sequence model (Section 6.1) and for
covariance estimation (Section 6.2). The block sparse linear and logistic
regression models from Section 5 are examined in Sections 6.3 and 6.4
respectively.

For each model we look at three target graph topologies with two fully
connected components consisting of: 5 , 10, and 25 nodes. In other words
$\beta^{*}$ has $D={2\cdot 5\choose 2}=45$ dimensions for the first graph,
${2\cdot 10\choose 2}=190$ for the second, and ${2\cdot 25\choose 2}=1225$ for
the third.101010For these graphs $\beta^{*}$ has $2\times{5\choose 2}=20$,
$2\times{10\choose 2}=90$, and $2\times{25\choose 2}=600$ non-zero elements
respectively.

This section focuses on how close the FCLS penalized estimator – and its
entrywise sparse competitors – comes the block oracle,
$\widehat{\beta}^{\text{oracle}}$. For each model and graph topology the
competing estimators are fit for a range of number of samples and each
experiment is repeated $20$ times. Throughout this section $g_{\tau}$ is set
to be the SCAD function111111We found empirically that smaller values of $a$
worked better for the FCLS penalty contrary to the the standard default of
$a=3.7$. with $a=2.1$.

Each of the algorithms in this section require selecting a tuning parameter
e.g. $\tau$ for the FCLS penalty. To simplify the comparison of competing
models we “cheat” by picking the best possible tuning parameter for the models
presented below. In other words, we fit each model for a range of tuning
parameter values then pick the tuning parameter that gives the best
performance (i.e. the one whose estimate is nearest the block oracle). The
tuning parameter range for the FCLS models is specified using the discussion
in Appendix B. Choosing a good initializer is important for obtaining good
performance. For each model below we tune the initializers using 10-fold
cross-validitaion i.e. we do not “cheat” for the initializers. For tuning the
FCLS penalty in practice we suggest cross-validation.

The code to reproduce the results is provided in the github repository linked
to in Section 1. This software makes use of several standard python libraries
(Hunter,, 2007; Pedregosa et al.,, 2011; Harris et al.,, 2020; Virtanen et
al.,, 2020; Waskom,, 2021), an accelerated coordinate descent package for
linear regression (Massias et al.,, 2020; Bertrand and Massias,, 2021) and a
recently developed package for penalized GLMs (Carmichael,, 2021).

###  6.1 Gaussian sequence model

This section examines the block diagonal shrinkage algorithm from Section 4 in
the context of a Gaussian sequence model. For this model we observe
$x_{1},\dots,x_{n}\in\mathbb{R}^{D}$, $x_{i}=\beta^{*}+\sigma\epsilon_{i}$
where each $\epsilon_{i}\sim N(0,I_{D})$ independently. Each non-zero entry of
$\beta^{*}$ is set to 1 and we set121212This value is selected such that
$||\widehat{\beta}^{\text{oracle}}-\beta^{*}||_{2}\approx||\beta^{*}||_{2}$
with $n=10$ samples, which indicates we are in a very challenging signal to
noise regime. $\sigma=3.25$. For the objective of Problem (28) we use
$\widehat{\beta}^{\text{ok}}=\overline{x}$.

We examine the LLA algorithm with three different initialization strategies:
1) hard-thresholding tuned with 10 fold cross-validation 2) from the empirical
means, $\widehat{\beta}^{\text{ok}}$, and 3) from 0. We also examine the LLA
after two steps (three for the 0 initialization) and after convergence to a
stationary point. As a baseline for comparison we contrast the block diagonal
shrinkage estimate to the entrywise hard-thresholding estimate and the
empirical means. Recall the FCLS and baseline hard-thresholded estimates are
tuned via “cheating” by selecting the tuning parameter whose estimate is
nearest to $\widehat{\beta}^{\text{oracle}}$.

Figure 3 examines the models across a range of number of samples for each of
the three graph topologies. This figure shows the FCLS penalty initialized
from either 10-CV hard-thresholding or from the empirical means performs the
best. The performance gap between block diagonal shrinkage and hard-
thresholding appears to widen for target graphs with larger connected
components.

Figure 3 shows 10-CV hard-thresholding and empirical means initialization
strategies perform similarly while the 0 initialization strategy performs
worse. For the first two initializers, running the LLA algorithm to
convergence does not provide much benefit over just two steps. These
observations hold for the models in the following sections so we omit them
from the following figures.

(a) Two $5\times 5$ blocks

(b) Two $10\times 10$ blocks

(c) Two $25\times 25$ blocks

Figure 3:  Results for Gaussian sequence model. The $x$-axis shows the number
of samples and the $y$-axis shows the relative $L_{2}$ norm error of the
estimated coefficient to the oracle coefficient i.e.
$||\widehat{\beta}-\widehat{\beta}^{\text{oracle}}||_{2}/||\widehat{\beta}^{\text{oracle}}||_{2}$.
The shaded area shows the standard error after 20 Monte-Carlo repetitions. The
FCLS penalized models are shown in blue with either a dot (hard-threshold
initialization), 0 (0 initialization) or e (empirical initialization).

###  6.2 Covariance estimation

This section examines the block diagonal shrinkage algorithm from Section 4 in
the context of covariance estimation. In this case we observe
$x_{1},\dots,x_{n}\in\mathbb{R}^{D}$ independently where $x_{i}\sim
N(0,\Sigma^{*})$ and $\Sigma^{*}=I_{D}+\mathcal{A}(\beta^{*})$. The non-zero
entries of $\beta^{*}$ are set to 0.3. Here $\widehat{\beta}^{\text{ok}}$ is
set to the upper triangular elements of the empirical covariance matrix
$\widehat{\Sigma}$. As in the previous section the LLA algorithm is
initialized with a hard-thresholding operation tuned with 10-fold cross-
validation.

Figure 4 examines the models across a range of number of samples for each of
the three graph topologies. As in the previous section the block diagonal
shrinkage estimate has the best performance. Similarly, the gap between block
diagonal shrinkage and hard-thresholding appears to increase with larger block
sizes.

(a) Two $5\times 5$ blocks

(b) Two $10\times 10$ blocks

(c) Two $25\times 25$ blocks

Figure 4:  Results for covariance estimation. The FCLS penalized model is
shown with blue dots.

###  6.3 Linear regression

This section examines the block sparse linear regression example from Section
5.1. In this case we observe $(y_{1},x_{1}),\dots,(y_{i},x_{n})$ where
$x_{i}\sim N(0,I_{D})$ and $y_{i}=x_{i}^{T}\beta^{*}+\epsilon_{i}$ for
$\epsilon_{i}\sim N(0,1)$ independently. The non-zero entries of $\beta^{*}$
are randomly set to $\pm 1$.

The LLA algorithm for the FCLS penalized model is initialized using a Lasso
estimator that is tuned via 10-fold cross-validation. As a baseline for
comparison we compute the Lasso estimate and the entrywise SCAD penalized
estimator with $a=3.7$ following (Fan and Li,, 2001). This entrywise SCAD
penalty is fit with one step of the LLA algorithm as in Fan et al., (2014) and
initialized with the same Lasso estimate. Recall both the Lasso and entrywise
SCAD estimators are tuning via “cheating”.

Figure 5 examines these models across a range of number of samples for each of
the three graph topologies. Both the FCLS solution and SCAD solution
eventually return the block oracle estimate (with high probability) after
enough samples. The FCLS estimator, however, typically finds the oracle with
fewer samples than its entrywise competitor. As in the previous sections FCLS
penalized estimate has the best performance and the gap to the competing
method appears to increase with larger block sizes.

(a) Two $5\times 5$ blocks

(b) Two $10\times 10$ blocks

(c) Two $25\times 25$ blocks

Figure 5:  Results for linear regression.

###  6.4 Logistic regression

This section examines the block sparse logistic regression example from
Section 5.2. Here we follow the setup from the previous section except of
course the conditional distribution $y_{i}|x_{i}$ follows (43). We added a
small ridge penalty of $0.01$ to the logistic regression loss function to
improve stability.131313Unpenalized logistic regression becomes unstable when
the classes are linearly separable. This issue comes up when the FCLS
penalized model solution finds the block oracle estimator and the block oracle
estimator can perfectly separate the two classes. In other words the loss
function is given by

$\ell(\beta)=\frac{1}{n}\sum_{i=1}\left(-y_{i}X(i,:)^{T}\beta+\psi\left(X(i,:)^{T}\beta\right)\right)+0.01\cdot\frac{1}{2}||\beta||_{2}^{2}$

instead of just the sum. Note the block oracle estimator inherits the ridge
penalty. Figure 6 examines the performance of the competing methods and the
takeaways are the same as in the previous sections.

(a) Two $5\times 5$ blocks

(b) Two $10\times 10$ blocks

(c) Two $25\times 25$ blocks

Figure 6:  Results for logistic regression.

##  7 Discussion

This paper makes four contributions: we propose the FCLS penalty, provide a
majorization-minimization algorithm based on a weighted Lasso surrogate
function, develop a theoretical framework showing this penalty obeys the
strong oracle property after 2 steps of the LLA algorithm, and show this
theory applies to several standard statistical models. The two step
convergence guarantees in Sections 4 and 5 apply in ultra-high dimensional
settings with an appropriate initializer (e.g. the Lasso estimate). The theory
should apply to many statistical models beyond those studied in these two
sections.

The simulations in Section 6 show that the FCLS penalized models outperform
competing methods such as hard-thresholding or the entrywise SCAD penalty. The
rates provided in Sections 4 and 5, however, are often worse than known rates
for the entrywise competitors (Fan et al.,, 2014). These two facts suggest
there is room for improvement in the theory of FCLS penalized models.

Finally we point out a few additional lines of future inquiry. Appendix A
sketches extensions of the FCLS penalty to rectangular and multi-array
settings, which may be interesting for a variety of applications such as
multi-response regression. While we focus on the penalized estimator, Problem
(3), the results in Section 3 can be adapted to a constrained formulation of
this problem similar to ones considered in (Nie et al.,, 2016, 2017; Kumar et
al.,, 2019). In reality we may not expect $\beta^{*}$ to be perfectly block
diagonal, but rather approximately block diagonal e.g. when
$||\lambda\left(\mathcal{L}(|\beta^{*}|)\right)||_{q}$ is small for some
$q\in[0,1]$. Extending our theory to this approximately block diagonal setting
may be useful. Decomposing $\beta=\beta_{\text{block
diag}}+\beta_{\text{sparse}}$ into the sum of a block diagonal plus sparse
vector – in the spirit of (Candès et al.,, 2011; Tan et al.,, 2014) – may also
be of interest for applications.

## Acknowledgments

The author was supported by the National Science Foundation under Award No.
1902440. We thank Mathurin Massias and Quentin Bertrand for adding a weighted
Lasso solver for linear regression to their andersoncd
package.141414https://github.com/mathurinm/andersoncd/ We also thank Deborah
Carmichael, Calum Carmichael, and Ema Perkovic for helpful editorial feedback.

##  Appendix A Block-diagonal rectangular matrices and multi-arrays

In the body of the paper we assumed $\beta\in\mathbb{R}^{{d\choose 2}}$ could
be viewed as the entries of a hollow-symmetric matrix,
$\mathcal{A}(\beta)\in\mathbb{R}^{d\times d}$. Then we used the FCLS penalty
to impose a block diagonal structure on $\mathcal{A}(\beta)$. This section
extends this idea to block diagonal rectangular matrices and multi-arrays (see
Figure 1). We sketch the main ideas, but do not pursue a detailed
investigation here.

###  A.1 Rectangular matrices and the bipartite FCLS penalty

Suppose $\beta\in\mathbb{R}^{RC}$ can be viewed as the entries of a
rectangular matrix $\textsc{mat}(\beta)\in\mathbb{R}^{R\times C}$. Let

$\mathcal{A}_{\text{bp}}(\beta)=\begin{bmatrix}0&\textsc{mat}(\beta)\\\
\textsc{mat}(\beta)^{T}&0\end{bmatrix}\in\mathbb{R}^{(R+C)\times(R+C)}$ (49)

be the adjacency matrix of the bipartite graph whose real valued edges are
given by $\textsc{mat}(x)$.

Forcing $\mathcal{A}_{\text{bp}}(x)$ to have multiple connected components
forces $\textsc{mat}(\beta)$ to have a block diagonal structure e.g. see
Figure 1(b). Let

$s_{\text{bp},\tau}(\beta):=\frac{1}{2}g_{\tau}\circ\lambda(\mathcal{L}(\mathcal{A}_{\text{bp}}(|\beta|))),$
(50)

be the bipartite FCLS penalty. We can then use the LLA algorithm presented in
Section 2.2 to solve the following problem

$\underset{\beta\in\mathbb{R}^{RC}}{\textup{minimize}}\;\;\ell(\beta)+s_{\text{bp},\tau}(\beta).$
(51)

###  A.2 Multi-arrays and the hypergraph FCLS penalty

In the previous section we saw how to view a rectangular matrix as a bipartite
graph. There we viewed the rows and columns as vertices and the edges as
connections between two vertices. In this section we start with a multi-array
$A\in\mathbb{R}^{d^{(1)}\times\dots\times d^{(V)}}$ and show how to view it as
a graph whose connected components define a multi-array block diagonal
structure. The key step is to view the entries of $A$ as the hyperedges of a
certain hypergraph. Then we can follow the outline of the previous section and
develop a multi-array version of the FCLS penalty. The discussion in this
section closely follows (Zhou et al.,, 2006; Carmichael,, 2020).

A hypergraph is a generalization of a graph where the hyperedges can connect
more than two vertices (Berge,, 1984; Zhou et al.,, 2006). Formally a binary
hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$ is a collection of vertices
$\mathcal{V}$ and hyperedges $\mathcal{E}$ where each hyperedge is a subset of
$V$ with at least two elements (we do not allow self-loops here!) For example,
a binary graph is a hypergraph where each subset in $\mathcal{E}$ has exactly
two elements. A weighted hypergraph
$\mathcal{H}=(\mathcal{V},\mathcal{E},\mathcal{W})$ has an additional map
$\mathcal{W}:\mathcal{E}\to\mathbb{R}_{+}$ that assigns a positive number to
each hyperedge (we only consider positive weights for simplicity).

Next we interpret a multi-array151515We will assume the entries of $A$ are
positive; we can always take absolute values to make this happen!
$A\in\mathbb{R}^{d^{(1)}\times\dots\times d^{(V)}}_{+}$ as a hypergraph,
$\mathcal{H}(A)$ where the vertices are

$\mathcal{V}(A):=\\{(v,i):v\in[V],i\in[d^{(v)}]\\}$

i.e. the generalization of rows and columns to multi-arrays. Note
$|\mathcal{V}(A)|=s:=\sum_{v=1}^{V}d^{(v)}$. The hyperedges correspond to the
non-zero entries of $A$. In other words the hyperedge
$\\{(1,i^{(1)}),\dots,(V,i^{(V)})\\}\subseteq\mathcal{V}(A)$ is present if and
only if $A_{i^{(1)},\dots,i^{(V)}}\neq 0$. Note each present hyperedge has
exactly $V$ elements; each edge contains exactly one element from each axis of
$A$. The hyperedge weights are then given by the entries of $A$.

We can identify the blocks of the multi-array $A$ with the connected
components of the hypergraph $\mathcal{H}(A)$. For example, the multi-array in
Figure 1(c) has 4 connected components. The first connected component is
$\\{(1,1),(2,1),(3,1)\\}$ and corresponds to the bottom left red block i.e.
the entry $A_{111}$. The second connected component is
$\\{(v,j):j=2,3,v=1,2,3\\}$ and corresponds to the green block whose entries
are $\\{A_{ijk}:i,j,k=2,3\\}$. The isolated vertex $(1,6)$ is also a connected
component corresponding to an empty block.

Next we map the weighted hypergraph of $A$ into a weighted $V$-partite graph
that we call the hypergraph adjacency matrix.161616This adjacency matrix
implicitly defines a weighted, undirected graph. Let
$\mathcal{HA}(A)\in\mathbb{R}^{s\times s}$ be a hollow symmetric matrix whose
rows/columns are indexed by the vertices, $\mathcal{V}(A)$. The entries of
this matrix correspond to a (weighted) graph where edges can only occur
between two vertices on different axes of $A$ e.g. $(a,k^{(a)})$ and
$(b,k^{(b)})$ where $a\neq b$. The weight of such an edge is equal to

$\mathcal{HA}(A)_{(a,k^{(a)}),(b,k^{(b)})}=\sum_{v\in[V]/\\{a,b\\}}\sum_{j^{(v)}=1}^{d^{(v)}}\mathcal{HA}(A)_{j^{(1)},\dots,k^{(a)},\dots,k^{(b)},\dots
j^{(V)}}.$ (52)

In other words, we take a two-dimensional slice of $A$ by fixing axes $a,b$
and squash the other dimensions down into this slice via summation. See Figure
10.c of Carmichael, (2020). Note $\mathcal{HA}(A)$ is equivalent to the
hypergraph adjacency matrix defined at the end of Section 2 in (Zhou et al.,,
2006). This graph captures the connected component information of
$\mathcal{H}(A)$.

######  Proposition A.1.

There is a one-to-one correspondence between the connected components of the
hypergraph $\mathcal{H}(A)$ and the connected components of the graph
$\mathcal{HA}(A)$.

The advantage of working with the graph $\mathcal{HA}(A)$ is we can use the
previously developed Laplacian approach to imposing a connected component
structure. In other words, the spectrum of $\mathcal{L}(\mathcal{HA}(A))$
captures the connected components of $\mathcal{HA}(A)$ and therefore also
$\mathcal{H}(A)$.

Finally suppose we have a model parameter $\beta\in\mathbb{R}^{p}$ where
$p:=\prod_{v=1}^{V}d^{(v)}$ that can be viewed as the entries of a multi-array
$\textsc{arr}(x)\in\mathbb{R}^{d^{(1)}\times\dots\times d^{(V)}}$. We then
define the hypergraph folded Laplacian spectral penalty as

$s_{\text{hyper},\tau}(\beta):=\frac{1}{2}g_{\tau}\circ\lambda\circ\mathcal{L}\circ\mathcal{HA}\circ\textsc{arr}(|\beta|).$
(53)

We can use the LLA algorithm presented in Section 2.2 with minor modifications
to solve the following problem

$\underset{\beta\in\mathbb{R}^{p}}{\textup{minimize}}\;\;\ell(\beta)+s_{\text{hyper},\tau}(\beta)$
(54)

that will impose a block diagonal structure on $\textsc{arr}(|\beta|)$.

##  Appendix B Specifying the largest value for the FCLS tuning parameter

In practice we need to compute the tuning path of solutions to the FCLS
penalized Problem (3) over a range of $\tau$ values in
$[0,\tau_{\text{max}}]$. For Lasso penalized problems, we can often find an
intelligent choice for the maximal tuning parameter (Friedman et al.,, 2010).

######  Definition B.1.

For a given loss function $\ell(\cdot)$ we say $\gamma_{\text{lasso-killer-
lbd}}\in\mathbb{R}_{+}$ is a killer Lasso lower bound if171717This value does
not have to exist! for all weight vectors $c\in\mathbb{R}^{D}_{+}$ satisfying
$\min(c)\geq\gamma_{\text{lasso-killer-lbd}}$ the solution to the following
weighted Lasso problem is 0

$\underset{\beta\in\mathbb{R}^{D}}{\textup{minimize}}\;\;\ell(\beta)+\sum_{j=1}^{D}c_{j}|\beta_{j}|.$
(55)

We are not required to find the possible smallest value of
$\gamma_{\text{lasso-killer-lbd}}$. For convex loss functions

$\gamma_{\text{lasso-killer-lbd}}=||\nabla\ell(0)||_{\text{max}},$ (56)

is a killer Lasso lower bound.181818To see this note $0$ is a stationary point
if there is a solution to the first order necessary condition
$\nabla_{\beta}\ell(0)+c\odot\nabla||0||_{1}=0$. Recalling the form of the
sub-gradient of the $L_{1}$ norm we obtain the stated bound. Of course we need
something like strict convexity to guarantee that 0 is the unique stationary
point. For the loss functions considered in Sections 4 and 5 we have the
following explicit expressions:

  * •

For the Frobenius norm loss function in (28), $\gamma_{\text{lasso-killer-
lbd}}=||\widehat{\beta}^{\text{ok}}||_{\text{max}}$.

  * •

For the least squares loss function without an intercept in (39),
$\gamma_{\text{lasso-killer-lbd}}=\frac{1}{n}||X^{T}y||_{\text{max}}$.

  * •

For the logistic loss function without an intercept in (44),
$\gamma_{\text{lasso-killer-
lbd}}=\frac{1}{n}||X^{T}(\frac{1}{2}\mathbf{1}_{n}-y)||_{\text{max}}$.

We can use a killer Lasso lower bound to obtain the largest reasonable tuning
parameter value for the LLA algorithm from Section 2.2.

######  Proposition B.1.

Let $\widehat{\beta}^{\text{initial}}\in\mathbb{R}^{D}$ be the initializer to
the LLA algorithm for Problem (3) where $g_{\tau}(\cdot)$ satisfies Definition
3.1. Suppose $\gamma_{\text{lasso-killer-lbd}}$ is a killer lasso lower bound
and let

$\tau_{\text{FCLS-killer-
lbd}}:=\max\left(\frac{\lambda_{\text{max}}\left(\mathcal{L}(|\widehat{\beta}^{\text{initial}}|)\right)}{b_{1}},\frac{\gamma_{\text{lasso-
max}}}{a_{1}}\right).$ (57)

Then for all $\tau\geq\tau_{\text{FCLS-killer-lbd}}$ the LLA algorithm
initialized from $\widehat{\beta}^{\text{initial}}$ converges to 0 in one
step.

##  Appendix C Laplacian spectral bounds

This section studies quantities and bound related to the Laplacian that play
an important role in the theory. Section C.1 reviews the spectra of some
important example graphs. Section C.2 compares norms of $\mathcal{L}(r)$ to
norms of the edge vector $r$. In particular, Remark C.1 summarizes facts that
we use frequently in the proofs. Finally, Section C.3 studies the Laplacian
coefficient from Section 2.2.

###  C.1 Spectra of some important binary graphs

The largest and second smallest Laplacian eigenvalues plan an important role
in our theory. Table 1 shows the largest and second smallest Laplacian
eigenvalues for some important graphs binary, undirected graphs.

| $\lambda_{(2)}\left(\mathcal{L}(A)\right)$ | $\lambda_{\text{max}}\left(\mathcal{L}(A)\right)$
---|---|---
Fully connected graph | d | $d$
Star graph | 1 | $1$
Path graph | $O\left(\frac{1}{d^{2}}\right)$ | $O(1)$
Any graph | $\geq\frac{d}{1+\text{diam}\cdot E_{\text{missing}}}$ |
Table 1:  Largest and second smallest Laplacian eigenvalues for connected
graphs on $d$ nodes. Here $A\in\\{0,1\\}^{d\times d}$ is the adjacency matrix
of graph listed in the first column. Here we see, unsurprisingly
$\lambda_{(2)}\left(\mathcal{L}(A)\right)$, is generally larger for graphs
with more edges though the path graph is a counter example of this trend.

Here $\text{diam}\leq d-1$ is the diameter of the graph and let
$E_{\text{missing}}\leq{d\choose 2}$ be the number of edges missing from $A$.
The claims about the three simple graphs are standard results in spectral
graph theory e.g. see (Spielman,, 2004). The lower bound on the algebraic
connectivity for any graph is from Theorem 1 of (Lu et al.,, 2007); a better
albeit less transparent lower bound can be found in (Rad et al.,, 2011). Using
this lower bound we can generalize (15) to

$\triangle^{*}\geq\frac{d^{*}_{\text{min}}}{1+E^{*}_{\text{max
missing}}\text{diam}^{*}_{\text{max}}}||\beta^{*}_{\mathbb{S}^{*}}||_{\text{min}}.$
(58)

where $\mathbb{S}^{*}=\\{(ij)|\beta^{*}_{(ij)}\neq 0\\}$ is the support set of
$\beta^{*}$.

###  C.2 Laplacian vs. adjacency matrix norms

The goal of this section is to bound norms of the Laplacian
$||\mathcal{L}(\cdot)||$ by norms of $||r||$. Throughout this section we
assume $r\in\mathbb{R}^{D}$ where $D={d\choose 2}$. The bounds191919Similar
expressions could be derived by starting with (59) and using the fact
$||r||_{1}\leq\sqrt{D}||r||_{2}\leq D||r||_{\text{max}}$ however these would
be looser than the stated bounds. in Proposition C.1 are also shown to be
tight (at least up to constants) without further assumptions.

######  Proposition C.1.

Let $r\in\mathbb{R}^{D}$, then

$\displaystyle||\mathcal{L}(r)||_{1}$ $\displaystyle\leq 4||r||_{1}$ (59)
$\displaystyle||\mathcal{L}(r)||_{F}$ $\displaystyle\leq\sqrt{2d}||r||_{2}$
(60) $\displaystyle||\mathcal{L}(r)||_{\text{F}}$
$\displaystyle\leq\sqrt{d^{3}+d^{2}-d}||r||_{\text{max}}$ (61)
$\displaystyle||\mathcal{L}(r)||_{F}$
$\displaystyle\leq\sqrt{2d}||\mathcal{A}(r)||_{\text{op}}$ (62)
$\displaystyle||\mathcal{L}(r)||_{\text{op}}$ $\displaystyle\leq
2||\mathcal{A}(r)||_{\text{op}-1}\leq 2d||r||_{\text{max}}$ (63)
$\displaystyle||\mathcal{L}(r)||_{\text{op}}$
$\displaystyle\leq||\mathcal{A}(r)\mathbf{1}_{d}||_{\text{max}}+||\mathcal{A}(r)||_{\text{op}}.$
(64)

If the largest degree of a node in the binary graph of
$\mathcal{S}\left(\mathcal{A}(r)\right)$ is equal to $\mathscr{d}^{*}$ then
$d$ can be replaced with $\mathscr{d}^{*}$ for claims (59), (60) and (63).

Furthermore we have the lower bound
$||\mathcal{A}(r)\mathbf{1}_{d}||_{\text{max}}\leq||\mathcal{L}(r)||_{\text{op}}$.

For a symmetric matrix $A\in\mathbb{R}^{d\times d}$ we have the following
inequalities: $||A||_{\text{op}}\leq||A||_{F}\leq||A||_{1}$,
$||A||_{F}\leq\sqrt{d}||A||_{\text{op}}$, and
$||A||_{\text{op}}\leq||A||_{\text{op}-1}\leq\sqrt{d}||A||_{\text{op}}\leq
d||A||_{\text{max}}$. Proof of the second two inequalities can be found in
Section 2.3 of (Golub and Van Loan,, 2013). Using these expressions we can
obtain additional upper bounds on $||\mathcal{L}(r)||_{\text{op}}$ from (59),
(60), and (63) as well as on on $||\mathcal{L}(r)||_{F}$ from (63). All pairs
of upper bounds are summarized in Table 2.

| $||r||_{1}$ | $||r||_{2}$ | $||r||_{\text{max}}$ | $||\mathcal{A}(r)||_{\text{op}-1}$ | $||\mathcal{A}(r)||_{\text{op}}$ | $||\mathcal{A}(r)\mathbf{1}_{d}||_{\text{max}}+||\mathcal{A}(r)||_{\text{op}}$
---|---|---|---|---|---|---
$||\mathcal{L}(r)||_{F}$ | O(1) | $O(d^{1/2})*$ | $O(d^{3/2})$ | $O(d^{1/2})*$ | $O(d^{1/2})$ | $O(d^{1/2})$
$||\mathcal{L}(r)||_{\text{op}}$ | $O(1)$ | $O(d^{1/2})*$ | $O(d)*$ | O(1) | $O(d^{1/2})$ | O(1)
Table 2:  Upper bound on the ratio
$\frac{||\mathcal{L}(r)||}{||\mathcal{A}(r)||}$ for different pairs of norms
from Proposition C.1. A $*$ means the dimension $d$ can be replaced with the
maximal degree $\mathscr{d}^{*}$.

All of the upper bounds in Proposition C.1 are as good as we can ask for (up
to constants) without additional assumptions. Table 3 shows the ratios from
Table 2 for three example graphs. For example, the star graph shows the
$\sqrt{d}$ factor is necessary for the ratio
$||\mathcal{L}(r)||_{\text{op}}/||r||_{2}$. These upper bounds, however, may
be loose for graphs observed in practice. For example, upper bound on the
Laplacian operator norm vs. $||r||_{1}$ or $||r||_{2}$ is loose for the
complete graph.

| Complete graph | Star graph | Path graph
---|---|---|---
$||r||_{\text{max}}$ |  $O(1)$ (op, F) |  $O(1)$ (op) | $O(1)$
$||r||_{2}$ |  $O(d)$ (F) |  $O(\sqrt{d})$ (op, F) | $O(\sqrt{d})$
$||r||_{1}$ | $O(d^{2})$ |  $O(d)$ (op, F) | $O(d)$
$||\mathcal{A}(r)||_{\text{op}}$ |  $O(d)$ (F) |  $O(\sqrt{d})$ (op, F) |  $O(1)$ (F)
$||\mathcal{A}(r)\mathbf{1}_{d}||_{\text{max}}+||\mathcal{A}(r)||_{\text{op}}$ |  $O(d)$ (op, F) |  $O(d)$ (op) |  $O(1)$ (op, F)
$||A(r)||_{\text{op}-1}$ |  $O(d)$ (op, F) |  $O(d)$ (op) |  $O(1)$ (op, F)
$||\mathcal{L}(r)||_{\text{op}}$ | $O(d)$ | $O(d)$ | $O(1)$
$||\mathcal{L}(r)||_{F}$ | $O(d^{3/2})$ | $O(d)$ | $O(d^{1/2})$
Table 3:  Norms of three example graphs on $d$ nodes (up to multiplicative
constants). An $(op)$ means the upper bound on the ratio for
$||\mathcal{L}(r)||_{\text{op}}$ given in Table 2 is met. An $(F)$ means the
same thing for $||\mathcal{L}(r)||_{F}$. For each upper bound there is an
example where this upper bound is met, however, for several of the examples
the upper bound is loose.

Due to the importance of controlling residuals of the Laplacian we explicitly
state the bounds we use frequently.

######  Remark C.1.

Let $r,x,y\in\mathbb{R}^{D}$ then

$||\mathcal{L}(r)||_{F}\leq 4||r||_{1}\wedge\sqrt{2d}||r||_{2}$ (65)
$||\mathcal{L}(r)||_{\text{op}}\leq
2d||r||_{\text{max}}\wedge||\mathcal{A}(r)||_{\text{op}-1}\wedge\left(||\mathcal{A}(r)\mathbf{1}_{d}||_{\text{max}}+||\mathcal{A}(r)||_{\text{op}}\right).$
(66)

We also have the obvious bound that
$||\mathcal{L}(r)||_{\text{op}}\leq||\mathcal{L}(r)||_{F}$. If
$\mathcal{A}(r)$ has a maximal degree of $\mathscr{d}^{*}$ then $d$ can be
replaced with $\mathscr{d}^{*}$ in these two equations. If $\mathcal{A}(r)$
has $K_{\text{cc}}^{*}$ connected components indexed by
$\mathcal{C}^{*}_{1},\dots,\mathcal{C}^{*}_{K_{\text{cc}}^{*}}$ then
$||\mathcal{L}(r)||_{\text{op}}=\sup_{k\in[K_{\text{cc}}^{*}]}||\mathcal{L}(r_{\mathcal{C}^{*}_{k}})||_{\text{op}}$.

We need to be careful about comparing $\mathcal{L}(|x|-|y|)$ to
$\mathcal{L}(x-y)$. In general we do not have the entrywise
relationship202020E.g. consider $r=[-1,-1,1]^{T}$ so
$\sum_{i=1}^{3}|r_{i}|=3>2=|\sum_{i=1}r_{i}|$.
$|\mathcal{A}(|x|-|y|)\mathbf{1}_{d}|\leq|\mathcal{A}(x-y)\mathbf{1}_{d}|$.
Therefore we are not guaranteed to be able to immediately compare
$||\mathcal{L}(|x|-|y|)||$ to $||\mathcal{L}(x-y)||$. We do have
$|\mathcal{A}(|x|-|y|)\mathbf{1}_{d}|\leq\mathcal{A}(|x-y|)\mathbf{1}_{d}$ so
we can immediately compare $\mathcal{L}(|x|-|y|)$ to $\mathcal{L}(|x-y|)$
using entrywise norms.

###  C.3 Laplacian coefficient comparison

The following proposition shows how much $\mathcal{M}(\cdot,w)$ can change as
a function of its first argument.

######  Proposition C.2.

Let $w\in\mathbb{R}^{K}_{+}$ and $V_{A},V_{B}\in\mathbb{R}^{d\times K}$ then

$|\mathcal{M}(V_{A},w)_{(ij)}^{1/2}-\mathcal{M}(V_{B},w)_{(ij)}^{1/2}|\leq
2\sqrt{\max(w)}||V_{A}-V_{B}||_{(2\to\infty)}$ (67)

Let $\mathcal{G}$ be a binary, undirected graph on $d$ nodes and let
$d^{*}_{\text{max}}$ be size of the largest connected component, then

$\sum_{(ij)\in\mathcal{G}}|\mathcal{M}(V_{A},w)_{(ij)}^{1/2}-\mathcal{M}(V_{B},w)_{(ij)}^{1/2}|^{2}\leq
2\max(w)d^{*}_{\text{max}}||V_{A}-V_{B}||_{F}^{2}$ (68)

and

$\sum_{(ij)\in\mathcal{G}}|\mathcal{M}(V_{A},w)_{(ij)}^{1/2}-\mathcal{M}(V_{B},w)_{(ij)}^{1/2}|^{4}\leq
8\max(w)^{2}d^{*}_{\text{max}}||V_{A}-V_{B}||_{F}^{4}$ (69)

where each edge is only counted once in the sum.

The following proposition shows that the surrogate function $Q(\cdot|b)$ only
penalizes between block edges when $b$ has multiple connected components.

######  Proposition C.3.

Let $A\in\mathbb{R}^{d\times d}_{+}$ be the adjacency matrix of a graph with
$K$ connected components. Suppose $V\in\mathbb{R}^{d\times K}$ is any
orthonormal matrix of eigenvectors corresponding to the $K$ 0 eigenvalues of
$\mathcal{L}(A)$ (i.e. a basis for the kernel). For $i,j\in[d]$ we write
$i\sim_{CC}j$ if nodes $i$ and $j$ are in the same connected component of $A$.
Then for any $w\in\mathbb{R}^{K}_{+}$,

$\displaystyle\mathcal{M}(V,w)_{ij}$ $\displaystyle=0$ $\displaystyle\text{ if
}i\sim_{CC}j$ $\displaystyle\mathcal{M}(V,w)_{ij}$
$\displaystyle\geq\min(w)\left(\frac{1}{|C(i)|}+\frac{1}{|C(j)|}\right)\geq\frac{2\min(w)}{d^{*}_{\text{max}}}$
$\displaystyle\text{ if }i\not\sim_{CC,y}j.$

where $|C(i)|$ denotes the number of vertices in the connected component that
the vertex $i$ belongs to and $d^{*}_{\text{max}}$ is the size of the largest
connected component.

The following lemma shows that when $b$ is close to a graph with multiple
connected components, the surrogate function $Q(\cdot|b)$ puts large weights
on between block edges and small weights on within block edges.

######  Lemma C.1.

Let $x,y\in\mathbb{R}^{D}_{+}$. Suppose $\mathcal{A}(y)$ is the adjacency
matrix of a graph with $K$ connected components and
$\lambda_{(K+1)}\left(\mathcal{L}(y)\right)\geq\triangle$. Let
$V_{x}\in\mathbb{R}^{n\times K}$ be any orthonormal matrix of the smallest $K$
eigenvectors of $\mathcal{L}(x)$ and let $w\in\mathbb{R}^{K}_{+}$. Let
$\mathcal{S}=\mathcal{BS}\left(\mathcal{A}(y)\right)$ be the block support of
$\mathcal{A}(y)$, $d^{*}_{\text{max}}$ be the largest number of nodes in a
connected component of $\mathcal{A}(y)$,

$\mathbb{F}=\min\left(||\mathcal{L}(x-y)||_{F},K_{\text{cc}}^{*^{1/2}}||\mathcal{L}(x-y)||_{\text{op}}\right),\text{
and }\mathbb{P}=||\mathcal{L}(x-y)||_{\text{op}}.$

Then

$\displaystyle||\mathcal{M}(V_{x},w)_{\mathcal{S}^{C}}||_{\text{min}}$
$\displaystyle\geq\left(\sqrt{\frac{2\min(w)}{d^{*}_{\text{max}}}}-2^{5/2}\sqrt{\max(w)}\frac{\mathbb{F}}{\triangle}\right)^{2}$
(70) $\displaystyle||\mathcal{M}(V_{x},w)_{\mathcal{S}}||_{\text{max}}$
$\displaystyle\leq 2^{5}\max(w)\left(\frac{\mathbb{F}}{\triangle}\right)^{2}$
$\displaystyle||\mathcal{M}(V_{x},w)_{\mathcal{S}}||_{1}$ $\displaystyle\leq
2^{4}d^{*}_{\text{max}}\max(w)\left(\frac{\mathbb{F}}{\triangle}\right)^{2}$
$\displaystyle||\mathcal{M}(V_{x},w)_{\mathcal{S}}||_{2}$ $\displaystyle\leq
2^{9/2}d^{*^{1/2}}_{\text{max}}\max(w)\left(\frac{\mathbb{F}}{\triangle}\right)^{2}$

If $\mathbb{P}\leq\frac{1}{2}\triangle$ then

$\displaystyle||\mathcal{M}(V_{x},w)_{\mathcal{S}^{C}}||_{\text{min}}$
$\displaystyle\geq\left(\sqrt{\frac{2\min(w)}{d^{*}_{\text{max}}}}-2^{5/2}\sqrt{\max(w)}\frac{\mathbb{P}}{\triangle}\right)^{2}$
(71) $\displaystyle||\mathcal{M}(V_{x},w)_{\mathcal{S}}||_{\text{max}}$
$\displaystyle\leq 2^{5}\max(w)\left(\frac{\mathbb{P}}{\triangle}\right)^{2}$

The operator norm part of the previous lemma depends on the following variant
of the Davis-Kahan theorem.

######  Lemma C.2.

Let $A,B\in\mathbb{R}^{d\times d}$ be symmetric and positive semi-definite.
Suppose $A$ has a $K$ dimensional kernel and $U_{A}\in\mathbb{R}^{d\times K}$
is any orthonormal basis for this kernel. Let Let
$\lambda_{B,\perp}\in\mathbb{R}^{d-K}_{+}$ be the leading $d-K$ eigenvalues of
$B$ and let $U_{B,\perp}\in\mathbb{R}^{d\times(d-K)}$ be a corresponding
orthonormal matrix of eigenvectors. Finally let
$\triangle_{A}=\lambda_{(K+1)}(A)$ and $\triangle_{B}=\lambda_{(K+1)}(B)$.

Then there exists an orthonormal matrix $Q\in\mathbb{R}^{K\times K}$ such that

$||U_{B}-U_{A}Q||_{\text{op}}\leq\sqrt{2}||U_{B,\perp}^{T}U_{A}||_{\text{op}}\leq\frac{\sqrt{2}||BU_{A}||_{\text{op}}}{\triangle_{B}}\leq\frac{\sqrt{2}||B-A||_{\text{op}}}{\triangle_{B}}.$
(72)

Furthermore, if $||B-A||_{\text{op}}\leq\frac{1}{2}\triangle_{A}$ then

$||U_{B}-U_{A}Q||_{\text{op}}\leq
2\sqrt{2}||U_{B,\perp}^{T}U_{A}||_{\text{op}}\leq\frac{2\sqrt{2}||BU_{A}||_{\text{op}}}{\triangle_{A}}\leq\frac{2\sqrt{2}||B-A||_{\text{op}}}{\triangle_{A}}.$
(73)

From the proof of this Lemma we can see that a similar result holds for any
unitarily invariant matrix norm.

##  Appendix D Proofs for Sections 2 and 3

######  Fact D.1.

Let $A,B\in\mathbb{R}^{d\times d}_{+}$ be two hollow symmetric non-negative
matrices then

$A\geq
B\implies\lambda_{j}(\mathcal{L}(A))\geq\lambda_{j}(\mathcal{L}(B)),\text{ for
each }j=1,\dots,d,$

where the inequality applies entrywise.

This follows from the fact $\mathcal{L}(A-B)$ is semi-definite (since $A-B\geq
0$ entrywise) and that summing two positive semi-definite matrices increases
the eigenvalues.

###  D.1 Proofs for Section 2.2

Recall $\mathcal{M}(V,w)$ defined in Section 2.2. A useful property of this
quantity is for any $\beta\in\mathbb{R}^{D}$,

$\beta^{T}\mathcal{M}(V,w)=\frac{1}{2}\sum_{i,j=1,i\neq
j}^{d}\beta_{(ij)}\sum_{k=1}^{K}w_{k}||V(i,k)-V(j,k)||_{2}^{2}=\sum_{k=1}^{K}w_{k}V_{k}^{T}\mathcal{L}(\beta)V_{k}=\text{Tr}(V^{T}\mathcal{L}(\beta)V\text{diag}(w)).$
(74)

###### Proof.

of Proposition 2.1 Following the discussion in Section 2.2 and the fact that
$t_{\tau}$ is concave we need only check the super-gradient formula (5) to
verify $Q$ is a surrogate function.

Let $G:\mathbb{R}^{d\times d}$ be given by $G(L)=g_{\tau}\circ\lambda(L)$ i.e.
$t_{\tau}\left(x\right)=f(\mathcal{L}(x))$. By Theorem 6 of (Lewis,, 1999), we
have the super-differential formula

$\nabla G(L)=V\text{diag}(w)V^{T}$

where $V\in\mathbb{R}^{d\times d}$ is any orthonormal matrix whose columns are
eigenvalues of $L$ and $w=g_{\tau}^{\prime}\circ\lambda(L)$ is any super-
gradient.

Recall $\mathcal{L}:\mathbb{R}^{d}\to\mathbb{R}^{d\times d}$ is a linear
function and $\frac{d\mathcal{L}(x)}{dx_{j}}=\mathcal{L}(e_{j})$ where $j$ is
the $j$th standard basis vector. Let $V$ be any matrix of eigenvectors of
$L(x)$ and $w=g_{\tau}^{\prime}\circ\lambda(L(x))$ any super-gradient.
Therefore by the chain rule e.g. see (Petersen and Pedersen,, 2012)

$\frac{d}{dx_{j}}t_{\tau}\left(x\right)=\left\langle\frac{d\mathcal{L}(x)}{dx_{j}},\nabla
G(\mathcal{L}(x))\right\rangle=\langle
L(e_{j}),V\text{diag}(w)V^{T}\rangle=\text{Tr}\left(V^{T}\mathcal{L}(e_{j})V\text{diag}(w)\right)=e_{j}^{T}\mathcal{M}(V,w),$

where the final equality is readily verified using (74). Thus
$\frac{d}{dx}t_{\tau}\left(x\right)=\mathcal{M}(V,w)$. We therefore conclude
$Q$ is a surrogate function. Note that $Q(\cdot|b)$ is convex since each entry
of $\mathcal{M}(V,w)$ is non-negative by (4).

Next we show the choice of eigenvectors does not matter. Let
$V,\widetilde{V}\in\mathbb{R}^{D}$ be two orthonormal matrices whose columns
are eigenvectors of $\mathcal{L}(|y|)$ and let
$w=g^{\prime}_{\tau}(\lambda^{y})$. Recall from (4) that
$\mathcal{M}(V,w)_{(ij)}=||V(i,:)-V(j,:)||_{2,w}^{2}.$ First note that
flipping the sign of a column of $V$ leaves $\mathcal{M}(V,w)$ unchanged. Thus
if all of the eigenvalues are unique the claim follows.

WLOG assume that the first $K$ eigenvalues are equal to each other and all
other eigenvalues are unique (otherwise the following argument easily
generalizes). Then $V_{1:K}=\widetilde{V}_{1:K}T$ for some orthonormal matrix
$T\in\mathbb{R}^{K\times K}$. Then we can check

$\displaystyle||V(i,:)-V(j,:)||_{2,w}^{2}$
$\displaystyle=||V_{1:K}(i,:)-V_{1:K}(j,:)||_{2,w_{1:K}}^{2}+||V_{(K+1):D}(i,:)-V_{(K+1):D}(j,:)||_{2,w_{(K+1):D}}^{2}$
(75)
$\displaystyle=w_{1}||V_{1:K}(i,:)-V_{1:K}(j,:)||_{2}^{2}+\textendash\textendash\textendash\|\textendash\textendash\textendash$
$\displaystyle=w_{1}(V_{1:K}(i,:)-V_{1:K}(j,:))^{T}(V_{1:K}(i,:)-V_{1:K}(j,:))+\textendash\textendash\textendash\|\textendash\textendash\textendash$
$\displaystyle=w_{1}(V_{1:K}(i,:)-V_{1:K}(j,:))^{T}T^{T}T(V_{1:K}(i,:)-V_{1:K}(j,:))+\textendash\textendash\textendash\|\textendash\textendash\textendash$
$\displaystyle=w_{1}||V_{1:K}T-V_{1:K}T||_{2}^{2}+\textendash\textendash\textendash\|\textendash\textendash\textendash$
$\displaystyle=||\widetilde{V}(i,:)-\widetilde{V}(j,:)||_{2,w}^{2},$

Thus $\mathcal{M}(V,w)=\mathcal{M}(\widetilde{V},w)$.

Finally we check that majorizing at $0$ leaves a Lasso penalty. Note
$\mathcal{L}(0)=0_{D\times D}$ so $\lambda_{y}=0$ and $V_{y}$ is any
orthonormal basis matrix of $\mathbb{R}^{D}$ thus
$||V_{i}-V_{j}||_{2}^{2}=||V_{i}||_{2}^{2}+||V_{j}||_{2}^{2}+2V_{i}^{T}V_{j}=||V_{i}||_{2}^{2}+||V_{j}||_{2}^{2}=2$.
Therefore
$\mathcal{M}(V,g^{\prime}_{\tau}(0)\mathbf{1}_{D})=g^{\prime}_{\tau}(0)\mathcal{M}(V,\mathbf{1}_{D})=g^{\prime}_{\tau}(0)\mathbf{1}_{D}$.

Finally, suppose $\beta$ is a fixed point of the LLA algorithm. This means
$\beta$ is a minimizer of

$\underset{x}{\textup{argmin}}\;\;\ell(x)+Q(x|\beta).$

The first order necessary conditions for this problem require
$\nabla\ell(\beta)+\nabla Q(\beta|\beta)$ where the gradient is applied to the
first argument of the second term. We can check that $\nabla
Q(\beta|\beta)=\nabla s_{\tau}\left(\beta\right)$ by construction. Thus
$\beta$ satisfies $\nabla\ell(\beta)+\nabla s_{\tau}\left(\beta\right)$, which
is the condition for being a stationary point of Problem (3).

∎

###  D.2 Proofs for Section 3

The proof of Theorems 3.1 and 3.2 are based on the proofs of Theorem 1 and 2
of Fan et al., (2014).

###### Proof.

of Theorem 3.1

The assumptions on $\widehat{\beta}^{(0)}$ imply that
$\mathcal{A}(\widehat{\beta}^{(0)})$ has exactly $K_{\text{cc}}^{*}$ connected
components and these connected components are exactly the connected components
of $\beta^{*}$. Let $\lambda\in\mathbb{R}^{d}_{+}$ be the eigenvalues of
$\mathcal{L}(|\widehat{\beta}^{(0)}|)$ and let $V\in\mathbb{R}^{d\times d}$ be
any orthogonal matrix of eigenvectors. Also let
$w=g_{\tau}^{\prime}(\lambda)\in\mathbb{R}^{d}_{+}$. Assumption (11) further
implies that $\lambda_{(K_{\text{cc}}^{*}+1)}\geq b_{2}\tau$. Thus by
Definition 3.1

$g_{\lambda}^{\prime}(\lambda_{k})=a_{0}\tau,\text{ for }1\leq k\leq
K_{\text{cc}}^{*},\qquad g_{\lambda}^{\prime}(\lambda_{k})=0,\text{ for }k\geq
K_{\text{cc}}^{*}+1,$

and we can check

$\mathcal{M}(V,w)=\mathcal{M}(V_{(1:K_{\text{cc}}^{*})},w_{(1:K_{\text{cc}}^{*})})=\mathcal{M}(V_{(1:K_{\text{cc}}^{*})},a_{0}\mathbf{1}_{K_{\text{cc}}^{*}})=:M\in\mathbb{R}^{D}.$

Now let $\widehat{\beta}^{(1)}$ be the output of taking one LLA step from
$\widehat{\beta}^{(0)}$. Then $\widehat{\beta}^{(1)}$ is a solution to

$\underset{\beta}{\textup{minimize}}\;\;\ell(\beta)+\frac{1}{2}M^{T}|\beta|$
(76)

and let $L(\cdot)$ be the loss function for this problem.

Recalling that $\widehat{\beta}^{(0)}$ has the same $K_{\text{cc}}^{*}$
connected components as $\beta^{*}$ and applying Proposition C.3 we see

$M_{\mathcal{S}^{*}}=0,\text{ and
}M_{\mathcal{S}^{*^{C}}}=\frac{2a_{0}\tau}{d^{*}_{\text{max}}}.$ (77)

Recall $\widehat{\beta}^{\text{oracle}}$ is the solution to the constrained
Problem (8). Therefore for any $\beta\in\mathbb{R}^{D}$,

$\displaystyle\ell(\beta)-\ell(\widehat{\beta}^{\text{oracle}})$
$\displaystyle\geq\nabla\ell(\widehat{\beta}^{\text{oracle}})^{T}(\beta-\widehat{\beta}^{\text{oracle}})$
(78)
$\displaystyle=\nabla_{\mathcal{S}^{*}}\ell(\widehat{\beta}^{\text{oracle}})^{T}(\beta_{\mathcal{S}^{*}}-\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*}})+\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})^{T}(\beta_{\mathcal{S}^{*^{C}}}-\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*^{C}}})$
$\displaystyle=\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})^{T}\beta_{\mathcal{S}^{*^{C}}}$

where the inequality comes from the convexity of $\ell$ and the second
equality comes from the facts
$\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*^{C}}}=0$ and
$\nabla_{\mathcal{S}^{*}}\ell(\widehat{\beta}^{\text{oracle}})=0$ comes from
the first order necessary conditions for Problem (8).

Then for any $\beta\in\mathbb{R}^{D}$,

$\displaystyle L(\beta)-L(\widehat{\beta}^{\text{oracle}})$
$\displaystyle=\ell(\beta)-\ell(\widehat{\beta}^{\text{oracle}})+\frac{1}{2}M^{T}\left(|\beta|-|\widehat{\beta}^{\text{oracle}}|\right)$
$\displaystyle=\ell(\beta)-\ell(\widehat{\beta}^{\text{oracle}})+\frac{1}{2}M_{\mathcal{S}^{*^{C}}}^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle\geq\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})\beta_{\mathcal{S}^{*^{C}}}+\frac{1}{2}M_{\mathcal{S}^{*^{C}}}^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle=\left(\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})\text{sign}(\beta_{\mathcal{S}^{*^{C}}})+\frac{1}{2}M_{\mathcal{S}^{*^{C}}}\right)^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle=\left(\frac{1}{2}M_{\mathcal{S}^{*^{C}}}-|\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})|\right)^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle=\left(\frac{a_{0}\tau}{d^{*}_{\text{max}}}-|\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})|\right)^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle\geq 0$

The second equality uses the facts $M_{\mathcal{S}^{*}}=0$ by (77) and
$\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*^{C}}}=0$ by construction. The
first inequality uses (78). The final equality comes from (77). The final
inequality comes from Assumption (12); this inequality is strict unless
$\beta_{\mathcal{S}^{*^{C}}}=0$. Putting this together with the uniqueness of
Problem (8) we conclude that
$\widehat{\beta}^{(1)}=\widehat{\beta}^{\text{oracle}}$.

The claim that fixed points are stationary points follows from Proposition
2.1.

∎

###### Proof.

of Theorem 3.2

Let $\lambda\in\mathbb{R}^{d}_{+}$ be the eigenvalues of
$\mathcal{L}(|\widehat{\beta}^{(0)}|)$ and let $V\in\mathbb{R}^{d\times d}$ be
any orthogonal matrix of eigenvectors. Also let
$w=g_{\tau}^{\prime}(\lambda)\in\mathbb{R}^{d}_{+}$. Assumption (21) says that
$\lambda_{(K_{\text{cc}}^{*})}\leq b_{1}\tau$ and
$\lambda_{(K_{\text{cc}}^{*}+1)}\geq b_{2}\tau$. Thus by Definition 3.1

$g_{\lambda}^{\prime}(\lambda_{k})\in[a_{1},a_{0}]\tau,\text{ for }1\leq k\leq
K_{\text{cc}}^{*},\qquad g_{\lambda}^{\prime}(\lambda_{k})=0,\text{ for }k\geq
K_{\text{cc}}^{*}+1$ (79)

and we can check

$\mathcal{M}(V,w)=\mathcal{M}(V_{(1:K_{\text{cc}}^{*})},w_{(1:K_{\text{cc}}^{*})})=\mathcal{M}(V_{(1:K_{\text{cc}}^{*})},a_{0}\mathbf{1}_{K_{\text{cc}}^{*}})=:M\in\mathbb{R}^{D}_{+}$

where by construction $\widehat{\beta}^{(1)}$ is a solution to

$\underset{\beta}{\textup{minimize}}\;\;\ell(\beta)+\frac{1}{2}M^{T}|\beta|.$
(80)

Note Assumption (22) guarantees
$||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{\text{op}}\leq\frac{1}{2}\triangle^{*}$
thus

$\displaystyle||M_{\mathcal{S}^{*^{C}}}||_{\text{min}}$
$\displaystyle\geq\left(\sqrt{\frac{2\min
w^{(0)}_{1:K_{\text{cc}}^{*}}}{d^{*}_{\text{max}}}}-2^{5/2}\sqrt{\max
w^{(0)}_{1:K_{\text{cc}}^{*}}}\frac{||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{\text{op}}}{\triangle^{*}}\right)^{2}$
(81)
$\displaystyle\geq\left(\sqrt{\frac{2a_{1}\tau}{d^{*}_{\text{max}}}}-2^{5/2}\sqrt{a_{0}\tau}\frac{||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{\text{op}}}{\triangle^{*}}\right)^{2}$
$\displaystyle=\frac{2a_{1}\tau}{d^{*}_{\text{max}}}\left(1-2^{5}\sqrt{\frac{a_{0}d^{*}_{\text{max}}}{a_{1}}}\frac{||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{\text{op}}}{\triangle^{*}}\right)^{2}$
$\displaystyle\geq\frac{a_{1}\tau}{2d^{*}_{\text{max}}}$

where the first inequality comes from (71) of Lemma C.1, the second inequality
comes from (79), and the final inequality comes from Assumption (22).
Similarly,

$\displaystyle||M_{\mathcal{S}^{*}}||_{\text{max}}\leq
2^{5}\max(w)\left(\frac{||\mathcal{L}(|\widehat{\beta}^{(0)}|-|\beta^{*}|)||_{\text{op}}}{\triangle}\right)^{2}\leq
2^{5}a_{0}\tau\rho^{2}$

where we have again used Assumption (22) and (71).

Let $\widehat{\beta}^{\text{orc, lasso}}$ be the solution to the Lasso oracle
problem,

$\displaystyle\underset{\beta\in\mathbb{R}^{D}}{\textup{minimize}}$
$\displaystyle\ell(\beta)+\frac{1}{2}M_{\mathcal{S}^{*}}^{T}|\beta_{\mathcal{S}^{*}}|$
(82) subject to $\displaystyle\beta_{\mathcal{S}^{*^{C}}}=0.$

The above discussion shows $\widehat{\beta}^{\text{orc,
lasso}}\in\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$ under Assumption
(22). We next show $\widehat{\beta}^{(1)}=\widehat{\beta}^{\text{orc,
lasso}}$.

Let $L(\beta)$ be the loss function for Problem (80) and let
$L^{\mathcal{S}^{*}}(\beta)$ be the loss function for (82). By convexity for
any $\beta\in\mathbb{R}^{D}$,

$\displaystyle
L^{\mathcal{S}^{*}}(\beta)-L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})$ $\displaystyle\geq\nabla
L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})^{T}\left(\beta-\widehat{\beta}^{\text{orc, lasso}}\right)$
$\displaystyle=\nabla_{\mathcal{S}^{*}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})^{T}\left(\beta_{\mathcal{S}^{*}}-\widehat{\beta}^{\text{orc,
lasso}}_{\mathcal{S}^{*}}\right)$
$\displaystyle\;\;\;\;+\nabla_{\mathcal{S}^{*^{C}}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})^{T}\left(\beta_{\mathcal{S}^{*^{C}}}-\widehat{\beta}^{\text{orc,
lasso}}_{\mathcal{S}^{*^{C}}}\right)$
$\displaystyle=\nabla_{\mathcal{S}^{*^{C}}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})^{T}\left(\beta_{\mathcal{S}^{*^{C}}}-\widehat{\beta}^{\text{orc,
lasso}}_{\mathcal{S}^{*^{C}}}\right)$
$\displaystyle=\nabla_{\mathcal{S}^{*^{C}}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})^{T}\beta_{\mathcal{S}^{*^{C}}},$

where we have use the fact that
$\nabla_{\mathcal{S}^{*}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})=0$ by the first order necessary conditions of (82) and
$\widehat{\beta}^{\text{orc, lasso}}_{\mathcal{S}^{*^{C}}}=0$ by construction.
Therefore

$\displaystyle L(\beta)-L(\widehat{\beta}^{\text{orc, lasso}})$
$\displaystyle=L^{\mathcal{S}^{*}}(\beta)-L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})+\frac{1}{2}M_{\mathcal{S}^{*^{C}}}^{T}\left(|\beta_{\mathcal{S}^{*^{C}}}|-|\widehat{\beta}^{\text{orc,
lasso}}_{\mathcal{S}^{*^{C}}}|\right)$
$\displaystyle=L^{\mathcal{S}^{*}}(\beta)-L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})+\frac{1}{2}M_{\mathcal{S}^{*^{C}}}^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle\geq\nabla_{\mathcal{S}^{*^{C}}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})^{T}\beta_{\mathcal{S}^{*^{C}}}+\frac{1}{2}M_{\mathcal{S}^{*^{C}}}^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle=\left(\nabla_{\mathcal{S}^{*^{C}}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})\text{sign}(\beta_{\mathcal{S}^{*^{C}}})+\frac{1}{2}M_{\mathcal{S}^{*^{C}}}\right)^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle\geq\left(\frac{1}{2}M_{\mathcal{S}^{*^{C}}}-|\nabla_{\mathcal{S}^{*^{C}}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})|\right)^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle\geq\left(\frac{a_{1}\tau}{4d^{*}_{\text{max}}}-|\nabla_{\mathcal{S}^{*^{C}}}L^{\mathcal{S}^{*}}(\widehat{\beta}^{\text{orc,
lasso}})|\right)^{T}|\beta_{\mathcal{S}^{*^{C}}}|$
$\displaystyle=\left(\frac{a_{1}\tau}{4d^{*}_{\text{max}}}-|\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{orc,
lasso}})|\right)^{T}|\beta_{\mathcal{S}^{*^{C}}}|$ $\displaystyle\geq 0$

where the penultimate inequality comes from (81). The final inequality follows
from Assumption (23) and the fact that $\widehat{\beta}^{\text{orc,
lasso}}\in\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$; this inequality is
strict unless $\beta_{\mathcal{S}^{*^{C}}}=0$. Putting this together with the
uniqueness of (82) we conclude
$\widehat{\beta}^{(1)}=\widehat{\beta}^{\text{orc, lasso}}$.

Next we show taking one more step results in the block oracle estimator. By
Assumption (23)

$\widehat{\beta}^{\text{oracle}}\in\mathcal{B}_{0,\tau}^{\text{lasso orc,
op}}\subseteq\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
op}}\subseteq\mathcal{B}^{\text{nice
grad}}_{\frac{a_{1}\tau}{4d^{*}_{\text{max}}}}\subseteq\mathcal{B}^{\text{nice
grad}}_{a_{0}\tau},$

so the condition (12) is satisfied. By Assumption (24)

$\widehat{\beta}^{\text{oracle}}\in\mathcal{B}_{0,\tau}^{\text{lasso orc,
op}}\subseteq\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
op}}\subseteq\mathcal{B}^{\text{big eval, component-wise}}_{b_{2}\tau}$

so the condition (13) is satisfied. Thus by the second claim of Theorem 3.1 we
conclude that $\widehat{\beta}^{\text{oracle}}$ is a fixed point of the LLA
algorithm.

By construction
$\mathcal{BS}\left(\mathcal{A}(\beta)\right)\subseteq\mathcal{BS}\left(\mathcal{A}(\beta^{*})\right)$
for any $\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$. Therefore
the fact that $\widehat{\beta}^{(1)}\in\mathcal{B}_{\rho,\tau}^{\text{lasso
orc}}$ and Assumption (24) together imply that the conditions of the first
claim of Theorem 3.1 are satisfied. Therefore taking a LLA step from
$\widehat{\beta}^{(1)}$ results in $\widehat{\beta}^{\text{oracle}}$, which is
a fixed point of the LLA algorithm. Thus all the claims of the theorem follow
except the final Frobenius norm bound.

If Assumption (22) is replaced with (22) then using (70) of Lemma C.1 we
obtain the same bounds on $||M_{\mathcal{S}^{*^{C}}}||_{\text{min}}$ and
$||M_{\mathcal{S}^{*}}||_{\text{max}}$ as above. Let $\mathbb{F}$ be the left
hand side of (22). Similarly, applying the $L_{1}$ and $L_{2}$ claims in (70)
we obtain

$\displaystyle||M_{\mathcal{S}^{*}}||_{1}$ $\displaystyle\leq
2^{4}d_{\text{max}}\max(w)\left(\frac{\mathbb{F}}{\triangle}\right)^{2}\leq
2^{4}d_{\text{max}}a_{0}\rho^{2}$ $\displaystyle||M_{\mathcal{S}^{*}}||_{2}$
$\displaystyle\leq
2^{9/2}d^{*^{1/2}}_{\text{max}}\max(w)\left(\frac{\mathbb{F}}{\triangle}\right)^{2}\leq
2^{9/2}d^{*^{1/2}}_{\text{max}}a_{0}\rho^{2}.$

The remainder of the proof is the same thus the claim about the Frobenius norm
bound follows.

∎

###### Proof.

of Corollary 3.2 We verify the conditions of Theorem 3.2 are satisfied. Under
the (complement of) the event in $\delta^{\text{good init}}$ we have

$||\mathcal{L}(|\widehat{\beta}^{\text{initial}}|-|\beta^{*}|)||_{\text{op}}\leq\min\left(\rho,\frac{1}{2^{6}}\sqrt{\frac{a_{1}}{a_{0}d^{*}_{\text{max}}}}\right)\triangle^{*}\wedge
b_{1}\tau$

where we have used the assumption $\triangle^{*}\geq(b_{1}+b_{2})\tau$. The
first term on the right hand side shows condition (22) holds. Using the second
term on the right hand side and Weyl’s inequality we see

$|\lambda_{(j)}\left(\mathcal{L}(|\widehat{\beta}^{\text{initial}}|)\right)-\lambda_{(j)}\left(\mathcal{L}(|\widehat{\beta}^{\text{oracle}}|)\right)|\leq
b_{1}\tau$

for each $j$. Setting $j=K_{\text{cc}}^{*}$ we get

$\lambda_{(K_{\text{cc}}^{*})}\left(\mathcal{L}(|\widehat{\beta}^{\text{initial}}|)\right)\leq
b_{1}\tau$

and setting $j=K_{\text{cc}}^{*}+1$ we get

$\lambda_{(K_{\text{cc}}^{*}+1)}\left(\mathcal{L}(|\widehat{\beta}^{\text{initial}}|)\right)\geq\triangle^{*}-b_{1}\tau\geq(b_{1}+b_{2})\tau-
b_{1}\tau=b_{2}\tau.$

Thus condition (21) holds. The remaining conditions of the Theorem are
controlled by $\delta^{\text{nice grad}}$ and $\delta^{\text{small lap
resid}}$.

The Frobenius norm claims follow analogously. Note condition (21) follows as
above since the Frobenius norm upper bounds the operator norm. ∎

##  Appendix E Proofs for Section 4

###  E.1 Preliminary results

We first give concentration bounds on $||\mathcal{L}(|X|)||_{\text{op}}$ and
$||\mathcal{L}(X)||_{\text{op}}$ where $X$ is a random vector with sub-
Gaussian entries. For the next two lemmas we assume the entries of
$X\in\mathbb{R}^{D}$ are $\sigma$ sub-Gaussian. The first lemma is based on
bounding $\mathcal{P}\left(||\mathcal{A}(|X|)||_{\text{op}-1}\geq t\right)$.

######  Lemma E.1.

Let
$\mu_{op-1,abs}:=||\mathcal{A}(\mathbb{E}\left[|X|\right])||_{\text{op}-1}\leq
d||\mathbb{E}\left[|X|\right]||_{\text{max}}\leq cd\sigma$. Then

$\mathcal{P}\left(||\mathcal{L}(|X|)||_{\text{op}}\geq t\right)\leq
2d\exp\left(-\frac{[t-\mu_{op-1,abs}]_{+}^{2}}{Cd^{2}\sigma^{2}}\right)$

and $\mathbb{E}\left[\mathcal{L}(|X|)\right]\leq c\sigma d\sqrt{\log d}$. If
the entries of $X$ are independent then

$\mathcal{P}\left(||\mathcal{L}(|X|)||_{\text{op}}\geq t\right)\leq
2d\exp\left(-\frac{[t-\mu_{op-1,abs}]_{+}^{2}}{Cd\sigma^{2}}\right)$

and if $||\mathbb{E}\left[|X|\right]||_{\text{min}}\geq c\sigma$ then
$\mathbb{E}\left[\mathcal{L}(|X|)\right]=Cd\sigma$.

The next lemma is based on bounding
$\mathcal{P}\left(||\mathcal{A}(X)||_{\text{op}}+||\mathcal{A}(X)\mathbf{1}||_{\text{max}}\geq
t\right)$.

######  Lemma E.2.

Assume the entries of $X\in\mathbb{R}^{D}$ are independent. Let
$\mu_{op-1}:=||\mathcal{A}(\mathbb{E}\left[X\right])||_{\text{op}-1}\leq
d||\mathbb{E}\left[X\right]||_{\text{max}}\leq cd\sigma$. Then

$\mathcal{P}\left(||\mathcal{L}(X)||_{\text{op}}\geq t\right)\leq
d\exp\left(-\frac{[\frac{t}{2}-\mu_{op-1}]^{2}}{dc_{1}\sigma^{2}}\right)+4\exp\left(-\frac{1}{c_{4}^{2}\sigma^{2}}\left[\frac{t}{2}-\mu_{op-1}-c_{4}\sigma\sqrt{d}\right]_{+}^{2}\right)$

and $\mathbb{E}\left[||\mathcal{L}(X)||_{\text{op}}\right]\leq
2\mu_{op-1}+c\sigma\sqrt{d\log(d)}$.

If $\mathcal{A}(X)$ has $K_{\text{cc, nz}}^{*}$ non-trivial connected
components, $d_{\text{non-iso}}$ non-isolated vertices and the largest
connected component has $d^{*}_{\text{max}}$ vertices then $\mu_{op-1}\leq
d^{*}_{\text{max}}||\mathbb{E}\left[X\right]||_{\text{max}}\leq
cd^{*}_{\text{max}}\sigma$,

$\mathcal{P}\left(||\mathcal{L}(X)||_{\text{op}}\geq t\right)\leq
d_{\text{non-
iso}}\exp\left(-\frac{[\frac{t}{2}-\mu_{op-1}]^{2}}{d^{*}_{\text{max}}c_{1}\sigma^{2}}\right)+4K_{\text{cc,
nz}}^{*}\exp\left(-\frac{1}{c_{4}^{2}\sigma^{2}}\left[\frac{t}{2}-\mu_{op-1}-c_{4}\sigma\sqrt{d^{*}_{\text{max}}}\right]_{+}^{2}\right)$

and $\mathbb{E}\left[||\mathcal{L}(X||_{\text{op}})\right]\leq
2\mu_{op-1}+c\sigma\sqrt{d^{*}_{\text{max}}\log(d_{\text{non-iso}})}$.

The next claim improves upon the naive bound
$\mathbb{E}\left[|x|-|\mu|\right]\leq c\sigma$ that comes from standard sub-
Gaussian properties.

######  Proposition E.1.

Let $\mu:=\mathbb{E}\left[x\right]$ and suppose $x-\mu$ is a $\sigma$ sub-
Gaussian random variable. Then $|x|-|\mu|$ is $\sigma$ sub-Gaussian and

$\mathbb{E}\left[|x|-|\mu|\right]\leq
C(\sigma+|\mu|)\exp\left(-\frac{\mu^{2}}{4\sigma^{2}}\right).$ (83)

The following lemma characterizes the error after applying a generalized
thresholded operator to $\widehat{\beta}^{\text{ok}}$. Recall from Section 4
$\mathscr{d}^{*}$ is the maximal degree of a node in the binary target
$\mathcal{G}^{*}$. Also let $\mathscr{s}^{*}$ be the number of non-zero
elements of $\beta^{*}$ i.e. the number of edges in $\mathcal{G}^{*}$.

######  Lemma E.3.

Suppose $\widehat{\beta}^{\text{ok}}\in\mathbb{R}^{D}$ satisfies a
$\mathcal{T}(f,v_{*})$ residual tail condition. Then for any
$\gamma\in(0,\frac{1}{v_{*}})$ and $\alpha\in(0,1)$,

$\mathcal{P}\left(||T_{\gamma}\left(\widehat{\beta}^{\text{ok}}\right)-\beta^{*}||_{1}>6\mathscr{s}^{*}\gamma\right)\leq\mathscr{s}^{*}f\left(n,\gamma\right)+Df\left(n,(1-\alpha)\gamma\right),$
(84)

and

$\mathcal{P}\left(||\mathcal{A}\left(T_{\gamma}\left(\widehat{\beta}^{\text{ok}}\right)-\beta^{*}\right)||_{\text{op}-1}>6\mathscr{d}^{*}\gamma\right)\leq\mathscr{s}^{*}f\left(n,\gamma\right)+Df\left(n,(1-\alpha)\gamma\right).$
(85)

The following are sufficient conditions for hard thresholding to return the
oracle estimate. Let $\widehat{\beta}^{\text{oracle}}_{\text{entrywise}}$ be
the entrywise oracle for the target parameter $\beta^{*}$ i.e. the solution to
(8) where $\mathcal{S}^{*}$ is replaced with $\mathbb{S}^{*}=\\{j\in[D]\text{
s.t. }\beta^{*}_{j}\neq 0\\}$.

######  Proposition E.2.

Suppose $\widehat{\beta}^{\text{ok}}$ in Section obeys a $\sigma$ sub-Gaussian
tail residual condition. Then
$\widehat{\beta}^{\text{HT}}_{\gamma}=\widehat{\beta}^{\text{oracle}}_{\text{entrywise}}$
with probability at least $1-\delta_{\text{big
true}}^{\text{HT}}-\delta_{\text{small noise}}^{\text{HT}}$ where

$\delta_{\text{big
true}}^{\text{HT}}=\mathcal{P}\left(||\widehat{\beta}^{\text{ok}}_{\mathbb{S}^{*}}-\beta^{*}_{\mathbb{S}^{*}}||_{\text{max}}\geq||\beta^{*}_{\mathbb{S}^{*}}||_{\text{min}}-\gamma\right)\leq
2\mathscr{s}^{*}\exp\left(\frac{-n\left[||\beta^{*}_{\mathbb{S}^{*}}||_{\text{min}}-\gamma\right]_{+}^{2}}{2\sigma^{2}}\right)$

and

$\delta_{\text{small
noise}}^{\text{HT}}=\mathcal{P}\left(||\widehat{\beta}^{\text{ok}}_{\mathbb{S}^{*^{C}}}||_{\text{max}}\leq\gamma\right)\leq
2(D-\mathscr{s}^{*})\exp\left(\frac{-n\gamma^{2}}{2\sigma^{2}}\right).$

###  E.2 Proofs for main results

###### Proof.

of Theorem 4.1

We will appeal to Corollary 3.1. The objective function of Problem (28),
$\ell(\beta)=\frac{1}{2}||\widehat{\beta}^{\text{ok}}-\beta||_{2}^{2}$, is
strongly convex so the solution is always unique. Thus Assumption 3.1 is
satisfied.

Note $\nabla\ell(\beta)=\widehat{\beta}^{\text{ok}}-\beta$ and
$\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*^{C}}}=0$ thus
$\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})=\widehat{\beta}^{\text{ok}}_{\mathcal{S}^{*^{C}}}$.
Therefore by the union bound

$\mathcal{P}\left(||\nabla_{\mathcal{S}^{*^{C}}}\ell(\widehat{\beta}^{\text{oracle}})||_{\text{max}}>t\right)=\mathcal{P}\left(||\widehat{\beta}^{\text{ok}}_{\mathcal{S}^{*^{C}}}||_{\text{max}}>t\right)\leq
2(D-s^{*})\exp\left(-\frac{nt^{2}}{2\sigma^{2}}\right),$ (86)

thus the claim about $\delta^{\text{nice grad}}_{\text{orc}}$ follows by
plugging in $t=\frac{a_{0}\tau}{d^{*}_{\text{max}}}$.

Note
$\widehat{\beta}^{\text{oracle}}_{\mathcal{C}^{*}_{k}}=\widehat{\beta}^{\text{ok}}_{\mathcal{C}^{*}_{k}}$.
By assumption
$\mathbb{E}\left[\widehat{\beta}^{\text{oracle}}_{\mathcal{C}^{*}_{k}}\right]=\beta^{*}_{\mathcal{C}^{*}_{k}}$
for any $k\in[K_{\text{cc, nz}}^{*}]$ and the entries of
$\widehat{\beta}^{\text{oracle}}_{\mathcal{S}^{*}}$ are independent and have
sub-Gaussian variance proxy $\frac{\sigma^{2}}{n}$. Therefore

$\displaystyle||\mathcal{A}(\mathbb{E}\left[|\widehat{\beta}^{\text{oracle}}|\right]-|\beta^{*}|)||_{\text{op}-1}$
$\displaystyle\leq
d^{*}_{\text{max}}||\mathbb{E}\left[|\widehat{\beta}^{\text{oracle}}|\right]-|\beta^{*}|||_{\text{max}}$
(87) $\displaystyle\leq
Cd^{*}_{\text{max}}(\frac{\sigma}{\sqrt{n}}+||\beta^{*}||_{\text{max}})\exp\left(-\frac{cn||\beta^{*}_{\mathcal{S}^{*}}||_{\text{min}}^{2}}{\sigma^{2}}\right)=:\Xi$

where the first inequality comes from the fact that the row sums have at most
$d^{*}_{\text{max}}$ non-zero terms and the second inequality comes from
Proposition E.1. Thus by Lemma E.2 we have

$\displaystyle\mathcal{P}\left(||\mathcal{L}(|\widehat{\beta}^{\text{oracle}}|-|\beta^{*}|)||_{\text{op}}\geq
t\right)\leq d_{\text{non-
iso}}\exp\left(-\frac{n[\frac{t}{2}-\Xi]^{2}}{d^{*}_{\text{max}}c_{1}\sigma^{2}}\right)+4K_{\text{cc,
nz}}^{*}\exp\left(-\frac{n}{c_{4}^{2}\sigma^{2}}\left[\frac{t}{2}-\Xi-
c_{4}\sigma\sqrt{\frac{d^{*}_{\text{max}}}{n}}\right]_{+}^{2}\right)$

From the assumptions of the theorem $\triangle^{*}-b_{2}\tau\geq b_{2}\tau$.
Therefore plugging $t=b_{2}\tau$ and using Assumption (29) the claim about
$\delta^{\text{small lap resid}}_{\text{orc}}$ follows.

∎

###### Proof.

of Theorem 4.2 To verify the two step convergence claims we will appeal to
Corollary 3.2.

For any $\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$,
$\beta_{\mathcal{S}^{*^{C}}}=0$ so
$\nabla_{\mathcal{S}^{*^{C}}}\ell(\beta)=\widehat{\beta}^{\text{ok}}_{\mathcal{S}^{*^{C}}}$.
Therefore by the union bound

$\mathcal{P}\left(\sup_{\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
op}}}||\nabla_{\mathcal{S}^{*^{C}}}\ell(\beta)||_{\text{max}}>t\right)=\mathcal{P}\left(||\widehat{\beta}^{\text{ok}}_{\mathcal{S}^{*^{C}}}||_{\text{max}}>t\right)\leq(D-s^{*})f(n,t)$
(88)

for any $t\in(0,1/v_{*})$. Thus the claim about $\delta^{\text{nice
grad}}_{\text{orc}}$ follows after plugging in
$t=\frac{a_{1}\tau}{4d^{*}_{\text{max}}}$.

Note the entries of any $\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso orc,
op}}$ are obtained by soft-thresholding the entries of
$\widehat{\beta}^{\text{ok}}$ so
$||\beta_{\mathcal{S}^{*}}-\widehat{\beta}^{\text{ok}}_{\mathcal{S}^{*}}||_{\text{max}}\leq
2^{5}a_{0}\tau\rho^{2}$ by the definition of
$\mathcal{B}_{\rho,\tau}^{\text{lasso orc, op}}$. Thus

$\sup_{\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso
orc}}}||\beta_{\mathcal{S}^{*}}-\widehat{\beta}^{\text{ok}}_{\mathcal{S}^{*}}||_{\text{max}}\leq
2^{5}a_{0}\tau\rho^{2}$

and we see

$\displaystyle\mathcal{P}\left(\sup_{\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso
orc}}}||\mathcal{L}(|\beta|-|\beta^{*}|)||_{\text{op}}\geq t\right)$
$\displaystyle\leq\mathcal{P}\left(||\mathcal{L}(|\widehat{\beta}^{\text{oracle}}|-|\beta^{*}|)||_{\text{op}}\geq
t-\sup_{\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso
orc}}}||\mathcal{L}(|\beta|-|\widehat{\beta}^{\text{oracle}}|)||_{\text{op}}\right)$
$\displaystyle\leq\mathcal{P}\left(||\mathcal{L}(|\widehat{\beta}^{\text{oracle}}|-|\beta^{*}|)||_{\text{op}}\geq
t-\sup_{\beta\in\mathcal{B}_{\rho,\tau}^{\text{lasso
orc}}}2d^{*}_{\text{max}}||\beta-\widehat{\beta}^{\text{oracle}}||_{\text{max}}\right)$
$\displaystyle\leq\mathcal{P}\left(||\mathcal{L}(|\widehat{\beta}^{\text{oracle}}|-|\beta^{*}|)||_{\text{op}}\geq
t-d^{*}_{\text{max}}2^{6}a_{0}\tau\rho^{2}\right)$
$\displaystyle\leq\mathcal{P}\left(||\widehat{\beta}^{\text{oracle}}-\beta^{*}||_{\text{max}}\geq\frac{t-d^{*}_{\text{max}}2^{6}a_{0}\tau\rho^{2}}{2d^{*}_{\text{max}}}\right)$
$\displaystyle\leq
Df(n,\frac{t-d^{*}_{\text{max}}2^{6}a_{0}\tau\rho^{2}}{2d^{*}_{\text{max}}})$

where the first inequality uses the triangle inequality, the second and fourth
inequality bound the operator norm using the max norm (Proposition C.1), and
the final inequality uses the union bound. Setting $t=b_{1}\tau$ and applying
Assumption (32) the claim about $\delta^{\text{small lap resid}}$ follows.

For the claim in Remark 4.2 we can argue as in the proof of Theorem 4.1 to
bound
$||\mathcal{L}(|\widehat{\beta}^{\text{oracle}}|-|\beta^{*}|)||_{\text{op}}$.

∎

###### Proof.

of Corollary 4.1

We need only verify the initialization condition of Corollary 3.2. Note

$\displaystyle\mathcal{P}\left(||\mathcal{L}\left(|\widehat{\beta}^{\text{ok}}|-|\beta^{*}|\right)||_{\text{op}}\geq
t\right)$
$\displaystyle\leq\mathcal{P}\left(||\widehat{\beta}^{\text{ok}}-\beta^{*}||_{\text{max}}\geq\frac{t}{2d}\right)$
$\displaystyle\leq Df(n,\frac{t}{2d}).$

where the first inequality comes from Proposition C.1. Thus the claim (35)
follows by setting $t=C_{\rho}\tau$. For the claim in Remark 4.2 we can
improve this rate by using Lemma E.2 to control the within block terms and
Lemma E.1 to control the between block terms.

If $\gamma\leq\frac{1}{2}\cdot\frac{1}{6\mathscr{s}^{*}}\cdot C_{\rho}\tau$
then

$\displaystyle\mathcal{P}\left(||\mathcal{L}\left(|T_{\gamma}\left(\widehat{\beta}^{\text{ok}}\right)|-|\beta^{*}|\right)||_{\text{op}}\geq
C_{\rho}\tau\right)$
$\displaystyle\leq\mathcal{P}\left(||\mathcal{A}\left(T_{\gamma}\left(\widehat{\beta}^{\text{ok}}\right)-\beta^{*}\right)||_{\text{op}-1}\geq\frac{1}{2}C_{\rho}\tau\right)$
$\displaystyle\leq\mathcal{P}\left(||\mathcal{A}\left(T_{\gamma}\left(\widehat{\beta}^{\text{ok}}\right)-\beta^{*}\right)||_{\text{op}-1}\geq
6\mathscr{s}^{*}\gamma\right)$ $\displaystyle\leq\text{right hand side of
\eqref{eq:bd_shrink_gen_thresh_init}}$

where the first inequality comes Proposition C.1 and the final inequality
comes from the operator one norm bound of Lemma (E.3). Thus (37) follows. Note
we can bound
$\mathcal{P}\left(||\mathcal{L}\left(|\widehat{\beta}^{\text{ok}}|-|\beta^{*}|\right)||_{F}\geq
t\right)$ similarly by making use of the $L_{1}$ bound in Lemma (E.3).

∎

######  Remark E.1.

The claims in Remark 4.2 follow by enlisting Lemmas E.1 and E.2 in the proofs
of Theorem 4.2 and Corollary 4.1.

###  E.3 Proofs for preliminary results

###### Proof.

of Lemma E.1 Recall $||\mathcal{L}(|X|)||_{\text{op}}\leq
2||\mathcal{A}(X)||_{\text{op}-1}$ from Proposition C.1.

Note

$\displaystyle\sum_{j=1,j\neq\ell}|X_{(\ell
j)}|\leq\sum_{j=1,j\neq\ell}\left(|X_{(\ell j)}|-\mathbb{E}\left[|X_{(\ell
j)}|\right]\right)+||\mathcal{A}(\mathbb{E}\left[|X|)\right]||_{\text{op}-1}.$
(89)

thus setting $R:=\mathcal{A}(|X|-\mathbb{E}\left[|X|\right])$ we see that