Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on the problem efficiently training Deep Equilibrium Models (DEQs) by estimating the gradient to the "equilibirum layer." Usually, this gradient is computed using a black-box fixed point solver (generally Broyden's), which makes the backward pass expensive. This paper introduces a gradient estimate, which they term the _phantom gradient_. They show that the dot product between this gradient and the true gradient is greater than 0, which means it constitutes a descent direction in a first-order sense. They empirically verify that these estimates are good using CIFAR-10 and ImageNet, where they get performance remarkably close to the standard Multiscale DEQ [1] with a reasonable training speed improvement. They also show that the phantom gradient approaches the true gradient in terms of cosine similarity with increasing series elements $k$. 
main_review: ### Strengths

1. The paper is well-written and organized very well. Every step is motivated properly and the remarks provide good intuition for the theory.
2. The empirical experimentation is reasonably thorough, in particular lines (174-179) provide a good roadmap for section 3. 
3. The speed improvement is significant. The results on ImageNet show that this algorithm scales well with minimal performance degradation (75.3 -> 75.0). 
4. The convergence theory provided in section 2.4 along with the cosine alignment plots in Figure 1 are very convincing.
5. The relevant hyperparameters of the method are ablated appropriately (Figure 3). 
6. I like the takeaway that precise gradient estimates are not always required, especially in cases where a layer is a black box. I think this will be of interest to the community.

### Weaknesses

1. Remark 2 seems incorrect. This holds in the linear model case, however for generic multilayer networks with ReLU or sigmoid non-linearity, the NTK is not a scalar network. See [2] for details. Perhaps there's some other effect keeping the Jacobian well-conditioned with large width however.
2. Does the Neumann Series for computing the phantom gradient always converge faster than Broyden's fixed point in the standard DEQ setup? It seems like this algorithm can be seen as trading one iterative solver for another.
3. There are no error bars for the small scale experiment. Is training with this gradient estimate stable in terms of performance?


Overall I think this method is quite interesting and will be of benefit to the larger NeurIPS community. My rating can be improved if the authors answer some of the questions I have posed, or clarify some misconceptions with their method.


### Questions to the Author

1. Is the Jacobian-inverse likely to be ill-conditioned in this setting, or is this mostly a motivation?
2. I would like to see a plot of the condition in Eq. 6, perhaps for a small dataset. Is this a reasonable assumption?
3. Figure 2 shows that cosine similarity with the exact gradient decreases with the training iterations. How does this affect training later on? Could the algorithm be improved by keeping $k$ low early in training and increasing it later?
4. Are there cases where Broyden converges faster than the Neumann series?
5. Do you find that these hyperparameters transfer well between tasks? Do you need to re-tune?


[1] Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Multiscale Deep Equilibrium Models. In Neural Information Processing Systems (NeurIPS), pages 5238–5250, 2020.
[2] Youngmin Cho, Lawrence Saul. Kernel Methods for Deep Learning. In Advances in Neural Information Processing Systems 22 (NIPS 2009)
limitations_and_societal_impact: They do not discuss the limitations or social impact of their work. Given that this paper is rather abstract, dealing with a learning method rather than an application, I believe this to be justified. One suggestion for limitations, however, would be to try to study cases where their gradient estimator is unstable.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes an approximate gradient, called phantom gradient, for training implicit models. They highlight that the method reduces the cost of gradient computation and it provides a descent direction suitable to train models. Their gradients are based on two methods, fixed-point unrolling and the Neumann series. The paper proves that under some network conditions on the eigenvalues of the derivative of the implicit module, the phantom gradient has a descent direction positively corelated to the exact gradient. The paper also provide almost surely convergence of the phantom gradient to the exact gradient under some conditions.
main_review: The paper is nicely written and is well-organized. The paper explains well how their method differs from prior works. Although the work is incremental, the approximate gradient due to its reduced cost computation is of interest. Here are my detailed comments.

- The term (1 - lambda) h_t in (13) is introducing a momentum. Please discuss the results from the perspective of momentum.

- It would be nice to emphasize that when \lambda = 1, the proposed gradient is reduced to backprop through the unrolled iterations (e.g., Figure 1b right). All reported results are based on lambda = 0.5, and k = 5. a) the choice reason should be explained. b) the experiments should cover a range for lambda and k, specially the case lambda = 1 (backprop but not exact gradient). Indeed, their approach should be compared against the case lambda = 1 to highlight the advantages of the phantom gradient.


