Universal Safeguarded Learned Convex Optimization with Guaranteed Convergence
Authors: Howard Heaton
Xiaohan Chen
Zhangyang Wang
Wotao Yin
Venue:  (2020)
Keywords: L2O
learn to optimize
fixed point
machine learning
neural network
ADMM
LADMM
ALISTA
D-LADMM

Abstract: Many applications require quickly and repeatedly  solving a certain type of optimization problem, each time with new (but similar) data. However, state of the art general-purpose optimization methods may converge too slowly for real-time use. This shortcoming is addressed by  “learning to optimize” (L2O) schemes, which construct   neural networks from parameterized forms of the update  operations of general-purpose methods. Inferences by each network form solution estimates, and networks are trained to optimize these estimates for a particular distribution of data. This results in task-specific algorithms (e.g., LISTA, ALISTA, and D-LADMM) that can converge order(s) of magnitude faster than general-purpose counterparts.  We provide the first general L2O convergence theory by wrapping all L2O schemes for convex optimization within a single framework. Existing L2O schemes form special cases, and we give a practical guide for applying our L2O framework to other problems. Using safeguarding, our theory proves, as the number of network layers increases, the distance between inferences and the solution set goes to zero, i.e., each cluster point is a solution. Our numerical examples demonstrate the efficacy of our approach for both existing and new L2O methods. 

Under review as a conference paper at ICLR 2020
SAFEGUARDED LEARNED CONVEX OPTIMIZATION WITH GUARANTEED CONVERGENCE
Anonymous authors Paper under double-blind review
ABSTRACT
Many applications require quickly and repeatedly solving certain type of opti- mization problem, each time with new (but similar) data. However, state-of-the- general-purpose optimization methods may converge too slowly for real-time use. This shortcoming is addressed by learning to optimize (L20) schemes, which construct neural networks from parameterized forms of the update operations of general-purpose methods. Inferences by each network form solution estimates, and networks are trained optimize these estimates for a particular distribution of data. This results in task-specific algorithms (e.g.. LISTA, ALISTA, and D- LADMM) that can converge order(s) of magnitude faster than general-purpose counterparts. We provide the first general I.20 convergence theory by wrapping all L20 schemes for convex optimization within a single framework. Existing L20 schemes form special cases, and we give a practical guide for applying L20 framework to other problems. Using safeguarding, our theory proves, as the number of network layers increases, the distance between inferences and the solu- tion set goes to zero, i.e., each cluster point is a solution. Our numerical examples demonstrate the efficacy of our approach for both existing and new L20 methods.
INTRODUCTION
Solving scientific computing problems often requires application of efficient and scalable optimiza- tion algorithms. Despite the ever improving rates of convergence of state-of-the-ard general purpose algorithms, their ability apply to real-time applications is still limited due to the relatively large number of iterations that must be computed. To circumvent this shortcoming, a growing num- ber of researchers use machine learning to develop task-specific algorithms from general-purpose algorithms. For example, inspired by the iterative shrinkage thresholding algorithm (ISTA) for solv- ing the LASSO problem, sparse coding problem, Gregor & LeCun (2010) proposed to learn the weights in the matrices of the ISTA updates that worked best for a given data set, rather than leave these parameters fixed. They then truncated the method K iterations, making their Learned ISTA (LISTA) algorithm form a K K-layer feed-forward neural network. Empirically, their examples showed roughly a 20-fold reduction Several related works followed, also demonstrating numerical success (discussed below). While classic optimization results often provide worst-case convergence rates, limited theory exists per- taining such instances of data drawn from common distribution (c.g.. data supported a low- dimensional manifold). As a step toward providing such theory, this work addresses the question:
computational cost compared the traditional algorithms.
Does there exist universal method that encompasses all L20 algorithms and generates iterates that approach the solution set with guarantees?
We provide an affirmative answer to this question by prescribing and proving properties of neural networks generated within our L.20 framework. Convergence is established by including any choice among several practical safeguarding procedures, including nonmonotone options. Nonmonotone safeguarding enables sequences to traverse portions of the underlying space where the objective function value may increase for a few successive iterations as long as, on average, the sequence approaches the solution set. Although counterintuitive, this ability may lead to faster convergence. Furthermore, we provide practical guide in our discussion for how practitioners may use our frame- work to create and apply 1.20 schemes to their own problems.

---

