Provable Learning-based Algorithm For Sparse Recovery
Authors: Xinshi Chen
Haoran Sun
Le Song
Venue: ICLR 2022 Poster (2022)
Keywords: learning to learn
sparse parameter estimation
learning to optimize
algorithm unrolling
generalization bound

Abstract: Recovering sparse parameters from observational data is a fundamental problem in machine learning with wide applications. Many classic algorithms can solve this problem with theoretical guarantees, but their performances rely on choosing the correct hyperparameters. Besides, hand-designed algorithms do not fully exploit the particular problem distribution of interest. In this work, we propose a deep learning method for algorithm learning called PLISA (Provable Learning-based Iterative Sparse recovery Algorithm). PLISA is designed by unrolling a classic path-following algorithm for sparse recovery, with some components being more flexible and learnable. We theoretically show the improved recovery accuracy achievable by PLISA. Furthermore, we analyze the empirical Rademacher complexity of PLISA to characterize its generalization ability to solve new problems outside the training set. This paper contains novel theoretical contributions to the area of learning-based algorithms in the sense that (i) PLISA is generically applicable to a broad class of sparse estimation problems, (ii) generalization analysis has received less attention so far, and (iii) our analysis makes novel connections between the generalization ability and algorithmic properties such as stability and convergence of the unrolled algorithm, which leads to a tighter bound that can explain the empirical observations. The techniques could potentially be applied to analyze other learning-based algorithms in the literature.

Published as a conference paper at ICLR 2022
PROVABLE LEARNING-BASED ALGORITHM FOR SPARSE RECOVERY
Xinshi Chen & Haoran Sun
Le Song
School Mathematics
Machine Learning Department
Georgia Institute of Technology
MBZUAA & BioMap UAE China songle@bi www.wpwwwmmm............. com
Atlanta, USA
{xinshi chen, haoransun]@gatech.ccoo
ABSTRACT
Recovering sparse parameters from observational data fundamental problem in machine learning with wide applications. Many classic algorithms solve this problem with theoretical guarantees, but their performances rely on choosing the correct hyperparameters. Besides, hand-designed algorithms do not fully ploit the particular problem distribution of interest. this work, we propose a deep learning method for algorithm learning called PLISA (Provable Learning- based Iterative Sparse recovery Algorithm). PLISA is designed by unrolling a classic path-following algorithm for sparse recovery, with some components be- ing more flexible and learnable. We theoretically show the improved recovery ac- curacy achievable by PLISA. Furthermore, we analyze the empirical Rademacher complexity of PLISA to characterize its generalization ability to solve new prob- lems outside the training set. This paper contains novel theoretical contributions the area of learning-basee algorithms in the sense that (i) PLISA is generically ap- plicable to a broad class sparse estimation problems, (ii) generalization analysis has received less attention far, and (iii) our analysis makes novel connections between the generalization ability and algorithmic properties such as stability and convergence of the unrolled algorithm, which leads tighter bound that explain the empirical observations. The techniques could potentially be applied to analyze other learning- based algorithms in the literature.
observations Zim
parameter
INTRODUCTION
The problem of recovering sparse vector 3 from finite ob- servations Zi:. ~ (P is fundamental machine learning, covering broad family of problems including compressed sensing, sparse regression analysis, graphical model estima- tion, etc. It has also found applications in various domains. For example, in magnetic resonance imaging, sparse signals need be reconstructed from measurements taken by a scan- ner. In computational biology, estimating a sparse graph struc- ture from gene expression data is important for understanding gene regulatory networks.
MRI imuge
dree image
expression
gane regulotorry authook
Figure 1: Sparse recovery problems.
Various classic algorithms are available for solving sparse recovery problems. Many of them come with theoretical guarantees for the recovery accuracy. However, the theoretical performance often relies on choosing the correct hyperparameters, such as regularization parameters and the learning rate, which may depend on unknown constants. Furthermore, in practice, similar problems may need to be solved repeatedly, but it is hard for classic algorithms to fully utilize this information.
To alleviate these limitations, we consider the approach of learning-to-lear and propose neural algorithm, called PLISA (Provable Learning-base Iterative Sparse recovery Algorithm). PLISA deep learning model that takes the observations Zı.. as the input and outputs an estimation for 3. To make use of classic techniques developed by domain experts, we design the architecture of PI.TAA by unrolling and modifying classic path-following algorithm proposed by Wang et al.

---

Published as a conference paper at ICLR 2022
(2014). To benefit from learning, some components in this classic algorithm are made more flexible with careful design and treated as learnable parameters in PLISA. These parameters can be learned set of training problems. The learned PLISA can then be used for solving other problems in the target distribution.
by optimizing the performances
With the algorithm design problem converted to a deep learning problem, we ask the two fundamen- tal questions in learning theory:
1. Capacity: What's the recovery accuracy achievable by PLISA? Can the flexible components in PLISA lead to an algorithm which effectively improves the recovery performance?
2. Generalization: How well the learned PIISA solve new problems outside the training ser?
Is the generalization behavior related to the algorithmic properties of PLISA?
Aiming at supplying rigorous answers to these questions, we conduct theoretical analysis for PLISA to provide guarantees for its representation and generalization ability. The results and the techniques in our analysis can distinguish our work from existing studies on algorithm learning. We summarize our novel contributions into the following three aspects.
1. Theoretical understanding. In contrast the plethora of empirical studies on algorithm leamn- ing, there have been relatively few studies devoted to the theoretical understanding. Existing the- oretical efforts primarily focus on analyzing the convergence rate achievable by the neural algo- rithm (Chen et al., 2018; Liu et al., 2019a; Zhang & Ghanem, 2018; Wu et al., 2020), but the generalization error bound has received less attention so far. A substantial body of works only argue intuitively that algorithm unrolling architectures can generalize well because they contain small number of parameters. In comparison, we provide theoretical guarantees for both the capacity and the generalization ability of PLISA, which are more solid arguments.
2. General setting. The problem setting in this paper is new and more challenging. Existing works mainly focus on specific problem. For example, the compressed sensing problem with fixed design matrix is the mostly investigated one. PLISA, however, is generic and is applicable to various sparse recovery problems long they satisfy certain conditions in Assumption C.I.
3. Novel connection. The algorithmic structure in PLISA can make it behaves differently from conventional neural networks. Therefore, we largely utilize the analysis techniques in classic algo- rithms to derive its generalization bound. By combining the analysis tools of deep learning theory and optimization algorithms, our result reveals a novel connection between the generalization ability of PLPIISA SA and the algorithmic properties including the convergence rate and stability of the unrolled algorithm. Benefit from this connection, our generalization bound is tight in the sense that matches the interesting behavior of PLISA observed in experiments the generalization gap could decrease in the number layers, which rarely observed conventional neural networks.
PLISA: LEARNING To SOLVE SPARSE ESTIMATION PROBLEMS
A sparse estimation problem is to recover 3 from finite observations Zi... sampled from P As a concrete example, sparse linear regression problem, n observations {Z, = (æ; 3/: ) are sampled from a linear model y = x 3 + e, and an algorithm needs to estimate 3 from n observations. Classic algorithms recover 3 by minimizing regularized empirical loss:
Bx E arg min T., (Z1,, B) + P)),
(1)
where L, an empirical loss that measures the "fit" between the parameter B and observations Zi.m and P(), (3) is a sparsity regularization with coefficient A. When L,, is the least square loss and P(), 33 A||,3||1. the optimization is known as LASSO and can be solved by the well-known algorithm ISTA (Daubechies et al., 2004). Based on the idea of algorithm unrolling, Gregor & LeCun (2010) proposed LISTA, a neural algorithm that interprets ISTA as layers of neural networks. It has been demonstrated that LISTA outperforms ISTA thanks its learnable components. Since then, designing neural algorithms by unrolling ISTA has become an active research topic. However, existing works mostly focus on the compressed sensing problem with fixed design matrix only.
To enable for more general applicability, we design the architecture of PLISA by unrolling a clas- sic path-following algorithm called APF (Wang et al., 2014) instead of ISTA. APF is applicable to nonconvex losses and nonconvex penalty functions, covering a considerably larger range of ob- jectives than LASSO. Designing the architecture based on APF allows PLTSA be applicable to
2

---