- At line 12 and 54, please be more specific that the speed up is compared to which methods (backprop, which implicit diff method)?

- It would be nice to move some of the questions asked on paragraph line 174 to the introduction or contribution.

- Although included in the supp, explain for the tables that A_{5,0.5} is for k = 5, and lambda = 0.5.

- Place the tables and figures close to their descriptions.

- It's nice that the code has been made available. I suggest to include a readme.

Minor comments:

- typo on supp line 20. It should be Remark.



----------------------------------------------------------------------------------------------------------------
Post response review
----------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------

I have found the authors' response to the reviews satisfactory. I strongly recommend to add some of the discussions made here to either the paper or supplementary, specifically elaboration on NTK, hyperparameter tuning, result discussion.

Overall, given the modifications suggested by the reviewers, I have increased my score.
limitations_and_societal_impact: Limitations is not included. A need for tuning lambda can be one limitation of the gradient.

I suggest to include some societal impact related to the computational cost of training implicit models and their robustness.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper presents a method called phantom gradient to increase the efficiency in training implicit deep models by approximating the exact gradient. The authors first exploit Neumann series for the damped inverse matrix in implicit gradient calculation. They then truncate the series to k terms to arrive at finite term approximation of the exact implicit gradient. They finally provide theoretical justification for when phantom gradients are descent directions for implicit models. The authors evaluate their methods by conducting experiments on thoroughly analyzing their descent direction and demonstrating acceleration over a current implicit training method.
main_review: [Strength] The paper has the following strength.
- The paper studies the very interesting and important problem of accelerating implicit model training. Which is also a difficult problem. The paper gives a novel insight that memorizing the first few steps of the forward fixed point iterations can help more efficient and stable gradient evaluation.
- The proposed method gives theoretical analysis of the method on the validity of phantom gradients and convergence analysis of the method. 
- The method offers significant speedup in backward steps over the current implicit gradient method in model training and offer a moderate speedup overall.
- Thorough empirical analysis on the property of the model is well conducted in the paper, showing cleverly chosen parameters are key to the speedup in implicit training. It is also demonstrated that the method scales well to large experiments in computer vision.

[Weekness] The paper is well written but has a few glitches. I think the paper would be a good addition to NeurIPS if the authors can carefully address them.
- The notations of the paper are not clearly given. (e.g. The norm and inner product of Theorem 1). I sugguest they are operator norm and matrix inner product. Though careful inspection could infer the notations, a clearer definition can help make the paper more readable for general public.
- The paper should more adequately discuss related works such as (El Ghaoui, 2019; Revay, 2020; Gu, 2020) on theoretical contributions like well-posedness (refereed as well-conditioned in this paper) for implicit models and (Wang, 2020; Gu, 2020) on recent applications of implicit models on object detection and graph neural networks.
- I have seen a varient of Theorem 2 in Theorem 6.1 of (El Ghaoui, 2019). I think the condition can be further relaxed to something like $\partial F / \partial h*$ has spectual radius less than 1. Note that this is not the same as being contractive. I think the relation should not undermine the contribution of this paper though.
- The parameter choices of k and lambda are not well-connected with the theoretical analysis as in Theorem 1. It would help the consistency if the empirical choices of the parameters in accordance to the theory can be discussed in section 2.3. Also in section 2.3 (i) and (ii), the benefits of the better conditioning of A matrix is not well discussed. It only start to make sense to me after reading the experiment section for a while. I sugguest it helps the accuracy of the model although resulting in less accurate gradient.. Right?
- Figure 3 (b) could use other colors for UPG and NPG to avoid visual confusion.
- The paper could also include speed comparison on just the backward steps as I suggest it would show a much more visible improvement. Because the method does not touch the forward pass which takes roughly the same amount of time to do as the backward, the overall improvement cannot exceed approximately 2x, making it appear less impressive.
- The proposed method should be general to all implicit models. The authors currently fail to show this by only offering experiments regarding computer vision tasks. I think the impact from generalization capability of the method would be better demonstrated if the author can include experiments on tasks in the final version, for example on natural language processing (Bai, 2019) and/or graph neural network (Gu, 2020) experiments whose code is available online.
- I hope the authors be more generous in sharing the limitations of the method as suggested by NeurIPS 2021 board (see checklist 1b).

