Jérôme Bolte

Edouard Pauwels

Antonio Silveti-Falls

Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems

Keywords: Maximal monotone operator, monotone inclusion, generalized equation, implicit differentiation, differentiating solutions, Clarke subdifferential, generalized gradient, conservative field AMS subject classifications. 49J40, 49J52, 49J53, 49K40, 65K15, 68T07

We leverage path differentiability and a recent result on nonsmooth implicit differentiation calculus to give sufficient conditions ensuring that the solution to a monotone inclusion problem will be path differentiable, with formulas for computing its generalized gradient. A direct consequence of our result is that these solutions happen to be differentiable almost everywhere. Our approach is fully compatible with automatic differentiation and comes with assumptions which are easy to check, roughly speaking: semialgebraicity and strong monotonicity. We illustrate the scope of our results by considering three fundamental composite problem settings: strongly convex problems, dual solutions to convex minimization problems and primal-dual solutions to min-max problems.

Introduction

Consider the following parametric maximal monotone inclusion problem

0 ∈ A θ (x) + B θ (x) (1.1)
where θ is some parameter and, for each θ, A θ : R n ⇒ R n is maximal monotone (possibly set-valued) and B θ : R n → R n is maximal monotone and Lipschitz continuous. For a fixed θ, a problem of this form is called a generalized equation [START_REF] Robinson | Generalized equations and their solutions, Part I: Basic theory[END_REF] or variational inequality, and it models a wide range of optimization problems [START_REF] Beck | First-order methods in optimization[END_REF]. In fact, designing algorithms to find solution to maximal monotone inclusions is at the heart of convex optimization [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF][START_REF] Patrick L Combettes | Solving monotone inclusions via compositions of nonexpansive averaged operators[END_REF][START_REF] Patrick | Signal recovery by proximal forward-backward splitting[END_REF][START_REF] Radu Ioan Boţ | Inertial douglas-rachford splitting for monotone inclusion problems[END_REF][START_REF] Radu | An inertial forward-backward-forward primal-dual splitting algorithm for solving monotone inclusion problems[END_REF][START_REF] Palaniappan | Stochastic variance reduction methods for saddle-point problems[END_REF][START_REF] Malitsky | A forward-backward splitting method for monotone inclusions without cocoercivity[END_REF] and consequently has received a lot of attention in the last decades [START_REF] Auslender | Lagrangian duality and related multiplier methods for variational inequality problems[END_REF][START_REF] Heinz H Bauschke | Finding best approximation pairs relative to two closed convex sets in hilbert spaces[END_REF][START_REF] Borwein | Fifty years of maximal monotonicity[END_REF][START_REF] Attouch | Modern maximal monotone operator theory: From nonsmooth optimization to differential inclusions[END_REF]. Assuming that the solution x ⋆ (θ) is unique for each θ, our main objective in this paper is to investigate the regularity and differentiability of x ⋆ with respect to θ as well as to develop calculus rules for computing a generalized derivative associated to it. In general, the solution x ⋆ is not a function of θ because there can be several solutions for a given θ and, even under the assumption that x ⋆ is unique, it is not guaranteed that x ⋆ will be differentiable with respect to θ, therefore motivating further study. Understanding the regularity of x ⋆ as a function of θ has important applications in several areas: in deep learning for neural networks with implicit layers defined through monotone inclusions (e.g., monotone operator deep equilibrium networks [START_REF] Winston | Monotone operator equilibrium networks[END_REF], OptNet [START_REF] Amos | Optnet: Differentiable optimization as a layer in neural networks[END_REF]), in machine learning (hyperparameter tuning [START_REF] Bolte | Nonsmooth implicit differentiation for machine learning and optimization[END_REF], meta-learning [START_REF] Finn | Model-agnostic meta-learning for fast adaptation of deep networks[END_REF], dataset distillation [START_REF] Blondel | Efficient and modular implicit differentiation[END_REF], adversarial examples [START_REF] Liu | Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond[END_REF]), signal processing ( [START_REF] Patrick L Combettes | Solving monotone inclusions via compositions of nonexpansive averaged operators[END_REF][START_REF] Patrick | Signal recovery by proximal forward-backward splitting[END_REF][START_REF] Fadili | Monotone operator splitting for optimization problems in sparse recovery[END_REF]), and general nonsmooth bilevel optimization [START_REF] Ye | Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints[END_REF][START_REF] Wang | Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis[END_REF], without being exhaustive. For this reason, many other works have studied regularity properties of solutions to various forms of (1.1), using a myriad of different techniques that we will now discuss.

Variational analytic methods

The study of solution mappings to parametric generalized equations can be traced back to variational analysis in the 1980s [START_REF] Robinson | Generalized equations and their solutions, Part I: Basic theory[END_REF][START_REF] Stephen M Robinson | Generalized equations[END_REF]; [START_REF] Stephen M Robinson | Strongly regular generalized equations[END_REF] examined the Lipschitz continuity of the solution mapping when the single-valued monotone operator in the generalized equation is parametrized. This continued with results in [START_REF] King | Sensitivity analysis for nonsmooth generalized equations[END_REF][START_REF] Adam | Sentitivity analysis of solutions to generalized equations[END_REF][START_REF] Shapiro | Sensitivity analysis of generalized equations[END_REF] showing further the stability of the solution mapping but again avoiding parametrizing the nonsmooth/set-valued monotone operator. Another variational analytic approach is to use the notion of protodifferentiability developed in [START_REF] Tyrrell | Proto-differentiability of set-valued mappings and its applications in optimization[END_REF], which is used in [START_REF] Adly | Sensitivity analysis of maximally monotone inclusions via the protodifferentiability of the resolvent operator[END_REF] to analyze the stability of solutions to parametric monotone inclusions. This approach was extended in [START_REF] Wachsmuth | From resolvents to generalized equations and quasi-variational inequalities: existence and differentiability[END_REF] to show that the directional differentiability of the solution map under the assumption that the Lipschitz continuous operator is strongly monotone. Both of these works consider generalized equations and allow for both the Lipschitz and set-valued monotone operators to be parametrized, the same as the current work. In the language of sensitivity analysis, all data in the problem (1.1) can be perturbed. A similar approach to [START_REF] Adly | Sensitivity analysis of maximally monotone inclusions via the protodifferentiability of the resolvent operator[END_REF] is used in [START_REF] Berk | Lasso reloaded: a variational analysis perspective with applications to compressed sensing[END_REF] to analyze the Lipschitz constant of the solution mapping to the lasso problem as a function of the penalization parameter. Finally, we mention that similar methods have also been applied to study the differentiability of the prox operator in [START_REF] René | Generalized hessian properties of regularized nonsmooth functions[END_REF], which is a special case of a generalized equation in which the Lipschitz operator is identically 0.

Nonsmooth implicit differentiation

As was already discussed, implicit differentiation is an important tool for characterizing properties of the solution to monotone inclusion problems, yet its application to nonsmooth problems remains a challenge. Specific cases involving the lasso and partial smoothness have been analyzed in [START_REF] Bertrand | Implicit differentiation of lasso-type models for hyperparameter optimization[END_REF] using the weak derivative and in [START_REF] Skaldehaug | Geometric numerical integration for optimisation[END_REF][START_REF] Vaiter | The degrees of freedom of partly smooth regularizers[END_REF] using the Riemannian gradient. Other specific cases have been worked out for projections onto the cone of positive semidefinite matrices [START_REF] Malick | Clarke generalized jacobian of the projection onto the cone of positive semidefinite matrices[END_REF], or solutions of semidefinite programming problems [START_REF] Sun | The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications[END_REF], both of which use the Clarke implicit function theorem [START_REF] Frank | Optimization and nonsmooth analysis[END_REF] to deduce Lipschitz continuity of the solution. From a computational perspective, a software library has been developed in [START_REF] Blondel | Efficient and modular implicit differentiation[END_REF] that can be used for automatic differentiation of implicitly defined functions. As we shall see, our approach is strongly based on the path differentiable implicit function theorem of [START_REF] Bolte | Nonsmooth implicit differentiation for machine learning and optimization[END_REF] which comes with a calculus compatible with the Python library presented in [START_REF] Blondel | Efficient and modular implicit differentiation[END_REF].