Under review as a conference paper at ICLR 2020
The theoretical portion of this work is presented in the context of fixed point theory. This is done to be sufficiently general and provide the desired convergence result for the wide class of optimization methods that can be expressed as special cases of the Krasnosel'sker skiis-iimmaaan Mann (KM) method. For concreteness and ease of application, we then provide the special-case results to several well-known methods (e.g., proximal-gradient, Mouglas-Rachfond splitting, and ADMM).
Related Works.
Learning to learn methods date back decades (e.g., see (Thrun & Pratt, 1998) for survey of earlier works and references). A seminal L.20 work in the context of sparse coding was by Gregor & LeCun (2010). Numerous follow-up papers also demonstrated empirical success at constructing rapid regressors approximating iterative sparse solvers, compression, to encoding, combining sparse coding with clustering models, nonnegative matrix factorization, compressive sensing MRI, and other applications (Sprechmann et al., 2015; Wang et al., 201 6a;b;e;d; Hershey et al., 2014; Yang et al., 2016). A nice summary of unfolded optimization procedures for sparse recovery is given by Ablin et al. (2019) in Table A.I. However, the majority of L20 works pertain to sparse coding and provide limited theoretical results. Some works have interpreted LISTA in various ways to provide proofs of different convergence properties (Giryes et al., 2018; Moreau & Bruna, 2017). Others have investigated structures related to LISTA (Xin et al., 2016; Blumensath & Davies, 2009; Borgerding et al., 2017; Metzler et al., 2017), providing varying results dependent upon the assumptions made. Chen et al. (2018) 8) introduced necessary conditions for the LISTA weight structure to asymptotically achieve a linear convergence rate. This was followed by Liu al. (2019a), which proved linear convergence of their ALISTA method for the LASSO problem and provided a result stating that, with high probability, the convergence rate of LISTA is at most linear. The mentioned results are useful, yet can require intricate assumptions and proofs specific to the relevant sparse coding problems.
L20 works have also taken other approaches. For example, the paper by Li & Malik (2016) used reinforcement learning with an objective function f and a stochastic policy I' that encodes the updates, which takes existing optimization algorithms as special cases. Our work related to theirs (ef. Method below and Algorithm 1 in that paper), with the distinction that we include safeguarding and work in the fixed point setting. The idea of Andrychowicz et al. (2016) to use long short term memory (LSTM) units in recurrent neural networks (RNNs). Additional learning approaches have been applied in the discrete setting (Dai et al., 2018; Li et al., 2018; Bengio et al., 2018). Balcan et al. (2019) reveal how many samples are needed for the average algorithm performance the training set to generalize over the entire distribution. This is practical for choosing training data and may be used for training 1.20 networks within our framework.
Our Contribution. This is the first work to merge ideas from machine learning, safeguarded opti- mization, and fixed point theory into general framework for incorporating data-driven updates into iterative convex optimization algorithms. In particular, given a collection of data and an update op- erator from an established method (e.g., ADMM or proximal gradient) for solving an optimization problem, we present procedures for creating a neural network that can be used to quickly infer solu- tion estimates. The first novelty of this framework is the ability to incorporate several safeguarding procedures in a general setting. The second is that we present a procedure for utilizing machine learning methods to incorporate knowledge from particular data sets. However, our most significant contribution to the L22 literature is to combine these results into a single, general framework for use by practitioners on any convex optimization problem.
Outline. We first provide a brief overview of the fixed point setting of this work in Section 2. Then we present the SKM method and convergence results in Section 3. The incorporation of the SKM method into a neural network and subsequent training approach is presented in Section 4. This is followed in Section 5 by numerical examples, discussion in Section 6, and conclusions in Section 7.
2 FIXED POINT METHODS
Let H be a finite dimensional Hilbert space (e.g., the Fuclidean space TR'") with inner product (: and norm || -I. Denote the set of fixed points of each operator T' H - H by Fix(T) := {i E H Tr = x.. In this work, for an operator I' with a nonempty fixed point set (i.c., Fix(T') # 0), the primary problem considered is the fixed point problem:
Find x² E Fix
2

---

Under review as a conference paper at ICLR 2020
Convex minimization problems, both constrained and unconstrained, may be equivalently rewritten as the problem (1) for an appropriate mapping T. The method chosen for solving the minimization problem determines the operator T in (1) (c.g., see Table below for examples). We focus on the fixed point formulation to provide a general approach, given T, for creating a sequence that converges solution of (1) and, thus, also of the corresponding optimization problem. problem..
The following definitions will be used the sequel. A mapping T H - H is nonexpansive if TTr Tyll S || - -vll. for all T, E H.
(2)
An operator T H - H is a-averaged if E (0, 1) and there is a nonexpansive operator Q H + H. such that T (1 a a)Id + aQ, where Id the identity operator. If the constant is not important, then T may for brevity be called averaged. We also denote the distance between a point E and a set C by
dc(x) = inf vll EE
Two operators frequently used in optimization are constructed from monotone relations. Letting > 0 and f: H + IR be a function, the resolvent of the (possibly) multi-valued subgradient 0 is
Joas == (Id + adf)-1
(4)
and the reflected resolvent of 0f is
Raof == Whaf Id.
(5)
If f is closed, convex, and proper, then the resolvent is precisely the proximal operator, i.e..
Jass = prox (x) == arg min (=))) + =11=== x||².
(6)
SEH
From these definitions, it can be shown that Rass is nonexpansive and Jaos is averaged. Results above may all be found in Bauschke & Combettes (2017) (e.g., see Prop. 4.4, Thm. 20.25, Example 23.3, and Prop. 23.8). See Table for examples of these operators in optimization methods.
A classic theorem states that sequences generated by successively applying an averaged operator converges fixed point. This method comes from Krasnosel skii (1955) and Mann (1953), which yielded adoption of the name Krasnosel' sirposellssii-Maaaa sski-MMann (KM) method. This result is stated below and can be found with various forms and proof' in many works (c.g.. see (Bauschke & Combettes, 2017, Thm. 5.)4). (Byrne, 2008, Thm. 5.2), (Cegielski, 2012, Thm. 3.5.4), and (Reich, 1979, Thm. 2)).
Theorem 2.1. If an averaged operator T H. + H. has nonempty fixed point set and a sequence LeThen with arbitrary x² E H. satisfies the update relation
x+1 T(**), for all le E.
then there is x² E Fix((T) such that JREN converges to x", i.e., x + x².
There are pathological cases where the result fails for operators that are only nonexpansive (e.g., when x² o convex combination of nonexpansive operator with the identity is averaged.
and either T = Ild or is rotation). However, this is easily remedied since any
3 SAFEGUARDED KM METHOD
This section generalizes the classic KM iteration in (7). We accomplish this by defining an envelope of operators .:). For parameter Ç chosen from an appropriate set, we let Tra0(;; {) define an operator on H. Changing may define a new operator with different properties. We do not impose restrictions on T220(:: <) other than it be well-defined, meaning T12o <) may fail to be averaged and/or fail to have a fixed point. This is illustrated by the following two examples.
Example 3.1. Let Q: : H > H be nonexpansive. Then define Ti2o H x + R by
Tr2o(2; () = (1 <)x + <Q(x).
For Ç E (0, 1). the operator T-20 () defined in (8) is S-veeraged. Although using < > 1 may result in an operator that fails to be averaged, this can be useful in accelerating the convergence of method (c.g., see (Giselsson et al., 2016)).
3

---

Under review as a conference paper at ICLR 2020
Table 1: Below are the averaged operators for well-known algorithms. We assume 0 and, when a is multiplied by gradient, we also assume < 2/L, with L the Lipschitz constant for the gradient. The dual of function denoted by a superscript * and f2 {(x, 2) Ar+ B2 b). The block matrix M is M (a Id, A"; -A, B Id).. IId). In each case, L is the associated Lagrangian.
(I,
Problem
Method
Averaged Operator
min f())
Gradient Descent
Id aVS
min f(x)
Proximal Point
prox
min(g(x) a с)
Projected Gradient
proje (Id [VVg)
min + g(x)
Proximal Gradient
prox a (Id - aVg)
min + g(x)
Peaceman Peaceman-Rachford
Rasr Roog
f(x) + g(x))
Douglas-Rachtin
(Id Raas Radg)
((x) + g(=)
ADMM
(Id + RA
min((x) s.t. Ar
Uzawa
I (AV - bb
Proximal Method of Multipliers
minf(x) s.t. Ax
Jadc
minf(x) + g(Ax)
PDHG
Method 1 Safeguarded Krasnosel' Mki--Mann (SKM)
1: Choose x¹ H and (0, 1)
2: for k = 1,2.... do
3: Choose parameter t*
4: Choose H* E 20)
y = T120 : c*)
([**) S (1 8) then
7: x+t y²
8: else
9: h+1 T(a*)
10: end if
11: end for
Example 3.2. Let f -> be closed, convex and proper, and define Tızo 00)
R by
TI2o(1; ç) = (x).
(9)
For fixed Ç oo). the operator T:20(:3 () is averaged.
A
The practicality of T:20 is discussed and demonstrated in Sections 4 and 5, respectively. In the remainder of this work, each operator
7 + HL is assumed to be averaged and we set == Id-T. Our proposed method below is called the Safeguarded Krasnosel's Maasnosel'skii-Maann skii-Mann (SKM) Method. Explanation the SKM Method is as follows. In Line 1, the initial iterate and parameter are initialized. common choice for the initial iterate is xt 0. The for loop Lines 2 to 11
4

---

Under review as a conference paper at ICLR 2020
Table 2: Choices for μı updates that ensure Assumption 3 holds. Here E (0, 1) and, for fixed
m E N, Eg is the set of the most recent min(m, k) indices for which the inequality in Line 6 holds.
NAME
UPDATE FORMULA
(1 (1-a)
a)pu
Line holds,
Geometric Sequence
pk+1
Pik otherwise.
GS(a)
Decrease μa by geometric factor whenever Line 6 holds.
m& +
if Line holds,
mg+1
mg
otherwise.
1
Arithmetic Average
if Line holds, otherwise. Use my to count how many times Line 6 holds and μu is the average of the residuals among those times.
(I[((*++1|| + mgMk)
pi41
my +1
AA
Exponential Moving Average
+1 ())--)
if Line 6 holds, otherwise.
P4+1
P4
EMA(a)
Average μa with the latest residual whenever Line holds.
Recent Term
{
||S(**)|
if Line 6 holds,
Mk+1 =
14 otherwise.
RT
Take μn to be most recent residual for
for which Line 6 holds.
max [|S(x()]
Recent Max RM(m)
Take to be max of the most recent residuals for which Line 6 holds.
generates each update x k+1 in the sequence {x* FREN. The choice of parameter Ç* in Line may be any value that results in well-defined operator T-20(-; (*) in Line 5. The choice of μı in Line defines the safeguarding procedure that is used to ensure convergence. Safeguarding is implemented through a descent condition inequality in Line 6. When the inequality in Line 6 holds, Ti20 (2*; (*) is used to update x² via Line 7. Otherwise, KM update is used to update I² via Line 9. Notice also the iteration indexed parameters may all chosen dynamically (rather than precomputed).
Below are several standard assumptions used to prove our convergence result in Theorem 3.1. Assumption The operator T is nonexpansive with nonempty fixed point set.
The following assumption ensures boundedness of sequences generated by the SKM method.
Assumption 2. The operator S is coercive, i.c.,
lim |S() | +oc
(10)
Remark 3.1. Assumption 2 does not hold, in general, for nonexpansive operators. For example, T' the gradient operator (Id VVf) f) for some a and a constant function, then S(x) for all x E H. However, a minor perturbation to the f enables Assumption 2 to hold. In this example, if one fixes small > 0 and sets f(x) == f(x) + |||=|| then the associated Š satisfies []Š(=)]] & || This idea generalizes and, since this works for arbitrarily small in practice it may be reasonable to assume Assumption 2 holds when applying the SKM Method,
5

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Learned SKM (LSKM)
1: Stage 1: Catpliizaatio/rrriiinn
2: Choose envelope T -) and network structure C, parameterized by = ((*)
3: Choose training loss function da
4: Choose 'optimal' parameter
- E arg min RAND ()( BEC
assuming 14 op at each layer k
5: Choose 8 and safeguarding scheme for }
)
6: Define the neural network M = MM 6,p2
7: Stage 2: Inference.
8: For input return M(d)
the inequality Line satisfied infinitely many times, then the sequence {Ek heN converges to zero.
Assumption 3.
Remark 3.2. Assumption 3 may be enforced by using various choices that are dependent upon combinations of the previous residuals. This is illustrated by Table 2 and Corollary 3.1 below.
Our main convergence result is Theorem 3.1 below (proven in the Appendix).
Theorem 3.1. If JeN is sequence generated by the SKM method and Assumptions I to 3 hold, then
lim deweCr) (x*) =0. k
(11)
And, if {x*] hees contains single cluster point, then JEEN converges to a point xt Fix((T).
We propose several methods for choosing the sequence {uRJKEN in Table 2. These methods adaptive in the sense that each update to an iterate μa depends upon the current iterate x and (possibly) previous iterates. These update schemes enable each μa to trail the value of the residual norm [((x))) []. This implies there may exist j E N for which
|S((')] < ||S()**))|| ||S (Tr2o(#²; (²) (1-8)ug
(12)
Such leniency desirable since it is possible that, even though the residual norms converge to zero, constructing a sequence of iterates along the quickest route to the solution set requires traversing portions of the underlying space where the residual norms increase for a few successive iterations. The safeguarding schemes in Table 2 are justified by the Corollary below (proven in the Appendix).
Corollary 3.1. If (T"Tke
IkeN is sequence generated by the SKM method and Assumptions 1 and hold and {μz keN is generated using a scheme outlined in Table then Assumption 3 holds and, by Theorem 3.1, the limit (33) holds.
A NEURAL NETWORK VIEW
The SKM method may be truncated and executed inferences with a neural network. The input into the network is the data d, often in vector form. Each layer of the network consists of an iterate x² with the output from the final layer K providing the inference estimate z that approximates solution to (1). The feedforward operations between layers are formed by the operator T120( c*) if the descent condition in Line 6 of the SKM method holds and T otherwise. We encode all the network parameters with θ == (= The set C, over which is minimized, may be chosen with great flexibility, the only restriction being that C is a subset of the K K-tupe set where each Ç* is such that ( (*) is well-defined. Since C' determines the form of possible O refer to it in Algorithm 2 as the network structure. For each application of the algorithm, the operators and S change, depending upon the particular data d. For example, the data d could correspond to the measurement vector d = Ar when attempting to recover x. Thus, to make explicit this dependence of each operator the data d, we henceforth incorporate subscript to write Ta and S4-

---

Under review as a conference paper at ICLR 2020
The "'pptimal" choice of parameters è depends upon the particular application. Suppose each d is drawn from a common distribution D. Then a choice of "optimal" parameters @ may be identified as those for which the expected value of (a(x*) is minimized, where Oa H. IR is appropriate cost function. In mathematical terms, this is expressed by stating O* forms a solution to the problem
min EARD ( (6, (0.d)).
(13)
where the expectation Edd-D is taken over all d E D and we emphasize the dependence of æ on O and d by writing æx x (O,d). In practice, the problem (13) approximately solved by using a sample set of data {d" jn=1 taken from the distribution D and minimizing an empirical loss function. We summarize the procedure for creating, training, and performing inferences with such L20 networks in Algorithm 2. There .M denotes the neural network, which is dependent upon O, 6, and the choice of safeguarding used to construct each μi (see Line 6).
[d")}==
Remark 4.1. Different learning problems than (13) may be used (e.g., the min-max problem used by adversarial networks (Goodfellow et al., 2014)).
Remark 4.2. Two particular choices of the set C are of interest. The first case is when each param- eter 5 may be chosen independently, i.e., the network weights vary by layer. This is used in numerical examples below. The second case is when C' is restricted such that each of its entries ç This latter
are identical, i.e., the parameters across all layers are fixed so that Ç² Ç² case corresponds to the structure of recurrent neural networks (RNNs).
NUMERICAL EXAMPLES
This section presents example L20 schemes applied within the LSKM framework.' We numeri- cally investigate (i) the convergence rate of LSKM relative to corresponding KM iterations, (ii) the efficacy of safeguarding procedures when inferences are performed on data for which L20 fails in- termittently, and (iii) the convergence of LSKKM schemes even when the application of Tı20 is not justified theoretically. We first use T220 from ALISTA (Liu et al., 2019a) on the LASSO Problem. Then we apply the differentiable linearized ADMM of Xie et al. (2019) to similar problem. We also implement a new L20 scheme for solving the nonnegative least squares (NNLS) problem.
In all experiments, we take μi = ||S((*))|2 Implementations of the LSKM Algorithm are abbre- viated by the scheme in Table 2, c.g., we write GS(aa) to mean the Geometric Sequence method with parameter a is used to construct {uv JeN. As in Algorithm 2, training is completed without safeguarding. For notational compactness, in each example we let fā the optimal value of fa(x) among all possible æ. Note each objective funetion is dependent upon the data d, which implies it is only meaningful to compare curves below that are within the same plot (and not appropriate to compare curves in separate plots). We illustrate the performance in plots using an approximation of the expected objective error
EA-D [fa(**) [a]
(14)
using 1,000 test samples, The optimal value få for each sample is estimated by running the KM method for 15,000 iterations.
5.1 ALISTA FOR LASSO
Here we consider the popular LASSO problem for sparse coding. Consider unknown sparse vector x² E R" and a matrix A E Rm**, which is called the dictionary. Then assume we have access to noisy linear measurements d R", where E Rm is additive Gaussian white noise and
A= +
(15)
Even for underdetermined systems, when xt is sufficiently sparse and e oz) is an appropriately chosen regularization parameter, x² can often be recovered faithfully by solving the LASSO problem
min fa(x) = 2 Ax - d11 + |||2||1, Rn
(16)
'lll of the codes for this work be found Github here: (link will be added after review process).

---

Under review as a conference paper at ICLR 2020
where || 1l2 and || 1111 are the Eg and & norms, respectively. A classic method for solving (16) is the iterative shrinkage thresholding algorithm (ISTA) (c.g,, see (Daubechies et al., 2004)), a special case of the proximal-gradient method in Table 1. Given x² E ER", this method iteratively computes
1- (* 1 - -d). dd)) for all & E N,
x++1 == -(=") MT/L.
(17)
where L - ||A and ne is the soft-thresholding function defined by component operations:
no (3) := sgn(1)) max (0, |ar] - 0)-
(18)
Implementation details for the LASSO problem may be found in the Appendix.
We applied the LSKM Algorithm to the LASSO problem above by using T defined in (17) and the update operation from ALISTA (Liu et al., 2019a). The tunable operator T120 is parameterized by
Ç = 7) for positive scalars A and y and defined by
T12 () == no (s :WT(Ax dd),
(19)
k= which )))) consists of 2K scalars. Note T120 may fail to be averaged, depending on the choice of ( (0, 7).
with W defined in the Appendix. The parameter θ used in Algorithm is θ -0*,
The primary illustration of the rapid convergence using LSKM-ALISTA relative to the KM counter- part ISTA is in Figure 1a. There each -² estimating solution (16) is computed for data d drawn from the same distribution D, that used to train the LSKM network. Figure lb shows plot comparing performance of LSKM and KM with each d there drawn from a distribution D, that is different than D.. For this reason, refer to D, the unseen distribution. For d Da. the L20 scheme ALISTA usually fails to converge without safeguarding whereas the safeguarded method LSKM-ALISTA still converges and much faster than ISTA. The dotted plot with square markers shows the percentage of safeguard activations that occurred in texting. The only two layers in Fig- ure lb where safeguarding kicked in were layers and 13, with respective percentages 36.7%, 99.6% and 99.2% among 1000 testing samples. Additionally summary results are provided in Table 3. These show the relative usefulness of difference choices of training loss function oa. safeguard- ing method, and performance measured by different test loss functions. In particular, using Φ = fa and EMA (0.25) safeguarding yielded the lowest function value fa; however, instead using (0 safeguarding resulted in estimates closer to the underlying sparse signals x². In both the seen and unseen cases, 20 iterations of AAASTA yields better function values fa than thousands of iterations of ISTA, which reveals orders of magnitude speedup by the safeguarded L2O schemes.
5.2 LINEARIZED ADMM
Let A E Rm x* E IR", and d E IRm be as in Subsection 5.1. Here we apply the L20 scheme differentiatable linearized ADMM (D-LADMM) of Xie et (2019) to the closely related sparse coding problem
|| d|/, + +||=||-- #ER
min
(20)
The operators defining T and Tr20 for LoKM-D-LADDMM are provided in the Appendix along with further implementation details. Comparison plots are provided in Figure and Table 4 summarizes further results.
5.3 PROJECTED GRADIENT FOR NONNEGATIVE LEAST SQUARES
Let A E Rmxx and E Rm Here we consider the nonnegative least squares (NNLS) problem
_ |Ax 2| s.l. 2 0.
min fa(z) zERn
(21)
We proceed by using the projected gradient method Table 1, where C == fo E R" 2 0), ff((z) AT (Ar d), and (r) m2x 0), with the max applied component-wise Then, for a A/T (ATA)) All2, we take
T(x) max (x - aA (Ax d).0).
(22)
8

---

Under review as a conference paper at ICLR 2020
EdvD, [fa( - fal
10
ISTA LSKM-ALISTA
10-2
10-5
100
10a
10a
10s
10
Iteration/Layer (a) Performance on seen distribution, i... d D.
106
ISTA I.KM-ALISTA
Safeguard Activation Freq.
IE Ed,D, [fa (ax) fal
80%
L20- -20-ALISTA
103
60%
40%
10
20%
0%
10P
10a
10a
103
Iteration/Layee Laaiiion/LLayrraaa k
(b) Performance on wnseen distribution, i.e., ~ D,
Figure I: Expected function value error versus iteration when applied to two different data distribu- tions. Training used 0d fa. Inferences used 5 0.01 and EMA(0.1).
We then relax T obtain, for ( (a, W) with a E R, W Raxx and B E R", obtain
Tr200 () = max (xr a (Ax d).
(23)
In the special case that W = AT, a = 1/Il [/]|AAAA|/> Al12, and 3 = 0, we recover (22). When safeguarding does kick in, (23) yields familiar network structure with the max as the activation function. Here O = (c*) k=1 (W D* ) consists of (n²² + 2n) trainable parameters. During training we force 3K 2 0 to ensure . E C. However, note .² might not be in C' for k: < K. In this example, each learned W is likely an approximation of the pseudo-inverse A. Summary plots given in Figure and more results in Table 5 of the Appendix.
6 DISCUSSION
Our numerical examples provide several insights. Tables 3 to in the Appendix reveal the choice of training loss function da results in different models and performance, even though the minimizers of each d. are identical. This is due to the difference in gradient directions of each du and reveals the 'best" choice of Φu may depend on the application. Figure 1b shows the necessity safeguarding to ensure convergence and that inferences on unseen data can still be much more rapid than traditional KM methods. For the space limit, we not focus on timed results. We simply note that the relative cost per iteration of the SKM method versus KM is roughly double in the worst case (since two tentative update operations are needed). However, in cases like our ALISTA example, this relative cost is greatly reduced because some computations (e.g., Ar d) common to both T220 and T. In each example, L20 schemes obtain an order of magnitude reduction in computational cost.
The results of this work reveal practical procedure for creating and implementing L20 schemes on new problems. Suppose one is presented a convex optimization problem and standard general purpose method for solving it. The method determines averaged operator T (e.g., in Table

---

Under review as a conference paper at ICLR 2020
LADMM
LADMM LSKM-DLADMM
LSKM-DLADMM
L20-DLADMM
80%
Safeguard Activations Freqq
10a
EdwDa (a(a") - fa
EAwD, [fa(=*) - fal
10a
60%
10a
40%
100
20%
10a
10-1
0%
100
10a
10a
103
109
10
102
Iteration/Layer A
Iteration/Layer
(a) Performance on seen distribution D,
(b) Performance on unseen distribution, i.c., d ~ Du
Figure 2: Expected relative function value error versus iteration when applied different dis- tributions. Training used dh = Sa. Inferences used 0.01, and GS(O.1) in (a) and (MA(0.75) in (b).
1). To construct TL2o, one may let each scalar, vector, and matrix that does not represent the data be parameterized (i.e., all of its entries learnable). We may further generalize the operations by replacing scalar parameters with vectors and using element-wise products as in D-LADMM (see (31)). Having T and TI20. a network can be constructed via the LSKKM algorithm. For training the network. the learnable parameters may be initialized to the quantities that reduce TL20 to the original operator T', Additional structures parameters may be invoked (e.g., as done by ALISTA with W in (26)). The number of terms to parameterize and how to structure parameterizations are matters subject to the practitioner's needs/priorities for given application.
CONCLUSION
This work establishes a framework for extending the L,0 methodology to wide class of iterative optimization procedures (i.e., KM methods). We provide theoretical results that demonstrate quences generated by our SKM method possess the property that the distance between each iterate and fixed point set converges zero. When there unique cluster point, this is equivalent to convergence of the method to a solution. Furthermore, our LSKM algorithm provides straightfor- ward neural network design that inherits the theoretical properties from the SKM method. Practical guidance is also given for constructing learnable operations for new problems. Our numerical ex- periments demonstrate order(s) of magnitude faster convergence by LSKM implementations than cineral-purpose counterparts and the efficacy of safeguarding in cases where L20 schemes would otherwise fail to converge. Future work will provide a more efficacious fall-back method for using data-driven updates than classic KM updates and will investigate stochastic extensions with quasi- Féjer monotone operators.
REFERENCES
Pierre Ablin, Thomas Moreau, Mathurin Massias, and Alexandre Gramfort. Learning step sizes for unfolded sparse coding. arXiv:1905.11071, 2019.
Marcin Andrychowicz, Misha Denil, Sergio Gmez, Matthew W Hoffmann, David Pfau, Tom Schaul, Brendan Shillingford, and Nando de Freitas. Learning learn by gradient descent by gradient
10

---

Under review as a conference paper at ICLR 2020
descent. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Gamett (eds.), Advances in Neural Information Processing Systems 29, pp. 3981-3989. Curran Associates, Inc., 2016.
Maria-Florimg Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn nigh-performing algorithms? arXiv: 02894, 2019.
Heinz Bauschke and Patrick Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaace. Springer, 2nd. edition, 2017.
Heinz H. Bauschke, Francesco lorio, and Valentin R. Koch. The Method of Cyclic Intrepid Pro- jections: Convergence Analysis and Numerical Experiments. In Masato Wakayama, Robert S. Anderssen, Jin Cheng, Yasuhide Fukumoto, Robert McKibbin, Konrad Polthier, Tsuyoshi Takagi. and Kim-Chuan Toh (eds.). The Impact of Applications on Mathematics, volume 1, pp. 187-200. Springer Japan, Tokyo, 2014.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d' d'horizon. arXiv:1811.06122 2018.
Thomas Blumensath and Mike Davies. Iterative hard thresholding for compressed sensing. Ap- plied and Computational Harmonic Analysis, 27(3):265-2744 2009, ISSN 1063-5203.
M. Borgerding, P. Schniter, and S. Rangan. AMP-Inspired Deep Networks for Sparse Linear Inverse Problems. IEEE Transactions on Signal Processing, 65(16):4293-4308, 2017.
Charles L Byrne. Applied Iterative Methods. A K Peters, Ltd., 2008
Andrzej Cegielski. Iterative Methods for Fixed Point Problems in Hilbert Spaces. Number 2057 in Lecture Notes in Mathematics. Springer, 2012.
Xiaohan Chen, Jialin Liu, Zhangyang Wang, and Wotao Yin. Theoretical Linear Convergence of Unfolded ISTA and Its Practical Weights and Thresholds. S. Bengio, H. Wallach, Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances Neural Information Processing Systems 31, pp. 9061-9071. 1. Curran Associates, Inc., 2018
Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Optimization Algorithms over Graphs. arXiv: / 704.01665. February 2018
I. Daubechies, M. Defrise, and C. De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Mathematics, 57(11): 1413-1457, 2004.
R. Giryes, Y. C. Eldar, M. Bronstein, and Sapiro. Tradeoff's Between Convergence Speed and Reconstruction Accuracy in Inverse Problems. IEEE Transactions on Signal Processing, 66(7): 1676-1690, 2018
Pontus Giselsson, Mattias Falt, and Stephen Boyd. Line search for averaged operator iteration. In 2016 IEEE 55th Conference Decision and Control (CDC), pp. 1015-1022, Las Vegas, NV, USA, December 2016. IEEE
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 26870, 2014.
Karol Gregor and Yann LeCun. Learning Fast Approximations of Sparse Coding. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML. 10, pp. 399-406, USA, 2010. Omnipress.
C.W Groetsch. A note on segmenting Mann iterates. Journal of Mathematical Analysis and Appli- cations, 40(2):369-322, November 1972.
John R. Hershey, Jonathan Le Roux, and Felix Weninger. Deep Unfolding: Model- Based Inspiration of Novel Deep Architectures. arXiv: 1409.2574 2014.

---

Under review as a conference paper at ICLR 2020
M.A. Krasnosel'ske skii. Two remarks about the method of successive approximations. Uspekhi Mat. Nauk, 10:122-127, 1955.
Ke Li and Jitendra Malik. Learning to Optimize. 0606. 2016.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, PP- 539-548, 2018.
Jialin Liu, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. ALISTA: ANALYTIC WEIGHTS
ARE AS GOOD AS LEARNED WEIGHTS IN LISTA. pp. 33, 2019a.
Q. Liu, X. Shen, and Y. Gu. Linearized ADMM for Nonconvex Nonsmooth Optimization With Convergence Analysis. IEEE Access, 7:76131-76144, 2019b.
Robert Mann. Mean Value Methods in Iteration. 4(3):506-510) 1953.
Chris Metzler, Ali Mousavi, and Richard Baraniuk. Learned D-AMP: Principled Neural Network based Compressive Image Recovery.
Guyon, U. V. Luxburg, S. Bengio, H. Wallach, Fer- gus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1772-1783. Curran Associates, Inc., 2017.
Thomas Moreau and Joan Bruna. Understanding Trainable Sparse Coding with Matrix Factorization. 2017.
Simeon Reich. Weak convergence theorems for nonexpansive mappings in Banach spaces. Journal of Mathematical Analysis and Applications, 67(2):274-276 1979.
P. Sprechmann, A. M. Bronstein, and G. Sapiro. Learning Efficient Sparse and Low Rank Models. IEEE Transactions on Puttern Analysis and Machine Intelligence, 371)11821-1833,, September 2015.
Sebastian Thrun and Lorien Pratt (eds.). Learning Learn. MA, USA, 1998.
Kluwer Academic Publishers, Norwell,
Z. Wang, S. Chang, Zhou, M. Wang, and T. Huang. Learning Task-Specific Deep Architecture For Clustering. In Proceedings of the 2016 SIAM International Conference Data Mining, Proceedings, pp. 369-377. Society for Industrial and Applied Mathematics, June 2016a.
Zhangyang Wang, Qing Ling, and Thomas S. Huang. Learning Deep lo Encoders. Thirtieth AAAI Conference on Artificial Intelligence, 2016b.
Zhangyang Wang, Ding Liu, Shiyu Chang, Qing Ling, Yingzhen Yang, and Thomas S. Huang. D3: Deep Dual-Domain Based Fast Restoration of PEG-Compressed Images. pp. 2764-2772, 2016c.
Zhangyang Wang, Yingzhen Yang, Shiyu Chang, Qing Ling, and Thomas S. Huang. Learning Deep loe Encoder for Hashing. In Proceedings of the Twenty- Fifth International Joint Conference on Artificial Intelligence, IJCAI' 16, pp. 2174-2180. AAAI Press, 2016d.
Xingyu Xie, Jianlong Wu, Zhisheng Zhong, Guangcan Liu, and Zhouchen Lin. Differentiable Lin- earized ADMM.
2019.
Bo Xin, Yizhou Wang, Wen Gao, David Wipf, and Baoyuan Wang. Maximal Sparsity with Deep Networks? In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 4340 4348. Curran Associates, Inc., 2016.
Yan Yang, Jian Sun, Huibin Li, and Zongben Xu. Deep ADMM-Net for Compressive Sensing MRI. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Gamett (eds.), Advances in Neural Information Processing Systems 29, pp. 10-18, Curran Associates, Inc., 2016.
A APPENDIX
This Appendix contains a subsection with supplemental materials and a subsection with proofs of the theoretical results.
12

---

Under review as a conference paper at ICLR 2020
Table 3: Summary of LASSO Problem Results on data d drawn from the seen distribution D,.
K 10, 000 iterations of ISTA are used by the KM reference method 'ISTA 10K' while K = 20 and 8 0.01 for the LSKM schemes. 'No guard' refers LSKM without safeguarding.
Method
ISTA 10K
No guard
EMA(0.1)
EMA(0.1)
EMA(0.1)
GS(0.1)
RM(3)
Loss tbs
NA
fa
2 |Sa(-)ll
||((0)
fa
fa
fa
R1,D( (a*)
7.72e-04
3.36e-04
4.65e-04
4.58e+00
3.33e-04
3.32e-04
6.68e-04
B (1)
2.1 1c-00
4.68c-07
3.75c-07
1.58c-05
4.68c-07
4.68c-07
4.95c-07
A.1 NUMERICAL EXAMPLE SUPPLEMENT MATERIALS
Supplement to Subsection 5.1. In similar manner to (Chen al., 2018) and (Liu al., 2019a), we use the following set up. We take m = 250, n = 500, and = 0.001. Each entry of the dictionary A sampled i.i.d from the standard Gaussian distribution, i.e., aey (O 1/m). Having these entries, we then normalize each column of A, with respect to the Euclidean norm. Each d in the distribution D, of data used train the neural network is constructed using (15) with noise e ~ 00, 1/mr) and each entry of x² as the composition of Bernoulli and Gaussian distributions, i.e., az ~ Ber(0.1 1) o (0, 1) for all j E [m]. Each d the unseen distribution D,, is computed using the same distribution of noise E as before and using zj ~ Ber(0.2) o (1,, Our data set consists of 10,000 training samples and 1,000 test samples.
If chosen too large, then the solution to the problem (16) is simply the zero vector, which is undesirable. If r is chosen too small, then the solution will not be sparse. Thus, appropriate choice of r is crucial. Since the goal of the LASSO problem is to faithfully recover the underlying sparse vector x" used to create the measurement d, find it reasonable to choose as a solution estimate of the problem
min EE-D || - x312] rE(0,00)
(24)
where & is the output of ISTA after K = 15, 000 iterations for the problem (16) and x; is the sparse vector from which was created. To simplify (24), we assume 7 was of the form t 10 with integer a E Z to obtain the problem
min aEZ
|| 21
(25)
Approximately solving this discrete problem for our data set revealed the optimal choice yielded -3 and - 0.001.
In practice, such a choice of r may be difficult to ascertain. However, if the practitioner has access to each underlying z for their training data d, then by simply using the training loss function (x(x) = || 1-1 This was precisely the approach taken in Liu et al. (2019a).
circumvent the problem of choosing
To define the learned operations in Ti20, we let
W E arg min || AllF, s.L( A.,= 1, for all e [n]] M MERmxn
(26)
where || is the Frobenius norm and the Matlab notation M.. is used to denote the εth column of the matrix M. Supplement to Subsection 5.2. LADMM is used to solve problems of the form
min ZER" Em
f(x) + g(=) s.t. Ar + B= = d,
(27)
for which LADMM generates sequences {-* JAEN, {a* JREN and {ur) JAEN defined by the updates
x k+1 = prox (s* - -AA= [ + a (Ar + B²* - d)]) k+1 prox (2 - -BT [ut + (Ax + B² d)])
(28)
A+1 = vht + (A + Bu d),
13

---

Under review as a conference paper at ICLR 2020
Table 4: Summary of D-LADMM Problem Results on data d drawn from the seen distribution D..
K 1. 000 iterations of LADMM are used by the KM reference method 'LADMM 1K' while
K 20 and 8 0.01 for the LSKM schemes. 'No guard' refers LSKM without safeguarding.
Method
LADMM 1K
No guard
EMA(0.755
GS(0.1)
RT
Loss te
NA
fa
fa
fa
fa
RJ.D. (x*)
3.48e+00
1.78e+00
1.52e+01
1.78e+00
1.28e+01
with given scalars a, 8, E oo). The problem (20) may be written in the form of (27) by taking T|| ||i, - || Il., and B Idd. this case, the proximal operators in (28) reduce to soft- thresholding operators. Although not given in Table the update w*+ is generated by applying an averaged operator T to v². (This follows since LADMM may expressed as a special case of proximal ADMM, which itself is a special case of the ADMM method. The details of this derivation are outside the scope of this paper.) This implies
||S(*))] III || T(**))l || ||0* - A AlI 2+1 dlI
(29)
Because we compare methods that use differing choices of a, the residual comparison illustrations presented below will, for consistency of interpretation, assume = 1 in (29). And, although x *+1 and =++1 form intermediate computations, for notational clarity, the term x in the SKM and LSKM
schemes is replaced in this subsection by the tuple (x* 2 =²). This is of practical importance too since it is the sequence {a*1 JeN that converges to a solution (20).
We now modify the iteration (28) for the problem (20) to create the D-LADMM L20 scheme. We generalize soft-thresholding to vectorized soft-thresholding for 3 E IR" by
(zx) (11,) (a, (12), .... 78, (I..).
(30)
We assume 77/ represents the scalar soft- noft-thresholdng in (18) when 3 E IR and the vector general- ization (30) when 3 E R", Combining ideas from ALISTA (Liu et al., 2019a) and D-LADMM (Liu et al., 2019b), given (x* 2t,,,, w*) E R x R x Rm a , , E Imm 8h ot E RR" Wi E Raxm
and W2 E mm set
* k++ = 173² (x* n² (WH)T [ +a o (Ax* 2h - -d]])
gh 17+ (s gh ( [u + aa o (Arkt1 - 2t - d]]),
(31)
x++1 = vh + ar (Ar+tI =k+1 - d)
with element-wise products denoted by For the parameter 5h == (at 3h 2 ot ek W W/). then define
T120 2²,,,, D²;; (h) == (a*+1, gh+1 x
(32)
Fixing the number of iterations K. the learnable parameters from (31) used in the LSKM Algorithm may be encoded by { (a 8h * at, ,h W Wh) wh) ) consisting of (2n + 3m +
mn + m²) K scalars.
For data generation, we follow the same settings as in the experiments of Subsection 5.1. Although the value of r is not optimally chosen, this was used as it worked well for D-LADMM.
Supplement to Subsection 5.3. We take
250, aiy Ber(O.1) rand 1]. We use noise E ~ 0.1 - 1/m).. Each d ~ D, used for training the neural network is sampled using d = Ax: + with x: max(A((0, 1), 0). For unseen data d D,, sample x max(N(5, 10 0). We sample 10,000 training samples from D, to train the neural network and 1,000 samples from D. and D,,, respectively, for testing.
500,
A.2 PROOFS
For case of reference, we restate Theorem 3.1 below. Then provide proof is provided for it.
Theorem 3.1. If {x* JeeN sequence generated by the SKM method and Assumptions hold, then
lim drix(T) (x*) =
(33)
100
14

---

Under review as a conference paper at ICLR 2020
10a
PG LSKM-PG
10*
PG
L.SKM-PG
Safeguard Activation Freq.
Ed-D, [fa(2=) - fäl
EAwD, [fa(=") --f
L20-PG
80%
10a
10a
60%
40%
10
10"
20%
10-2
10-2
0%
100
10
102
103
10
10
10a
10a
lteration/Layer &
Iteration/I Layer k
Performance distribution
(b) Performance
distribution, i.c., d D,,
Figure 3:
Expected function value error versus iteration when applied to two different data distribu- tions. Training used dd fa- Inferences used 0.01 and GS(O.1).
Table 5: Summary of NNLS Problem Results on data drawn from the seen distribution D,. K 1, 500 iterations of PG are used by the KM reference method 'PG 1.5K' while K 20 and ó 0.01 for the LSKM schemes. 'No guard' refers LSKM without safeguarding.
Method
PG 1.5K
No guard
EMA(0.75)
GS(0.1)
RT
Loss the
NA
fa
fa
fa
Ry.D, (x*)
3.80++06
1.86c+06
2.37c+07
1.86c+06
1.65c+08
And, if (arh JKEN contains a single cluster point, then f- JeEN converges to a point x" E Fix(T).
Proof. If the inequality in Line 6 holds finitely many times, then there exists an index beyond which Line 9 is always used to update x² In this case, for large k the SKM Method takes the form of the classic KM Method, which known to converge (e.g., see (Cegielski, 2012, Theorem 3.7.1), (Groetsch, 1972, Corollary 3), and (Bauschke & Combettes, 2017, Theorem 5.15)). Thus, it sufficient to only consider the case where the inequality in Line 6 holds infinitely many times. We proceed by first showing the sequence {a** keN is bounded (Step 1). This is used to prove (a*) JAE has a cluster point in Fix(T) (Step 2). Results from these steps are then applied to obtain the desired limit (33) (Step 3).
Step 1: By Assumption 2, there exists R E (0, oo) sufficiently large to ensure ||>||| R ||S())] 1, for all H.
(34)
Equivalently, we may write
||((x]] 1
| S R. all E H.
(35)
By Assumption 3, there also exists N1 E N such that
< 1, for all à 2 Nr.
(36)
Fix any 2 E Fix(T). We claim
|| -
max (2R, || =11}, for all & E N. EE(N.)
(37)
The result (37) holds trivially for all E [Ni]. Proceeding by induction, suppose (37) holds for some k > N₁. If the inequality in Line holds, then (35), (36) and the update formula in Line
together imply ||a+t|| I| < R. Since [|S(2)] (35) also implies || < R. Thus,
++1 - =|| S ||x0 (+11
||=||| S 2R < max (2R, || =1]}-
(38)
(E(NT)
15

---

Under review as a conference paper at ICLR 2020
If instead the update in Line 9 is applied, the averagedness of T implies there is a E (0, 1) such that
|| =11² s 1| =11² a ||
(39)
(e.g., see Prop. 4.35 in (Bauschke & Combettes, 2017) or Cor. 2.2.15 and Cor. 2.2.17 in (Cegielski, 2012)), and so | 2|| S | =|1 max (2R, || - -21] M.
(40)
Equations (38) and (40) together close the induction, from which (37) follows. Whence
| || - || - z|| + ||=||| - max (2R, || - =|1} + R, for all & E N,
(41)
EE|Mi]
which verifies the sequence (a*) KEN is bounded.
Step 2: Because the inequality in Line 6 holds infinitely many times, there exists a subsequence
{2 kRE f-*** JkEN satisfying
- lim ||(x.*)||
I lim (1 5)14 = 0, k
(42)
1-000
from which the squeeze theorem asserts [15(244)
0. Since Ju* is bounded, so also is
{a**) JKEN- Thus, there exists a subsequence (- jKEN S. {a JEEN converging to a limit p E H. Then applying the fact S is 2-Lipschitz and || is continuous yields
I| ||(
0 = lim |S(5*>1
lim xh k
= Fix(T..
(43)
That is, {a" JkeN contains cluster point E Fix(7).
Step 3: Let > 0 be given. Following (Bauschke et al., 2014, Def. 2), define the s-enlargement Fix(T) == {ar H dF (2)) e).
(44)
Note Fi is nonempty closed and bounded subset of H. Set
; = (B(O, R) (ex(())e/a)) U (F
(45)
where B(0, R) is the closed ball of radius R centered at the origin. Because H is finite dimensional and C is closed and bounded, C is compact. Thus, every continuous function obtains its infimum over C. In particular, we may set
Ç = min [[(x)]]- #EC
(46)
Note <> since C Cn Fix(T) = 0. Consequently, letting := min(1, yields
||(()]] S = E Fix
dFix(r((x) S E, for all x E H.
(47)
where the first implication holds because a E B(0, R. by (35) and C by (46). By Assumption 3, there exists N2 E N such that
#s < ?, for all k 2 N2.
(48)
By the result of Step 2, there exists
N₂ 2 N₂ such that
N pll S
dFix(T)(e (x:Na) S Sc
(49)
We claim
(F S E, for all k2 2NN..
(50)
which, by the arbitrariness s, implies (33) holds. Indeed, inductively suppose (50) holds for some 2 N3. the inequality in Line holds, then (47) and (48) together imply
[|S(a S (1 8)pz á =
dFII(T) (x*+t) S 6.
(51)
Otherwise, letting P: 7 + H be the projection operator onto Fix(T'), we deduce
|a+ P(x S || P(x & I|=0* P(x*)) || dFIx(T) (2*) ) See
(52)
16

---

Under review as a conference paper at ICLR 2020
where the second inequality follows from (39), taking P. Note the left hand side of (52) equals the distance from x to Fix(T). Therefore, (51) and (52) close the induction in each case, and (33) holds.
The limit (33) can be used in a similar manner to the work in Step 2 above to prove each cluster point of (x*) keN is in Fix(T). Thus, if (e*) admits unique cluster point, then the entire sequence converges to a point x² E Fix
We restate Corollary 3.1 below and then provide proof.
Corollary 3.1. If (x* JeE is sequence generated by the SKM method and Assumptions and 2 hold and {ex keN generated using scheme outlined Table 2, then Assumption 3 holds and, by Theorem 3.1, the limit (33) holds.
Proof. The proof is parsed into four parts, one for each particular choice of the sequence {uR]eeN heN in Table 2, where we note "Recent Term" is special case of "Recent Max" obtained by taking m = 1. Each proof part is completely independent of the others and separated by italic text. However, to avoid excessive writing, in each section let T S N be the set of all indices for which the descent condition in Line 6 holds, the sequence {ts Jeen be an ascending enumeration of I, my be the number of times the descent condition has been satisfied by iteration k. and μa (0, oc).
Geometric Seqeunce. Define the sequence {Na using, for each & N. the update formula
po++1 {
M4 (1 (1-8)pu
if Line 6 holds, otherwise.
(53)
This implies
A (1 8)m pl.
(54)
Since I' is infinite, lim my 0o, and it follows that k-+00
lim Am = lim (1 8) mn = 0 M 0,
(55)
i.c., Assumption 3 holds.
Arithmetic Average. Define the sequence {pu Jee using, for each & E N, the update formula
(||((**+)]I + madk)
if Line 6 holds, otherwise.
A9+1 ==
mk +1
(56)
H4
Then observe
(1 - 8)plc MorHte
5 (1--+++)) Mie S Pcc for all N.
0 0 Ml++1 <
(57)
ma, +
my
+1
Since 148+11 = f* whenever $ T, (57) shows fKEN monotonically decreasing. Consequently. using induction reveals
8
opte
Σ 8pt for all & E N, +1
0 0 Pte my + M1 S p1
P1
(58)
my +
where we note my, = l in the sum since my increments once each time modification occurs in the sequence (MA)KER. By way of contradiction, suppose there exists
(0, oo) such that
lim inf pa > 0. k-000
(59)
Then (58) implies
Σ
od
b
8pl
<
< kn,
for all ls E
(60)
l
1+1
(+l
17

---

Under review as a conference paper at ICLR 2020
However, the sum on the left hand side becomes a divergent harmonic series as l - oc, contradict- ing the finite upper bound on the right hand side. This contradiction proves assumption (59) is false, from which it follows that
lim inf μi = 0. R-000
(11)
By the monotone convergence theorem, we deduce fh - O, i... Assumption 3 holds. Exponential Moving Average. Given 0 (0, 1), for all & N, define
M4+1 == 01]S(* + (1 0) if Line 6 holds, otherwise.
(62)
P4
Now observe
Pac+1 = 0|5((***1)] + (1 0) S 0011-))4 + (1 0) = (1 -0)
(63)
This shows the sequence {ux} JeeN nonincreasing and, when a decrease does occur, it is by geometric factor of the current iterate. Through induction, it follows that
Pk S (1 *8) μı: for all l E N.
(64)
Since is infinite, lim my = co. This, combined with the fact (1 - 00)) E (0, 1): implies
1-+00
0 S lim Fa S lim (1 (1-08) 08) fn 0 p4 0,
(65)
10000
1+000
from which the squeeze theorem asserts Assumption 3 holds.
Recent Max. Let E N. Set Es to be the set of the most recent min m, k} indices for which the descent condition in Line held, where {uK [ukN defined, for all & E by the update formula
max EE
if Line 6 holds,
(66)
otherwise.
The sequence } is monotonically decreasing since the inequality in Line implies, each time new term [](((=)]] is introduced so that ||S(a*)]l E the new term is larger than the largest term in Ex. All that remains is to show this sequence converges to zero. By way of contradiction, suppose there exists a E (0, 20) such that
lim inf P4
0.
(67)
Then choose
5a
(68)
2(1-8)
which implies
(1 + +) < a.
(69)
By (67) and the fact I' is infinite, there exists Ñ E N with Ñ > m such that
| - al <E
Pig a tE
(70)
Then note each new element to E5 is no larger than (1 - 5)plg. And, for any k after m such replacements occur, it follows that
[4
max
[|S(z*]| < (1 8)Pl S (1-8)(a + <a EEE
(71)
contradiction to (67). This contradiction shows assumption (67) must be false, and
lim inf μr = 0. R-+00
(72)
By the monotone convergence theorem, we conclude Assumption holds.
18


Reviews:
[{"review_id": "SylIK-A0FS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a unified framework for parametrizing provably convergent algorithms and learning the parameters for a training dataset of problem instances of interest. The learned algorithm can then be used on unseen problems. One key idea to this algorithm is that it is safeguarded, meaning it will perform some standard, non-learned iterations, if the predicted iterate is not good enough under some condition.\n\nThere are three main features of the proposed approach:\n1- It unifies various previous approaches such as LISTA, ADMM, non-negative least squares, etc. By defining some operators and safeguarding rules, the same learning approach can be leveraged for these different optimization problems.\n2- It is shown that the learned algorithms are provably convergent under some mild assumptions.\n3- Empirically, it is shown that the learned algorithms converge faster than the non-learned counterpart on sparse coding, ADMM and non-negative least squares; they use safeguarding sparingly, particularly when used to solve test instances from the same distribution as the training instances.\n\nAdditionally, the paper is very well-written. I did not verify the proofs in detail but they seemed OK at a high-level; however, I am not an expert in convex optimization so I hope other reviewers will be able to comment on this aspect.\n\nI do have some deep concerns about the evaluation metrics used to report the results that I will discuss next; these are the main reason for my current score, but I am willing to adjust it if the authors address them convincingly. I also have some comments about related work.\n\nExperimental evaluation:\n- The error metric (15) is not suitable for evaluating the performance of an optimization algorithm. You should compute the expectation of the relative error, i.e. E_{d~D} [(f_d(x)-f_d^*) / f_d^*]. This is similar to the average approximation ratio used in the learning to optimize papers for discrete problems (see refs. below). (15) is just the ratio of the expected absolute error to the expected optimal value; I don't think that is equivalent to what I suggested.\n- The relative error values are massive in some cases, e.g. Fig. 3. What's going on there? Are all methods performing that horribly? Am I misinterpreting the metric?\n- Why do the plots for the seen distribution extend over thousands of iterations but only for tens of iterations for the unseen distribution?\n- Please use the same scale for the y-axes in Figs. 1-3.\n\nMethodology:\n- Your method requires learning per-iteration parameters. The other L2O methods for gradient descent (see refs. below) use shared parameters instead. This allows them to run for many iterations, possibly beyond what they were trained for. Your method does not allow for that. On the other hand, such models are recurrent and thus possibly more difficult to train than your unrolled feedforward model. Is the fixed number of iterations a limitation of your method? Please discuss this.\n\nRelated work:\n- Learning for gradient descent: I am surprised these papers are not mentioned although they are quite relevant. They are rather recurrent networks with shared parameters across iterations, but you should also compare against them both conceptually and experimentally:\n\n\"Learning to optimize.\" arXiv preprint arXiv:1606.01885 (2016).\n\"Learning to learn by gradient descent by gradient descent.\" Advances in neural information processing systems. 2016.\n\n- Learning to optimize in the discrete setting: there is lots of recent work on this that you should at least point to in passing, e.g.:\n\n\"Learning combinatorial optimization algorithms over graphs.\" Advances in Neural Information Processing Systems. 2017.\n\"Combinatorial optimization with graph convolutional networks and guided tree search.\" Advances in Neural Information Processing Systems. 2018.\n(Survey) \"Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon.\" arXiv preprint arXiv:1811.06128 (2018).\n\n- Theory for learning to optimize: Since you have a theoretical basis for your framework, you should discuss connections to other recent frameworks such as the one below by Balcan et al. It is geared towards the discrete setting and sample complexity rather than convergence, but you should nevertheless discuss it.\nBalcan, Maria-Florina, et al. \"How much data is sufficient to learn high-performing algorithms?.\" arXiv preprint arXiv:1908.02894 (2019).\n\nClarification questions:\n- \"The choice of parameter ζ k in Line 3 may be any value that results in a well-deﬁned operator T L2O\": what is \"well-defined\" here? that T_{L20} is averaged?\n\nMinor:\n- Page 3: \"A classic theorem states sequences\" -> \"A classic theorem states that sequences\"\n- Appendix proofs: please organize into sections and restate the statements before the proofs.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xdZV-RKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a framework to unfold the safeguarded Krasnosel’ski˘ı-Mann (SKM) method for the learn to optimization (L2O) schemes. First, SKM is proposed in Algorithm 1 with convergence guarantee established in Theorem 3.1 and Corollary 3.1. Then, SKM is unfolded and executed with a neural network summarized in Algorithm 2. Experiments on the Lasso and nonnegative least squares show the efficiency of the proposed method as well as the effectiveness of safeguarding compared to traditional L2O methods.   \n\nAdvantages:\n1. A general framework that encompasses all L2O algorithms for use by practitioners on any convex optimization problem.\n2. It seems that the convergence analysis of Krasnosel’ski˘ı-Mann equipped with safegarding is established for the first time. \n\nWeakness:\nThe idea of reimplementing an iterative algorithm in a deep architecture is not new, and the combination of safegarding with KM has already been analyzed [1,2].  Moreover, the experiments are not convincing. \n1. Safegarding is the key point of this paper, but the authors did not review related works on safegarding. Please show the relationships of SKM with prior works and comment on the novelty of the analysis in this paper. \n[1] Themelis, Andreas, and Panagiotis Patrinos. \"SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators.\" IEEE Transactions on Automatic Control (2019).\n[2] Sopasakis, Pantelis, et al. \"A primal-dual line search method and applications in image processing.\" 2017 25th European Signal Processing Conference (EUSIPCO). IEEE, 2017.\n\n2. All the 3 experiments are conducted on synthetic datasets which is not convincing enough to show the efficiency and effectiveness of LSKM. It is suggested to carry out experiments on real-world datasets like [3,4] with state-of-the-art methods. \n[3] Sun, Jian, Huibin Li, and Zongben Xu. \"Deep ADMM-Net for compressive sensing MRI.\" Advances in neural information processing systems. 2016.\n[4] Metzler, Chris, Ali Mousavi, and Richard Baraniuk. \"Learned D-AMP: Principled neural network based compressive image recovery.\" Advances in Neural Information Processing Systems. 2017.\n\n3. The are too many errors in references, for examples:\n(3.1) What is \"In S. Bengio, H.Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31\"? This error appears multiple times. \n(3.2) Show complete information of reference \"Liu et al. (2019a)\".\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1l7OLzF5B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is trying to provide a general learning-to-optimize(L2O) convergence theory. It proposes a general framework,  the Learned Safeguarded KM(LSKM) method, and proves the convergence of the algorithms generated by this method under certain conditions. Both the theoretical results and the experimental findings have been presented.\n\nThis paper should be rejected because it does not properly answer the problem it is trying to address. (1) The LSKM method with any \\mu_k is the universal method and it encompasses all L2O algorithms when the safeguarding condition \\|S(y^k)\\|<= (1-\\delta) \\mu_k always holds.  However Assumption~3 cannot cover the cases that the safeguarding condition always holds. Thus Theorem 3.1 gives the convergence of some algorithms generated by the LSKM method rather than the convergence of L2O schemes. (2) Theorem~3.1 is only related to the safeguarding procedure and the convergence of T. If we replace T_{L2O} by other operators, Theorem~3.1 still holds.  In my view, this work provides a practical technique to guarantee the convergence of L2O algorithms rather than a general L2O convergence theory.\n\nAlso I have some comments as follow:\n1. Section~2 provides an overview of the fixed point method. However only a few definitions and notations in this section is helpful to understand the proposed method. Please shorten this part.\n2. Dose the safeguarding procedure guarantee the convergence of the LSKM method and decrease the convergence rate comparing to the corresponding L2O algorithm? Please explain more about the role of the safeguarding procedure.\n3. It would be better to have a real data example in Section~5.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper gave a general L2O convergence theory called Learned Safeguarded KM (LSKM).  The reviewers found flaws both in theory and in experiments.  While all the reviewers have read the authors' rebuttal and gave detailed replies, they all agree to reject this paper.  I agree also.
Decision: Reject