Ref:

Bai, S., Kolter, J. Z., & Koltun, V. (2019). Deep equilibrium models. Advances in Neural Information Processing Systems 32. https://papers.nips.cc/paper/2019/hash/01386bd6d8e091c2ab4c7c7de644d37b-Abstract.html

El Ghaoui, L., Gu, F., Travacca, B., Askari, A., & Tsai, A. Y. (2019). Implicit deep learning. arXiv preprint arXiv:1908.06315, 2. https://arxiv.org/abs/1908.06315

Revay, M., Wang, R., & Manchester, I. R. (2020). Lipschitz Bounded Equilibrium Networks. arXiv preprint arXiv:2010.01732. https://arxiv.org/abs/2010.01732

Gu, F., Chang, H., Zhu, W., Sojoudi, S., El Ghaoui, L. (2020). Implicit graph neural networks. Advances in Neural Information Processing Systems 33, 11984--11995. https://papers.nips.cc/paper/2020/hash/8b5c8441a8ff8e151b191c53c1842a38-Abstract.html

Wang, T., Zhang, X., & Sun, J. (2020). Implicit feature pyramid network for object detection. arXiv preprint arXiv:2012.13563. https://arxiv.org/abs/2012.13563


---------------------------------------
Post Rebuttal:
I appreciate the authors' detailed responses to my questions. I am glad that the authors find my comments useful and will include them in the final draft. I have no further concerns about the paper being accepted by NeurIPS. Thus, I will update my score to 7.
limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new method to estimate gradient for implicit models, which empirically accelerates  the training of implicit models.
main_review: Overall this is an interesting paper. The major contributions are:

1. This paper proposes a new method to estimate gradient in training implicit models, where the idea is quite straight-forward and easy to follow; 
2. Some analyses are provided on how well the approximation could be, including some theoretical results and their intuitive explanations;
3. Experimental results on CIFAR-10 and ImageNet are also provided, in which the proposed method shows its effectiveness in terms of accuracy and efficiency.

Below are some other comments and questions:

1. There are three major theorems in the paper. The first one relies on the condition  based on singular values and the last one relies on the condition of good approximation. As mentioned in the paper, the condition for the first theorem is related to  NTK. Consequently, when the model is 'sufficiently wide', the condition can be easily satisfied. However, Theorem 3.1 & 3.2 in [Arora et al. 2019] suggest that this 'sufficiently wide' requirement could be rather impractical, as the required width  is much wider than those commonly used models in practice. Thus, the conditions for the first and third theorems are somewhat strong. Maybe the authors can consider adding an experiment to study the impact of different model designs. 
2. It would strengthen the paper if it compares more related works in experiments and reports all the results with mean (standard deviation);
3. In the experiments, the proposed method leads to worse results sometime. It would be interesting to know whether this is due to the approximation quality or something else. Hope the authors can provide some detailed discussions on this.

limitations_and_societal_impact: N/A
review_title: null

Meta-review: Many current architectures use "implicit" layers where a solver (e.g. root finder or ODE solver) gives the output. Exactly differentiating these models requires implicit differentiation in the backprop step, which is expensive. This paper introduces a novel "phantom" gradient which is easy to compute, and shows that the inner-product of this gradient with the true gradient is >0, meaning it is a descent direction. An empirical verification shows that optimization using this gradient succeeds.

Reviewers generally felt the paper was novel, well-organized, convincing, clear, and had experiments that show the method truly works. There were a few weaknesses that were identified. First, there were some technical issues in the theoretical results. From the author response, these appear to be relatively minor and specific corrections have been identified. Second, there were some concerns about the rigor of the experiments (e.g. the lack of error bars in the small-scale experiment). Third, there were some concerns about notation and related works. For these latter two concerns the authors have responded at length in the feedback, and this has improved reviewer confidence about these issues. We trust the authors will integrate this content into the main paper, which will strength it considerably.
Decision: Accept (Poster)