Lagrangian Proximal Gradient Descent for Learning Convex Optimization Models

We thank the reviewer for the helpful feedback. We reply to the individual points below.

• The proposed method does not come with the convergence rate analysis.

  • It is very challenging even for the special cases to derive convergence rates, which is reflected by only the SPO+ and the Fenchel-Young loss in example 5 and 6 coming with convergence rates. For these methods it is possible because the loss is assumed to be convex in the parameters. In our generalized setup this is not necessarily true.
  • We are also mostly interested in the case in which the model $W_\theta$ is a neural network, which means that reasonable convergence results are in general hard to provide.
  • However, we agree that deriving convergence results for out algorithm under stronger assumptions would be a very nice addition to our work. Especially because due to our unification of previous methods, any convergence results would also directly apply to multiple existing methods. In this paper we focus on the first step of showing the similarities between various seemingly disconnected methods, and we leave the challenging analysis of the convergence to future work.

• Could the authors provide examples of neural network-type constrained minimization problems? The neural network can be chosen as a simple one. This is to demonstrate the difference and the connection between current methods and the classical ones. and One expects to see the method working on a neural network-type constrained optimization problem

  • Many of the methods that are covered as special cases have already been applied to problems involving neural networks. Examples include extracting edge costs in a shortest path problem from visual input (example 2 & 4, Vlastelica2020), extracting edge costs in graph matching problems for keypoint matching from visual input (example 2 & 4, Rolinek2020a) or extracting rankings in a retrieval system from visual input (example 2 & 4, Rolinek2020b). We added more detailed information on the experiments that have been proposed in the preceding literature of methods that we generalize.
  • However, we want to highlight that the distinguishing difference between our proposed method and the methods which we refer to as traditional or classical, is that we consider the bilevel optimization problem instead of single-level optimization problems for which proximal methods were originally designed. We clarify this in the revision by explicitly formulating the bilevel problem in eq. 3.

We thank the reviewer for the helpful feedback. We answer to individual weaknesses and questions below.

• The literature survey in this paper is not good enough. They surveyed many papers in Section 2, but the details of the most relevant papers are not provided either in the main text or in the Appendix. I'm particularly interested in existing papers that can also compute the (approximate) gradient of the function $\ell(x^\*(w))$.

  • In the revised version, we added a detailed description of previous related methods in Appendix B. We hope that this provides a good overview for readers who are not familiar with all the related work.

• Moreover, the authors claim that the proposed method generalizes many existing methods and discuss this in Example 1,2,3. For more general problems rather than these examples, whether the proposed method generalize existing methods?

  • Our method fully captures the update rules of all methods appearing in example 1-6. We do not restrict these methods to a specific case in the examples, the setups described in the examples mostly capture these methods in their full generality. Of course, beyond just the update rules used as gradient replacement, some of these methods come with deep individual theoretical results and extensions (e.g. Fenchel Young losses), which are currently not directly captured by our framework.

• From the experiment (Figure 2), even in terms of Epochs, LPGD-medium $\tau$ is faster than GD. This is not straightforward to me. If I understand correctly, all the simulated methods in the experiments are based on GD, while the gradient is computed based on different approaches. Therefore, I wonder whether the poor performance of GD comes from the low accuracy of gradient information computed by the method in Argarwal 19b?

  • It is important to mention that LPGD, in general, does not compute the true gradient that is used by the gradient descent baseline. We deliberately decide to use finite values of $\tau$ which intuitively means that the solver is not linearly approximated when computing the parameter updates. Not doing this approximation allows for more informative updates containing higher-order information. This is why in our experiment, the updates computed by LPGD lead to better results than plain GD. We do not believe that the baseline Agrawal19b suffers from low accuracy of gradient information, as the linear system which has to be solved during their backward pass to compute the gradient, is solved to a very high accuracy.
  • However, note that our method LPGD is also capable of computing the true gradient when considering the limit $\tau\rightarrow 0$, as shown in Theorem 5.1.

• What is the state-of-the-art method for solving the considered problem? Stochastic gradient-based or? Can this work be extended to that setting? I will suggest the authors to discuss this in Conclusion.

  • The state of the art method highly depends on the specifics. This includes: 1) Is the parameter-to-solution mapping smooth? (SOTA: stochastic gradient descent, gradients computed via implicit function theorem or direct loss minimization), otherwise 2) Are ground truth solutions to the optimization problem or objective parameters available? (SOTA: smart predict then optimize setting) 3) Is it possible to solve a regularized version of the problem? (SOTA: Fenchel Young losses) 4) Is an efficient projection method available? (SOTA: Identity with projection) 5) Is the solver only available as a blackbox oracle and no direct supervision on cost parameters/solutions? (SOTA: blackbox backpropagation)
  • With our unification we show that for these various settings, there is actually one generalized method that performs well over many different scenarios. We think that this is an important part of the contribution, and we emphasized it more in the revised conclusion.

• Should the sentence ``Note that for a general loss, the optimization (16) and (17) may diverge" below Eq (17) be revised as "Note that for a general loss, update using (17) may diverge". This sentence is unclear and less accurate because first, (16) is only an approximate loss and it's incorrect to say it may diverge.

  • Thank you for pointing this out, we changed the assumption to the existence of a non-empty solution set in the revision.

We thank the reviewer for the helpful suggestions. We answer to the individual weaknesses and questions below.

