Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduced a theory for the piggyback iteration of nonsmooth functions. While existing asymptotic analysis for the piggyback AD procedure only works for twice continuously differentiable functions, with the conservative derivative framework, this paper provided the asymptotic convergence results for nonsmooth path-differentiable functions under a nonexpansive condition (in Assumption 1). They formally defined the notion of general Clarke Jacobian for piggyback and its fixed point, with which the convergence of an infinite piggyback iteration is proved in Corollary 1. For mapping with a Lipschitz gradient selection, they proved a non-asymptotic convergence rate. They also showed applications by applying the piggyback iterations to various methods for convex problems.
strengths_and_weaknesses: The paper is well-written with a clear introduction to various new and existing notions in the conservative derivative framework. The problem studies are timely and important. The theoretical results are nontrivial and demonstrate wide extensibility, which also suggests important applications. The failure example discussed in Section 5 is interesting. It shows that even functions with a Lipschitz gradient cannot ensure the convergence of the piggyback procedure. For assumption 1, how does this assumption compare with these in the smooth cases? For example, in [37], they assume the Hessian at optimum is positive definite and they use the gradient descent method. So it would be better to discuss the strength of assumption 1 in various situations where we assume the function is C^2 and fixed the algorithm. Is Assumption 1 for the nonsmooth procedure stronger or weaker than that in existing papers? Some minor points:

L131: "X\in R^{p \times n}" -> "X\in R^{p \times m}"
L153: "this a" -> "this is a"
questions: See above.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors investigate the differentiation of iterates $x_k(\theta)\in \mathbb{R}^p$ of nonsmooth optimization algorithms with respect to algorithm parameters $\theta \in \mathbb{R}^m$. This task is motivated by the need to differentiate through the argmin of objectives that give rise to nonsmooth algorithmic iterations $x_{k+1} = F(x_k(\theta), \theta)$. Differentiation with respect to algorithmic iterates is frequently used because the argmin itself might for example be incaccessible to explict differentiation or alternative approaches.

An important question is whether Jacobians with respect to algorithmic iterates converge to classical Jacobians at fixed points $\bar x(\theta)$. This has previously been answered for the case of smooth iterations and the authors consider the nonsmooth case in this paper. To that end, they first introduce conservative Jacobians that are set-valued and enable a recursive differentiation framework for nonsmooth iterations. Under assumptions, they show that the defined recursion converges to a nonempty and compact set of fixed points in $\mathbb{R}^{p\times m}$ that is a conservative Jacobian of $\bar x(\theta)$. The limit of conservative Jacobians of $x_k(\theta)$ is therefore equal to a conservative Jacobian at $\bar x(\theta)$. In other words: Limit formation and differentiation can be exchanged here.

Afterwards, the authors also provide a linear convergence result for a specific class of functions (where the iteration is a Lipschitz gradient selection function), they show that their framework is applicable to several splitting algorithms including numerical examples, and they finally provide a concrete counterexample using the heavy-ball algorithm, where the sequence of derivatives diverges although the iterates themselves are linearly convergent.
strengths_and_weaknesses: I think that this is an interesting and well-written paper. To the best of my knowledge, the presented results for nonsmooth algorithms are novel and also relevant (from a theoretical point of view but also in view of a growing number of use-cases of algorithm unrolling). Moreover, the authors provide rigorous proofs of their results in the appendix. One small weak point is, according to my personal impression, that the paper is partially not self-contained. For example the inputs of algorithmic differentiation in Section 3.3 could at least be briefly explained. 
questions: Line 77: Should it be $x\in\mathbb{R}^p$ rather than $x\in\mathbb{R}^n$?

Line 89: Should it be $\mathbb{R}^{m\times p}$ rather than $\mathbb{R}^{p\times m}$?

Line 110: How do you initialize $J_{x_0}(\theta)$?

Line 131: Should it be $X \in \mathbb{R}^{p\times m}$ rather than $\mathbb{R}^{p\times n}$?
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors consider a possibly non-smooth but structured iterative algorithm which additionally depends on some parameter $\theta$, also in a possibly non-smooth but structured manner; the structure being defined in Assumption 1. They used the tools developed in [1, 2] to differentiate this parametric fixed-point iteration through Chain Rule. This defines a (so-called) piggyback recursion, where the sequence being generated is set-valued. They show that the conservative jacobian of the fixed-point $\bar x (\theta)$ of the algorithm satisfies a set-valued, affine fixed-point equation. They show the convergence of the resulting sequence to the conservative jacobian of the fixed-point of the algorithm for all $\theta$ with respect to the gap metric defined in Section 3.1. They also link the implicit differentiation of the fixed-point $\bar x (\theta)$ by using the conservative calculus in [3] to the limit of the set-valued sequence. They show linear convergence of this sequence under additional Lipschitz-gradient-selection assumption of the algorithm mapping $F$. Finally, the consider instances of the iteartive algorithm to solve a composite optimization problem, namely, Forward-Backward Splitting, Douglas Rachford and ADMM. They put another assumption on the optimization problem (Assumption 2) and show that Assumption 1 is satisfied by the above listed algorithms. They also show the failure of convergence of the derivative sequence for inertial methods.

[1] Jerome Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning. Mathematical Programming, 2020.