Iterative differentiation/Unrolling Another growing field in which differentiation of solutions is fundamental is unrolling. In that case one wishes to find a solution of an optimization problem together with its derivative by differentiating some optimization algorithm with respect to external parameters. Pioneering works are [START_REF] Charles | Automatic differentiation and iterative processes[END_REF][START_REF] Beck | Automatic differentiation of iterative processes[END_REF] and also [START_REF] Griewank | Piggyback differentiation and optimization[END_REF]. In a machine learning context, research has been done for smooth algorithms setting in [START_REF] Pedregosa | Hyperparameter optimization with approximate gradient[END_REF][START_REF] Lorraine | Optimizing millions of hyperparameters by implicit differentiation[END_REF][START_REF] Mehmood | Automatic differentiation of some first-order methods in parametric optimization[END_REF] and in the nonsmooth setting in [START_REF] Bolte | Automatic differentiation of nonsmooth iterative algorithms[END_REF] for path differentiability, [START_REF] Mehmood | Fixed-point automatic differentiation of forward-backward splitting algorithms for partly smooth functions[END_REF] for partial smoothness, and [START_REF] Ochs | Bilevel optimization with nonsmooth lower level problems[END_REF] using a specific Bregman divergence. This is generally treated through ad hoc techniques, using for instance the smooth implicit function theorem approach. In [START_REF] Bolte | Automatic differentiation of nonsmooth iterative algorithms[END_REF], the approach is different and closer to ours as it uses the theory of conservative gradients. To understand the deep link this unrolling topic has with our present concerns, one needs to remind that iterates of algorithms are generally defined as solutions to a parametrized optimization problem. So unrolling offers a wide field of applications for solution's differentiation techniques. Although we illustrate our results on general parametrized problems, let us emphasize that our results could also provide results for "unrolling", in the spirit of the iterative differentiation analysis of [START_REF] Bolte | Automatic differentiation of nonsmooth iterative algorithms[END_REF].

Each approach has its benefits, e.g., the variational analytic methods exploiting protodifferentiability are more adapted to giving information about the Lipschitz constant of the solution mapping than what we will propose. The most salient point of our contribution is that we are able to guarantee the path differentiability of the solution, which legitimates, in turn, the use of formal derivatives of the solution. In contrast to nearly all of these works and many others on this subject, this means our approach is compatible with modern differential tools like automatic differentiation and the backpropagation algorithm. This compatibility is achieved by way of a flexible calculus that allows all the usual operations of smooth calculus, in particular, the chain rule for differentiation. In the language of the optimization community, our differential results are qualification-free, and, in terms of differential regularity, everything will boil down to checking that the problem is semialgebraic (or definable).

Our approach and its advantages

The general method we propose is to study the solution mapping x ⋆ by first rewriting (1.1) as a locally Lipschitz fixed-point equation, using ideas from operator splitting methods for nonsmooth optimization [START_REF] Patrick | Signal recovery by proximal forward-backward splitting[END_REF]. For generalized equations of the form given in (1.1), we can use the resolvent R A θ to write the forward-backward map H, which a solution must be a fixed point of:

x ⋆ = H(x ⋆ , θ) := R A θ (x ⋆ -B(x ⋆ )).
With this equation, we can continue by applying the nonsmooth implicit function theorem of [START_REF] Bolte | Nonsmooth implicit differentiation for machine learning and optimization[END_REF] to deduce regularity properties and an expression for the generalized derivative (i.e., the conservative mapping) of the solution mapping x ⋆ (θ).

As has been discussed, the rise in popularity of modern automatic differentiation libraries [START_REF] Abadi | {TensorFlow}: a system for {Large-Scale} machine learning[END_REF][START_REF] Bradbury | Jax: composable transformations of python+ numpy programs[END_REF][START_REF] Paszke | Pytorch: An imperative style, high-performance deep learning library[END_REF]] and their widespread use in machine learning calls for a flexible calculus at the crossroads of mathematics and computer science. For instance, almost the entire field of deep learning crucially relies on using the renowned backpropagation algorithm to do training. In spite of this, most prior work on this subject has either only considered the smooth case or has ignored non-differentiability issues. Thus a major advantage of the present approach, in contrast to other works, is to provide results that are broadly applicable (e.g., for nonsmooth solutions) but which are also compatible with automatic differentiation.

Besides compatibility with automatic differentiation, another advantage of our work is that the formula given by [START_REF] Bolte | Nonsmooth implicit differentiation for machine learning and optimization[END_REF]Corollary 1] to compute an implicit conservative gradient is formally the same as the formula used in the smooth case. More specifically, a key feature of [16, Corollary 1] that our results will inherit is its coherence with the smooth implicit function theorem -that is to say, elements of the conservative Jacobian associated to the solution mapping x ⋆ can be rigorously computed by formal differentiation just as in the smooth implicit function theorem.

Main results

Our key technical result is an implicit function theorem for families of contractive Lipschitz continuous equations under path-differentiability assumptions. The simplicity of the contractivity assumption allows us to derive a wealth of regularity results for parametric strongly monotone problems. Our core result (Theorem 3.5) asserts that if A θ or B θ is strongly monotone, then x ⋆ is path differentiable and there is a formula to compute a conservative Jacobian for it, based on the Clarke Jacobians of R γA θ and B θ . Let us insist on the fact that path differentiability easily follows from semi-algebraic or definable assumptions.

As a consequence, many fundamental parametrized optimization problems can be studied, we provide three important classes of examples. Theorem 4.2 deals with sum composite strongly convex optimization problems, which are ubiquitous in many fields from signal processing [START_REF] Patrick | Signal recovery by proximal forward-backward splitting[END_REF][START_REF] Day | On the inversion of diffusion nmr data: Tikhonov regularization and optimal choice of the regularization parameter[END_REF][START_REF] Weese | A reliable and fast method for the solution of fredhol integral equations of the first kind based on tikhonov regularization[END_REF] to machine learning [START_REF] Bishop | Training with noise is equivalent to tikhonov regularization[END_REF][START_REF] Sham M Kakade | On the complexity of linear prediction: Risk bounds, margin bounds, and regularization[END_REF]. In the framework of generalized convex duality, in the spirit of the Fenchel-Rockafellar theorem, we provide in Theorem 5.1 a regularity result for dual solutions to primal together with a calculus. In the min-max setting, under classical assumptions, we study the regularity of parametrize saddle points, this is Theorem 5.4. To be clear, the reach of our results extends beyond just these selected problems; our results represent a way to analyze solutions to any problem, which can be represented as a parametric monotone inclusion having this additive composite structure, encompassing a significant portion of the convex optimization problems in the literature.

Let us conclude by mentioning the fact the contractivity assumption which is behind our analysis in Lemma 3.4 is sharp in the sense that we are able to provide several counterexamples having apparently similar properties -as semialgebraic problems enjoying quadratic Łojasiewicz inequalities-which are not amenable to our optimization framework.

Organization of the Paper

In Section 2, we review the necessary background material and notation, mostly regarding convex analysis, conservative calculus, and the nonsmooth implicit function theorem for path differentiable functions. In Section 3, we develop results for path differentiability of the solution to parametric monotone inclusion problems, formally stating the monotone inclusion problem we consider and the assumptions needed to ensure path differentiability of the solution mapping. In Section 4, we turn to convex optimization and explore sufficient conditions in terms of properties of the objective function to ensure the solution to a convex optimization problem is path differentiable. In Section 5, we consider some general convex optimization problems and show how to apply the results of Section 3 and Section 4 to find expressions for implicit conservative Jacobians associated to the solution mappings. Finally, in Section 6, we conclude by noting some alternative formulations of the problem, its fixed point equations, and some other details that could have been chosen differently.

Background

Notation The set of real numbers will be written as R and the extended real numbers as R := R ∪ {+∞}. We denote the set of p-times continuously differentiable functions on a given connected open subset X ⊂ R n by C p (X) and denote the set of C 1 (X) functions whose gradient is Lipschitz continuous by C 1,1 (X). We will use Id n to denote the identity matrix in R n×n and Id to denote the identity mapping. A set-valued map A : R n ⇒ R m , is a function from R n to subsets of R m (including the empty set). The graph of a set-valued mapping A : R n ⇒ R m will be denoted gph A := {(x, u) ∈ R n × R m : u ∈ A(x)}. We denote the operator norm of a linear operator K : R n → R m as

K op := sup v∈R n Kv v
and extend this to sets of linear operators K = {K ω } ω∈Ω in the following way

K op := sup K∈K sup v∈R n Kv v .

Convex Analysis

The following definitions and notations coming from convex analysis are well-known and can be found, for instance, in [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF].

Definition 2.1 (Monotone Operator).

A set-valued mapping A : R n ⇒ R n is called monotone if there exists α ≥ 0 such that for all (x, u) ∈ gph (A) and (y, v) ∈ gph (A),

u -v, x -y ≥ α x -y 2 .
If α > 0 then A is called α-strongly monotone.

A monotone operator A is said to be maximal if its graph is not contained in any other monotone operator. Recall that the resolvent of a maximal monotone operator A θ : R n ⇒ R n is the function R A θ : R n → R n defined to be R A θ := (Id + A θ ) -1 . There is a special relationship between closed convex proper functions and maximal monotone operators, which we summarize in the next example.

Example 2.2. Let f : R n → R be a closed convex proper function, then the subdifferential of f , ∂f (x) := {u : ∀y ∈ R n , f (y) ≥ f (x) + u, y -x }, is a maximal monotone operator [START_REF] Rockafellar | On the maximal monotonicity of subdifferential mappings[END_REF] and the resolvent R ∂f is the prox operator [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Example 23.3] given by prox f (x) := argmin

u∈R n f (u) + 1 2 x -u 2 . Additionally, if f is α-strongly convex, then ∂f is α-strongly monotone [7, Example 22.3(iv)].

Conservative calculus and path differentiability

