Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper pointed out an interesting phenomenon in bi-level optimization: the tradeoff between the convergence rate and the length of "burn-in" phase. Mathematical descriptions and analysis are provided.

----
The authors addressed my concerns and I updated my score.
strengths_and_weaknesses: The "curse of unrolling" and its mathematical descriptions are really interesting. Thus, I think this paper is very insightful. But the completeness and presentation have room to improve. I listed some questions below and I'm open to updating the grade if the authors are able to fix my concerns.
questions: 1. At the beginning of this paper, Fig. 1 shows the difference between the function suboptimality and Jacobian suboptimality. This phenomenon is really interesting. However, in the main text, there is only the upper bound for Jacobian suboptimality. Why is there no bounds for the function gap? I believe that this paper will be better if the function gap bound can be provided and it matches Fig. 1.
2. Through this paper, only quadratic functions are considered both in the theoretical and experimental parts. Is it possible to provide some experiments to show that the phenomenon "curse of unrolling" exists not only with quadratic functions but also with more general functions? At least some references on this phenomenon should be provided. If such a phenomenon only happens on quadratic functions, the significance of this paper will be weakened.
3. Line 182: typo: "Figure ??" Such typo also occurs in the caption of Figure 3.
4. Figure 4: Why does gradient descent on "synthetic dataset" diverge?
limitations: My main concerns are Questions 1 & 2 in the previous section, some potential suggestions are provided following the questions.
This paper is purely theoretical and I think it has no potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose a framework for convergence analysis of unrolled differentiation of quadratic objectives. To that end, they use a connection between optimization methods and residual polynomials which allows one to establish convergence bounds by evaluating appropriate polynomials on the spectrum of the hessian. From their theoretical results it can be seen that the convergence behaviour of the Jacobian of the argmin and the optimization objective behave differently during unrolling. A larger step size that yields fastest convergence of the optimization objective induces in turn a longer burn-in phase of the Jacobian sequence. Smaller step sizes can mitigate this burn-in phase while inducing slower asymptotic convergence. This tradeoff is called the curse of unrolling by the authors. Finally the authors propose an accelerated unrolling procedure for quadratic objectives that is motivated by the theory of Sobolev Polynomials and is shown to outperform reference methods (GD and Chebyshew) on different datasets.
strengths_and_weaknesses: From my perspective, the presented results are novel and technically correct. Apart from a few typos and missing references that can likely be fixed, I also find that the paper is well-structured, clearly written, and has some comprehensive figures. I personally think that the theoretical underpinning of distinct convergence phases during unrolling is a very interesting result. Also I would say that the methodology and the derived accelerated method are strengths of the paper. Clear limitations that the authors also mention in their discussion are that the results only apply to first-order methods and quadratic objectives. With that said, the presented results are in my opinion still interesting, although maybe less relevant to a broader audience.
questions: Some typos I found:

17: function(s)

27: differentiation(m)

30: of (an) iterative algorithm

32: What does "mode differentiation" stand for here?

49: algorithm(s)

189: iteration(s)

194: (that) that

217: (we) don't have

Top of page 8: Figure ??

260: there is no Figure 5

280: should it be "formalism does (not) apply"?

One thing I was wondering about is whether the analysis still works when $n > 1$, i.e., when $\theta$ is not a scalar but a vector. How do I need to read for example (2) in that case? What is the dimension of $\partial H(\theta)$ then?
limitations: Yes.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the use of unrolling as a way to differentiate through an optimization problem. Specifically, it focuses on the estimation of the Jacobian (of the solution w.r.t. the trainable parameters of the network) when the problem is a quadratic optimization and the algorithm is a first-order method. The main contribution is the analysis which shows ``the curse of unrolling'' and on top of it, this paper proposes a scheme to accelerate the unrolled differentiation based on Sobolev orthogonal polynomials. The experiments show curves that match well with the proposed analysis.
strengths_and_weaknesses: Strengths:
1. The topic is both theoretically and practically important considering that the unrolling scheme has been utilized by a large family of deep learning works.
2. The results (theorem1-3) are novel and can explain the practical observation. Discussions are given to explain how the results can lead to certain pattern in the plot.
3. The proposed accelerated scheme for unrolling has a limited ``burn-in'' phase which is a useful property.

Weaknesses:
1. My largest concern is that for deep pipelines, both the Jacobian $\partial x_t - \partial x_*$ and the final solution $||x_t-x_*||$ matter at the same time. With only the bound for the former one, the results cannot be directly used to guide the practical use of unrolling. Especially for the proposed accelerated scheme, it is not clear how this modified scheme will influence $||x_t-x_*||$ .
2. The datasets used in the experiment are kind of toy-size by modern standards. Since the topic is the use of unrolling in deep learning pipelines, it would be more convincing if more serious experiments were included.
questions: Please see weaknesses.
limitations: The authors have discussed the limitations in detail and claim to have no potential negative societal impact.
review_title: null

Meta-review: metareview: All the reviewers judged the paper to be novel and interesting and voted to accept it. There were some concerns about the size of the experiments that were partially solved during the discussion phase. Hence, I encourage the authors to add even more experiments in the camera ready to increase the impact of the paper.
confidence: Certain
Decision: Accept