[2] Jerome Bolte and Edouard Pauwels. A mathematical model for automatic differentiation in machine learning. In Conference on Neural Information Processing Systems, Vancouver, Canada, 2020.

[3] Jerome Bolte, Tam Le, Edouard Pauwels, and Antonio Silveti-Falls. Nonsmooth Implicit Differentiation for Machine Learning and Optimization. In Advances in Neural Information Processing Systems, Online, 2021.
strengths_and_weaknesses: Strenghts
- The paper provides a fairly general result for non-smooth iterative algorithms. This is useful for instance in a bilevel framework since their result along with [1, 2] provides theoretical guarantees for correctly evaluating the gradient of the upper level problem by differentiating through the argmin of the lower problem by using Automatic Differentiation.

Weaknesses
- A comment on the difference between the convergence speed of Piggyback iterations for the mentioned optimization algorithms is missing.
questions: - What do the authors think of the difference in using Automatic and Implicit Differentiation for non-smooth fixed-point iterations and equations respectively in terms of
    - the computational efficiency of the algorithms in their setting, and
    - the correct evaluation of the derivative of the fixed-point (or something "reasonable" when that does not exist) in a more general setting.
- If the answer to the previous question is hat Implicit Differentiation behaves atleast as well as Automatic Differentiation then why even use Automatic Differentiation since Implicit Differentiation is memory efficient.

Minor Typos and other Confusions
- Page 3, Line 94: "...classes convex functions..." -> "...classes of convex functions...".
- Page 3, Line 110: $J_{x_1}$ was not defined.
- Page 4, Line 132, Equation (6): "$[A, B] \in J$" -> "$[A, B] \in \mathcal J$".
- Page 4, Line 145: "...Jacobian of the fixed-point of $F_\theta$" is misleading -> "...Jacobian at the fixed-point of $F_\theta$" is more suitable perhaps.
- Page 5, Line 153: "...this a limit..." -> "...this is a limit...".
- Page 7, Line 220: "...Proposition~1, as well Corrollar~3..." -> Sentence does not look correct gramatically.
limitations: See Weaknesses. Other than that, in my opinion their work is sound.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors present a theoretical framework based on nonsmooth analysis concepts to analyze the asymptotic behavior of « piggyback » derivatives for nonsmooth iterations, i.e. how we can define the automatic differentiation of the iterates of unrolled iterations of an algorithm with nondifferential updates. Cases of practical interest include most popular proximal algorithms : proximal gradient descent, Douglas Rachford splitting and the ADMM. The authors show that a notion of set-valued Jacobians can be defined for these algorithms, and that they coincide with classical Jacobians almost everywhere. What is more, they show that, under suitable assumptions, the fixed point admits a derivative in this sence, and the derivatives of the iterates converge towards the derivatives of the fixed point. They prove, again under suitable assumptions, that there is a linear convergence of the derivatives towards those of the fixed point. They also show that this does not apply to other optimization methods with momentum, the given example being the heavy ball methods for which Jacobian iterates can become unstable for an objective that is not regular enough.
strengths_and_weaknesses: Strengths :

- The proposed framework gives a precise meaning to procedures that are now frequently used in practice of unrolling (potentially nonsmooth) iterative algorithms programmed in modern autodiff packages (Tensorflow, Pytorch, JAX…) and were shown to work and give good results when optimizing some of their parameters, but without a firm theoretical explanation of why it worked and the derivatives were well defined. In this sense, the work is a valuable theoretical contribution

- The linear convergene of piggyback derivatives is proven for a number of classical algorithms of interest, and is experimentally confirmed through simple examples. A counterexample is given, showing that one must be careful with momentum methods (though I assume that in most practical cases the functions will be regular enough for this not to happen).


Weaknesses :

- I believe the authors should have provided more references to works actually using piggyback derivatives of nonsmooth algorithms in different contexts, to give precide illustrations beyond the toy examples used in the experiments. This would strengthen the impact of the paper and point practical cases for which we now have guarantees.

- The presentation is clear enough to understand the general ideas, but the paper is not exactly self-sufficient. In particular, I believe one must already be very familiar with concepts developed in [12] to understand the tools that must be leveraged. Maybe it would have been nice to include a crash-course exposition to these concepts in the appendices.
questions: - Is it possible to find a case of practical interest where the heavy ball algorithm (or other momentum algorithms) will fail ? I feel like, from the example given, than in most cases the cost functions are regular enough for this not to happen, but I would appreciate to be proven wrong.

- How hard would the analysis get in the case where there are multiple fixed points of F ? E.g. when minimizing a nonconvex function ? I understand the analysis would get much more complex, and is probably out of the scope of the paper, but this could have been discussed a bit.
limitations: The authors state clearly the assumptions they need for their framework and discuss their relevance and connections to practical cases. Some important cases are not covered by the analysis, such as multiple fixed points (useful e.g. for nonconvex bilevel optimization), but this remark is quite minor since results in this case are scarce (to my knowledge) in the literature, and the analysis probably gets much harder. The connection to implicit differentiation is drawn and is interesting but unfortunately not equivalent to the piggyback differentation presented here.
review_title: null

Meta-review: metareview: The reviewers agreed that the paper has solid and novel technical contributions. Nevertheless, please consider elaborating more on the background of the techniques used in the revision, so that the paper is more self-contained.
confidence: Certain
Decision: Accept