The following notions generalize the concept of differentiability to locally Lipschitz functions, from Clarke Jacobians to conservative Jacobians. In contrast with Clarke Jacobians, conservative Jacobians [START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF] offer a way to extend differentiation to locally Lipschitz functions in a way that is compatible with differential calculus.

Definition 2.3 (Clarke Jacobian).

The Clarke Jacobian of a locally Lipschitz function f : R n → R m at a point x is defined to be

Jac c f (x) := conv lim k→+∞ Jac f (x k ) : x k ∈ difff, lim k→+∞ x k = x ,
where difff ⊂ R n is the set of full measure where f is differentiable in the classical sense.

The following lemma comes from [28, Proposition 2.1.2(a)], it is a nonsmooth generalization of the classical result that a β-Lipschitz continuous differentiable function has gradient bounded by β in norm.

Lemma 2.4 ([28]). Let U ⊂ R n be an open set and consider a Lipschitz continuous function

f : U → R m .
Then f is Lipschitz continuous with constant β, if and only if, for all x ∈ U , Jac c f (x) op ≤ β.

Definition 2.5 (Conservative Jacobian [18]).

A conservative Jacobian for a locally Lipschitz function f : R n → R m is a set-valued mapping J f : R n ⇒ R m×n which is nonempty, locally bounded, graph closed, and satisfies, for any absolutely continuous curve γ :

[0, 1] → R n , ∀u ∈ J f (γ(t)), d dt f (γ(t)) = u, γ(t) for almost all t ∈ [0, 1]
A function f : R n → R m is called path differentiable if it is locally Lipschitz and admits a conservative Jacobian J f . This is equivalent to the Clarke Jacobian Jac c f being conservative for f . Path differentiable functions are ubiquitous among locally Lipschitz functions. The most prominent class of examples is that of semialgebraic functions. For an introduction to the subject of semialgebraic functions, we refer the interested reader to [START_REF] Coste | Istituti editoriali e poligrafici internazionali[END_REF]. We simply recall here that a function f : R n → R n is said to be semialgebraic if gph f is a semialgebraic set, i.e., it can be written as the finite union and-or intersection of polynomial equations and inequalities. Let us also mention that all locally Lipschitz definable functions are path differentiable, see [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF] and [START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF].

Given a path differentiable function f : R p+n → R n , we will write Jac c

x,f (θ, x)

:= {V : [U V ] ∈ Jac c f (θ, x)} ⊂ R n×n
and refer to this object as the Clarke Jacobian of f with respect to x (and the analog for when a conservative Jacobian has been specified). Similarly, we will write Jac c θ,f (θ, x)

:= {U : [U V ] ∈ Jac c f (θ, x)} ⊂ R n×p
for the Clarke Jacobian of f with respect to θ. A very important but subtle point is that these sets are the projections of the joint Clarke Jacobians, which are possibly distinct from the sets given by fixing θ and computing the conservative Jacobian or the Clarke Jacobian with respect to x alone.

The following nonsmooth implicit differentiation theorem from [16, Corollary 1] is the main tool with which we can prove path differentiability and calculate elements of conservative Jacobians of solutions to monotone inclusions. Its main requirements are a path differentiable defining equation f and an invertibility condition on the elements of a conservative Jacobian associated with f .

Theorem 2.6 (Conservative implicit function theorem [16]). Let

f : R n ×R m → R m be path differentiable with conservative Jacobian J f . Let (x, ŷ) ∈ R n × R m be such that f (x, ŷ) = 0. Assume that J f (x, ŷ) is convex and that, for each [U V ] ∈ J f (x, ŷ), the matrix V is invertible. Then, there exists an open neighborhood C × D ⊂ R n × R m of (x, ŷ) and a path differentiable function g : C → D such that, for each x ∈ C, f (x, g(x)) = 0
and g admits a conservative Jacobian given, for each x ∈ C, by

J g : x ⇒ {-V -1 U : [U V ] ∈ J f (x, g(x))}.
In contrast to the accessibility of the formulas involved, the invertibility condition needed to apply Theorem 2.6 is more difficult to verify than its smooth counterpart due to the fact that the ordinary gradient is a singleton while the conservative gradient is set-valued. Indeed, for smooth implicit differentiation, it suffices to check the invertibility of a single matrix, while in the nonsmooth setting, one is tasked with showing the invertibility of every element of a set of matrices. Additionally, the invertibility of the matrix computed in the smooth setting can be checked during runtime while, in the nonsmooth setting, checking the matrix computed at runtime will not be sufficient to ensure that the invertibility condition is holding (see [START_REF] Bolte | Nonsmooth implicit differentiation for machine learning and optimization[END_REF]Section 5]). For these reasons, it is imperative to have general sufficient conditions outlined which guarantee that the invertibility condition is satisfied, which is what we develop in the following sections.

Analogy with the Smooth Case One way to frame our work is as a study of how the calculus for solutions to smooth convex parametric optimization persists in nonsmooth convex parametric optimization thanks to conservative Jacobians. To explain this further, let us describe first a typical application of the smooth implicit function theorem to study convex parametric problems. Consider

min x∈R n f (θ, x)
where f : R p × R n is continuously differentiable jointly in (θ, x), twice-differentiable in x, and convex in x for all θ ∈ R p . To examine the existence and regularity of a solution mapping x ⋆ as a function of θ, one can use the smooth implicit function theorem on the optimality condition

∇ x f (θ, x ⋆ ) = 0 to get ∂x ⋆ ∂θ (θ) = -(∇ 2 x f (θ, x ⋆ (θ))) -1 ∂ ∂θ ∇ x f (θ, x ⋆ (θ)).
In addition to the differentiability assumptions we've made, the application of the smooth implicit function here requires the Hessian ∇ 2

x f (θ, x ⋆ ) to be invertible. For a twice-differentiable convex function, the invertibility of the Hessian ∇ 2

x f (θ, x) locally around x ⋆ is equivalent to the strong convexity of the function f locally around x ⋆ , which is itself equivalent to a local quadratic growth condition f (x) -f (y) -∇f (y), x -y ≥ ρ 2 x -y 2 for some ρ > 0, for all x, y in some neighborhood of x ⋆ . A byproduct of this paper is to investigate to what extent this trifold equivalency fails to hold when f is no longer assumed to be twice-differentiable. To this end, we are able to show positive and negative results in Section 4: strong convexity is sufficient to ensure the invertibility condition required by the nonsmooth implicit function theorem of [16, Corollary 1] holds, meanwhile a local quadratic growth condition is insufficient even when f is a semialgebraic function.

Solutions to monotone inclusions

Regularity assumptions and Lipschitz reformulations

A Lipschitz reformulation We begin this section by formally defining the parametric monotone inclusion problem we are considering (whose solution we seek to differentiate) and the assumptions we impose on it. When dealing with parametrized mappings like A : R m × R n → R n , it will be convenient to use subscript notation A θ to denote the mapping corresponding to A(θ, •) : R n → R n -this notation will be used frequently throughout the rest of the paper.

Assumption 3.1 (Path differentiability). Let

Θ ⊂ R p be a nonempty connected open set, A : Θ×R n → R n , B : Θ × R n → R n ,
and γ > 0 be a stepsize. For all θ ∈ Θ, assume the following two conditions hold, 1. A(θ, •) : R n ⇒ R n is maximal monotone and B(θ, •) : R n → R n is maximal monotone and locally Lipschitz. Furthermore the solution set to the following inclusion is nonempty

0 ∈ A(θ, •) + B(θ, •). (P mono )
2. The resolvent R γA θ and the map B are both locally Lipschitz and path differentiable, jointly in (θ, x), so that the function

H(θ, x) := R γA θ (x -γB θ (x)) (3.1)
is path differentiable jointly in (θ, x).

There are many different fixed-point reformulations of (P mono ) one can choose from, each one inducing a function H θ , which we discuss in Section 6. The Lipschitz mapping H θ we have opted for is reminiscent of the forward-backward splitting algorithm [START_REF] Lions | Splitting algorithms for the sum of two nonlinear operators[END_REF]. It is general enough to cover a variety of monotone inclusions coming from both smooth and nonsmooth convex optimization problems. Similar to the choice of H θ , the choice of the constant γ in Assumption 3.1 is also arbitrary provided γ is positive. Note also that the solution x ⋆ does not depend on γ, although it can be defined as a fixed point of H θ , which depends on γ. In each theorem, this constant will be finely tuned so as to obtain the most general regularity results possible. It is important to understand here that the regularity properties we will obtain in the following sections may depend on the reformulation in Assumption 3.1 that we have chosen. Whether it is the case or not is a matter for future research.

We define the residual function res : R p+n → R n to be res

(θ, x) := x -H θ (x) (P mono-bis ) so that res (θ, x * (θ)) = 0, (3.2)
whenever the expression is well-defined. An essential fact is that this equation will be automatically path differentiable if its constituents are semialgebraic, or more generally definable [START_REF] Coste | Istituti editoriali e poligrafici internazionali[END_REF][START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF][START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF]. Classically, this will also imply that the solution mapping is semialgebraic (as a set-valued mapping).

First-order properties of the residual equation Let us describe the key first-order objects that will ensure the existence of solution maps and allow us to establish their path-differentiability. We work under Assumption 3.1.

