Danskin’s Theorem (General Form)

Danskin’s Theorem

Value functions, envelope formulas, directional derivatives, and nonsmooth gradients.

Let $x \in X$ be the decision variable and $y \in Y$ be a parameter. Define the value function $g (y) := min_{x \in X} f (x, y) .$ When the minimizer is not unique, $g$ may fail to be differentiable. The right object is a directional derivative (and, if desired, a generalized subdifferential).

Reference. The material is standard; see Theorem 4.13 in the book Perturbation Analysis of Optimization Problems (Bonnans–Shapiro) for closely related statements and proofs.

Danskin’s theorem is a workhorse because it turns a seemingly “implicit” differentiation problem into a “direct” one. When a value function is defined by an inner optimization,

g (y) = min_{x \in X} f (x, y),

it is tempting to think that differentiating $g$ requires differentiating the optimizer map $y \mapsto x^{⋆} (y)$ . In practice that map can be discontinuous, non-unique, or simply expensive to differentiate (it may require sensitivity equations or differentiating through an iterative solver). Danskin’s theorem says you typically don’t need any of that: whenever $g$ is differentiable at $y$ , its gradient is obtained by holding the optimizer fixed,

\nabla g (y) = \nabla_{y} f (x^{⋆} (y), y),

so the dependence $x^{⋆} (y)$ “drops out.” This is exactly what makes bilevel objectives and value functions tractable in modern optimization pipelines: compute an optimal (or near-optimal) $x^{⋆} (y)$ by solving the inner problem, then compute $\nabla_{y} f (x^{⋆} (y), y)$ by standard autodiff—without backpropagating through the solver or ever forming $d x^{⋆} / d y$ . In large-scale settings this is the difference between a cheap, stable gradient oracle and an impractical one, and it underpins widely used methods such as envelope-based gradient descent, alternating minimization with outer updates, and many dual/regularized formulations where the “min over $x$ ” is used to define a smooth (or directionally smooth) outer objective.

Assumptions

Let $X \subseteq R^{n}$ be nonempty and closed, and let $Y \subseteq R^{m}$ be open. Assume:

$f : X \times Y \to R$ is continuous in $(x, y)$ .
For every $y \in Y$ , the minimum $g (y) = min_{x \in X} f (x, y)$ is attained, and the minimizer set $S (y) := \arg min_{x \in X} f (x, y)$ is nonempty and compact.
For every $x \in X$ , the map $y \mapsto f (x, y)$ is differentiable on $Y$ , and $\nabla_{y} f (x, y)$ is continuous in $(x, y)$ .

Theorem (directional derivative and generalized gradient)

Directional derivative.

Under the assumptions above, $g$ is directionally differentiable on $Y$ and for every $y \in Y$ and $d \in R^{m}$ ,

g^{'} (y; d) = min_{x^{*} \in S (y)} \nabla_{y} f (x^{*}, y)^{⊤} d .

Differentiability criterion.

If either $S (y)$ is a singleton, or $\nabla_{y} f (x^{*}, y)$ is the same for all $x^{*} \in S (y)$ , then $g$ is differentiable at $y$ and

\nabla g (y) = \nabla_{y} f (x^{*}, y) for any x^{*} \in S (y) .

Clarke subdifferential (optional).

If $g$ is locally Lipschitz (e.g., $\nabla_{y} f$ is bounded on a neighborhood of $(y, S (y))$ ), then the Clarke subdifferential satisfies

\partial^{C} g (y) = conv {\nabla_{y} f (x^{*}, y) : x^{*} \in S (y)} .

Proof (directional derivative)

Fix $y \in Y$ and direction $d \in R^{m}$ . For $ϵ > 0$ small, set $y_{ϵ} = y + ϵ d \in Y$ .

Upper bound. For any minimizer $x^{*} \in S (y)$ , we have $g (y) = f (x^{*}, y)$ and $g (y_{ϵ}) \leq f (x^{*}, y_{ϵ})$ . Hence

\frac{g (y_{ϵ}) - g (y)}{ϵ} \leq \frac{f (x^{*}, y_{ϵ}) - f (x^{*}, y)}{ϵ} .

Letting $ϵ ↓ 0$ and using differentiability of $f (x^{*}, \cdot)$ ,

\underset{ϵ ↓ 0}{lim sup} \frac{g (y_{ϵ}) - g (y)}{ϵ} \leq \nabla_{y} f (x^{*}, y)^{⊤} d .

Since this holds for every $x^{*} \in S (y)$ ,

\underset{ϵ ↓ 0}{lim sup} \frac{g (y_{ϵ}) - g (y)}{ϵ} \leq min_{x^{*} \in S (y)} \nabla_{y} f (x^{*}, y)^{⊤} d .

Lower bound. Let $x_{ϵ} \in S (y_{ϵ})$ be any minimizer at $y_{ϵ}$ . Since $g (y) \leq f (x_{ϵ}, y)$ , we have

g (y_{ϵ}) - g (y) = f (x_{ϵ}, y_{ϵ}) - g (y) \geq f (x_{ϵ}, y_{ϵ}) - f (x_{ϵ}, y) .

Divide by $ϵ$ . By the mean value theorem applied to $θ \mapsto f (y + θ d, x_{ϵ})$ , there exists $θ_{ϵ} \in (0, ϵ)$ such that

\frac{f (x_{ϵ}, y_{ϵ}) - f (x_{ϵ}, y)}{ϵ} = \nabla_{y} f (x_{ϵ}, y + θ_{ϵ} d)^{⊤} d .

By compactness of $S (y_{ϵ})$ and continuity, the sequence $(x_{ϵ})$ has limit points. Take a sequence $ϵ_{k} ↓ 0$ such that $x_{ϵ_{k}} \to \bar{x}$ . By standard stability of argmin under continuity + compactness, $\bar{x} \in S (y)$ . Using continuity of $\nabla_{y} f$ ,

\underset{k \to \infty}{lim inf} \frac{g (y_{ϵ_{k}}) - g (y)}{ϵ_{k}} \geq \nabla_{y} f (\bar{x}, y)^{⊤} d \geq min_{x^{*} \in S (y)} \nabla_{y} f (x^{*}, y)^{⊤} d .

Since the right-hand side does not depend on the subsequence, we obtain

\underset{ϵ ↓ 0}{lim inf} \frac{g (y_{ϵ}) - g (y)}{ϵ} \geq min_{x^{*} \in S (y)} \nabla_{y} f (x^{*}, y)^{⊤} d .

Conclusion. The limsup and liminf match, so the directional derivative exists and equals $min_{x^{*} \in S (y)} \nabla_{y} f (x^{*}, y)^{⊤} d$ .

Remark (Clarke subdifferential)

The Clarke formula can be derived quickly by rewriting $g (y) = - h (y)$ with $h (y) = max_{x \in X} (- f (x, y))$ and applying the standard Clarke/Danskin rule for maxima, which yields $\partial^{C} h (y) = conv {- \nabla_{y} f (x^{*}, y) : x^{*} \in S (y)}$ , hence $\partial^{C} g (y) = conv {\nabla_{y} f (x^{*}, y) : x^{*} \in S (y)}$ .

Dr Sarat Moka

Lecturer & Researcher