Many applications require quickly and repeatedly solving a certain type of optimization problem, each time with new (but similar) data. However, state-of-theart 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.
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.