Set T : Θ × R n → R n to be T (θ, x) := R γA θ (x) and consider the two following conservative Jacobians relative to the path differentiable mapping H:

J H (θ, x) = { U -γV W V (Id n -γZ) : [U V ] ∈ Jac c T (θ, x -γB θ (x)), [W Z] ∈ Jac c B (θ, x)}. J x,H (θ, x) = Jac c x,T (θ, x -γB θ (x)) × (Id n -γJac c x,B (θ, x)). (3.3)
The first set valued map J H given in (3.3) is simply obtained by a formal application of the rules of differential calculus to the composite structure of H in Assumption 3.1 using Clarke Jacobians instead of classical Jacobians, while the second is a partial derivative version obtained by mere projection. Indeed, define S : Θ × R n → Θ × R n to be S(θ, x) := (θ, x -γB(θ, x)) so that T (S(θ, x)) = H(θ, x). One can check that J H is the following product of Clarke Jacobians for (θ, x)

∈ Θ × R n J H (θ, x) = Jac c T (S(θ, x)) × Jac c S (θ, x) = { U V × Id p 0 -γW Id n -γZ : [U V ] ∈ Jac c T (θ, x -γB θ (x)), [W Z] ∈ Jac c B (θ, x)} = { U -γV W V (Id n -γZ) : [U V ] ∈ Jac c T (θ, x -γB θ (x)), [W Z] ∈ Jac c B (θ, x)}
which is a conservative Jacobian for H. Consequently we have the following conservative Jacobian with respect to x for H, for each fixed

(θ, x) ∈ Θ × R n , J x,H (θ, x) = {V (Id n -γZ) : [U V ] ∈ Jac c T (θ, x -γB θ (x)), [W Z] ∈ Jac c B (θ, x)} = Jac c x,T (θ, x -γB θ (x)) × (Id n -γJac c x,B (θ, x)),
which concludes our explanation.

Let us now define a conservative Jacobian for the residual function res from (P mono-bis ) through:

J res (θ, x) = { γV W -U Id n -V (Id n -γZ) : [U V ] ∈ Jac c T (θ, x -γB θ (x)), [W Z] ∈ Jac c B (θ, x)}, for each (θ, x) ∈ Θ × R n .
Remark 3.2. The choice of J x,H (θ, x) in (3.3) corresponds to the set-valued object computed by applying formal differentiation, i.e., the chain rule, to H as a composition of functions. Additionally, the particular form of J x,H (θ, x) we consider above allows one to control J x,H (θ, x) op when one of the monotone operators A θ or B θ is strongly monotone, as we will expose later. In terms of the residual function res from (P mono-bis ), the choice made in (3.3) induces a particular conservative Jacobian J res and thus also a particular conservative Jacobian with respect to x,

J x,res (θ, x) = {Id n -V (Id n -γZ) : [U V ] ∈ Jac c T (θ, x -γB θ (x)), [W Z] ∈ Jac c B (θ, x)} = Id n -Jac c x,T (θ, x -γB θ (x)) × (Id n -γJac c x,B (θ, x)).

Contractivity implies the path differentiatiability of solutions

With this particular choice of conservative Jacobians for H and res given by (3.3), and under the additional assumption of strong monotonicity, we show below that a simple contractivity condition holds.

Definition 3.3 (Contractivity of residual equations).

Under Assumption 3.1, we shall say that the residual equation res = 0 is contractive, or has the contractivity property, if for each θ ∈ Θ, there is a solution x ⋆ (θ) to (P mono ) with

J x,H (θ, x ⋆ (θ)) op < 1
where we recall that H = Idres .

Contractivity in Definition 3.3 is key to applying nonsmooth implicit path differentiation, first because it actually warrants the well-posedness and the single-valuedness of the solution mapping ([7, Proposition 26.1], see as well [START_REF] Hiriart-Urruty | Tangent cones, generalized gradients and mathematical programming in banach spaces[END_REF]Theorem 11]), and also because it is closely related to the invertiblity condition required in the conservative implicit function theorem (Theorem 2.6).

The next lemma shows that contractivity is key to our approach to solutions of monotone inclusions.

Lemma 3.4 (Path differentiability of the solution map). Under Assumption 3.1 and assuming res has the contractivity property, then x ⋆ is unique, path differentiable on Θ, and admits a conservative Jacobian of the form

J x ⋆ : θ ⇒ {(Id n -V (Id n -γZ)) -1 (U -γV W ) : [U V ] ∈ Jac c T (θ, x ⋆ (θ) -γB θ (x ⋆ (θ))), [W Z] ∈ Jac c B (θ, x ⋆ (θ))}.
Proof. We begin with the uniqueness of x ⋆ for each θ ∈ Θ. By convexity of the operator norm, it holds

conv (J x,H (θ, x ⋆ (θ))) op ≤ J x,H (θ, x ⋆ (θ)) op < 1.
However, Jac c x,H (θ, x ⋆ (θ)) ⊂ conv (J x,H (θ, x ⋆ (θ))) and so Jac c x,H (θ, x ⋆ (θ)) op < 1. From this we conclude that H is locally a strict contraction around (θ, x ⋆ (θ)) and thus the solution x ⋆ (θ) is unique.

We will apply Theorem 2.6 to res using the pointwise convex hull (θ, x) ⇒ conv(J res (θ, x)) as a conservative Jacobian for res . Note that it is indeed conservative since J res is and pointwise convex hulls preserves Definition 2.5. We will use the shorthand notation conv(J x,res ) to denote for each fixed θ ∈ Θ the set valued map (θ, x) ⇒ conv(J res (θ, x)), and similarly for H. Note that conv(J x,res ) = Id n -conv(J x,H ).

Fix θ ∈ Θ. Let us show that the contractivity condition entails that every element of conv(J x,res (θ, x ⋆ (θ))) is invertible. Indeed, set ρ = conv(J x,H (θ, x ⋆ (θ))) op = J x,H (θ, x ⋆ (θ)) op < 1 (use triangle inequality), so that for any M res ∈ conv(J x,res (θ, x ⋆ (θ))), there is M H ∈ conv(J x,H (θ, x ⋆ (θ))) such that M res = Id n -M H , and for all v ∈ R n , we have

M res v = (Id n -M H )v ≥ v -M H v ≥ v (1 -ρ)
which shows that M res is invertible because ρ < 1. Since res is path differentiable and all of the elements of J x,res (θ, x ⋆ (θ)) are invertible for each θ ∈ Θ, the conditions to apply Theorem 2.6 to the equation res (θ, x ⋆ (θ)) = 0 hold, and thus x ⋆ is path differentiable on Θ. The formula for the conservative Jacobian follows from Theorem 2.6 because it defines a graph closed and locally bounded set valued map which is a subset of the set valued map obtained by applying Theorem 2.6 to conv(J res ) which satisfies the chain rule of Definition 2.5.

The expression for the conservative Jacobian of x ⋆ given in Lemma 3.4 can be more compactly expressed in terms of the conservative Jacobian of H defined in (3.3), for each θ ∈ Θ,

J x ⋆ : θ ⇒ {(Id n -V ) -1 U : [U V ] ∈ J H (θ, x ⋆ (θ))}.

Strongly monotone inclusions have path differentiable solutions

The following theorem is related to [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Prop. 26.16], which provides sufficient conditions for linear convergence of the forward-backward algorithm applied to finding a zero of the sum of two maximally monotone operators A and B. It is however important to observe that linear convergence is not enough to reach the same conclusions (see Section 4.2). Theorem 3.5 (Path differentiability: strongly monotone case). Under Assumption 3.1, consider (P mono ) and, for each θ ∈ Θ, assume that B θ is β-Lipschitz continuous and that either A θ or B θ is α-strongly monotone, for some α, β > 0, uniformly in θ.

Then, for γ ∈ 0, 2α (α+β) 2 , the residual map res of (P mono ) is contractive, i.e., the inequality in Definition 3.3 holds. Furthermore, x ⋆ is unique and path differentiable on Θ with a conservative Jacobian given for each θ ∈ Θ by

J x ⋆ : θ ⇒ {(Id n -V (Id n -γZ)) -1 (U -γV W ) : [U V ] ∈ Jac c T (θ, x ⋆ (θ) -γB θ (x ⋆ (θ))), [W Z] ∈ Jac c B (θ, x ⋆ (θ))}.
Proof. Under Assumption 3.1 with the conservative Jacobians given in (3.3), the forward-backward mapping H is path differentiable on Θ × R n with a conservative Jacobian with respect to x given by

J x,H (θ, x) = Jac c x,T (θ, x -γB θ (x)) × (Id n -γJac c x,B (θ, x)).
We take an arbitrary θ ∈ Θ and divide the proof into cases depending on whether A θ or B θ is α-strongly monotone.