• The experiment section is rather small compared to the rest of the presentation.

  • The main contribution of this paper is in showing the similarities between different methods developed for different experimental settings, and how they can be combined in a unified framework. We believe that this contribution is decoupled from experimental results, and does not need to be supported by experiments, as each of the methods has previously been established independently to achieve strong empirical performance.
  • However, in our mission of unification we noticed that our framework actually suggests applying finite-difference based methods (with finite values of $\tau$) even in the setting in which the solver has non-degenerate derivatives. We tested this on our small-scale toy-experiment and observed that this technique can indeed improve performance over the previously typically used gradient-based approaches. Exploring this in-depth is beyond the scope of our paper, but we still wanted to include the small experimental section to share that our method could also lead to empirical improvements in future work.

• A lot of mathematical details could be eluded or referred to by a citation to a previous work (e.g. derivation of Moreau envelope, proximal operators, etc..). A quick (and rigorous) definition is more than enough, see below for a few remarks.

  • We changed many parts of the paper in the revision to make the treatment more rigorous by e.g. clearly stating the assumptions.

• There is too much context at the beginning of the presentation. No need to mention a vector $\mu$ that is not used in the demonstration. I would first consider a convex optimization problem, and introduce the Lagrangian and the primal/dual variables. Explain that $f$ can be composite and have a non-smooth component, and explain Moreau and its connection with the proximal operators with 2 definitions. Finally, you can start your demonstration. Some space would be saved by shortening in "Background and Notations" section can be used to do one more experiment (see above).

  • We rewrote entirely the problem setup section, which now presents more clearly what our aim is and which components are involved in the learning algorithm. Unfortunately the vector $\mu$ is needed here when trying to write down the training objective (equation (3) in revision).
  • Regarding the background on Moreau envelope and proximal map we removed the unnecessary part on the intuition and instead added references as suggested by the reviewers, we also removed the relation between proximal gradients and projected gradients. However, we still think that it is important to give some background on the proximal point method and proximal gradient descent here as these algorithms are so closely connected to our Lagrangian versions of them.

• Missing hypotheses in the Moreau envelope definition: $f$ must be proper and lower semi-continuous.

  • Thank you for pointing this out, we added this in the revision.

• Instead of establishing a connection between the Moreau envelope and the proximal operator, refer the reader to a chapter in a well-known textbook that already explains in great detail the connection (e.g. Bauschke and Combettes).

  • We included the additional reference and restructured the section as described above.

• In your experiments figure (figure 2), how do you explain that the $LPGD$ (avg) yields a significantly lower loss compared to the $LPGD$ (lower) and $LPGD$ (upper) schemes? Could you provide an intuition?

  • This is intuitively similar to the central-difference method having higher precision than forward or backward difference methods. Further intuition can be gained from Figure 1, which highlights that the different envelopes provide non-zero gradients of the envelope in different subsets of the domain, while $LPGD$ (avg) is able to use informative gradient information in both subsets. We added this intuition to the results section of the revision.

We thank the reviewer for the constructive criticism. We agree with many of the weaknesses regarding the original manuscript, and significantly improved the presentation and quality in the revised version. This includes, among many other changes, a clarified problem formulation with updated and precisely formulated assumptions, proofs and corrections for the claims in the paper, and a clarified presentation of the implementation of our method including an algorithm box. We provide more detailed answers to the individual points of critique below.

• Unfortunately, the paper is not written in a precise way for problem statements, results, tools etc. In many places it is not clear what the goal is and hence the contribution of the paper is quite unclear both in terms of mathematics and also practical aspects (not clear how to solve subproblems etc.). The assumptions and discussions about them are unclear. Even though many technical concepts are introduced, not much is proven with them and much of the claims in the paper are not proven (a list is below). The problem definition, goal etc are not clearly written and it requires the reader to read multiple times to even understand this. Unfortunately, the presentation needs to be vastly improved for this paper to be suitable for readers to understand and gain from.

  • In the revision we make the assumptions more precise (both in the problem statement and in the proofs). We also include additional proofs in a more standard format in the revised Appendix F.
  • Regarding the unclear main contribution of our work, we want to stress that it is in highlighting similarities between various methods for embedding paramterized optimization problems in machine learning architectures and showcasing that the corresponding update rules can be derived from principles routed in traditional optimization algorithms. We made this goal clearer in the revision, see e.g. the changes in the abstract and introduction.

• Proper references are not given in many places. For example, last paragraph in page 1 cites for "traditional proximal optimization" the papers by Moreau, 1962 (an excellent reference) and Parikh&Boyd, 2014, Boyd&Vandenberghe, 2004 which are okay (even though it is not clear where in Boyd&Vandenberghe's book proximal methods are discussed) however many of the most important references are not there. For example, no mention of Rockafellar who is the founding father of the field along with Moreau, his book Convex Analysis (at the least) should be cited here with many of his other founding papers. One of the most impactful proximal gradient based algorithms is FISTA by Beck and Teboulle which is also not cited. Nesterov's or Tseng's accelerated proximal methods are not cited. Another important reference is by Figueiredo, Nowak, Wright, 2007 which is again, not cited. It is also not hard to find these references, they are all included in Parikh&Boyd's text.

  • Thank you for pointing out these missing references; we include them in the revision.

• Sect 3.1, problem setup is not written well. One can write this in a much clearer fashion. Especially for optimization audiences, it is much better to write a well-defined problem, rather than the arrows and unclear notation in the start of Sect 3.1. For example, one should define precisely the "model" $W_\theta$. What kind of a function is it? What assumptions are needed on it? One then needs to write the optimization problem in terms of the main variable ($w$ or $\theta$) and then clearly describe the assumptions on each function appearing in the problem. Problem (1) is well-defined but it depends on $w$ hence it does not really describe the whole problem. It should be written in a precise problem formulation by taking into account the relations with arrows given at the start of the section.

  • We completely restructured Section 3.1. It now includes a well-defined problem formulation and lists the assumptions that we make.