Published as a conference paper at ICLR 2022
broader class of problems such nonlinear sparse regression, graphical model estimation, etc. Furthermore, employing nonconvexity can potentially lead to better statistical properties (Fan & Li, 2001: Fan et al., 2009; Loh & Wainwright, 2015), for which we will explain more in Section 3.
In the following, we will introduce APF and the architecture of our proposed PLISA. After that, we will describe how optimize the parameters in PLISA under the Carning-to-leam setting.
2.1 A BRIEF INTRODUCTION TO APF
We briefly introduce the classic algorithm APF (Wang et al., 2014), and its details are presented in Algorithm 3 in Appendix I. The key idea of path-following algorithms is creating sequence of T many sub-objectives to gradually approach the target objective that is supposed to be more difficult to solve. More specifically, APF approximates the local minimizers of sequence of suboobjectives:
B ~ 3x, E arg min L. (Z B) + P(),, for L = 1, ..... T
(2)
3
Ar is a decreasing sequence of regularization parameters. The last parameter Xr is the target regularization parameter. As result, APF contains T blocks, and each block contains an iterative algorithm that minimizes one sub-objective in Eq. 2. The output of the (1 - 1)-th block, denoted by B--1, is used as the initialization of the 1-th block, i.e., B = B.-1- Then the 1-th block minimizes the 1-th sub-objective by the modified proximal gradient algorithm:
where A1 > A2 >.>....
for k = 1, 1, K, 3 t Ta. (g
+ V 33Q(A, (x
(3)
output of t-th block: B. 3
The notation (3) == sign( (3) max {|3] - 8, 03 is the soft-thresholding function, and the function Q is the concave component of P defined as ((), := P(A, 33) 1|| The number of steps K in each block is determined by certain stopping criteria. It can be seem that the update steps in each block is similar to the ISTA algorithm, but it modified in order to incorporate nonconvexity.
B1
2.2 ARCHITECTRRE OF PLISA
celi algorithm
2y
The architecture of PLISA designed by unrolling the APF algo- rithm, and augmenting some learnable parameters 6. Therefore, the
Pr-1
architecture of PLISA, contains T blocks and each block contains K layers defined by the K-step algorithm in Eq. 3 (See Figure 2). Note that PLISA,, both K and T are pre-defined. The architecture of PLISAg different from APF as summarized below:
P
'1.2"
cel w at algorithon stopr
A
1. Element-wise and learnable regularization parameters. Most classic algorithms including APF employ a uniform regulariza- tion parameter X across all entries of ,,, but PLISA, uses a d- dimensional vector X I>t.1.... >v.a]' to enforce different levels of sparsity to different entries in B. Furthermore, the reg- ularization parameters in SAA are learnable, which will be op- timized during the training.
P
1
cel
2
algorition
Po
n22
7 input
Ao
Vl, 0)
Learnable penalty function: Classic algorithms use a pre-defined sparse penalty function P. but PLISAa parameterizes it as com- bination of q different penalty functions and learns the weights of each penalty. In other words, PLISAa can learn to select specific combination of the penalty functions from training data.
Figure 2: Architecture.
3. Learnable step size: The step sizes in APF are selected by line-scarch but they are learnable in PLISAg. Experimentally, find the learned step sizes lead much faster algorithm.
In later sections of this paper, we will show how such differences can make PLISAa perform better than APF both empirically and theoretically.
Algorithm 1 and 2 present the mathematical details of the architecture, follow which we explain some notations and definitions. Red-colored symbols indicate learnable parameters in PI..AAg
3

---

Published as a conference paper at ICLR 2022
Algorithm 1: PLISAA architecture
Algorithm 2: Layers in each block Block
#blocks: T, #layers per block: K
Input: Zim Br-1,
Parameters: 0 {n,,",, X", 2.
Input: samples Zimm 30 0, A < VnLn (Z (Z1m, 0) For t = , do
3 t 31-1
For = 1.... K do
g t VgLn (on ( Vo
A max {n((n) A X²}
B t To. B g6
B + Bl Block K
w.a (7 1,
return Br = 3.5
return Br
Regularzation parameters. In PI.S the element-wise regularization parameters are initialized by a vector Ag == VVllnn (7 0), and then updated sequentially by
A f- max (a(n) ),)
(5)
where a-), o, and max(-;) . are element-wise sigmoid function, multiplication, and maximization. (n, }² are both d-dimensional learnable parameters. Eq. 5 creates sequence ' Ar through the decrease ratio (1)), until they reach the target regularization parameters A
Penalty function. PI.TAAg parameterizes the penalty function follows,
Po (A, 3) = E Wi; p() (x,3), where Wh Σx exp(we))
exp(we)
(6)
In other words, Pw is a learnable convex combination of q penalty functions (P(I), p(o)). The weights of these functions are determined by learnable parameters w [W1.-. wg). In this paper, we focus on learning the combination of three well-known penalty functions:
P(U (A, 3) = [| Bl1,, (22) = Σ MCP(A,, By), (x)) Σ SCAD(A,, By),
where p(1) is convex, and MCP (Zhang, 2010a) and SCAD (Fan & Li, 2001) are nonconvex penal- ties whose analytical forms are given in Appendix B. One can include any other penalty functions as long as they satisfy set conditions specified in Appendix B. Qu (A, G) == Pw (A, 33) | o B|1 represents the concave component of Pw. The analytical form of V VaQw (A, B) are in Appendix B.
2.3 LEARNING- SETTING
Now we describe how to train the parameters 0 in PLISAg under the learning-to- lo-learn setting.
Training set. Similar to other works in this domain, assume the access to problems from the target problem-space P, and use them as the training set:
D (ZZ()) (,(("), ((
(Z(m) (mm))) with (Z ())() E P.
Here each estimation problem is represented by a pair of observations and the corresponding true parameter to be recovered. A different problem can contain different number of observations.
Training loss. Since the intermediate outputs 3,(Z f) of PLISA, are also estimates of 3", common design of the training loss is the weighted sum of the intermediate estimation errors (Chen al., 2021). More specifically, we employ the following training loss:
m
Crrain (Dmi
T-t
B6 -3))))))))))
(r)
m
where 7 < 1 is discounting factor If 0 then the loss is only estimated at the last layer.
Generalization error. The ultimate goal of algorithm learning to minimize the estimation error on expectation over all problems in the target problem distribution:
Egen (P)()): B. (= (Z1::
13" 11
(8)
where P(P) is a distribution the target problem-spar P. Let 6* E arg min 27 (Dm: 0) be minimizer of the training loss. It is well-known that the generalization error can be bounded by:
Egen (P(P); (P); 0*) Lgen (P(P): - C (D.:: 0*) + train (Dm;;)
(9)
generalization gap: Theosem 4.1
training Thearem 3.1
We will theoretically characterize these two terms in Theorem 3.1 and Theorem 4.1.
4

---

Published as a conference paper at ICLR 2022
3 CAPACITY OF PLISA
Can PI.ISAg achieve small training error without using too many layers? How can designs of element-wise regularization and learnable penalty functions help PLISAa to achieve smaller train- ing error compared to classic algorithms? We answer this question theorectically in this section.
3.1 FIRST MAIN RESULT: CAPACITY
Let Bi(Zi::: 0) be the output of the t-th block in PLISAg. Let V a denote entry-wise maximal value max x, a}. Let (x)s denote the sector of x with entries indexed by the set S.
Theorem 3.1 (Capacity). Assume the problem space P satisfies Assumption C.I and D P. Let be the number of blocks PLISAg and K be the number of layers each block. For any & >> O, there exists a set of parameters 0 {n, X², , u. o) such that the estimation error of every problem (Zums (3)) E Dm is bounded as follows, VT >> to.
[13r(Zin:0) 0) - 30112 SE ''ooss exp( CC - 10))
optimization error
(10)
+ cfrmmll (V V) l12, statistical error
(11)
where S == supp( is the support indices of 3", Co, co. and Co are some positive values de- pending on the chosen 0, and Rom is condition number which reveals the similarity of the problems in Dm- Note that K and to are required to be larger thun certain values, but we will elaborate in Appendix that the required lower bounds are small. See Appendix E for the proof of this theorem.
This estimation error can be interpreted as a combination of the optimization error (in Eq. 10) and the statistical error (in Eq. 11). The optimization error decreases linearly in both K and T. The statistical erroroccurs because of the randomness in Zt.. The gradient at the true parameter V To (7mm, 33*)
characterizes how well the finite samples Zi.. can represent the distribution Fa-.
A direct consequence of Theorem 3.1 is that the training error can be small without using too many layers and blocks in PLISAg- We will also elaborate on how the entry-wise regularization and learnable penalty function can effectively reduce the training error in the following.
(i) Impact of entry-wise regularization. Restricting the regularization to be uniform across entries will lead to an error bound that replaces the statistical error || (V T. (Z f3r) V g) . ll2 in Eq. 11 by * L 1Z), 3a) Ve). To understand how the former has improved the latter, we can consider the sparse linear regression problem. If the design matrix is normalized such that maxis/5d [1( ... [xm],) la S Vτ, then (V (Z1.,, (3) VE) lle S Cv/s*/a /nn with high probability. In comparison, V VV Lm (Zi., B*)1 S CCV8 / log d/n with high probability is slower statistical rate due to the term log d.
(ii) Impact of learnable penalty function. To explain the the benefit of using learnable penalty function, we give a more refined bound for the statistical error in Eq. 11 in the following lemma.
Lemma 3.1 (Refined bound). Assume the same conditions and parameters 0 in Theorem 3.1. As- sume T + co so that the optimization error can be ignored. For simplicity, assume W33 = 0 and only consider the weights Wi and Wt2 for E1 penalty and MCP. Then for every problem (Z 3²) )) Dmn
11 (Zis; 0) 0 S 1+8(1+ wrz Mm
(I Ln (Zi. , 3r) ()sssla
(ST: Small 88] 's) (12)
1+8(1 W0g 1iem
I( (V (Z 3r) E)s; l12
(Sy: Large
| 's) (13)
D-
where b 1 is a hyperparameter in MCP, and the index sets Si and S are defined as S {j
S" |87| $ bA}} and Sž = [j S* | bAī}. ). See Appendix for the proof.
This refined bound reveals the benefit of learning the penalty function because:
1. According to Lemma 3.1, the optimal penalty function is problem- For example, if
(8(bp_ 1)km, + 1)ll (V L. (Z 3²) E)s; ll2 > (8(bp_ 1)km, () e)s; choosing W2
V
0 can induce smaller error bound. Otherwise, W02 1 is better. Therefore, learning is a more suitable way of choosing the penalty function.
The convergence speed Co in Eq. is also affected by the weights, monotonely decreasing in W2. Through gradient-based training, we can automatically find the optimal combination of penalty functions to strike nice balance between the statistical error and convergence speed.
5

---

Published as a conference paper at ICLR 2022
4 GENERALIZATION ANALYSIS
How well can the learned PLISAg solve new problems outside the training set? In this section, we conduct the generalization analysis in novel way to focus answering the questions:
How is the generalization bound of P PLI SLI related to its algorithmic properties? And how is it different from conventional neural networks?
4.1 SECOND MAIN RESULT: GENERALIZATION BOUND
To analyze the generalization properties of neural networks, many works have adopted the analysis framework of Bartlett & Mendelson (2002) to bound the Rademacher complexity via Dudley's 's in- tegral (Bartlett et al., 2017; Chen et al., 2019; Garg et al., 2020; Joukovsky et al., 2021). A key step in this analysis framework is deriving the robustness of the training loss to the small perturbation in iterative algorithm,
model parameters 8. Since tools of classic optimization algorithms to derive its robustness in The following lemma states this key intermediate result, which connects the Lipschitz constant to algorithmic properties of PLI SAg-
view PLISA,
borrow the analysis
Lemma 4.1 (Robustness to 0). Assume P satisfies Assumption C.I and Dm ~ P(P)". Assume PLISAg contains T to blocks and K layers. Consider parameter space in which the param- eters satisfy (i) E [amin: 1..] (ii) TΙ E =00'((09)) Mmaa)) (iti) W2 + ww's - S Emax < p-,, and (iv) X3 E [8sup(Z JED,. LV (Zims 31il e, Amax] with some positive constants amin Mmax Emax, and Amax. Then for any {n, X-, w, at and 0' = {n', X w', a'} in O and for any recovery problem (Z1.ns 33) D the following inequality holds,
1| (Z1:: -3 0') S (T (TT--)-) to) la a'lexpl CCac--CK((TT) - to))
(14)
convergence rall
-/2l X + caVal un u0'l2) expl exp(-CoKTT
(15)
stability rate
where C1, C2 C32 C4 and Ce are some positive constants. Note that similar to Theorem 3.1, K and to are required to be larger than certain small values. See Appendix F.1 for the proof.
Convergence rate & step size perturbation. In Eq. 14, the Lipschitz constant in the step size scales at the same rate as the convergence rate of P PLISAg, decreasing exponentially in T and K (See Fig. for a visualization). To understand this, consider when both step sizes a and a' are within the convergence region (i.c., (0, p. DD After infinitely many steps, their induced outputs will both converge to the same optimal point. This intuitively explains why the output perturbation caused by a-perturbation has the same decrease rate as the optimization error.
Stability rate & regularization perturbation. In the literature of optimization, stability of an algorithm expresses its robustness to small per- turbation in the optimization objective. This clearly related to the robustness of PLISAş to the perturbation in 1,,", w, because these parameters jointly determine the regularization P., (X, B), which is part of the optimiza- tion objective. Therefore, we exploit the analy- sis techniques for algorithmic stability derive the robustness in (n) A" pertttuurraatoo and ob- tain the Lipschitz constant Eq. 15, which bounded but increasing in T and K (See Fig. 3 for a visualization).
Convergence Rate
Stability
Generalization Bound
Convergence Rate
Stability
Generalization Bound
KT
Figure 3: Visualization convergence, stability, and generalization bound in Theorem 4.1. The two obtained by choosing differ-
sets of visualizations ent speeds Ce in the convergence rate and stability. Based on the key result in Lemma 4.1, we can apply Dudley's 's integral to measure the empirical Rademachar complexity which immediately yields the following generalization bound.

---

Published as a conference paper at ICLR 2022
Theorem 4.1 (Generalization gap). Assume the assumptions in Lemma 4.1. For any with probability at least 1 6, the generalization gap is bounded by
gen (P((P):)) - Crain (Dm: & c1 V m- log(4E
(16)
Vom log (VmKTexp(-CoK(() to)) V 1) cydm log (Vm(1 exp(-CeKTT)
convergence
stability
where 01, C22 C3. Ce are constants independent of d, m, K and T. See Appendix F for the proof.
Fig. 3 visualizes how the generalization bound in Theorem 4.1 grows when KT increases. The two sets of plots look slightly different by picking different constants Ce. We have also tried varying the values of c22 c3, d, in Theorem 4.1. Overall, they lead the types of behaviors in Fig.
An important observation in Theorem 4.1 and Figure 3 that the generalization gap could decrease in the number of layers, and we will see in Section 7 that this matches the empirical observations. It also distinguishes algoritm--unrollig based architectures from conventional neural networks, whose generalization gaps rarely decrease the number of layers.
Remark. The above generalization results are conducted on a constrained parameter space (as de- scribed in Lemma 4.1) that we can utilize the algorithmic properties of PLISAg. We focus on this space because the analysis contains more interesting and new ingredients. For parameters out- side this space, the analysis procedure is similar to other conventional recurrent networks. Since the bound in Theorem 4.1 has matched the empirical observations, it is reasonable to believe that after training, the learned parameters are likely to be in this 'nice' constrained space.
EXTENSION To UNSUPERVISED LEARNING-TO-LEARR SETTING
Real-world datasets may not contain the ground-truth parameters ,r but only contain the samples from each task, D {2 z(m) In this setting, construct unsupervised training loss to minimize the empirical loss function Ln (e.g., the likelihood function) on the samples.
Unsupervised training loss: Ctrain (D% 0) =
Lag Br Br
(17)
2=1
In this loss, both 2 and 2 are subsets of 2 The samples Zian, are used as the input to PLISAg and the samples 2 are used for evaluating the output 3r from PLISA
Let 0f E arg min Crrain (Dl, (4;00 0) be minimizer to this unsupervised loss. Theoretically, bound the generalization етror of 0%. we can show that
gyen (P(P))0)) - C Σm i=
Lma (Z Br
- Lng (Z(1)
1:ng ('(()
(18)
unsupervised training
+ Lgen (P(P): 01) Ctrain (Dmi
V VLnn (2 B
(1)
(19)
generalization gap: Theoeem
statistical error
Compared to Eq. 9, this upper bound contains an additional statistical error, which appears because of the gap between the unsupervised loss and the true error that we aim optimize. Clearly, in this upper bound, the generalization gap can be bounded by Theorem 4.1. Furthermore, the unsupervised training error in Eq. 18 can be bounded by combining Theorem 3.1 with the following in equality.
Log (Zingy Br 2 1:00 01)) - Log 1:ngg 33*) )))) Lmz (41m2 3r)
(20)
< Lug (Z1.ng
IV (Z1:0 8r 112 |r (Z 0²) 32112
|| (Z 0-) 13,13
(21)
bounded by Theorem
bounded by Theorem
More details of the extension to unsupervised setting be found in Appendix H.

---

Since Published as a conference paper at ICLR 2022
6 RELATED WORK
Learning-to-lear has become an active research direction in recent years (Bora et al., 2017;
Franceschi al., 2017; Niculae et al., 2018; Denevi et al., 2018; Pogančić al., 2019; Liu al., 2019b; Berthet et al., 2020). Many works share the idea of unrolling or differentiating through al- gorithms to design the architecture (Yang et al., 2017; Borgerding
al., 2017: Corbineau et al., 2019; Xie et al., 2019; Shrivastava et al., 2020; Chen et al., 2020a; Wei et al.. 2020; Indyk et al., 2019; Grover et al., 2019; Wu al., 2019). A well-known example of learning-based algorithm is LISTA (Gregor & LeCun, 2010) which interprets ISTA (Daubechies et al., 2004) as layers of neu- ral networks and has been an active research topic (Zhang & Ghanem, 2018: Kamilov & Mansour, 2016; Chen et al., 2018; Liu et al., 2019a; Wu et al., 2020; Kim & Park, 2020).
However, the generalization of algorithm learning has received less attention. The only exceptions are several works. However, Chen et al. (2020b) and Wang et al. (2021) only consider learning to optimize quadratic losses. Behboodi et al. (2020); Joukovsky al. (2021) do not connect the generalization analysis with algorithmic properties to provide tighter bounds as in our work. Unlike our work that analyzes the Lipschitz continuity (Lemma 4.1); the work of Gupta & Roughgarden (2017); Balcan et al. (2021) studied the generalization of learning- based algorithms with focus on scenarios when the Lipschitz continuity is unavailable. We will refer the audience to Shlezinger al. (2020); Chen al. (2021) for more comprehensive summary of related works.
7
EXPERIMENTS
7.1 SYNTHETIC EXPERIMENTS
In synthetic datasets, we consider sparse linear regression problems and sparse precision matrix estimation problems for Gaussian graphical models. Specifically, we recover target vectors 3 e Rd, where {256, 1024] in SLR, and estimate precision matrices O' Rdxd, where
{50, 100) in SPE. See Appendix I.2 for descriptions of the dataset and data preparation.
dbm-226
dm-1624
7.1.1 SPARSE LINEAR REGRESSION (SLR)
plia
In this experiment, we compare PLISA with several baselines and also verify the theorems.
alist
mn
error
m1
62
Performance comparison. We consider baselines including APF (Wang et al., 2014), ALISTA (Liu et al., 2019a), RNN (Andrychowicz et al, 2016), and RNN-E,- APF is the path- woth-following algorithm that is used as the basis of our architecture. ALISTA is a representative of algorithm unrolling based archi- tectures. which is an advanced variant of LISTA. We have tried the vanilla LISTA, but performs worse than ALISTA on tasks so it is not reported. RNN refers to the L.STM-based model in Andrychowicz et al. (2016). Besides, we add a soft-thresholding baseline, called RNN-
wall Cock Dme (900)
wall cloc Binc (sec)
Figure 4: Convergence of recovery
APF takes long time converge. its curve are outside the range of these plots. We use dash- line to represent the final & crror it achieves.
operator this model to enforce sparsity, and include this variant Except for APF, all methods are trained on the same set of training problems and selected by the validation problems. For APF, perform grid-search to choose its hyperparameters, which is also selected by the validation set. The detailed specification of each model can be found in Appendix I.3.
Fig. 4 shows the convergence of ||3. 112 for problems in the test set. The r-axis indicates the wall-clock time. terms of the final re- covery accuracy, PLISA outperforms all base- line methods. In the more difficult setting (i.e,
Generoitation Gop
0:00
-01
6.0
d 1024), its advantage is obvious. Although PLISA is slightly slower than other deep learn- ing based models due to the computations of KT,, for two different experimental settings. MCP and SCAD, PLISA achieves a better accuracy and has been converging much faster than the classic algorithm APE. APF is very slow mainly due to the use of line-search for selecting step sizes.
Figure 5:
Generalization gap of PLISP SA with varying
8

---

Published as a conference paper at ICLR 2022
Generalization gap. We are interested in the generalization behavior of PLISA. As this experiment conducted for theoretical interest, we do not use the validation set to select the model. We vary the number of layers (K) and blocks (I') in PLISA create set of models with different depths. For each depth, we train the model with 2000 training problems, and then test it on a separate set of 100 problems approximate the generalization gap. In Fig. 5, observe the interesting behavior of the generalization gap, where the left one increases in KT at the beginning and then decrease to a constant, and the right one increases fast and then decrease very slowly. This surprisingly matches the two different visualizations in Fig. 3 of the predicted generalization gap given by Theorem 4.1.
7.1.2 SPARSE PRECISION MATRIX ESTIMATION (SPE)
We compare PLISA with APF, GLASSO (Friedman et al., 2008), GISTA (Guillot et al., 2012), and GGM (Belilovsky et al., 2017) on sparse precision estimation tasks in Gaussian graphical models. GLASSO estimates the precision matrix by block-coordinate decent methods. GISTA is proximal gradient method for precision matrix estimation. GGM utilizes convolutional neural network to estimate the precision matrix. Details of each model and the training can be found in Appendix 1.4.
Table reports the Frobenius error |
Table 1: Recovery error in SPE. The reported time is the av- erage wall-clock time for solving each instance in seconds.
@' between the estimation θ and the true precision matrix O", averaged over 100 test problems. PLISA achieves con- sistent improvements. Classic algorithm are slower because they perform line- search. GLASSO faster than other clas- sic algorithm because
Sizes
p = 50
p == 100
Methods
O" 1
Time
0
O* 1:
Time
PT.TSA
119.47 + 12.23
0.117
142.70 + 13.38
0.132
GLASSO
169.63 1: 17.99
1.66
237.95 1 27.49
3.12
the sklearn package (Pedregosa et al., 201 1) in which the implementations optimized.
GISTA
186.96 + 25.48
53.47
373.66 + 41.72
36.02
APF
269.51 1: 32,28
46.02
485.94
60.33
86.82
GGM
194.26
+ 10.73
0.007
445.00
58.89
0.008
7.1.3 DISCUSSION ON TRAINING-TESTIE
TIME
Test time. Fig. 4 and Table 1 shows the wall-clock time for solving test problems. Overall, classic algorithms are slower because they need to perform line- search. It noteworthy that learning- based methods can solve batch of problems parallelly but most classic algorithms cannot. To allow more advantages for classic algorithms, the test problems are solved without batching in all methods.
Train time. As metioned earlier, we perform grid-search to select the hyperparameters in classic algorithms using validation sets. The training time comparison is summarized in Table 3 and Table in Appendix 1.4. We can see that training time is not bottleneck of this problem. Moreover, In SPE, classic algorithms even require a longer training time than learning-basee methods.
7.2
UNSUPERVISED LEARNING ON REAL- WORLD DATASETS
We conduct experiments of unsupervised algorithm learning on 3 datasets: Gene expression dataset (Kouno al., 2013), Parkinsons patient dataset (Tsanas al., 2009), and School exam score dataset (Zhou et al., 201 1). See Appendix 1.6 for details of datasets and the configuration.
The goal of the algorithm is estima- tion the sparse linear regression parame- ters f for each problem. Recovery ac- curacy is estimated by the least-square er- ror on a of held-out samples for each problem. Table 2 shows the effectiveness of PLISA. Note that these real-world datasets may not satisfy the assumptions in this paper. This set of experiments are conducted only to demonstrate the robustness of the proposed method.
Table 2: Recovery accuracy on real-world datasets.
PLISA
APF
RNN
RNN-
ALISTA
Gene
1.177
1,289
1.639
1.349
1.289
Parkinsons
11.63
11.86
11.91
13.05
34.843
School
296.6
367.9
561.5
310.3
884.2
DISCUSSION
We proposed PLISA for learning to solve sparse parameter recovery problems. We analyze its capacity and generalization ability. The techniques could be used derive guarantees for other algorithm-unrolling based architectures. The model PLISA can be improved by using more flexi- ble penalty function (e.g., a conventional neural network) as long as satisfies Assumption B.I.

---

Published as a conference paper at ICLR 2022
REFERENCES
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems, pp. 31813998199991 19999, 2016.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data sufficient to learn high-performing algorithms? generalization guar- antees for data-driven algorithm design. In Proceedings of the 53rd Annual ACM SIGACT' Sym- posium on Theory of Computing, pp. 919-932, 2021.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research. 3(Nov):463-482.2 2002.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky.
margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 0240-62499 2017.
Arash Behboodi, Holger Rauhut, and Ekkehard Schnoor. Compressive sensing and neural networks from statistical learning perspective. arXiv preprint arXiv:2010. 2020.
Eugene Belilovsky, Kyle Kastner, Gaël Varoquaux, and Matthew B Blaschko. Learning to discover sparse graphical models. In International Conference on Machine Learning, pp. 440-448. PMLR, 2017.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean- Vert, and Francis Bach. Learning with differentiable perturbed optimizers. arXiv preprint wrXXi:2002.08676 2020.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using genera- tive models. In International Conference on Machine Learning, pp. 537-546. PMLR, 2017.
Mark Borgerding, Philip Schniter, and Sundeep Rangan. Amp-inspired deep networks for sparse linear inverse problems. IEEE Transactions Signal Processing, (5(16):4293-4000 2017.
Sébastien Bubeck. Convex optimization: Algorithms and complexity.
arXiv preprint
arXiv: 4980, 2014.
Emmanuel J Candes and Terence Tao. Decoding by linear programming. ICEE transactions information theory, (1(2)):403-42115 2005.
Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds of a family of recurrent neural networks. arXiv preprini arXiv: (ee::1900..994 2019.
Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and a benchmark. arXiv preprint arXiv:2103. /2828, 2021.
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical linear convergence of un- folded ista and its practical weights and thresholds. In Advances in Neural Information Processing Systems, pp. 9061-9071, 2018.
Xinshi Chen, Yu Li, Ramzan Umarov, Xin Gao, and Le Song. Rna secondary structure prediction by learning unrolled algorithms. arXiv preprint arXiv:2002.058// 2020a.
Xinshi Chen, Yufei Zhang, Christoph Reisinger, and Le Song. Understanding deep architecture with reasoning layer. Advances in Neural Information Processing Systems, 33, 2020b.
M-C Corbineau, Carla Bertocchi, Emilie Chouzenoux. Marco Prato, and J-C Pesquet. Learned image deblurring by unfolding a proximal interior point algorithm. In 2019 IEEE International Conference on Image Processing (ICIP), pp. 4664 4668. IEEE, 2019.
Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for linear inverse problems with sparsity constraint. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, (711)1144 1457, 2004.
10

---

Published as a conference paper at ICLR 2022
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning to learn around a common mean. Advances in Neural Information Processing Systems, 11110169-11199, 2018.
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 96(456): 1348-33)3 2001.
Jianqing Fan, Yang Feng, and Yichao Wu. Network exploration via the adaptive lasso and sead penalties. The annals of applied statistics, 3(2):521, 2009.
Luca Franceschi, Paolo Frasconi, Michele Donini, and Massimiliano Pontil. A bridge between hyperparameter optimization and larning-to-learn. stat, 1050:18, 2017.
Jerome Friedman, Trevor Hastie. and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatisticss 9(3):432-444 1413322441.22 2008.
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprini arXiv:2002.06157 2020.
Karol Gregor and Yann LeCun. Learning fast approximations of sparse coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. Omnipress, 2010.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. arXiv preprint arXiv: 1:Xiv:1903008850 2019.
Dominique Guillot, Bala Rajaratnam, Benjamin T Rolf', Arian Maleki, and lan Wong. Iterative thresholding algorithm for sparse inverse covariance estimation. arXiv preprint arXiv:1211.2532, 2012.
Rishi Gupta and Tim Roughgarden. pac approach application-speeife algorithm selection. SIAM Journal on Computing, 46(3);992-1017, 2017.
Piotr Indyk, Ali Vakilian, and Yang Yuan. maaring-bbssdd low-rank approximations. arXiv preprint arXiv: 1910. 13984, 2019.
Boris Joseph Joukovsky, Tanmoy Mukherjee, Nikos Deligiannis, et al. Generalization error bounds for deep unfolding rnns. In Proceedings of Machine Learning Research. Journal of Machine Learning Research, 2021.
Ulugbek S Kamilov and Hassan Mansour. Learning optimal nonlinearities for iterative thresholding algorithms. IEEE Signal Processing Letters, 23(5)7777-751, 2016.
Dohyun Kim and Dacyoung Park. Element- adaptive thresholds for learned iterative shrinkage thresholding algorithms. IEEE Access, 8:45874-45886, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Tsukasa Kouno, Michiel de Hoon, Jessica C Mar, Yasuhiro Tomaru, Mitsuoki Kawano, Piero Carn- inci, Harukazu Suzuki, Yoshihide Hayashizaki, and Jay W Shin. Temporal dynamics and tran- scriptional control using single-cell gene expression analysis. Genome biology, 14(10):1-12, 2013.
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. ALISTA: Analytic weights are as good as learned weights in LISTA. In International Conference on Learning Representations, 2019a. URL httph:tp///cmc http:s:s//ppeeevvieeee net.iiewwweeeeeeeee.... seeee//orrmiidddnneee
Risheng Liu, Shichao Cheng, Yi He. Xin Fan, Zhouchen Lin, and Zhongxuan Luo. On the conver- gence of learning-based iterative methods for nonconvex inverse problems. IEEE transactions on pattern analysis and machine intelligence, 42( 42(12):327-30339 2019b.
Po-Ling Loh and Martin J Wainwright. Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima. The Journal of Machine Learning Research, 16(1):559-616, 2015.
11

---

Published as a conference paper at ICLR 2022
Vlad Niculae, Andre Martins, Mathieu Blondel, and Claire Cardie. Sparsemap: Differentiable sparse structured inference. In International Conference on Machine Learning, pp. 3799 --008, 2018.
Edouard Ollier and Vivian Viallon. Regression modelling on stratified data with the lasso.
Biometrika, 104(1):83-22) 2017.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and F. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differ- entiation of blackbox combinatorial solvers. In International Conference on Learning Represen- tations, 2019.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Nir Shlezinger, Jay Whang. Yonina C Eldar, and Alexandros G Dimakis. Model-basee deep learn- ing. arXiv preprint arXiv:2012.08405, 2020.
Harsh Shrivastava, Xinshi Chen, Binghong Chen, Guanghui Lan, Srinivas Aluru, Han Liu, and Le Song. GLAD: Learning sparse graph recovery. In International Conference on Learning Representations, 2020. URL https: : wpwp./eeeee....eeo//pp/. net forum? BKxpMTT.....
Athanasios Tsanas, Max Little, Patrick McSharry, and Lorraine Ramig. Accurate telemonitoring of parkinson's 's disease progression by non-invasive speech tests. Nature Precedings, pp. 1-1, 2009.
Xiang Wang, Shuai Yuan, Chenwei Wu, and Rong Ge. Guarantees for tuning the step size using a Seaming-to-leame approach. In International Conference Machine Learning, pp. 10981-10990. PMLR, 2021.
Zhaoran Wang, Han Liu, and Tong Zhang- Optimal computational and statistical rates of conver- gence for sparse nonconvex learning problems. Annals of statistics, 42(6):2164, 2014.
Kaixuan Wei, Angelica Aviles Riller, Jingwei Liang, Ying Fu,
Schönlicb, and Hua Huang. Tuning-free plug-and-play proximal algorithm for inverse imaging problems. In Interna- tional Conference on Machine Learning, pp. 10158-10169. PMLR, 2020.
Kailun Wu, Yiwen Guo, Ziang Li, and Changshui Zhang. Sparse coding with gated learned ista. In International Conference Learning Representations, 2020. URL https: /oppnevveee.e...ee
net forumm id=3ygdO2VKKE.
Shanshan Wu, Alex Dimakis, Sujay Sanghavi, Felix Yu, Daniel Holtmann-Ree Rice,, Dmitry Storcheus, Afshin Rostamizadeh, and Sanjiv Kumar. Learning a compressed sensing measurement matrix via gradient unrolling. In International Conference on Machine Learning, pp. 6828-6839. 6ML,, 2019.
Xingyu Xie, Jianlong Wu, Guangcan Liu, Zhisheng Zhong, and Zhouchen Lin. Differentiable lin- earized admm. In International Conference on Machine Learning, pp. 6902-6911, PMLR, 2019.
Y Yang, Sun, Li, and Z Xu. Admm-net: A deep learning approach for compressive sensing mri. corr. arXiv preprint arXiv: (777.06666)) 2017.
Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of statistics, 38(2):894-942, 2010a.
Jian Zhang and Bernard Ghanem. Ista-net: Interpretable optimization-inspired deep network for image compressive sensing. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1828-1837, 2018.
Tong Zhang. Analysis of multi multi-stage convex relaxation for sparse regularization. Journal of Machine Learning Research, 11(3), 2010b.
Jiayu Zhou, Jianhui Chen, and Jieping Ye. Malsar; Multi-task learning via structural regularization. Arizona State University, 21, 2011.
12

---

Published as a conference paper at ICLR 2022
A LIST OF DEFINITIONS AND NOTATIONS
For the convenience of the reader, we summarize a list of notations blow.
1. || A |3ك| denotes element- wise & norm.
(=)s is the sub-vector of with entries in the index set S.
æ Ve= max ) [max{21, . max e]]".
Element-wise :ettthheeshod:
(xx = (13) + sign(33 (131 + sign(31)
(22)
(23)
(13a) *AA) (3g)
Denote a single iteration of the modified proximal gradient step as
G MMGGBB ; a.
Ta.x (3h-1-a0 W
B PENALTY FUNCTIONS
We provide detailed descriptions of the penalty functions used in PLISA. We focus on learning the combination of three well-known penalty functions:
p()) (A, 3) = || - 311,, (x, = En B3), (A. Σn- SCAD(A,, By),
where MCP (Zhang, 2010a) and SCAD (Fan & Li, 2001) are nonconvex penalties whose analytical forms are given below.
B. ANALYTICAL FORMS
The MCP penalty can be written as
DAa
MCP(A,
1 (13)
DA)
1 [[ bA),
2b
2
where b is some hyperparameter. The SCAD penalty can be written as
8² 2ad |8| +
SCAD(A, = A |3| 1 (18)
11A (A< {
2(a 1)
(a 1)
(1 >X),
where a > 2 some hyperparameter.
PLISA uses the concave components of these penalty functions. Their analytical forms as follows.
__2 .82
(b2
q (A, MCP(A. A181
2b [1 6A) +
(22 \ 1( > bA)
( = SCAD(A. 8) - -188 2A131
82 X2
1 < |8] S aA)
2(a - 1)
(a + 1)X²
2x 2
+
1( > aA)
2
13

---

Published as a conference paper at ICLR 2022
B.2 IMPLICATIONS
Based on the definitions of these penalty functions, it is easy to check that their convex combination satisfies of conditions as stated in the following Assumption B.1.
Assumption B.1 (Regularization). Let P(X,3) Q(2. | where Q is concave in B, and that Q(,, 3) = Σ ((), B,). Denote the partial gradient of q as (x(3) == 9g(2.9)
Assume the
83
following regularization conditions.
(a) There exists constants ç N 0 such that for any B' 3,
((0)) 9 (8)
5
S 0.
8
(b) ((,, -3) 3).
(c) (0) (A,0) = O.
(d) (8) S.
(e) (8) (3) S A1 A2/.
Note that the penalty function Puo (A, 3) PLISAe satisfies all these conditions, with the constant & in condition (a) being
1 Ew = W2 + W3
a
where and b are the hyperparameters in SCAD and MCP.
Next, we present an important lemma which states the restricted strongly convexity and smoothness of the modified loss
LA (3) = In (n 3) + (X.
Lemma B.1 (Restricted Strongly Convex and Restricted Strongly Smooth). Assume P satisfies Assumption C.I and (Zn, E P. If (),, satisfies the regularization conditions in Assump- tion B.1 l with constant & < p_. Then
Lx(B) == Ln (Z 3) Q)),3)
strongly convex and smooth in the subspace - B11o S s" + +2]. That is, for any B. 3' such that ||3' - Bloo I x* 28, the following inequalities hold
Lx(B) 2 Lx + VL (8' 33 + P- -
1 - -11
(24)
LA(3' < (3) + (B) T 3)
P= 1 3112 2
(25)
Proof. The proof is straightforward by using the condition (a) in Assumption B.1 and the sparse- eigenvalue condition in Assumption C.I.
14

---

Published as a conference paper at ICLR 2022
C PROBLEM SPACE ASSUMPTIONS
We follow the notations in Wang et al. (2014); Loh & Wainwright (2015) to describe some classic assumptions the estimation problems.
Assumption C.1 (Problem Space). Let s be positive integers and p-, be positive constants such that & > (121(p+/p-) + 144(p+/p-)d
Assume for every estimation problem (Zims 3*) in the space P, the following conditions satisfied.
(a) 11 S s* and || bl S B1;
V'ViLa(2 1ell E {p-,p++]:
(b) For any nonzero Rd with sparsity |ol|oo S s" + 23, it holds
(c) 8 8 1m 3²1 S IV 0)1, S Bz. Vj 1, d.
Condition (a) assumes 3 is 8 -spare and Bi-bounded. Condition (b) commonly referred as 'sparse eigenvalue condition" (Zhang, 2010b; Wang et al., 2014), which weaker than the well- known restricted isometry property (RIP) in compressed sensing (Candes & Tao, 2005). Note that the class of functions satisfying conditions of this type is much larger than the class of convex losses. In the special case when L, (21.0 (3) is strongly convex in B, condition (b) holds with + oc. The last condition bounds the gradient of the empirical loss Ln at the true parameter 3 and 0.
15

---

Published as a conference paper at ICLR 2022
D RECOVERY GUARANTEE FOR PARAMETERS IN CONSTRAINED SPACE
Our generalization analysis is conducted on a constrained parameter space. In this section, we of PLISAp when 0 is in the constrained
provide theoretical guarantees for the estimation space. We first formally define the parameter space as follows.
Definition D.1 (Constrained parameter space). Assume P satisfies Assumption C.I and Dm P. Given some positive values O'nin Tmax: Smax. and Amax- We definite the constrained parameter space ((Dm) as (Dmm) = {0- {n. wn, conditions (i) (ii) (iii) (iv) are satisfied), where the conditions are:
(i) a E [a'in 1.
(ii) My E [Mmin = -009)))))) Mmaax for all 1,...
1 (iii) W22 + W3 a-1 I Smax p-, where b is the hyperparameter in MCP and is the hyperparam- eter in SCAD.
(iv) X E (sup
Valnn 3')be V e, for all = -,,,,, ,d.
For parameters in this constrained space, we can show the performance guarantee for the outputs of PLISAg, stated in the following Theorem D.1.
Theorem D.1 (Recovery guarantee). Assume satisfies Assumption C.I and Dm P. Let (Dm be the constrained parameter space defined in Definition D.1 and assume O {n, X", w, a) O (Dm)). Assume
29p+
1
[1 V vV''s=lle /log (5-1/2 +
K 2 log
1 p- Emax
(1 +
Ominp+
where 8 : amii (p_ Emax) Then for any problem (Z 3²) in the training set Dm all intermediate outputs of PLISAL SAg have the following error bounds for all t 1,... ,T.
15/2
113 (Z 0) 12
||AeeZZ:::
0))s 1|2,
4k: = 1, K,
P- &max
19/8
113r(Z1.ni0) - -3 S p_ Emax
|1(Ar(Z1n 0))s-
Proof. The proof of this theorem is based on series key lemmas for the properties the modified proximal gradient steps in each cell of PLISA. We state these key lemmas and their proofs in Section With these lemmas, the proof of this theorem is straightforward, and we state the proof below.
Given fixed problem (Zim, 3²r E Dm and a fixed set of parameters = (17, we simplify some notations in this proof by removing the dependency on Zt. and 0. For example, denote Br -3:(7 0), 3 Bh (Z f), A, >e f), etc.
(n,,** X w, a) O(Dm),
Notations. Furthermore, we will use the following simplified notations and definitions.
empirical loss
Ln (B) = (,, 1,m= 3))
modified loss
T.x ( Ten (71:n, 3) Qu (A,
regularized loss
xx(33 = Lnn (Z 3) + P.. (A, B) = (A + ||
local optimal
BA arg min
B1R -loss (33
(B- (VLx(B) + -
sub-optimality
(x = min max e 1
Now we are ready to state the proof. We first show the following statement holds true for all t < T by mathematical induction.
Statement((); wx, (3 < 2' and 11(3.) S 5, =k 1.... K.
16

---

Published as a conference paper at ICLR 2022
Statement(1). First we verify that Statement(1) holds true. Recall that Ao [L) In the following, we prove that O is a local solution of Φxx (33 Lxo (3) + 11,311a.11.
LL, (3)) + d o 011
VI,, (0) + V V Ao 0) A i||l||
sigu (V., VL (0) + 0 o
sign sigu(VLL.(0)) A o 0
Since sign(VL, (0)) e 0||0|| then have 0 E VL (3 Ao 011
Therefore,
wxo (39) = O. Since d = d 7h, by Lemma G.6, we have
wa ( < WAo (8) 0.2
< 1/2.
0.9
By Lemma G.5, we have Φx, (3)) のx (G¹) I 21/2 1 which implies that the conditions
-mma
in Lemma G.4 are satisfied. Therefore, we have proved that )(())) llo S
8 4k I....,.. K.
This finishes the proof of Statement(1).
Statement(1) ()). Now assume Statement(I 1) true and prove Statement(I). First, we prove that Wx._, (3 & 1/4. By Lemma G.2 and Lemma G.5,
WA.., (3 < V2(1 +
1 DVP+
K-1 29/2/ (2,
aminP1
amin (p_ Emax)
min(Ar-1)
P_ Emax
29p+
(1oo v=))s= ll2 V(1 Cmuin (p- Emax)
V P- Smax
amiup+
E (AnVA')s-l12 / log (6-1/2) where
Assume K 2 log
(4V - Emax
29p+
Ominn
8 = amin Smax).
Then have
Wx, _ (3 5 1/4.
(26)
Since 3 = BK Lemma G.6 implies that
wx, ( $ 1/2.
Furthermore, by Lemma G.5, wxx (3)) < 1/2 implies
Φ> (0)) Φx, (0*) S 21/2]((A)s-
(27)
P- &max
which in turns implies that the conditions in Lemma G.4 are satisfied. Therefore, have
(10*)) llo S $ Vk: 1, ,,...,.. K,
which completes the proof of Statement(t).
Now we derive the error bounds. Similar to how we derive Eq, 26 and Eq. 27, it is easy to show that wx. (B*k) 1/4,
Vt = 1, ... ......,.. T,
21 21/2 112
and Φx (3:) - Φx (8*) -
Vt =t 1.... T.
P_ Emax
Combining dx. (33) - xx. < p- p- Emax
21x2 15 with Lemma G.3, we have
|| 1/2 1| < 15/2 112
Vk 1.... K.
(28)
p_ Emax
Combining wx, (g < 1/4 with Lemma G.5, we have
|3 - 1/ < 1 + 17)
17) |1(A))
(9/
p_ Emax
p_ -mmax
17

---

Published as a conference paper at ICLR 2022
E CAPACITY ANALYSIS: PROOF OF THEOREM 3.1
Proof. This theorem is a direct result of Theorem D.I, by taking a suitable set of parameters 0. Similar to the proof of Theorem D.I, some notations are simplified. Please refer to the proof of Theorem D.I for detailed illustrations.
Denote the union support set of the true parameters 3r by S =- ; Dm Then we specify set of parameters = {n, X*, w, aj for PLISAş as follows.
j E supp( (Z 3*)
aa
P+
w: The weights w can take any values as long as they satisfy W2 g + Wa a-I < p... Since w2 and Wy and be arbitrary close to 0, there must exists set of weights w that satisfy this constraint, In particular, we denote this value by &w 1i22 + W3 a-1'
X For each j Sm we take X; = 8 m2. (L B)) V e as the target regularization parameter. For each j & S we take X; = B2, which the upper bound of 1 0) cc by Assumption C.I. 17: For all j. take 77 log 9 that the decrease ratio is (n,) = 0.9.
Clearly, this set of parameters satisfy the conditions in Theorem D.I, so we can apply its result in this proof.
In the following, we will show that, with this specification of the parameters, PLISAg can achieve the recovery accuracy stated in Theorem 3.1.
Let ty = min {t: : t 2 0, A = max VgLn (Z.m. 0)| X*} Zim E Dm, X E 8 E @(Dx)) be the number of blocks after which Ae (Z 0) X We know to is small number because the decrease rate is linear. To be more clear, it is easy to show that to loog B2) /109(1//)). Therefore, after to cells, the regularization parameters do not change anymore. That is,
Ae(Z1mni 0) X², Vt 2 to.
Since the specified parameters satisfy the conditions in Theorem D.I, we can follow the same way as how we derive Eq. 26 to obtain that
WX (Bi-1) S 1/4, Vt 1, ,T Since we have A X for 2 fn- The last (T - to) cells can be viewed as a single cell with K(T to) many steps. Therefore, we can apply Lemma G.2 and Lemma G.5 to obtain
wx. (Bt)) 2/2pt
alp- - -ww)) ((t-))(11))-1 29/2| 11-1)s-11 11
(L (1-a(p-
p- - Ew
29p+
1 ) |1(20 V v>*)s-11 V(1 - (1-aapp- - -ww))
k((t-fo--1
(1
p_ &w
apt
29p+
1 v B2 v(1 alp- - (vm)
1(1-20)-1
(1
P- Ew
apt
E
co S exp(-Coo((t -t))),
where C.
2 log a(p- [ww),, co = =V PP--tu (1+ 1 B,
29p4
apt 1-alp- -(m) By Lemma G.5,
(w.. )+ + 17
||
8
|| - 33 S
P- Ew
Agg- ll2
11 1|2 CoE V55 Ccp(-CoK(t - to)) +
17
8
P_ En
P_ Ew
E05 5" expl-Coo(( - (o)) + A1- ll2
(29)
where čo
B2 co and cg 8lp- J. P--E-
What remains is bounding || 112. First, we define a
condition number as
Smax V (Zn, ("),
Km
max
8min 1 (2n, 3r) Ve
18

---

Published as a conference paper at ICLR 2022
In fact, Km B2. Then recall the specification of X at the beginning of this proof. We have
| 11 S
Σ
8tim
V (Zn, 33), VE
JES
S 8m (V 3*) V E)s 1|2-
Plugging this back Eq. 29, have
|| 3 2| 03E s* exp(- - to)) + c) (V (*) V E)s- 112.
This is equivalent to the statement to be proved.
19

---

Published as a conference paper at ICLR 2022
F GENERALIZATION ANALYSIS: PROOF OF THEOREM 4.
We first state a well-known incquality that bounds the generalization gap by empirical Rademacher complexity.
Theorem F.1 (Adapted from Theorem 26.5 (Shalev-Shwartz & Ben-David, 2014)). Assume that for all (Z 3*) E P and all E θ we have that (Br(Z 0*, S c. Then with probability at least 1 e, for all E O
2 2log(4e-1) gen (P(P);:) firai (Dm; < (fm))e) + 4cv
m
where te == [(Z1mn 3r) + (/rr(1mm 3 }} is the space of loss functions of our model PLISAg, and Rm (fe) is its empirical Rademacher complexity. defined as
Rm (fe) EE supece 1. m - Br(2i 3-
2
where {o are m independent Rademacher random variables.
Therefore, it resorts to bound the empirical Rademacher complexity, which can bounded via Dudley's 's integral. The following theorem states the bound for the empirical Rademacher complexity and its proof follows.
Theorem F.2 (Empirical Rademacher complexity bound). Assume the assumptions Theorem I. Let θ = (D,,. be the constrained space defined in Definition D.I. Let Eg == {(Z1:n 3r) m || (Z1:: 0) - 31 E }} be the space of loss functions of our model PLISAg. Then the empirical Rademacher complexity is bounded by Rmle
Yog (c2/mK(T (o) exp(-CcX((TT---- (n)) VI) + cyd (c1y/m (1-eep((e-xCppp exp(-CoKT)) Vm
where Cb, 02 Cz2 C4 are some constants independent of d, m, K and
Proof. The classical Dudley's entropy integral bound gives us an upper bound for the empirical Rademacher complexity in terms of the covering number.
12
ll li
Rmto S inf az0
4a
Vog.N (e, La, (m(()m) de
Vm
12
le Vlog.N NogNN(e, lo (2(m)) de
<
vm
Vm
Vi
12|l
Pm
log.N
m
mm
The notation Pm, means the empirical measure defined based on the samples in Dm, and
P == sup Pm (Lp)
dee
sup 00r
Σ
1| (Z 0) - -3"
B)
19/8
by Theorem D.1
sup o m
Σ
[[Ar((zsn;:))s
p_ Emax
(7in DD
19/8
Σ
V max BBz, Amax) CC
sup lE
P_
Emax
JED
Here we use a constant C' as the upper bound because we only care about the scales in d, m, K and Vm ,e, L2 L2( By the key result in Lemma 4.1,
T. Next, we bound the covering number N
20

---

Published as a conference paper at ICLR 2022
easy to derive that
l1eo lor (l()((())) 220(ca (o) -a to))
(c2llm - 11/1l2 + c3 X - 1 + w'll)) (1 (1-eepp exp(-CooKT)
<K - -to) la a' exp( Cak - to))
(Iln n'll2 [[|n-n'll2 | x ||2 Vdluu w (12) (1- (1-cxp(-CoKTT)
From now abuse the symbol to generally represent some constant that does not depend on d, m, K,
cK(T - to) exp( CT - to))' Omin: 1
( lo, (2(P))
.111
p+
xN
c(1 (11-exm) e(1-exp(- (Pp(-CCKT)) [Amiu: mmax| ,2)
X
x j.min Aismasll l2
c(1- expl (x-xxp(CCoKT)
X
cvd - (xp(-CCoT)) [W Wmax] ;,
For the covering number of d-dimensional compact vector space T C Rd, can bound it by the e-packing number. That is, (T,, S M(T, (2) s cIT Phima-1iy.mn + for some constant c. Applying this fact, we have
cK(T - to) exp()xxppCKKK too) V1
(e,
c(1 ex1-e (Ppl-CaKT) +
6
j=1
c(1 ex1lexp( (Cpp-CCKT)) +1
6
j=1
exp(((-exp(-Con)
which implies
1 ( les, (2(mm)
log
< log (evmK(T to) (xp))((CC(((Ttol)) V1)
+ (2d) log (ovm (1 exp(- +1) + 3log cv dm (1 - (1-cx((-CeKT))
< log (cvmK(T - to) exp(-CoK(T to)) colgg(//mm1-eeppp-gg//777 +
Therefore, R
Vml V log (c/TK((T 10) exp( 10)) V1) + ed (c/m (1 exp( exp(-CokTT))
21

---

Published as a conference paper at ICLR 2022
F.1 ROBUSTNESS TO PARAMETER PERTURBATION: PROOF OF LEMMA 4.1
We split the parameters = (x*, w, 77 o into two sets 0. (X', wn m). Clearly, the robustness can be bounded by
01 02. where 01 {a} and
(2 mm 81 22) 3 1Z : 8 U 02) 2 + 1 B U82) (r 04 U82) 12)
We derive the upper bounds of these two terms in Lemma F.I and Lemma F.2, which imply
(Z 0) (r )l2 - CV (T) 6 la a'l
1 - 8KT
+ (Cilln -n'l2 C2 1 + C Cavdlw w'll2)
1-8
where 5 == v Ommi (p- Emax) < 1. Lemma 4.1 is equivalent to this inequality by taking Ce (8) > Therefore, the key derivation steps are in the proof of Lemma F.I and Lemma F.2, as stated below.
Lemma F.1. Assume the assumptions Lemma 4.1 are satisfied. Let
0 = =x n) and 0' = {x,, w. n,
be parameters in the constrained space Q Let 1B.1T=1 = PLISAn and (B,'TT- PIITAA (7)m)) be the intermediate ouiputs of PI.SA with different parameters and f'. Assume
29p+
V B2 Amma)) /log (5 + +1,
K 2 log $V p_ Smax
(1+
aminpt
E
where 5 = V1 Ornin (p- - {maxx < 1. Then
1| - 31' S CV (T to) t (K(T-bo) la a'l.
13'-11r'1
Proof. By triangular inequality,
3 3.- |1 = |IM ; w. MPG "; w.
< MMG Ae,, w. a) - MMGG( A w, w. a0)
M3G >r, w. a') MPG(3, vv, w. a²))
WLOG, assume > a'. Applying Lemma F.3 and Lemma F.4 to the above two terms on the right hand side, we obtain
3
3.:/ 2
3 - "112
a' a + a¹
|
3r -
+
< 8l B/
-/1-111 + cla
all
3
3
(30)
where e is the Lipschtiz constant. e is a finite number because a is bounded and positive. Applying it recursively, have
3R 3x0/| < 1130
3.1112 + cla- a'1
8 A
0
-:11
(31)
k=1
22

---

Published as a conference paper at ICLR 2022
Now we bound the term
B - 3,-
By Lemma G.1 and Lemma G.2,
2
3
B
20minn
(0 Φdc (3xi)
V
2
aminP+
2
(Dxnne 2x (Bxx) )
V
P+
(By Lemma G.6)
2
10
11 1120
V
P+
p
Emax
2
10
B2 82
P+
p
Emax
8
where =
Emas B20-1. However, we can have a tighter bound for this term if is
larger than a certain integer. More precisely, recall the definition that A; = max {Ao o o(n)", ) Since (Tmma) 1, the entries of Åo ( will decrease exponentially to reach the entry values of A Let to = min (t: :t 1 2 0, X = max { (A o a (Thaux) X*] VX E A E ((xx)} be the number of blocks after which A, = X We know to is small number because the decrease rate is linear.
Now, the regularization parameters satisfy A = A" Vt 2 ty. Therefore, we can apply Lemma G.1 and Lemma G.2 again to obtain the following bound for all f 2 to:
0 35 11.
20min
(0x w (36 Ōx wo ,x (3x-))
2 aminf+
2
(ox:,u(0tt ox xx (3x-) )
V
A+
(By Lemma G.6)
2
10
((
p+
p_
Emax
Combining the two different bounds for
3 3/ with Eq. 31, we have
C la - a'l Vs*" DK 8 gggh
ift < to if 2 to
||B, - -Bill2 S 8t 1111-11-8--11111
- -B'-al12+
C la a'l vs" Σ (K-K
ift to CC (Cla-a' v (ot ift to
[ala- a'l K&
8 1|, Bi-1l12
where C = cc'. We apply the above inequality recursively and obtain that
T (T la - -a'++ 3K(T-1)z la 1o-1
1|0r - 1001-1111a 3 CV
1=1o
(10-
= K8K (8K(T-
+ (T - (0) 1a
8K
(0(1-18(1001) + (T +T-
=V
100
(k((T(W) 1a - a'l
1 1- gK
SCVFK -1 1) (T(
la aa'
CVV' (T (1) 6 (1 |a aal
23

---

Published as a conference paper at ICLR 2022
Lemma F.2. Assume the assumptions in Lemma 4.1 are satisfied. Let
0 = (X", a} and 0' = {x*,, , w aa
be parameters in the constrained space O Let (Br PLISAg (Z))) and {B:'T=] PLISAg (Z1-n) be the intermediate outputs of PLISA with different parameters 0 and 0' Then [ 0) - Br(Zim 8011
C2|1A' 1 CaVd//w- w''lz) 1 5KT
(Cilln- (cillm-n'l12 n
- 1
where = V Umin(( Smax) < and C1,2,4 are some constants.
Proof. Let (B11111 U (3/
K
& be the intermediate outputs of respectively. By triangle inequality,
and (3,'7- U (
11=1k=1
1==1
PLISA (mm) and PLISA0 1mm)
. 3.o1| = |PCC( de. w. a) - (3 k
1; At', w aa)
|MPG Xe, w. ()) - MP - Ao w, a)
MPG "; Ae, MP -:: X
M
+ MPC AV', w. a) MPC X w/ .a)
Applying Lemma F.3, Lemma F.S, and Lemma F.6 to the above 3 terms on the right hand side, we obtain
2
2011
3/- 14-1 +
||
X1I22 + CC
w Aeela
(32)
2
P+
(i)
(8)
where C some absolute constant.
Term (i). By definition and triangular inequality,
|| A 122 < max (Ao o o } - max (Ao (('"nn'''')))))) l/2
+ || max Do o o }+} max (Au (n)') A") llz
< Ao oc to (Mraax) ((lo))) o(n')ll2 + "|^ X
B2 a (Mhma)) )1 ''nn "11n-'ll + -
<
The last inequality holds by Assumption C.I and the bounded first derivative of (-)). Therefore, for some constants C2
2. and Č C2 B2.
2 A X/12 S (io 1'llm 7/122 C2 X
p+
< - 7'1l2 + A2 - X
The last inequality holds because the value (Tmaa)* bounded by some constant.
Term (i.) Since ||el|2 S max (amax)) Ao. ) } ||2 < || max {a Ao. Ao) l|2 = ||Aol12 s
Bvd,
i = ClIw - w Aella S C. -d
Plugging the bounds for (i)-(ii)) into Eq. 32, we have
O 3 < 611,)/-
- + Ci |l n' C2llA* - X C.vdll w'll2.
24

---

Published as a conference paper at ICLR 2022
By direct computation,
3K/1
K-1
8*
3/-
+ (C1
12 +
w' 112)
Σ 84
km
1 8k
8 3
+
+2 xx w'll2)
1
Recall that 3 Br and 3 3 We can apply the above inequality recursively and obtain that
|1 - Br'll2
1 + Cavallw w0'll)) 1 8 s 6*1 |, - -Br-11l1- - (Cillo) 7/122 + C2l
1- 8
1 5k T-1
- (Cilln- - 1/112 + +C2 12122* X 1 CaVdllw (
Σ
(8
1 1
1=U
1 5KT
= - + C2 X - 12 Civall w'llz)
1- 8
Lemma F.3 (Robustness to 3). Assume (Zim 3²) P and satisfies Assumption C.I. Assume
B3 B' satisfy ||3 - B'llo S === = s* + 23 and S p4
Then
1 - 2a (p_ - kw))t
|MMG(B:A, a, - MPG(33; A, w. alla -
/
11 - B3 l|2
(33)
P_ E10 P+
S v1 a a -(e) 113 33' 1l
(34)
Proof.
|MPG(B;A, w, a) - M X,
= =I[Ta-> (B a (VV - Ta-> (3' - a (VL (VLxx
||@
(B) 3' + a (T 1 (3'))11
||@ 1321 a² |V (B) VL _ ( (12 - 20 - -3', (B) - LL w (3"))
(35)
Since on the restricted subspace (0 || B011a s 23). LA is (p- Ewto-srongly convex and P4-smooth, by Lemma G.7,
(B 3', V w (B) VL (B')) (p- Ew)
|| 3 1/ VV - V Lo
p_ Ew p+
p_ Ew + p+
Combining this inequality with Eq. 35, we have
|MMG((3: X, w, a) MPG(3'; ; x, w. a)l
1 2a (p - )w)
113 - 1132-3112
p_ Ew + p+
2
+ a a p_ Ew + p+
VV (B) - VL (3))
By the assumption that < 1 the second term in the above inequality is non-positive. Further- more, this assumption also implies that 1 2a P Enttn 2 0. Therefore,
(0--E=]0+
|MPG X, w. MPG A, w. al S / 11 2a (p_ (ww -ww)Pt ||3 B'112
p_ Ew + P+
25

---

Published as a conference paper at ICLR 2022
Lemma F.4 (Robustness to a.) With out loss of generalization, assume 2 d' Denote
B == MPG X, w, and := (M: X, w.)
Then
11 B 112 S a a' a || BB12
Proof. Define the quadratic approximation function as
(2, =- L (3) + vL --)) + 2a || -112 1
(36)
Clearly,
MPG(3; w. a) = arg min an (2, B).
2
Since th (2,33 is I d-strongly convex in 2, and that 3+ : MPG(3: X, w. a) is its optimal point,
1
Va.A(zz (at ,))
|| - --11
Zz.
(37)
2a
Similarly,
ae A (2, vo A. (++1 (B) +
|| 11 vz.
(38)
20
Taking B in Eq. 37 and B in Eq. 38 yields
| - 3+1 - th A, ( 1 ,3) Do (5 B3,
20
1
g 3 S tha (B ,3) A (Bt1
2
Summing the above two inequalitics, we have
a + 2 |1 - 3+11|2 s (o.A..0(tt .g) Vo Am (gt1, (3))
+ (ver Ano (B . Va (Bt 33)
(by a 0¹)
I Va' (, (0t ;3) (0 (3)
2 a' |1t - -3112-
1
Lemma F,5 (Robustness to A). Let 3 MPC(3; X, w. a) and 3+ = MPG(B; X, w. w.,,). a). Then
| - - < 2all(A \')s122
(39)
where S = supp(@+)) supp(@tt))
Proof.
Recall the quadratic approximation in Eq. 51 and the definition that MPG(3; X, w, a) =
arg min_ (2, By the I strongly convexity of A..A,w in z, it holds true for all z that a
|| - | S th (2, - Va (
2a
= -VV (B), Bt + 1
[|
-3112 -1BBt - -3112) + (1|=1la. - -113t l1x.)
-
(40)
2a
Similarly,
1
-3+1112
(41)
2a
< ( -(tt)
1
[| 31/
-1(0- a112)) <11=lxx,1 - (42)
2a
26

---

Published as a conference paper at ICLR 2022
Taking 3 in Eq. 40, taking 3 in Eq. 42, and summing up the two inequalities, we have
1 11+ - (V (3) VLX au (B), -B²) + 11+ (X' A) - 1,9 o (X - A) ||
a
= (Vex (g) - (3). -B* + 1| - -/
Vn ();, (2)) - (2,, 13)1851 - 351 + 11 - gt || X-
j=1
(by Assumption B.1) <
Σ 14g X311851 351 + 113 11
j=1
21| -B*1||A- 11
s 2|
X')s || - B
where S =
Dividing both side by ||3 / draws the conclusion.
Lemma F.6 (Robustness to w) Let B = MMG X, w. a)) and B+ MPG(B; X, w', a). Then
|| 3 la S Cl w - w (2) where S = supp(@*) U supp(B*1)
(43)
and C' is some absolute constant.
Proof. Recall the quadratic approximation in Eq. 51 and the definition that MPG X, w, a) = arg min, V..A.w (2, 3). By the --strongly convexity of aa in B, it holds true for all z in the restricted subspace that
a
1
1=--3+13 S (0, - Vo (3* ,3)
2a
(B), B+) + 2x
|| B11 -11Bt - -B122 + (1|=1l,, - -113+11
(44)
Similarly,
1
2a || 1
$ (VLw, w (B), B+")
2a (11-1112 18
-B12) 11
(1|=1|21 - (11+t112,))
(45)
3 in Eq. 45, and summing up the two inequalities, we have Taking z = B+ in Eq. 44, taking
1
| - 3- $ (VLA, (3) L (B), B+)
(vQx (B) - V Vx, 13), Bt)
Ve ()) d'w (),, B;)1137' BJ
Note that o', ()3 Ei=
exp(1n.) (())) (2) where Z(w) = Σi= exp(w:). Then 7(w)
exp(w:)
exp(x()
Id'u (2g, 35) - (A, < Σ
(00' B,)
Z(w)
Z(w²)
1=1
exp(w:)
exp(u!)
(by Assumption B.1) <
Z(w") Aj.
Z(w)
27

---

Published as a conference paper at ICLR 2022
Therefore,
_ |1
11
exp(w:)
exp(w()
Σ Ay133 - 1371
Z (ww)
Z Z(w))
i=1
==1
3
exp(w:)
exp(w()
|1 1|gtt1 - -13t
((w)
Z(w")
i=1
(By Lipschitz continuity)
v C ||
w
12llll
(A)
1 2
for some constant C.
28

---

Published as a conference paper at ICLR 2022
G
KEY LEMMAS
This section supplies some fundamental results for the modified proximal gradient algorithm. All the results in this section are based the following assumption and notations.
Assumption G.1. Assume P satisfies Assumption C.I and consider a problem (Zn,3*) E P. As- sume we have penalty function P( () whose concave component Q(,, (3) -( satisfies the regularization conditions in Assumption B. with a Lipschitz constant f the condition (a). We adopt the following notations for the statements in this sections.
empirical loss
La (33) == Ln (Z (3)
modified loss
LA (3) = (21n (3) + Q(2, (3)
regularized loss
xx(3) == (Z B) + P(A, (3 Lx(3) + 1/11a,1
local optimal
3x arg min
(3
BERd: Agrlloss
quadratic approximation
Va,A (2, = (A(3) + (VIx (3) + 2a
1
|a - -112
1=111 + ||=1|x,1
(9 TT)
sub-optimality wx( = min max 6 3'
U - 11 (VL(B))
Lemma G.1 (Contraction of MPG). Assume Assumption G.I. Let .o.... B be a sequence of vectors obtained by the modified proximal gradient updates:
B MPG X, w. a)
= Taix (3 - a V (V V
Assume (13t) S 3. Then
(2 -=- P+
||3 -3 -hh 1
(46)
2
Proof. Note that
3k= (3h-11, where (G) = a-= a Tax (3 VVIx
It easy observe that (B) VLA(3) + + [3-o0. By RSS in Lemma B.1, holds that
LA (B*) S Lx(B3-11 aVLx 60 + p+ a² ||00(0* 1|2 2
Furthermore, by RSC in Lemma B.I, for any & in the space {||2 - 3 11o S s" + +33],
LA (B+) < Lx(z) + (L TT
(B - 2) (B3% 10gga--11TTT) (8h-11
(47)
+ + [,0 112 P- || -
(48)
2
Denote v = 6a( 1) - VLA(B(-1)). 1) We have v E A 2 011gtt - ad (Bk-1))
since
add 8, (13-1) L 1) + X . 01| - (3* By the convexity of || 1|x.1
| - a0. 1)||,11 S 1 + T (gh-1 ad, (3 -2).
Combining this inequality with Eq. 48, we have
(x(0)) + | llx,1 S Lx(2) A || + ( -2) 2)
(49)
- a (1 (11- -a (1=)(2t) alo+))
(3th
P_ -E ||/ -
(50)
2
Taking = = =B in Eq. 50 implies that
1 (1
a(p+)
(x*) ||,3 S (B*--)) +1100-11
1
11 3/4-1112
2.1 a
2
29

---

Published as a conference paper at ICLR 2022
Therefore,
(1 - 2
P+
- -
|10
S - -
Lemma G. (Convergence of modified proximal gradient). Assume Assumption G.I.
Let
3 3 be a sequence of vectors obtained by the modified proximal gradient updates:
B = MM ; w. a))
= To (3
+)
with step size or in (0, pt
1. Assume 1133)) S 8. Then
ex - (3x) S (1 - a(p- - =² (dx(39) Φ2 (3x))
11B - 3x11 < (1 a(p- )² 11300 -Bx112.
wA(Bt) v2(1 + ap- DVP
V (1 (1-o(p- alp-
Emo)) (ox(30) dx (Bx).
min(A)
Proof. Consider the quadratic approximation function
(a, Lx(3) + (VLx(3), = B3 + 2a
|| -311 + -11=11x11
(51)
By definition,
MPG X, w. a) arg min Vo.A(z 3h
Since tha. dz,,(zz, Bh-1) is -strongly convex with respect z, and that B is its optimal point, can obtain
1 || 3/ Vz.
M Mz, 2 , + 2a
(52)
Note that by Lemma B.1,
Vo (B Bg- 3 LA(B4-1) VLA(B-11) (Bt -1a-11 +
11 3
2a
+ +11.811Ax Il,11
2 Lx(Bh) + a P+ 11 - 1 +1 1|2,1
2
) +
11 3 3k- 112.
Similarly, by Lemma B.1,
Va (2.2(2, = (2(--11) + (L*
- (z-13 1)
+
|| 3
2a
+ +
$ (2(2) + 1p E)
||2 113
Combining the above two results with Eq. 52, we have
1 (p_ E
(x S xx(2) +
||
3h
p+
1
x
2
2
2a |
3*1
(53)
< {z) +
(p_
8
kk-1
2
1
p+
3k-111
2
2
30

---

Published as a conference paper at ICLR 2022
Taking cBx + (1 -c) for some c [0, 11, then
ex(3g)
<cdx(Bx) + (1 (1-c)ox(0)-1) + - - (p- -6)- c²
1
P+
1|
11
$ (3x) + (1 -c))xx(3)t)) cC2 -pp- - -))
13
3x113
a 2
pt
1
11
2
Taking c a (p_ - -)), it implies
1 -
2x Φ2 (3x) S (1 - (p- -0) (()
-
0
pt
11
Bk-
2
Assume 5 L. Then
Sx(3%) - p2(32)
s S (1 a (p_ - E)) (Dx(00-1) - xx
(Ba)
Taking z 3x in Eq. 53 implies
1 (p_ E) xx(B²) S Φa (3x) +
13x - 3
-/1 113x - 3/112.
2
2a
By the optimality of Bx, we have
a (p_ 8)
133 - 1gh11133
-113-- - 131 20, 0.
1
113x
2
2a
which implies
13x - 3012 - -1) - -1
Finally, derive the upper bound for wx (Bt).. Since 3 arg ming th (22 Bh-1), by the optimality condition, for each j ..... d. there exists a subgradient Ey E a |88 such that
VLA(B--1) + - (0" - + =
a
By the definition of wX and combining it with the above equality.
1138 9911a, + }
(3t B3')T
w> (B*)
min 33
max
grE
(B* B¹
(
S max 8'E0
1 1'1l,,1
(8+ B¹)
(VIA(09) VIA(B--1) 1 ( -10))) )
max 3'En
| 1'AA,
(0) 8J)a (VL2(3*)- - VLA(OR-1)) + _ - 1341,
max 3'E0
B B'AA,11
A
1
VLA - VLA 1) 1 (B - -3a)
())
1
(LA - VLA(B(-1) 1 -(hh11 -Bbi)12
(A)
(LA - VLA + 1 -1( -B*
(A)
1
(p+ -1( - -B4)112-
(by RSS)
min
31

---

Published as a conference paper at ICLR 2022
By Lemma G.I, 11(3//11 -Bhh1l2 S V 2. (p4) (0) 1 -3)(3))) Therefore,
2
)x(x 5 min( (p+ + |
2 - (p+) (0A(B3-1) (3(K))
Min (p+ + - V
(Bx - 12(3k))
P+
1
(Dx13t-1) -
min(A) (p+ +
V
p+
min(A) (p+
+
1
2
(1-a(p- (p- - -))) (1)--)))-1 (0x(89) (0x(89)-x((31)) -6x
p+
Lemma G.3 (Statistical &2 error). Assume Assumption G.I. If the following conditions are satisfied
- 3 S 8* + 23,
(54)
6x(3) - ox - 21/2
Ag 12
(55)
p- -
2 2 (V )1
(56)
then 33 S mina20 max {v
21 +
17 1
+ 17
> la S 1 -
15/2 la.
-5
Proof. By the restricted strong convexity of Lx in Lemma B.1,
P_ - E ||8 3/
2
S LB( - LA(B)) VLA((*) (3- 3*)
eA( - xx + (11@* ||.11 - 11 VLA(B*) -3-
S 21/2
Ass 113 (11 ||,,1 11 - VLA(B)) 3r) (3-))
(57)
P- -
For the term (i),
||,1 - 1|,11|.1
11,33- |xg- ||8 || |lag-, 11 + (11 1A5
1133 1103-111-00 11135011)
11,3-- |lagr,1 1 - |1|3--1 ||>g-,1 11,3-= 12gr,1
S [[(3 - )-)s-l |lag- .1 - |135=|1
= [[ - 3')s |lag-,1 - 11B3 - BB)) >gmn11
For the term (ii).
-VLA(3) (3" - (B) (B -3' (Q 3*)
1
(By Eq. 56) < -
||3 - |A,1 - VQA(B*) (3-8))) -3¹)
8
1
(since 4h, (0) = 0)
|/
B II - VQA(33.) ((B (BB-))s-
g
1
(since (8) < A1)
||3
8 Ilx.1 + 11(3 - B-)s- 15-111...1
8
9
1
3²) ||ag.,1 [ - B3))²
s' ||age11-
32

---

Published as a conference paper at ICLR 2022
Combining the upper bounds of term (i) and term (ii) with Eq. 57, we have
|13 - 3²1
21
17
$ (p_ - E)²
As 112
1(B - -9))s= Ilas-.1 A(p- 13 11(3 - (1)0))8))" glgg (58)
4(p_ E)
2 - P_ - As 11 + 4 (1 - -3*)s (laoo.)
21
17
Let a 2 0 be constant. If [3 3z) |las..1 S p-- |ss 12 then
17 a p- - E 21+ +
A 1|
||3 30 S /21
If [3 (3) 11a--lag,,122 > x--5 As [|3 then
21
17
1(B - 3r)s Ilas.,1 E (21
21 + 11) | ll2
|/3 - 33 1 P- - {
+
- |(B - 33)
a
4
which implies || 3 2 v
21
+
17)
|As p--5
Combining the two cases, we know that
17
17
\ 2| p- E
||3 3 2 3 min max
21
4 0.
+
#20
4
Taking a 7 is easy to derive that
15/2 As- 1| p- - E
|| 3-
5
Lemma G.4 (Retain in the restricted space). Assume Assumption G.I. Let Ba,... , be quence of vectors obtained by the following update:
3 = MMPG(3 a,
with step sizes o in [Amin: 1. Assume the following conditions:
11(B9) 5 S 3,
21/2
(x(B) (3*)
p--5 - | 12.
, 228 8 (VI.((31)
121
P- (- ))
|As ll min(25=)
144
23
amin (p_ [)
P_
where i. p- Then for all k: = 1,...,, K,
|1(/g) 13-110 & 8,
and
21/2 - ox(33) S p- - |As-
-
Proof. Recall that _ Tax (3²) where
3 = 3h VV
3 aVLA(8") a (VL)(3*) - (LA(3+-1)).
33

---

Published as a conference paper at ICLR 2022
To show ||(09)); is no more than s. Note that
I s, we need to prove that, for j E S", the number of j's such that 1.9%) > ad,
st
18 - |8)
1 + a (VLA(3)) VLA(BH-1)), +
[LL(
s 1 1 + (VLA(8) VLA(3+-1)) 1),
+ 8 aayy.
1
Therefore, Vc E [0,
7 (
||08 5= lo S Card
{j : 0
(59)
E (VLA(0)) - (LA(B > (1 (1) -,²)
Card
(60)
where Card () represents the size of the set. For the term in Eq. 59,
(GEE5=:18)) {ad1))
13
8
|8 -1
Card
caad
e. Ta
JEB
JEB
8
11(3)-1) ))==1) Ag311
c. min
2
8
11 B²) )= Agg
c. 7a
Bounding |1(Bk -B3) -8)))==1 Following the derivation of Eq. 58, we can obtain
(p- - - -1
< (p_ E) |As- 112 +
21
17
/ (1 - (8*)=-1lass - 11 - -3")3" Alage.l
which implies
12
17 7
- (3) 1
[1age,1 5
| 12-112- +
- 1-)s1-1la,, 11ag0,1-
p- -
Let 2 0 be constant. If ||/ - 33" -130) 11s-|llg-,1 S - A 112, then
17a) |
11(3 11 Agrn11 5
-
12
7 p- E
If [[([a-11 - B²)s- l2s..1 .1 > p- Ass= 112. then
12
17)
11xgg11 S
-B")s 1las-,1
a
7
12
17)
+
||
||s=||al|(B3411 -Ba)2
7
15
12 +
17)
As 1
(Lemma G.3)
<
2
7
p_
E
Combining the above two cases yields
17a 15
12
17
|
|As 1
|1( - -3")s' 12gens S min max
12 +
+
a20
2
7
p- - g
423
12 E
14
p-
34

---

Published as a conference paper at ICLR 2022
where the last inequality is obtained by taking bounded by
253
Therefore, the term in Eq. 59 can be
_ Card (1E3: 109 {
811 33")²" 1-Aggeo!
c. 7a min( min()n-)) (2g-)²
1692
||As-
49ca min (gg.)²
p-
- 5
1692
| l12)
2
49ca(p- - E)
min(Ag=)
Now we bound the term in Eq. 60 as follows. Denote the set as S =
E
5
(VIx(3)) - VIA(BL-11) 1)) > (1 -c-c c)- {ンn}} and its size as 8' == |S Then
5 = Card { { (VLA / - VLA 1)2{ > (1 (1-c) c) ? b1/))
(VLA(3)) - ()A(3H-1))
$ 11 c) JES'
(VLA(B*) - (LA(0H-1)), })
5
(1 c) JES
min()g=)
8
VLA(B*) - VLA(B*-1)11 112
(1 c)
min
(p-)113- - -Bh-111
(1 min
The last inequality holds because Lx is (p+)-smooth in the restricted subspace by Lemma B.1. Applying Lemma G.3, we have
64(p+)2
s' Σ 49(1 - c)2 min
113 - 1
)2
64(p+)²
15/2 s- 112
2 1
3600
) p+
2
IAs ll2 min (ATT)
49(1 - c)² min A }z=)²
p_
- E
49(1
c)²
Pp_ - E
Combining the above bounds for the terms Eq. 59 and Eq. 60, we have
[1(*)) )sr)s llo s min cE(0.1)
1692
3600
P+ p_ 10--6
)²
| l22
49ca
P_ -
49(1 cc²
min(Ag-
121
p+ {+)))
||s-. l1/
2
+ 144
Omin (p_ -)
p_ -
minn(aa"
The second last inequality is obtained by taking
3.
Finally, if we can show (xtht - ex(B²) < that [|(())))(]))))))))))))))) < $ for all k.
21/2 ||s- 112. then we can show by math induction
p-
TTaking = 3h-1 in Eq. 53, we have
21 p+
xx(3²) < (x 11
|| 3 (xt-111).
2
Therefore,
- (x('") s 2dx(3+-1) - xx(B)) v 21/2
-
Ags 112.
p- 5
35

---

Published as a conference paper at ICLR 2022
Lemma G.5 (Statistical error), Assume Assumption G.I. If
wx(3) c, with e & 1/2,
- 1 S 5* + 25, 2, 2 | 11,
then the following relations hold true.
(e+ 17) | l2 21/8
8)
- 10 -
| 11
p- -
p_ -
3e(e + 17/8) ||s=
21/2
xx(33 ox(3))
p- - ||
7/8 E p- -
(3 (( + +117)
| 11
S 29/2
(3 xx(3x) c
p_ - { p_ - 1 112
7/8- -
Proof. Since || 30 S s" + 28, then by the RSC and RSS in Lemma B.1,
(p_ 3)||3 - ق1 (3 V (B - ---) VLx
(61)
Let E E 0||B|1 be the subgradient that attains the minimum in (B Adding and subtracting (X o E) the right-hand side of Eq. 61 yields
(3 TT
(e_ =)1 311 s (B- - (B-3) (BL xo - (B B*) B LLx(B))
(ii)
(B 3 (A+
(iil)
Now we bound the terms (i)-(ii)..
Bound (i) using (x)) Since attains the minimum in wx(3), by definition,
[ (3 - T²)
wx
max feen
||3- 3111,11 (V)x + Xx)
Therefore,
(B (rr (VTx(33) Xx) S swx(3)1 - -3 S 56113 - 3r ||
Bound (ii). Note that L^ = In + Qx. Thus,
[(ii]
VL, + < |(B 3rr
|B ( (B-
Since X3 28 (p)m5 we have
- 33) (B,) 8 1 B A.
Since o2, (0) = 0 and oh, (8) < x (Assumption B.1), it holds true that [B )T) T (QX(B*) = |[B 3- (VQx()*)ss)
< 11(B- 33*) Ilag-.1-
Therefore,
1 [(ii
1/3 1111 + 11(3-130 ss-l|ls.,,1-
Bound (iii) by the definition of subgradient.
(iii) = (B - () (As. o (B - )s Es + (8z o 13))==E8+))
36

---

Published as a conference paper at ICLR 2022
By Holder's inequality and the fact E| I
(As- (g - Bs) Es+) 2 (3")s- 1las.,1-
Since & E 011/311 and that P O,
g- (B 8 g=:))==(s5 E5=) g5 33- S5-) 1/3= lxge,1 = 1133 - 8-")==1 Agr.ll
(62)
Combining the above three equations, it holds true that
(iii) 2 - [1(3 3s* Ilag. + 11(3 - (²) (3"))=lAA=m)
Combine (i)-(iii) Combining the bounds for (i)-(ii)), it holds true that
(o_ E)1|3 - +11
+ +1 + 1) 11(3 - -3")s- Dis-llas,1- - (1 (1 - -- 8) 11 - (03--1")3111 -9")3-11a33""
8
8)
c+ 17)
(3
11(3 3²)s- >>s-1lag.11
11B - -3- 3g)3-~11a 1
(63)
8
8
20
(e+
17) |1(B 33's-- 112g-.1.
8
Using the fact that |I@B - s- IlAg-.1 S ||As-1121(BB- ((0)0--))ss--- 122 it implies the first conclusion:
(e+ 17) |Ag-
113- -B12 I
(64)
p- p--E -
Now prove the objective value. Since Lx is convex on B, 3* and ||-111 is convex,
xx(6²) 2 2x (3" BB) (VLx(()) + xo
which implies
$A (B*) S (B (V) x
< || (8 S <c|B- B A,1
(65)
Now we bound the norm ||g 3* A,1 as follows. By triangle inequality,
||3 3 A1a11 - || )- ll-llag- + 11@ 3 )5 lAg..1.
(66)
To bound [| - (*) Ag moving the term |[B 3=)==l1>==1 in Eq. 63 to the left hand side yields
(7/8- 3²) 11 S (E+ 17/8)]| - 33)s-- IlAs-.1:
which implies
|( - 30) 11 S 17/7/8
((3-)3))
7/8 - |1,3 B²)s- Ilag..
(67)
Plugging it into Eq. 66, we have
+
17/8)
7/8 - ) ||As-112|/3 -3
3
| - 3 S
+
|(@ 1(88- -B*)s- |1ag0,1 S
7/8 -
3
(E+ 17)
| l|2
(by Eq. 64) <
|As-112
8
7/8 -
--
3(c +ic+17/88
DAs+ 12
(68)
7/8 -
P_
Combining with Eq. 65, we have
36(e + 17/8) |As= 12
(x (1())
7/8
p-- - E
37

---

Published as a conference paper at ICLR 2022
Finally, we derive the bound for the term xx (xx)). Since ||3 -xlloo S s* + 28 and Φ is convex on the restricted space, then
41 (3x) S +o0 32)
I (A())] BallA.11
S é (18- - -1 + -18- -3xl2.11
33c++ 17/8) (3(c+17/8) 1
(by Eq. 68)
S
113" -3xlla.)
(69)
7/8
P- P-
Now only need to bound the term ||3- 118--Bpp -1x1la,1. We can derive its bound following the same steps as we derive Eq. 68 and using the fact that wa (Bx) = O, which will imply that
3 17/8)
A 11
51/7 12
1 1
-/8-0 0
P- 5
p-
Plugging it into Eq. 69, we have
xx(3) - (xx)
3 17/8)
| 11
Se e
7/8 -6 + +51/7)
E
Assuming S 1/2, then
S 29/2| As- 11 p- -
xx(3) (0133-xx(8.) -xx
Lemma G.6 (Optimality when À decreases). Assume Assumption G.I. If
-x ( S ft-1, A = no A--1 with ny E [0.9, 1],
(70)
(71)
|| S 3,
(72)
then
wx. (B) S fr- + 0.2
0.9
33 (3 + 17/8)
4-1 + 0.2 [1(Ae) 112
(3) - Φx. (3xx) <
+ +51/7)
0.9((78 - 1)-)
0.9
P- - E
If E S 1/4, then
1
wx. (B) - 2
10]l(A:)s=18 11
Φx (3) ox, (Bx.) 5
p- -
Proof. Recall the definition of (B).
|| - 3' (1 (VLA-, (3) + 2c-1E") }
(G- B¹)
Wx, (B)
min max |
Let & E 0|| be the subgradient that attains the minimum in wx_, (3). Then
(B - 1-)
Wx (3)
mmxx En
(VI,,,,, (8) X, x)
||3 - B 1
38

---

Published as a conference paper at ICLR 2022
Now consider X 17 Ac-1- By definition,
{ (3 BT)
max E'E gf ||, 3" 12n.1 (VLA, + 2157}
Wx. (3)
min
(3 BT) (3) + xx15)
S max 0e
|| 32111
Note that
VL (B) + X (VLA,-, (3) + X1-1E)
(A, - of + (VQx, (B) -VQx.,,3))
which implies
(8-
wx, (3) S max 9EEl
(VLa, 1(8) + 11
|13 - 111,,111
(B - BTT
+ max 8'En
(A 11-- of
||3 - 11
(i1)
(3- BTT
|| - 1r (VQx, - vQx- (8)
max 3'E0
(ii)
Using the fact that ||3 - 10003111,,0 1,,1,,,1 2 0.91|.3 - B311 term (i) can be bounded as follows.
(i) - 0.9 |3 1111111111 (VLA- Ac-1E) S
(B - B²
0.9 Wx. (3) S 4-1
1
0.9
Using the fact |5y1 < 1 and the fact that (A - -Dejj = -1) [ill S can be bounded as follows.
(1)-))
(0/9 1)
[eel term (ii)
B3 - 331
0.9 -1) Adls
113 - 3 ||
1
1
(ii
1)
1
1.
B 3'1A..11
1 3111
0.9
0.9
Term (iii) is bounded similarly as term (ii). Since (x,(8) 9x, (3)
S |Ag - X31,
we have
d
33-33
d
|B, - 331
(1110 -1 [ull
(iii) <
A Adl S
0.9 1.
j=1 3 3'll,,,1
1 3' A
0.9
1=1
Combining the bounds for (i)-(iii), we have
wx, (3) S 6--1
6t-1 --- 0.2
2
0.9
0.9
The first part of the proof finished. Now we bound the term Φx. - Φxx (3x.). Since ||9
Bxllo I s" + 23 and Φx is convex on the restricted space, then
(B) - Φx. (Bx.)
< (VL (3) + A o T -3xx)
S wA. (B) (B)113 -BxillA.11
f-1 + 0.2
(1.33
1111 + +11/* -3x,11x.)
(73)
0.9
39

---

Published as a conference paper at ICLR 2022
Following the same way derive Eq. 67, obtain that
6-1 17/8
(3 3)) (Ar)gn
11(3 )=) 11(ad)s-..
7/8 c1-1
Therefore,
1/3-8%aa 2,,1 = 11(3 1 -3))) 1lllarigr.11 + 11(3 - 3-)s 1l(ar)s
(74)
3
$
11B - 11-))ss-1(aa)
7/8 ft1
311( )s 2|
$
|3 - 13112
7/8 Et-1
(By Lemma G.5) < (11())) ll2 (4-1 + 17) 11(Ar-1ss
7/8 61-1
p- E
3 ((4-1 + 17/8) [1(A))s-12
(75)
0.9(7/8 - -4-1
P_ -
Using the same arguments for the term -133 - -3x,11,,1 and using the fact that wx, (3x.) S 0 A obtain that
11xx - 33 S 6(0+17/8) I1())ss
(1/7)
7/8 - - p-
Combining this inequality with Eq. 73 and Eq. 75, we have
ex, (B) - ex, (3x.)
3 3 17/8) 0.9(7/8 6c-1 +51/7
6--1 + 0.2
(At))s 11
0.9
p- E
Assuming 6:-1 S 1/4, then
1011 (A))s= 11
Φx. (B) (xx.)
S
p- -
Lemma G.7 (Coercivity of the gradient). [Lemma 3.11 in Bubeck (2014)) Let be a-strongly conver b-smooth and on B C Rd. Thenfor all B, 3 B, one has
b ab 3 B3 +
1 a b -
(V) - 3(B',,3- - 3) 2
40

---

Published as a conference paper at ICLR 2022
H DETAILS OF SECTION 5: EXTENSION TO UNSUPERVISED LEARNING-TO-LEARN SETTING
In addition to the assumptions in the supervised setting, in this unsupervised setting, we assume for each estimation problem, both Ln, (Z1:n, and Lng (Zi:g) satisfy condition (b) and (c) in As- sumption C.I. Similar to the supervised setting, the generalization error of the optimizer 0g can be bounded by
Leen (P(P):0T) S ( || (Zmm) 33
Σ m
1
m
Br
3-
generilization gap: Theorem 4.1
(76)
Br Br(Zin 3r
(77)
supervised training
However, in the unsupervised setting, the minimizer 8% only guarantees that unsupervised training loss function Em= L., ( Br(Z (8)))
is small. It requires further derivations show that the corresponding supervised training loss in Eq. 77 is small, too.
Therefore, in the following, bridge the gap between the supervised training loss and the unsuper- vised training loss. Based on the proof of Theorem D.I, we know that 1,3T(Z 1:my 3= I s. Therefore,
apply the restricted strong convexity of L,g to obtain the following inequality for 3r = Br (Z br), G = (+),,, and = Z for each i =, 1.......... m.
|| 13 <
2
Ting (7, Ting (2, + V Tng (2 (B* (B))
p-
< p-
(Img (7, - -Logg (7, + [ (7, (*) ||2/| (3 - (r) (12)
4 (Teng (7, Tong )) 16
|| 11
ng (7 11
p-
Aggregating this inequality for = 1, m. we can obtain the following inequality that bounds the supervised training loss using the unsupervised loss.
B 07) - 33000
| Wi (2 (1(1)
p
statistical
4 p
Lnn (2n Br (r(z ;0)) - Lng (2 ling (7(1))
1=1
unsupervised training entor
The hand-side of this inequality consists of a statistical eгrоr and the unsupervised training eтror. Finally, to characterize how small the unsupervised training error can be, we can combine the following inequality (by restricted strongly smooth) with the result of Theorem 3.1.
Lnz (Zim2 Br (0 (1)) - Lng (Zim2 3²)
< Lnd (Zim2 Br (Zrmi 0²)) Liz (Z1.nzr 3rm
< || an Z1.n 3" )|12 11 (Zim 0²) 3r112 + Pt 13 0') 3
(78)
bounded by Theurem
bounded by Theorem 3.1
41

---

Published as a conference paper at ICLR 2022
Overall, the generalization error can be bounded by
gen ()))
(=)2 ( - 33 1
m Σ
gr :0))
;0;) 33
generalization Theorem 4.1
4
Σ
m
P+ ( IVghnng (Z g-(0) l2 Br imm: : 07) gr(0) 2
11
p-m m
statistical error
bounded by Theorem 3.1
bounded by Theorem 3.1
16
V Tong ( (3i0))
0 m
statistical error
42

---

Published as a conference paper at ICLR 2022
1 DETAILS OF SYNTHETIC EXPERIMENTS
1.1 A GENTLE REVIEW OF LINEAR REGRESSION AND PRECISION ESTIMATION
1.1.1 SPARSE LINEAR REGRESSION
sparse linear regression model reads
x B
where 8 is a sparse vector and c is Gaussian noise. {101 vI), ... (æ Nn)]. , the goal is to estimate the vector 3 In our method, we use the the least-square error to define the empirical loss function.
Given observations Z
x B 2/
Ln 3) = 2n j=1
1.1.2 SPARSE PRECISION ESTIMATION
The sparse precision matrix estimation problem in Gaussian graphical models assumes the observa- tion of n samples from a distribution (00, Σ). Given the samples, X1m = {æ1,- .x from (0, )) the goal is to estimate the precision matrix O" := ツーー which is the inverse covariance matrix. This precision matrix represents the conditional independency among random variables.
commonly used objective for estimating the precision matrix is the & l1-penalized log determinant divergence:
log de) + (0, En) x||l|11
where E., is the sample covariance matrix. In our method, we the likelihood term as the empiri- cal loss.
Ln (X1ms Q) log det(@) + (9, En)
I.2 DATA PREPARATION
For the sparse linear recovery problem, we follow the setting in Wang et al. (2014). We create the synthetic data by sampling a set of estimation problems {(((1) ( (+))). each problem, the design matrix (+) E RRd contains n = 64 independent realizations of a random vector R with p 256, 1024 in easy difficult setting, respectively. follows zero mean Gaussian distribution with covariance matrix (Σ),) = 0.9 (ixs) + (i=r)) The true parameter vector (1) has sparsity s* || = 16 and its nonzero entries take values uniformly sampled from -2) U [ 2). The support set of each (1) is independently sampled from union support set S, with |S| 128 allow some similarity among the problems. The observation ( is sampled such that ( (0))3=(0 is n-dimensional Gaussian random vector with zero mean and covariance matrix I,, In all the experiments, 2000 such problems are used for training, 200 such problems are used for validation, and 100 such problems are used for test.
In sparse precision matrix estimation problem, we follow the setting in Guillot et al. (2012). We create the synthetic data by sampling the ground truth precision matrix is generated in the following ways: the lower diagonal part (lower triangular parting, exluding diagonal) of true precision matrix θ has sparsity s", that are uniformly selected from a union support with size S. After selecting the nonzero entries, we assign them values uniformly from (-2, - U ()) and let the upper diagonal part has the same value as lower di- agonal part. Finally, a multiple of the identity was added to the resulting matrix so that the smallest eigenvalue was equal to In this way, θ was insured be sparse, positive definite, and well- conditioned. After the precision matrix is generated, we generate the observational samples for each precision matrix, by generating n independent samples of the random vector x ~ Ao (e(+))))
of estimation problems {(5()) (())). In each problem,
The samples are denoted by x(0) E Baaxd Using the samples, we can compute the sample covari- ance matrix (()) - (X0)TxX
43

---

Published as a conference paper at ICLR 2022
In all the experiments, 2000 such problems used for training, 200 such problems used for val- idation, and 100 such problems are used for test. We use (n, s*) = (100, 375, 75), (200, 600, 150) for d = 50, 200, respectively.
1.3 BASELINE IMPLEMENTATION
ALISTA: We follow the implementation in Liu et al. (2019a).
RNN: The RNN is designed following Andrychowiez et al. (2016). Initialize the 30 as O. At every step, we compute the gradient V ((B) w.r.t. to objective as the input to a LSTM with hidden dimension equals to 128. Then we use the output of the LSTM as the increment:
B+1 B +
(79)
We repeat this iteration 20 steps and use B20 final output.
RNN-41: RNN-4 use the same architecture as RNN. The only difference is we add an extra learn- able parameter A for soft thresholding each step:
it+1 3r :
(80)
B++1 = (B.-1)
(81)
where the softthresholding 7)x is elementwise operator maps 77a (æ) = is |x| < A and (2()) sign(z)([<) X).
GLASSO: we use the implementation in the sklearn package.
GGM: We follow the implementation in Belilovsky et al. (2017).
APF: We follow the implementation in Wang et al. (2014). The specific algorithm steps are sum- marized in Algorithm 3.
Algorithm 3: The Approximate Path Following Method
Input: Am 0, copt (Here we assume Eopt < \rgt/ E (0.9,
Initialize 8o < 0, Lo + Lmins Ào = |[ + (go/) log(n ) for t N 1,...N
do
d + 1
\//4
{Be, Le} + Trxxima-Gradienn((p. 6,, B LL-1, R) as in Algorithm
end
AN + Augt
EN Eapt
(ÔN, LN) } t- Pooximal-GraadeettAA.......... IN-1, Rt).
10 return {3:)
Algorithm 4: The Proximal Gradient Method
Input: X; > 6; > 0, E RP, L4 >
Initialize 5-
repeat
+ ++ +1
Linit +- maxfLmmn I//-1/23
L Line-Search(N,, (dr, 3.- Linit) in Algorithm
until Wx. (3t) S c as defined in Equation 82;
3r gk
L2
+ L
return (3,, L.).
44

---

Published as a conference paper at ICLR 2022
Algorithm 5: The Line Search Method
Input: x 0, 0, RR Linit > 0, R > 0
repeat
3 T (B)-1) as defined in Equation 83
if TA I I.g.
(3t) > VLLIA. ( then
end
until Φx (3f) S Le (8t, 1) as defined in Equations 84 and 85;
3t f-1 3 T
return
(3,, Le
|| - 13'l1 (VÊx(3) - )
3')
-XE))
wx min max E'E81I BlEl?
(82)
(TLAA (3--11) = 50
if 13, S L
(83)
sign (3;) (13,1 - \r
if [3 > de/ L
6x Σx(B) \|l|||
(84)
L
FItA 1B L
VL ( (B- 1k-1)
| 3 k--11
3/-1112 Px. (85)
I.4 TRAINING AND EVALUATION
We trained the learning- baased methods minimize the weighted loss. That's is say, for each sparse linear recovery problem, given the sequence outputs (BI,... 3r), ) the loss is computed as:
T
=
T 113 3313
(86)
1=1
where y decreasing from 0.9 to 0.1 during the training process. The procedure similar in the sparse precision matrix estimation problem. We use optimizer Adam (Kingma & Ba, 2014). For sparse linear recovery problem, we use batch size 10, we train 500 epochs with learning rate le- 4 and select the model based on the 12 loss on valid data. For sparse precision matrix estimation problem, we use batch size 40, we train 200 epochs with learning rate le-3 and select the model based Frobenius loss valid data.
For classical algorithms, we select their parameters, À for APF and for GISTA, based on their performance on the validation set. Specifically, we evaluate APF or GISTA with p or À from (0.01, 0.025, 0.1, and use one with the best recovery error in test.
Table 3: Training time for SLR (minutes)
Table 4: Training time for SPE (minutes)
Sizes
d = 256 d = 1024
Sizes
d = 50
d = 100
PLISA
393
462
PLISA
35
39
ALISTA
176
271
GGM
14
RNN
96
99
GISTA
176
116
RNN,
101
106
APF
316
331
APF
214
426
GLASSO
42
57
We report the total training time for learning based methods as well as the parameter tuning time for classical algorithms. From Table 3 and Table 4, that training learning-basse method is
45

---

Published as a conference paper at ICLR 2022
cheap in our experiments, 1) A single forward for PLISA GGM is very fast stated in Table 1. 2) We can easily parallel the computations to handle a batch problems during the training time, as the learning-basee methods do not require line-search.
The evaluation is performed on a server with CPU: Intel(R) (e) Silver 4116 CPU 2.10GHz, GPU: Nvidia GTX 2080TI, Memory 264G, in single thread.
1.5 ABLATION STUDY
dim-256
dm-1024
Table 5: Ablation study of PLISA (p 1024). TPR is the true positive rate of recovering the nonzero en- tries of 3 FPS is the cardinality of false positive entries. Note that the true sparsity level s" 16. Standard deviations over 100 test problems are present in the parantheses.
plisa
30-
pllsa piisa_single
25-
20-
15-
PLISA
PLISA-single
PLISA-61
8 error
1.34 (2.28)
18.25 (6.06)
2.20 (2.76)
TPR
0.99 (0.01)
0.62 (0.19)
0.99 (0.02)
# Beeraioon
Korations
FPS
16.65 (13.60)
51.07 (6.67)
25.11 (13.30)
Figure 6: Ablation study.
We consider two variants of PIISA to perform the ablation study. One is PI.I PI.SAA-singl which employs a single regularization parameter across different entries, i.e., ?) =
A) and d; X² The other is PLISA-L, which does not learn the penalty function but uses the & norm, ie.. Pw (A, 3) = || o BllI- Fig. and Table show the vanilla PLISA performs better than alternatives. Especially, it has much better accuracy than P PLISA-singl.. Therefore, this ablation study has validated the effectiveness of using entry-wise regularization parameters and learning the penalty function.
1.6 REAL-WORLD EXPERIMENTS
We use the following 3 real-world datasets.
(1) Gene a single-cell gene expression dataset that contains expression levels of 45 transcription factors measured at different time-points. We follow Ollier & Viallon (2017) to pick the transcription factor, FGR2, as the response variable and the other 44 factors as the covariates. this dataset, each time-point is considered as estimation problem. In each estimation problem, the goal is learning the regression weights 3 on the 44 factors to predict the expression level of the target transcription factor, EGR2. Therefore, in this problem, p 44. This dataset contains the gene expression data for 120 single cells at 8 different time points. For each time point, we randomly split the 120 samples into 6 sets, that each set contains 20 samples. By doing this, we construct 48 estimation problems each of which contains 20 samples. 10 samples are used for recovering the parameters 3 and the other 10 samples are used for evaluate it by computing the least-square error. We use 36 problems for training, problems for validation, and 6 problems for testing.
(2) Parkinsons- a disease dataset that contains symptom scores Parkinson for different patients. Each patient is considered as an estimation problem. In each estimation problem, the goal is learning the regression weights 3 on 19 bio-medical features to predict the symptom score. This dataset contains 42 patients, so there are 42 estimation problems in total. Each patient is examined at different time-point and each time sample is generated. For each patient we randomly select 100 samples, so that eventually our dataset contains 42 estimation problems each of which contains 100 samples. 50 are used for recovering the parameter f and 50 are used for evaluation. We use 28 problems for training, 7 problems for validation, and 7 problems for testing.
(3) School an examination score dataset of students from 139 secondary schools in London. Each school is considered as estimation problem. In each estimation problem, the goal is learning the regression weights 3 on 28 23-dimensional school and student features to present the exam scores for all students. We use the dataset from Malsar package (Zhou et al., 2011). For each school, randomly select 40 students as the samples. Since some schools contain less than 40 students, we finally obtain 125 estimation problems (schools) each of wich contains 40 samples. 20 are used for
46

---

Published as a conference paper at ICLR 2022
recovering the parameter (3 and 20 are used for evaluation. We use 100 problems for training, 10 problems for validation, and 15 problems for testing.
On each dataset, train each learning- based algorithm for 200 epochs using Adam with learning rata 1c-3. The batch size is set to be
47


Reviews:
[{"review_id": "Rrur3tQSsgl", "reviewer": "Reviewer_ZD71", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Strengths:\n\n+ The idea of unrolling path-following algorithms for learning to optimize hyper-parameters (such as learning rate, regularization modulus and mixture weights of regularization components) is somewhat novel as far as I can see.\n\n+ The analysis is theoretically sound and the writing style is clear and clean. \n\n2. Weaknesses\n\n- My main concern is about the relevance and strength of theory. There are two types of guarantees established in this work on parameter estimation error and generalization gap bounds respectively. As shown in Theorem 3.1, the sparsity recovery analysis basically reveals that there exists a set of hyper-parameters under which the proposed PLISA algorithm is able to efficiently and accurately recover the underlying true model. This result seems not surprising at all as PLISA by definition naturally mimics an existing iterative sparse recovery method with similar guarantees. More importantly, IMO the current convergence/estimation analysis has little to with the optimization of hyper-parameters $\\theta$ which is of central interest of deep unrolling but unfortunately totally ignored in the present study. In Theorem 3.1, the existence of the desired set of parameters is lack of transparency in the sense that it relies on another set of conditions as defined in Definition C.1 which are fairly stringent especially the condition (iii).  \n\n- Continuing the above comment, the generalization analysis is also of limited interest and novelty. First of all, since the generalization is about the hyper-parameters involved in meta-optimization, most existing uniform convergence analysis techniques in classic learning theory are expected to work for bounding the generalization gap. Is there any particular reason to adopt the framework of Bartlett and Mendelson (2002) for generalization analysis? The technical part is relatively straightforward; it is not clear what’s new in this section of analysis, if any.\n\n- It is unclear how to optimize the meta-parameters contained in Algorithms 1, probably via backpropagation? More implementation detail about meta-parameter update are desirable in addition to the iterative proximal gradient steps for cell objectives.\n\n- Last but not least, I am seriously doubting the practical usage of the proposed approach to real-data sparse learning problems because it is only designed for well-defined sparsity models. An immediate challenge here is that the ground-truth sparsity models are required to supervise the meta-learning, which however are typically unavailable over the training optimization tasks! \n\n3. Minor comments:\n\n- Equation (6): the general case of varying $n_i$ seems not investigated throughout. \n\n- The reason of introducing $\\varepsilon>0$ in Theorem 3.1 is not clear. \n\n- Typos: P3, beside Algorithm 1: minimize  minimizes; and others. \n\n", "summary_of_the_paper": "The paper presents a deep unrolling method that unrolls the path-following algorithm of Wang et al. (2014) for learning to regularized sparsity estimation. Theoretical guarantees on sparsity recovery and generalization performances are provided. A simulation study is carried out to verify the theory and effectiveness of the proposed algorithm. ", "summary_of_the_review": "The algorithm is somewhat interesting but the theory is of limited relevance and novelty. The implementation details and practical usage of algorithm are largely unclear in the current stage. \n\n=== Post discussion update ===\n\nAfter reading other reviews and the author response, I would upgrade my rating to 5: marginally below the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "O_pdi8CxT2P", "reviewer": "Reviewer_uCY5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My first concern is that there is not enough interest or applications for learning-based compressed sensing. It is not a good assumption that there exists a supervised dataset of sparse recovery instances available for tuning the parameters of the proposed algorithm. The fact that all experiments in this paper are based on synthetic datasets and no real datasets are used in this paper confirms my concern. \n\nIn terms of presentation, I think it would help if the authors discussed the path-following algorithm a bit since their result is based on this algorithm.\n\nMoreover, the algorithm is recursive and each recursion of the algorithm involves running an instance of the path-following algorithm. So even after fully training the parameters, just evaluating the algorithm on an input instance is several times slower than the original path-following algorithm. The complexity is even much worse during the training phase because one needs to evaluate the whole algorithm multiple times and compute its derivatives with respect to the learnable parameters. The paper does not analyze the runtime complexity, unfortunately.\n\nOn page 5, after assumption 3.1, it is stated that condition b is weaker than RIP. It seems to me that when the loss function is least squares, then condition b is exactly the RIP.\n\nTheorem 3.1 is somehow telling that the optimal parameters give a small error but it does not tell you how easy it is to find the optimal parameters. In particular, the parameters need to be found by solving some optimization problem but it is not even clear if this optimization problem is convex or not. If the problem is non-convex, you would only be able to find a local minimum and Theorem 3.1 would become useless. \nFurthermore, \\kappa_n in Theorem 3.1 is defined ambiguously. It needs to be defined more specifically.\n\n\n-------------------------------- Score after revision -----------------------\n\nThe revised version looks better now and seems to address my concerns. Therefore, I raise my score to 6.\n\n", "summary_of_the_paper": "The paper proposes a learning-based sparse regression or compressed sensing algorithm. The paper assumes that a supervised dataset of sparse recovery instances is available and uses the dataset to fine-tune the hyperparameters of a sparse recovery algorithm known as the path-following algorithm. The proposed algorithm has a recursive structure where at each recursion it needs to solve an instance of the path-following algorithm with different hyperparameters.", "summary_of_the_review": "I think there is not enough interest or applications for learning-based compressed sensing. The fact that all experiments in this paper are based on synthetic datasets and no real datasets are used in this paper confirms my concern. \n\n\nMoreover, the algorithm is recursive and each recursion of the algorithm involves running an instance of the path-following algorithm. So even after fully training the parameters, just evaluating the algorithm on an input instance is several times slower than the original path-following algorithm. The complexity is even much worse during the training phase because one needs to evaluate the whole algorithm multiple times and compute its derivatives with respect to the learnable parameters. The paper does not analyze the runtime complexity, unfortunately.\n\n\nTheorem 3.1 is somehow telling that the optimal parameters give a small error but it does not tell you how easy it is to find the optimal parameters. In particular, the parameters need to be found by solving some optimization problem but it is not even clear if this optimization problem is convex or not. If the problem is non-convex, you would only be able to find a local minimum and Theorem 3.1 would become useless. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BTTHSZ3Rh5N", "reviewer": "Reviewer_AZru", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "update\n-----\nI maintain my rating after reading the author(s)' response.\n\nThe approach from this paper is promising and mostly novel. The paper is generally well written. Overall I recommend accept. I have a few concerns regarding the theoretical claim and experiment.\n\nStrong points \n-----\n1. The paper tackles a classic and important problem (i.e., compressed sensing), and the learning-to-learn approach should be a good step in this direction.\n2. The framework from the paper appears flexible enough to handle other sparse estimation problems. So the work may lead to future impact. \n3. The author(s) gives some theoretical justification of their procedures. \n\nConcerns\n-----\n1. In abstract and later in the intro, the author(s) claims that \"our analysis makes novel connections between the generalization ability and algorithmic properties such as stability and convergence\". The author(s) should be careful about the scope of this claim. The connection between algorithmic stability and generalization is textbook classic. The paper applies this framework to the specific setting of learning-based sparse recovery. \n\n2. Theorem 3.1 appears somewhat weak. The claim is that \"there exists a set of parameters θ .... such that the estimation error is small\". However, these parameters are also learned. Is there any (theoretical) justification why the algorithm would find such good parameters θ?\n\n3. In Section 4 on generalization, the author(s) should clarify the distributional assumptions here. Are we assuming random iid design? Is $\\beta^*$ also distributional? (Note that Assumption 3.1 is a set of deterministic conditions.)\n\n4. The paper does not compare PLISA with other classic algorithms in the sparse recovery literature, for example, convex relaxation or linear sketching methods. It would to nice if the experiments are more comprehensive. \n\nOther minor issues\n-----\n1. There has been a few works on unrolling or differentiable learning of classic algorithms. For example, https://arxiv.org/abs/1910.13984 and https://arxiv.org/abs/1903.08850. This is very closely related to the nature of this work. The authors should make a reference.\n2. I am not familiar Wang, et al (2014). It would be helpful if the author(s) could give a quick rundown of the algorithm therein, perhaps in the appendix. What are the main features of Wang, et al (2014) that PLISA borrows?  ", "summary_of_the_paper": "The paper proposes a learning-to-learn algorithm for the classic problem of compressed sensing. The algorithm is based on a deep unrolling of a non-convex optimization procedure from a prior work (Wang et al, 2014) in the literature. The paper contains some theory (for capacity and generalization) and experiments, establishing the efficacy of the algorithm. ", "summary_of_the_review": "The paper aims at an important problem and provides a novel solution. The theory and experiment are generally solid. I believe the work could have future impact.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "4ksb5LJ2une", "reviewer": "Reviewer_7xPS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is generally well-written. The idea of the algorithm, its precise details, and the assumptions and claims of the theoretical analysis are all presented clearly and in detail. The approach of the algorithm makes sense and seems potentially promising, and targets an important set of problems.\n\nThe weakest point of the paper is the experimental section. The experiments are restricted to synthetic data of a limited scale, and to perhaps the most basic sparse recovery setting (linear regression, while the introduction makes the point that the method is more broadly applicable). While I appreciate the theoretical analysis and its validation on synthetic data, the utility of learning-based algorithms hinges to a significant extent on whether they can be substantiated on real data, where the correspondence between the training and test data is not as structured and clear as in the synthetic case. At present, it is hard to say from the paper whether the proposed method is plausibly useful in practice.\n\nThere seem to be parts of related literature that are not mentioned. I am not sure if they are directly related, and perhaps the authors could comment on it in the response. These include some additional learning-based algorithms for latent parameter recovery (e.g., [a,b], though they move away from sparsity), and generalization bounds for learning-based algorithms [c,d].\n\n[a] Bora, A., Jalal, A., Price, E. and Dimakis, A.G., Compressed sensing using generative models, ICML 2017\n[b] Wu, S., Dimakis, A., Sanghavi, S., Yu, F., Holtmann-Rice, D., Storcheus, D., Rostamizadeh, A. and Kumar, S., Learning a compressed sensing measurement matrix via gradient unrolling, ICML 2019\n[c] Gupta, R. and Roughgarden, T., A PAC approach to application-specific algorithm selection, SICOMP 2017\n[d] Balcan, M.F., DeBlasio, D., Dick, T., Kingsford, C., Sandholm, T. and Vitercik, E., How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design, STOC 2021\n\n\nPost-rebuttal update: The authors' response and revisions of the paper answered my main concerns, primarily the lack of empirical evaluation on real data, which they have now added. As a result, I have revised my numerical assessment of the empirical merit of the paper, and have upgraded my overall score. Pending some concerns raised by other reviews, which would be resolved in the internal discussion phase, from my point of view the paper can be accepted. ", "summary_of_the_paper": "The paper suggests a learning-based algorithm for sparse recovery, where the goal is to recover a latent sparse parameter vector from observations (say, in the basic setting of sparse linear regression, the observations are noisy linear measurements). The algorithm is based on \"unrolling\" an existing non-learned iterative algorithm, which means fixing some number of iterations and learning some of the algorithm's internal parameters by optimization on an existing training dataset of related problems and their known solutions. The paper theoretically studies the capacity and generalization properties of the proposed algorithm, and presents some experimental results on synthetic data.", "summary_of_the_review": "This is a well-written paper that presents a plausible approach to a meaningful problem, but falls short in empirical validation.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear Authors,

The paper was received nicely and discussed during the rebuttal period.
There is consensus among the reviewers that the paper should be accepted:

-  This paper does contribute solidly to a timely topic of theoretical understanding of sparisty recovery with deep unroling. 
-  The original version had very limited experiments and only synthetic ones, which raised concerns about whether the setting is motivated and whether the algorithm works on actual real data. The revision fixed that to an extent with some experiments on real data.

Yet, there are still some concerns that we suggest to be tackled for the final version:
- The capacity analysis is carried out inside a strongly convex regime while the algorithm is advocated for nonconvex sparsity recovery (see, e.g., the Discussion at the end of Section 2.1 );
- The analysis is relatively loosely connected to the adopted fist-order optimization procedure;
- While the depth of network plays a role in the upper bound of Equation (15), its real impact on generalization gap looks quite limited.

The above are just suggestions to be looked more carefully, but there are not necessary. 

The current consensus is that the paper deserves publication.

Best
AC
Decision: Accept (Poster)