Assume that B θ is α-strongly monotone with α ≤ β. Since α > 0 and 0 < γ < 2α (α+β) 2 < 2α β 2 , it holds that γ(2α -γβ 2 ) > 0, and furthermore γ(2α -γβ) ≤ γ2α < 4α 2 (α+β) 2 ≤ 1. Setting τ = 1 -γ(2α -γβ 2 ), we have that R γA θ is nonexpansive [7, Proposition 23.8] and Id-γB θ is τ -Lipschitz continuous with 0 ≤ τ < 1. Thus, by applying Lemma 2.4 for each (θ, x)

∈ Θ × R n , J x,H (x) op ≤ Jac c x,T (θ, x -γB θ (x)) op (Id n -γJac c x,B (θ, x)) op ≤ τ < 1.
Now we consider case where A θ is α-strongly monotone. We have by [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Proposition 23.13] that the resolvent R γA θ is Lipschitz continuous with constant 1 1+γα and the mapping Id -γB θ is 1 + γ 2 β 2 -Lipschitz continuous by Lemma A.1, giving for each

(θ, x) ∈ Θ × R n , J x,H (x) op = Jac c x,T (θ, x -γB θ (x)) op (Id n -γJac c x,B (θ, x)) op ≤ 1 + γ 2 β 2 1 + γα . Since γ ∈ 0, 2α (α+β) 2 , it holds 1 + γ 2 β 2 < 1 + γ(γ(α + β) 2 ) < 1 + 2αγ < 1 + γ2α + γ 2 α 2 = (1 + γα) 2 , so that √ 1+γ 2 β 2 1+γα < 1.
Putting everything together we find, for each

(θ, x) ∈ Θ × R n , J x,H θ (x) op = Jac c x,T (θ, x -γB θ (x)) op (Id n -γJac c B (θ, x)) op ≤ 1 + γ 2 β 2 1 + γα < 1.
We have established that J H θ (x) op < 1 for all (θ, x) ∈ Θ × R n in both cases of the theorem, and we have contractivity. By Lemma 3.4, x ⋆ is, therefore, path differentiable on Θ and the desired formula for the conservative Jacobian follows.

Remark 3.6 (On the constant γ).

The restriction on the values that γ can take in the different cases of Theorem 3.5 can be relaxed if more information about the operators A θ and B θ is specified. For instance, if B θ is β-cocoercive rather than β-Lipschitz and A θ is α-strongly monotone, then H θ is a contraction for any γ ∈ (0, 2β). It is important to notice that the choice of γ for implicit differentiation need not match the γ chosen for solving the problem (indeed, the algorithm to solve the problem and the fixed point equation for optimality need not match to begin with).

Path differentiation of solutions to convex optimization problems

Let Θ ⊂ R p be a connected open set and consider, for each θ ∈ Θ, the parametric optimization problem of finding a minimizer

x ⋆ := argmin

x∈R n f (θ, x) + g(θ, x) (P opt )
where

f θ := f (θ, •) ∈ C 1,1 (R n ) is convex and g θ := g(θ, •) is a closed convex proper function from R n to R.
It is well known [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Theorem 26.2] that this problem is equivalent to finding a zero x ⋆ of the sum of two monotone operators given by the subdifferentials of the functions,

0 ∈ ∇f θ (x ⋆ ) + ∂g θ (x ⋆ ).
In this way, the problem of differentiating a solution of (P opt ) is equivalent to the problem of the previous section -differentiating a solution to a monotone inclusion (P mono ). This equivalence motivates the following assumptions on (P opt ), which are analogous to Assumption 3.1 with the conservative Jacobians defined in (3.3) for the case where the monotone operators A θ and B θ are subdifferentials of closed convex proper functions.

Assumption 4.1. Let Θ be a connected open set and let γ > 0. For all θ ∈ Θ, let f θ := f (θ, •) ∈ C 1,1 (R n ) and g θ := g(θ, •) be closed convex proper functions from R n to R and assume that the prox operator prox γg θ : Θ × R n → R n and the gradient ∇f θ : Θ × R n → R n are both path differentiable, jointly in (θ, x).

A sufficient condition guaranteeing the path differentiability in Assumption 4.1 holds is to assume that f and g are semialgebraic functions. Under Assumption 4.1, one can consider A θ = ∂g θ and B θ = ∇f θ so that Assumption 3.1 is met and H is the forward-backward algorithm applied to (P opt ). Using the conservative Jacobians defined in (3.3), we have in this case for all (θ, x)

∈ Θ × R n J H (θ, x) = { U -γV W V (Id n -γZ) : [U V ] ∈ Jac c prox γg θ (θ, x -γ∇f θ (x)), [W Z] ∈ Jac c ∇f θ (θ, x)} J x,H (θ, x) = Jac c x,prox γg θ (θ, x -γ∇f θ (x)) × (Id n -γJac c x,∇f θ (θ, x)). (4.1)
For the moment, we do not explicitly assume that the solution x ⋆ to (P opt ) is unique for each θ ∈ Θ; the results in later sections will make stronger assumptions that imply the uniqueness of x ⋆ as a byproduct. We shall also provide assumptions on g θ and f θ that will ensure the invertibility condition of Theorem 2.6 holds at the solution x ⋆ (θ).

Solutions of strongly convex problems

Recall that the subdifferential of a strongly convex function is strongly monotone [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Example 22.4]. As a consequence of Theorem 3.5 for strong monotonicity, we can then formulate the following analgous result for (P opt ) with strong convexity of f θ or g θ . Theorem 4.2 (Path differentiability: strongly convex case). Let Assumption 4.1 hold with the conservative Jacobians given in (4.1) and consider (P opt ) for θ ∈ Θ. Denote β > 0 a Lipschitz constant of ∇f θ which is assumed to be uniform in θ. Assume that either f θ or g θ is α-strongly convex with α > 0 which is also assumed to be uniform in θ. Then, for γ = α (α+β) 2 , the solution x ⋆ (θ) is unique for each θ ∈ Θ and path differentiable on Θ with a conservative Jacobian given by

J x ⋆ : θ ⇒ {(Id n -V (Id n -γZ)) -1 (U -γV W )} where [U V ] range in Jac c T (θ, x ⋆ (θ) -γ∇f θ (x ⋆ (θ))) and [W Z] in Jac c ∇f θ (θ, x ⋆ (θ)).
Proof. Due to Assumption 4.1, the function res (θ, x) is path differentiable on Θ × R n ; fix an arbitrary θ ∈ Θ. Since f θ : R n → R and g θ : R n → R are closed convex proper functions, ∇f θ and ∂g θ are maximal monotone operators [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Example 22.4]. Furthermore, since one of f θ or g θ is α-strongly convex, one of the operators ∇f θ or ∂g θ is α-strongly monotone and Theorem 3.5 can be applied with A θ = ∂g θ and B θ = ∇f θ , yielding the path differentiability of x ⋆ and the formula for its conservative Jacobian on Θ.

The choice of γ can be relaxed to be any value in 0, 2α (α+β) 2 without issue, we have simply taken α (α+β) 2

for convenience. In contrast to some prior work, e.g., [START_REF] Jalal | Sensitivity Analysis for Mirror-Stratifiable Convex Functions[END_REF], we allow for both f θ and g θ to be parametrized functions, rather than just one or the other.

Beyond strong convexity?

Strong convexity may be generalized by means of quadratic growth conditions, such as global error bounds [START_REF] Pang | Error bounds in mathematical programming[END_REF] or equivalently KL inequality [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF]. On the other hand, quadratic Łojasiewicz inequality, quadratic error bound, turn out to be equivalent to linear convergence of forward-backward iterations under mild conditions; one may consult, for instance, [START_REF] Garrigos | Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry[END_REF]. Since contractivity obviously implies linear convergence, it is tempting to think that it could be somehow inserted into the equivalence chain. This would be a natural path beyond strong convexity assumptions. This calls, for instance, for the following question: Does the contractivity of res always hold if f and g are such that H is linearly convergent to a unique fixed point? An element of motivation is that in the smooth case, when f is C 2 and g = 0, contractivity is indeed equivalent to (4.2) as discussed in Section 2, so that the questions relates to extension of this equivalence to the nonsmooth setting.

Linear convergence of the forward-backward mapping can simply be formulated as follows: for a fixed θ ∈ Θ there exists ρ ∈ (0, 1), such that, for all x,

H(θ, x) -x ⋆ (θ) ≤ ρ x -x ⋆ (θ) . (4.2)
We provide below two examples having this property while being non strongly convex contradicting contractivity of res . The first one has C 1,1 objective (g = 0), while the second is nonsmooth Proposition 4.4 (f = 0). This answers negatively to the above question.

Let us start with the differentiable case for which H reduces to a gradient step.

Proposition 4.3 (Linear convergence does not imply contractivity I). There exists a convex semialgebraic function

h ∈ C 1,1 (R 2 )
with ∇h 1-Lipschitz and x -∇h(x) ≤ ρ x for all x for some ρ ∈ (0, 1), such that h is not strongly convex locally around 0 and Jac c ∇h (0) contains singular matrices.

Proof. Let Q ⊂ R 2 be a closed convex set with 0 ∈ int(Q) and a smooth boundary so that there is a differentiable outer pointing unit normal vector n ∈ C 1 (bd(Q)). We consider the gauge function

