Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: 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.

This 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.

Also I have some comments as follow:
1. 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.
2. 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.
3. It would be better to have a real data example in Section~5.


review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: 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.

There are three main features of the proposed approach:
1- 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.
2- It is shown that the learned algorithms are provably convergent under some mild assumptions.
3- 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.

Additionally, 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.

I 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.

Experimental evaluation:
- 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.
- 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?
- Why do the plots for the seen distribution extend over thousands of iterations but only for tens of iterations for the unseen distribution?
- Please use the same scale for the y-axes in Figs. 1-3.

Methodology:
- 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.

Related work:
- 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:

"Learning to optimize." arXiv preprint arXiv:1606.01885 (2016).
"Learning to learn by gradient descent by gradient descent." Advances in neural information processing systems. 2016.

- 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.:

"Learning combinatorial optimization algorithms over graphs." Advances in Neural Information Processing Systems. 2017.
"Combinatorial optimization with graph convolutional networks and guided tree search." Advances in Neural Information Processing Systems. 2018.
(Survey) "Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon." arXiv preprint arXiv:1811.06128 (2018).

- 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.
Balcan, Maria-Florina, et al. "How much data is sufficient to learn high-performing algorithms?." arXiv preprint arXiv:1908.02894 (2019).

Clarification questions:
- "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?

Minor:
- Page 3: "A classic theorem states sequences" -> "A classic theorem states that sequences"
- Appendix proofs: please organize into sections and restate the statements before the proofs.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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.   

Advantages:
1. A general framework that encompasses all L2O algorithms for use by practitioners on any convex optimization problem.
2. It seems that the convergence analysis of Krasnosel’ski˘ı-Mann equipped with safegarding is established for the first time. 

Weakness:
The 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. 
1. 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. 
[1] Themelis, Andreas, and Panagiotis Patrinos. "SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators." IEEE Transactions on Automatic Control (2019).
[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.

2. 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. 
[3] Sun, Jian, Huibin Li, and Zongben Xu. "Deep ADMM-Net for compressive sensing MRI." Advances in neural information processing systems. 2016.
[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.

3. The are too many errors in references, for examples:
(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. 
(3.2) Show complete information of reference "Liu et al. (2019a)".

review_title: Official Blind Review #2

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