Ψ Q associated to Q Ψ Q (x) = inf{λ > 0 : x ∈ λQ}.
The gauge function Ψ Q [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Example 8.36] is the unique positively homogeneous function such that the sublevel set of level 1 is Q [7, Corollary 14.13]. Furthermore, the sublevel sets of Ψ Q of level λ ≥ 0 are equal to λQ. For x ∈ R 2 , we extend n(x) to be the outer pointing normal vector to the set Ψ Q (x)Q at x, it defines a C 1 function on R 2 . The gradient of Ψ Q for x = 0 has to be of the form α(x)n(x) for a positive function α. By homogeneity, we have for small t

Ψ Q x 1 + t Ψ Q (x) -Ψ Q (x) t = 1 = x Ψ Q (x) , ∇Ψ Q (x) = α(x) x Ψ Q (x)
, n(x) from which we obtain

∇Ψ Q (x) = Ψ Q (x) x, n(x) n(x).
Since n is homogeneous of order zero, so is ∇Ψ Q . We have for x = 0

Jac ∇Ψ Q (x) = Jac x → ∇Ψ Q x Ψ Q (x) = Jac ∇Ψ Q (x/Ψ Q (x)) Id n Ψ Q (x) - x∇Ψ Q (x) T Ψ Q (x) 2 . Now set h(x) = Ψ Q (x) 2 /2, which is convex and C 1 since ∇h(x) = Ψ Q (x)∇Ψ Q (x)
is a continuous function. We have for x = 0

Jac ∇h(x) = ∇Ψ Q (x)∇Ψ Q (x) T + Ψ Q (x)Jac ∇Ψ Q (x/Ψ Q (x)) Id n Ψ Q (x) - x∇Ψ Q (x) T Ψ Q (x) 2 = ∇Ψ Q (x)∇Ψ Q (x) T + Jac ∇Ψ Q (x/Ψ Q (x)) Id n - x∇Ψ Q (x) T Ψ Q (x) .
This expression remains bounded which shows that ∇h is Lipschitz and we may assume by rescaling that its Lipschitz constant is 1. Set for all x, x + = x -∇h(x), we have using standard arguments in the analysis of gradient descent on h, whose global minimum is the origin, that

2h(x + ) + x + 2 ≤ x 2 .
We have that h is positively homogenoeous of degree 2 so that

h(x + ) = x + 2 h(x + ) x + 2 = x + 2 h x + x + ≥ x + 2 min y =1 h (y) ,
where the minimum is attained and is positive, call it c > 0. All in all, we have

x -∇h(x) ≤ 1 √ 1 + 2c x ,
so that the constructed function complies with hypotheses of the Lemma, independently of Q. By definition of the gauge function, the sublevel sets of Ψ Q are of the form λQ for λ ∈ R. If h was strongly convex locally around 0, one would have that its sublevel sets are also strongly convex (positively curved). This is not the case, for example if Q is a square with smoothed corners. This shows that h is not necessarily locally strongly convex. To ensure h is semialgebraic, it suffices to take Q a semialgebraic square with smoothed corners.

We conclude with the following implication: if Jac c ∇h (0) contains only nonsingular elements then h is strongly convex locally around 0. Indeed in this case Jac c ∇h (x) contains only positive definite elements for all x in a convex compact neighborhood of 0, set λ > 0 a lower bound on the minimum eigenvalue in this neighborhood (which exists by graph closedness and continuity of the smallest eigenvalue), we have by (Aumann) integration in Definition 2.5 using conservativity of Jac c ∇h , for all x, y in this neighborhood,

∇h(x) -∇h(y), x -y = 1 0 Jac c ∇h ((1 -t)x + ty)(x -y)dt, x -y = 1 0 Jac c ∇h ((1 -t)x + ty)dt(x -y), x -y ≥ λ x -y 2 ,
which means strong monotonicity of ∇h, equivalent to strong convexity of h. By contraposition, if h is not locally strongly convex around 0, then, Jac c ∇h (0) contains singular matrices.

Proposition 4.3 shows that the equivalence between contractivity and (4.2) does not hold in the C 1,1 case, higlighting a gap between C 1,1 and C 2 functions. This actually extends to the nonsmooth setting with a proximal point step using convex analysis and Moreau enveloppes.

Proposition 4.4 (Linear convergence does not imply contractivity II).

There exists a convex semialgebraic function g : R 2 → R such that g(0) = 0, prox g is path differentiable, and, for some 0 < ρ < 1, prox g (x) ≤ ρ x for all x, such that, for any convex conservative Jacobian J prox g , not every element of Id 2 -J prox g (0) is invertible.

Proof. Let h ∈ C 1,1 (R 2
) be a function given by Proposition 4.3, it is convex and semialgebraic with ∇h 1-Lipschitz, path differentiable, and x -∇h(x) ≤ ρ x for some ρ ∈ (0, 1) such that h is not strongly convex locally around 0 and Jac c ∇h (0) contains singular elements. The function h :

x → x 2 2 -h(x) is convex [7, Theorem 18.15 (vi)] with 1-Lipschitz gradient. Recall that the conjugate of h is h * (x) : x → sup u x, u -h(u). The function g : x → h * (x) -x 2
2 is convex and semialgebraic, because h * is 1-strongly convex and semialgebraic [START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF]Proposition 10.8]. It satisfies prox g (x) = ∇ h(x) = x -∇h(x) [7, Corollary 24.5], so that the gradient descent mapping for h with unit step size is equivalent to the prox operator for g.

Thus for all x, prox g (x) = x -∇h(x) ≤ ρ x for some ρ ∈ (0, 1), prox g is path differentiable, and J ∇h := Id 2 -J prox g is a convex conservative Jacobian for ∇h. Finally, by contraposition, Id 2 -J prox g (0) = J ∇h (0) which contains at least one singular elemen by Proposition 4.3 using the fact that Jac c ∇h (0) ⊂ J ∇h (0) by convexity of J ∇h (0). for some λ > 0 and for all x (see [START_REF] Pang | Error bounds in mathematical programming[END_REF] and references therein) as well as global Kurdyka-Łojasiewicz inequality

min v∈∂g(x) v ≥ λ ′ g(x) -min z g(z)
for some λ ′ > 0 and for all x (see [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF] and references therein). In our setting (coercive, semialgebraic, unique critical value), these conditions are equivalent and are sufficient for (4.2) to hold true [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF]. On the other hand, (4.2) implies a quadratic Łojasiewicz inequality (KL with exponent 1/2) or a global quadratic error bound in our setting [START_REF] Garrigos | Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry[END_REF]Proposition 4.19]. Since all these conditions are equivalent the results of this section actually hold true replacing (4.2) by a quadratic error bound or a quadratic Łojasiewicz inequality showing a fundamental limit to the extension of Theorem 4.2 beyond strong convexity.

Applications to saddle point problems and duality

We demonstrate how to apply the previous sections' results to several different parametric optimization problems in which one seeks to differentiate the solution mapping as a function of the parameters θ. In each of the following subsections, Θ ⊂ R p is a connected open set on which Assumption 4.1 will be required to hold for various operators.

Differentiating the dual solution of a convex composite problem

Consider the following composite minimization problem

min x∈R n f θ (x) + g θ (K θ x) (5.1)
where, for each θ ∈ Θ, f θ ∈ C 1,1 (R n ) is a strongly convex function, g θ : R m → R is a proper closed convex function, K θ : R n → R m is a surjective linear operator, and x ⋆ (θ) is the unique solution (the objective is proper by surjectivity).

The goal is to differentiate the solution x ⋆ with respect to θ, for which we assume that ∇f θ and prox γg θ are path differentiable, jointly in (θ, x), so that Assumption 4.1 holds here. It is then possible to directly apply Theorem 4.2 to differentiate x ⋆ since Assumption 4.1 holds and f θ is strongly convex. However, because of the coupling between g θ and K θ in (5.1), computing J x ⋆ through this approach would necessitate computing prox g θ •K θ , which is nontrivial even when prox g θ is known (unless K θ is a (semi)orthogonal matrix [START_REF] Patrick | Signal recovery by proximal forward-backward splitting[END_REF]Lemma 2.8]).

We can instead use the generalized duality of Fenchel-Rockafellar, which will decouple the linear operator Proof. For each θ ∈ Θ, the function g * θ : R m → R is a closed convex proper function since g θ is, meanwhile the function f * θ : R n → R is 1 β -strongly convex and differentiable with

(-K * θ y) - λ 2 2β y 2 = f * θ (-K * θ y) - 1 2β K * θ y 2 + 1 2β K * θ y 2 - λ 2 2β y 2 .
The first term, f * θ (-K * θ y)- Corollary 2] with ∇f * θ = (∇f θ ) -1 , the assumptions of which hold due to the fact that ∇f θ is path differentiable and f * θ is both Lipschitz-smooth and strongly convex.

Example 5.3 (Learning sparsity priors).

The problem of learning a sparsity prior can be seen as a bilevel optimization problem [START_REF] Ghanem | Supervised learning of analysis-sparsity priors with automatic differentiation[END_REF][START_REF] Peyré | Learning analysis sparsity priors[END_REF][START_REF] Ravishankar | Sparsifying transform learning with efficient optimal updates and convergence guarantees[END_REF] which fits the framework of this subsection. Given some set of training data {(u 1 , û1 ), . . . , (u q , ûq )} where u i is the ground truth for some signal (e.g., an image) and ûi is a noisy observation of u i , we seek to find an optimal linear operator K θ ∈ R s×n , the so-called sparsity prior. The general form of the problem can be cast as the following bilevel optimization problem,

min θ∈R p q i=1 1 2 u i -x i (θ) 2 2
such that, ∀i ∈ {1, . . . , q} , x i (θ) ∈ argmin

x i ∈R n 1 2 x i -ûi 2 2 + K θ x i 1 where θ ∈ R sn with K θ :=    θ 1,1 . . . θ 1,n . . . . . . . . . θ s,1 . . . θ s,n   . Assume that Θ ⊂ R sn is a connected open set such that,
for all θ ∈ Θ, K θ is surjective and its singular values are contained in [λ, λ] for some 0 < λ ≤ λ. Then the lower level problem matches exactly that of (5.1) with

f θ (x) = q i=1 1 2 x i -ûi 2 2 and g θ (x) = q i=1 1 2 K θ x i 1
, which we write here as sums even though they are separable in x i . Note that K θ is obviously not surjective for all θ ∈ R sn because of the general parametrization chosen. Instead of fixing the required open set Θ, one could employ a different parameterization of K θ with constraints on parameters ensuring that K θ remains surjective. Regardless, by assuming surjectivity, Theorem 5.1 applies and we can continue.

The dual of the inner problem, is given, for each i ∈ {1, . . . , q}, by

y i (θ) ∈ argmin {y i ∈R s : y i ∞ ≤1} 1 2 K * θ y i -ûi 2 2
which has a fixed point equation

y ⋆ i = P D (y ⋆ i + γK θ (K * θ y ⋆ i -ûi )),
where P D is the projection onto the ℓ ∞ unit ball in R s , i.e., the mapping whose coordinates are given by z → sign(z) min(1, |z|) component-wise. Using the notation of Section 3, we have T (θ, y i ) = P D (y i ) and S(θ, y) = y ⋆ i + γK θ (K * θ y ⋆ i -ûi ). The primal solution x ⋆ can be recovered from the dual solution through the relationship given in Remark 5.2, for each θ ∈ Θ and i ∈ {1, . . . , q},

x ⋆ i (θ) = ∇f * θ (-K * θ y ⋆ i (θ)) =⇒ x ⋆ i (θ) = ûi -K * θ y ⋆ i (θ).
We emphasize the difference in our approach to those taken in previous works [START_REF] Ghanem | Supervised learning of analysis-sparsity priors with automatic differentiation[END_REF][START_REF] Peyré | Learning analysis sparsity priors[END_REF][START_REF] Ravishankar | Sparsifying transform learning with efficient optimal updates and convergence guarantees[END_REF]. While [START_REF] Peyré | Learning analysis sparsity priors[END_REF] relies on a smoothing process for the ℓ 1 -norm in the lower level problem, [START_REF] Ravishankar | Sparsifying transform learning with efficient optimal updates and convergence guarantees[END_REF] assumes that K θ is an orthogonal matrix in contrast to our assumption that K θ is surjective. In [START_REF] Ghanem | Supervised learning of analysis-sparsity priors with automatic differentiation[END_REF], the authors use unrolling on the algorithm used to solve the lower-level problem rather than implicit differentiation as we do.

Differentiating the solutions of min-max problems

Consider the following min-max problem

min x∈X max y∈Y Φ θ (x, y) (5.4)
where X ⊂ R n is closed and convex, and Y ⊂ R m is convex compact and, for each θ ∈ Θ, Φ θ : R n × R m → R is continuous such that -Φ θ (x, •) : R m → R and Φ θ (•, y) : R n → R are α-strongly convex for each x and for each y, respectively. Assume also that Φ

(•) (x, y) is Lipschitz continuous on Θ for all (x, y) ∈ R n × R m .
The very general form of this problem encompasses min-max problems with nonlinear couplings of the form considered in [START_REF] Yazdandoost | A primal-dual algorithm for general convex-concave saddle point problems[END_REF][START_REF] Yazdandoost | A primal-dual algorithm with line search for general convex-concave saddle point problems[END_REF]. The solution mapping for this problem incorporates the primal and dual variables together, θ → (x ⋆ (θ), y ⋆ (θ)). The optimality condition can be written for each θ ∈ Θ as

0 0 ∈ ∂ x Φ θ + N X 0 0 -∂ y Φ θ + N Y x ⋆ (θ) y ⋆ (θ)
where N X and N Y denote respectively the normal cones to X and Y . This is a special case of (P mono ) with

A θ = ∂ x Φ θ + N X 0 0 -∂ y Φ θ + N Y
and B θ ≡ 0. Indeed from strong convexity, for each θ ∈ Θ, A θ is α strongly monotone, and from closedness of X and compactness of Y it can be shown that the range of

I + A θ is R n × R m so that A θ is maximal [69, Theorem 12.12].
For the function H θ defined in Assumption 3.1 applied to this problem, we have H θ (x) = R A θ (x) so that res (θ, x) = x -R A θ (x), leading to the following result. Theorem 5.4 (Path differentiability of min-max solutions). Consider (5.4) where, for each θ ∈ Θ, -Φ θ (x, •) : R m → R and Φ θ (•, y) : R n → R are both closed α-strongly convex proper functions. Assume that R A θ is path differentiable so that Assumption 3.1 holds with the conservative Jacobians defined in (3.3) with γ ∈ (0, 1/α). Then, the solution mapping θ → (x ⋆ (θ), y ⋆ (θ)) is unique and path differentiable on Θ with a conservative Jacobian given for each θ ∈ Θ by

J (x ⋆ ,y ⋆ ) : θ ⇒ { Id (n+m) -[V 1 V 2 ] -1 U : [U V 1 V 2 ] ∈ Jac c T (θ, (x ⋆ (θ), y ⋆ (θ)))}.
Proof. For each θ ∈ Θ, the maximal monotone operator A θ is α-strongly monotone by the α-strong convexity and α-strong concavity of Φ θ (•, y) and Φ θ (x, •) respectively. Using this fact with Assumption 3.1 and the conservative Jacobians defined in (3.3), we can apply Theorem 3.5 with any β ∈ (0, ∞) since B θ ≡ 0.

In particular, we can take β = ( √ 2 -1)α so that applying Theorem 3.5 requires γ ∈ (0, 1/α). Therefore, the solution (x ⋆ (θ), y ⋆ (θ)) is path differentiable with a conservative Jacobian given by

J (x ⋆ ,y ⋆ ) : θ ⇒ { Id (n+m) -[V 1 V 2 ] -1 U : [U V 1 V 2 ] ∈ Jac c T (θ, (x ⋆ (θ), y ⋆ (θ)))}.

Differentiating the solutions of primal-dual problems

The min-max problem (5.4) from the previous subsection is general in that it does not assume a particular coupling between x and y. We turn now to primal-dual optimization with linear coupling, a well-known problem template that was studied, for instance, in [START_REF] Chambolle | Accelerated bregman primal-dual methods applied to optimal transport and wasserstein barycenter problems[END_REF][START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF][START_REF] Chambolle | On the ergodic convergence rates of a first-order primal-dual algorithm[END_REF][START_REF] Condat | A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms[END_REF][START_REF] Liang | Local linear convergence analysis of primal-dual splitting methods[END_REF][START_REF] Silveti-Falls | A stochastic bregman primal-dual splitting algorithm for composite optimization[END_REF]] and allows to model many different problems coming from computer vision and machine learning. Consider the parametrized primal-dual problem

min x∈R n g θ (x) + max y∈R m K θ x, y -f * θ (y) (5.5)
where, for all θ ∈ Θ, K θ ∈ R m×n is a linear operator and both f * θ : R m → R and g θ : R n → R are closed convex proper functions. In contrast to [START_REF] Chambolle | Learning consistent discretizations of the total variation[END_REF][START_REF] Bogensperger | Convergence of a Piggyback-style method for the differentiation of solutions of standard saddle-point problems[END_REF], we allow for the functions g θ and f * θ to be parametrized by θ, in addition to the linear operator K θ . For each θ ∈ Θ, the optimality conditions for a solution (x ⋆ (θ), y ⋆ (θ)) to this problem are

K θ x ⋆ (θ) ∈ ∂f * θ (y ⋆ (θ)) and -K * θ y ⋆ (θ) ∈ ∂g θ (x ⋆ (θ))
which can be equivalently written as As in [START_REF] Bogensperger | Convergence of a Piggyback-style method for the differentiation of solutions of standard saddle-point problems[END_REF] and [START_REF] Chambolle | Learning consistent discretizations of the total variation[END_REF], we have assumed that both g θ and f * θ are strongly convex; in contrast to [START_REF] Bogensperger | Convergence of a Piggyback-style method for the differentiation of solutions of standard saddle-point problems[END_REF] we do not assume that prox g θ or prox f * θ are differentiable at any specific points, nor do we assume that g θ or f θ are twice differentiable as in [START_REF] Chambolle | Learning consistent discretizations of the total variation[END_REF].

In [START_REF] Chambolle | Learning consistent discretizations of the total variation[END_REF] the authors consider using a bilevel optimization problem to learn the best discretization of the total variation for inverse problems in imaging. The proposed bilevel problem was further studied in [START_REF] Bogensperger | Convergence of a Piggyback-style method for the differentiation of solutions of standard saddle-point problems[END_REF] where the authors noted the theoretical difficulties in differentiating the solution to a nonsmooth optimization problem with respect to some parameters. Indeed, they have no guarantees that their algorithm will avoid the set of points where the prox operator is not differentiable, nor can they show that the solutions will be points of differentiability. On the other hand, so long as the prox operator is path differentiable, our results apply despite these obstacles, and one can compute implicit conservative gradients.

Automatic differentiation of algorithms

The results of Theorem 3.5 (in particular, the fact that res is contractive) imply that the forward-backward splitting algorithm applied to solve monotone inclusions of the form in the theorem will converge linearly for γ ∈ 0, 2α 2 (α+β) 2 . We illustrate our results with implicit differentiation which only requires the solution of the inclusion problem and does not depend on the algorithm used to solve it. Yet, it is worth emphasizing that under Assumption 3.1, the contractivity property in Definition 3.3 is sufficient to apply the convergence result of [START_REF] Bolte | Automatic differentiation of nonsmooth iterative algorithms[END_REF] to the forward-backward algorithm in our context. More precisely, Definition 3.3 is precisely the same as [START_REF] Bolte | Automatic differentiation of nonsmooth iterative algorithms[END_REF]Assumption 1] applied to the forward-backward algorithm to solve (1.1). Therefore, in addition to path differentiability of the solution map, assumptions of Theorem 3.5 provide a sufficient condition to ensure that automatic differentiation of the forward-backward algorithm generates a sequence of conservative jacobians such that conservativity is preserved asymptotically: the limits of iterative differentiation conservative jacobians form a conservative jacobian for the solution of (1.1) [19, Corollary 1 and 2].

As a consequence, Theorem 3.5 implies that the iterative derivative convergence results of [START_REF] Bolte | Automatic differentiation of nonsmooth iterative algorithms[END_REF] apply to the forward-backward algorithm in all special cases described in the paper: Theorem 4.2 for strongly convex optimization problems, Theorem 5.1 for solutions to primal problems obtained from their dual, Theorem 5.4 for general strongly monotone saddle point problems and Theorem 5.5 for strongly monotone structured saddle point problems.

Conclusion

We have presented sufficient conditions in the form of strong monotonicity, under which the path differentiability of the solution to a monotone inclusion problem is satisfied. As special cases, we have derived conditions that ensure path differentiability of solutions to a large class of nonsmooth parametric convex optimization problems -those which can be written as the sum of two parametric convex functions, one smooth and one possibly nonsmooth. By expressing the monotone inclusions as equivalent fixed point equations using the resolvent mapping, we were able to leverage path differentiability and the recently developed nonsmooth implicit path differentiation theorem of [START_REF] Bolte | Nonsmooth implicit differentiation for machine learning and optimization[END_REF]Corollary 1] to deduce regularity of x ⋆ . Most importantly, we were able to characterize and give a formula for a conservative Jacobian of x ⋆ with respect to θ using only the Clarke Jacobians associated with the resolvent mapping R γA θ and the operator B θ .

While this work is primarily theoretical, our results also lend insight to practical applications, e.g., the design of implicit neural network layers defined using convex optimization problems. Ensuring that an implicit layer is compatible with training is an important part of implicit layer design and, consequently, ensuring the invertibility condition is a necessary part of guaranteeing that training will work (c.f., [START_REF] Bolte | Nonsmooth implicit differentiation for machine learning and optimization[END_REF]Section 5]). Besides this, our results highlight the relevancy of the typical strong convexity assumption made on the lower-level problem of a bilevel optimization problem to ensure implicit conservative Jacobians will exist when this lower-level problem is nonsmooth.

It is important also to understand the dependence of x ⋆ on the step size γ taken in the definition of H. In the smooth case, where A θ ≡ 0 and B θ = ∇f θ for some twice differentiable convex function f θ , there is no dependence on γ which is to be expected since 0 = B θ (x ⋆ ) can be differentiated directly without introducing γ. We delay exploring such questions for future work.

At a few points in the paper, we encounter objects which are not canonical or which can be chosen in multiple ways. We collect here these instances and elaborate on why we've chosen the way we have and the possible consequences of choosing to formulate things differently.

Choice of H Our selection for H in res can be attributed to the additive structure of A θ + B θ and the Lipschitz continuity of B θ . There are alternatives, for instance, considering the resolvent directly R A θ +B θ or considering Douglas-Rachford, Peaceman-Rachford, etc, and extensions of this flavor are a matter for future research.

Choice of J H We use multiplication of Clarke Jacobians in the formula for J H given in (3.3) because it allows to obtain sufficient condition on problem data in (P mono ) to ensure the contractivity of the residual equation. On the other hand, all the corollaries of the paper would hold similarly with arbitrary conservative Jacobians for R γA and B combined in a similar way, provided that this is compatible with the contractivity in Definition 3.3. However, in this case, the contractivity defined in Definition 3.3 has to be explicitly assumed, not deduced from properties of problem data, because conservative Jacobians can be changed on a set of measure zero.

Choice of Θ

The set Θ could be the whole space R p or possibly a subset, for example if one of the operators A θ or B θ is not defined for every θ ∈ R p , or if some of conditions (Lipschitz continuity, strong monotonicity, etc) can only be ensured to hold on some subset. The set Θ can also be taken as a neighborhood of some point θ ∈ R p of interest, in which case it's possible to obtain local versions of all of our later results. For these local versions, we need only to assume that the contractivity in Definition 3.3 holds at the single point θ, from which it follows that there is some open neighborhood Θ on which the inequality must hold.

Remark 4 . 5 (

 45 On local growth conditions). The result of this section may be refined by considering local growth conditions, which are sufficient to ensure linear convergence of the forward-backward algorithm as in (4.2). Most important examples include global error bounds g(x) -min z g(z) ≥ λdist(x, argmin g) 2

  Lipschitz continuous because ∇f θ is Lipschitz continuous with constant 1 α and both K θ and K * θ are λ-Lipschitz continuous. To demonstrate that f * θ • -K * θ is λ 2 β -strongly convex, we have for all y

	Theorem 18.15(vii)]. The function f * θ (-K * θ y) has gradient -K θ •∇f * θ •-K * θ which is α -f * λ2 θ
	1 α -Lipschitz continuous gradient [7,

2 (Path differentiability of the primal solution).

  -λ 2 y 2 , is convex because the smallest eigenvalue of K θ K * θ is λ 2 . Hence the claimed strong convexity modulus of λ 2 β , justifying the first part of the theorem claiming regularity of f * θ • -K * θ . Then, using the assumption that prox γg θ , ∇f * θ , and K θ are all path differentiable so that Assumption 4.1 holds, we are finally able to apply Theorem 4.2 to (5.2) and its fixed point formulation (5.3) and the desired results follow. We can recover the primal solution from the dual solution through the equation x ⋆ (θ) = ∇f * θ (-K * θ y ⋆ (θ)), coming from the primal-dual optimality conditions, since ∇f * θ is path differentiable. Indeed, the functions prox γg * θ and ∇f * θ are path differentiable if prox γg θ and ∇f θ are assumed to be path differentiable. By the Moreau decomposition[START_REF] Heinz | Convex analysis and monotone operator theory in Hilbert spaces[END_REF] Theorem 14.3(ii)] we can express prox γg * θ (y) = y -prox g θ /γ (y/γ). Meanwhile for ∇f * θ , we can invoke the path differentiable inverse function theorem[16,

	1 2β K * θ y 2 , is convex as it is the composition of a convex function f (•)-1 2β • 2 θ . Indeed, by 1 and a linear map -K * β -strong convexity of f * θ , the function f * θ (•) -1 2β • 2 is necessarily convex [7, Proposition 10.6]. The second term, 1 2β K * θ y 2 Remark 5.

Acknowledgements

The authors acknowledge the support of the Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA9550-19-1-7026. JB and EP acknowledge the support of ANR-3IA Artificial and Natural Intelligence Toulouse Institute, and thank Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant numbers FA8655-22-1-7012 ANR MasDol. JB acknowledges the support of ANR Chess, grant ANR-17-EURE-0010.

A Appendix

The next lemma is a general result that gives a bound on the Lipschitz constant of the forward mapping Id -γB in terms of the Lipschitz constant β of the maximal monotone operator B. This bound is slightly better than the more obvious bound 1 + γβ, and this improvement is crucial to prove Theorem 3.5.

Proof. For all x, y ∈ R n ,

where we have used the monotonicity of B followed by the β-Lipschitz continuity of B for the first and second inequalities, respectively. Thus, taking square roots, the mapping Id -γB is 1 + γ 2 β 2 -Lipschitz continuous.