The Elements of Differentiable Programming

Chapter 18Duality

In this chapter, we review duality principles in optimization.

18.1 Dual norms

We introduce in this section dual norms, since they are useful in this book.

Definition 18.1 (Dual norms)

Given a norm ∥u∥\|\u\|, its dual is ∥v∥∗≔max⁡∥u∥≤1⟨u,v⟩. \|\v\|_* \coloneqq \max_{\|\u\| \le 1} \langle \u, \v \rangle.

Therefore, the dual norm of ∥⋅∥\|\cdot\| is the support function of the unit ball induced by the norm ∥⋅∥\|\cdot\|, B∥⋅∥≔{u∈RD ⁣:∥u∥≤1}. B_{\|\cdot\|} \coloneqq \{\u \in \RR^D \colon \|\u\| \le 1\}. We give examples of pairs of dual norms below.

Example 18.1 (Dual norm of pp-norms)

The pp-norm is defined by ∥u∥p≔(∑j=1D∣uj∣p)1/p. \|\u\|_p \coloneqq \left( \sum_{j=1}^D |u_j|^p \right)^{1/p}. Its dual is ∥v∥q\|\v\|_q where qq is such that 1p+1q=1\frac{1}{p} + \frac{1}{q} = 1. For instance, the dual norm of the 22-norm is itself, since 12+12=1\frac{1}{2} + \frac{1}{2} = 1. The 11-norm and the ∞\infty-norm are duals of each other, since 11+1∞=1\frac{1}{1} + \frac{1}{\infty} = 1.

The definition of dual norm implies a generalization of the Cauchy–Schwarz inequality: for all u,v∈RD\u, \v \in \RR^D ∣⟨u,v⟩∣≤∥u∥∗∥v∥. |\langle \u, \v \rangle| \le \|\u\|_* \|\v\|. See, e.g., Beck (2017, Lemma 1.4).

Proposition 18.1 (Conjugate of norms and squared norms)

We know that the conjugate of the support function is the indicator function. Therefore, if f(u)=∥u∥f(\u) = \|\u\|, then f∗(v)=ιB∥⋅∥(v)={0 if ∥v∥∗≤1∞ otherwise . f^*(\v) = \indic_{B_{\|\cdot\|}}(\v) = \begin{cases} 0 &\mbox{ if } \|\v\|_* \le 1 \\ \infty &\mbox { otherwise } \end{cases}. On the other hand, if f(u)=12∥u∥2f(\u) = \frac{1}{2} \|\u\|^2, then f∗(v)=12∥v∥∗2. f^*(\v) = \frac{1}{2} \|\v\|^2_*.

18.2 Fenchel duality

We consider in this section standard objectives of the form min⁡w∈WL(w)≔min⁡w∈Wℓ(f(w))+R(w), \min_{\w \in \cW} L(\w) \coloneqq \min_{\w \in \cW} \ell(f(\w)) + R(\w), where f ⁣:W→Mf \colon \cW \to \cM, ℓ ⁣:M→R\ell \colon \cM \to \RR and R ⁣:W→RR \colon \cW \to \RR. We first show that the minimization of this objective, called the primal, can be lower bounded by a concave maximization objective, called the dual, even if the primal is nonconvex.

Proposition 18.2 (Weak duality)

Let f ⁣:W→Mf \colon \cW \to \cM (potentially nonlinear), ℓ ⁣:M→R\ell \colon \cM \to \RR (potentially nonconvex) and R ⁣:W→RR \colon \cW \to \RR (potentially nonconvex). Then min⁡w∈Wℓ(f(w))+R(w)≥max⁡α∈M−Rf(α)−ℓ∗(−α), \min_{\w \in \cW} \ell(f(\w)) + R(\w) \ge \max_{\alphav \in \cM} -R^f(\alphav) - \ell^*(-\alphav), where we used the conjugate ℓ∗(−α)≔max⁡θ∈M⟨−α,θ⟩−ℓ(θ) \ell^*(-\alphav) \coloneqq \max_{\thetav \in \cM} \langle -\alphav, \thetav \rangle - \ell(\thetav) and the “generalized conjugate” Rf(α)≔max⁡w∈W⟨α,f(w)⟩−R(w). R^{f}(\alphav) \coloneqq \max_{\w \in \cW} \langle \alphav, f(\w) \rangle - R(\w). Moreover, ℓ∗\ell^* and RfR^f are both convex functions.

We emphasize that the result in Proposition 18.2 is fully general, in the sense that it does not assume the linearity of ff or the convexity of ℓ\ell and RR. The caveat, of course, is that RfR^f and ℓ∗\ell^* are difficult to compute in general, if ff is nonlinear, and if ℓ\ell and RR are nonconvex.

Proof

min⁡w∈Wℓ(f(w))+R(w)=min⁡w∈Wθ∈Mℓ(θ)+R(w)s.t.θ=f(w)=min⁡w∈Wθ∈Mmax⁡α∈Mℓ(θ)+R(w)+⟨α,θ−f(w)⟩≥max⁡α∈Mmin⁡w∈Wθ∈Mℓ(θ)+R(w)+⟨α,θ−f(w)⟩=max⁡α∈Mmin⁡w∈W⟨α,−f(w)⟩+R(w)+min⁡θ∈Mℓ(θ)+⟨α,θ⟩=max⁡α∈M−max⁡w∈W⟨α,f(w)⟩−R(w)−max⁡θ∈M⟨−α,θ⟩−ℓ(θ)=max⁡α∈M−Rf(α)−ℓ∗(−α).\begin{align*} &\min_{\w \in \cW} \ell(f(\w)) + R(\w)\\ =& \min_{\substack{\w \in \cW\\\thetav \in \cM}} \ell(\thetav) + R(\w) \quad \text{s.t.} \quad \thetav = f(\w) \\ =& \min_{\substack{\w \in \cW\\\thetav \in \cM}} \max_{\alphav \in \cM} \ell(\thetav) + R(\w) + \langle \alphav, \thetav - f(\w) \rangle \\ \ge& \max_{\alphav \in \cM} \min_{\substack{\w \in \cW\\\thetav \in \cM}} \ell(\thetav) + R(\w) + \langle \alphav, \thetav - f(\w) \rangle \\ =& \max_{\alphav \in \cM} \min_{\w \in \cW} \langle \alphav, -f(\w) \rangle + R(\w) + \min_{\thetav \in \cM} \ell(\thetav) + \langle \alphav, \thetav\rangle \\ =& \max_{\alphav \in \cM} -\max_{\w \in \cW} \langle \alphav, f(\w) \rangle - R(\w) - \max_{\thetav \in \cM} \langle -\alphav, \thetav\rangle - \ell(\thetav) \\ =& \max_{\alphav \in \cM} -R^f(\alphav) - \ell^*(-\alphav). \end{align*} ◻

In the case when f(w)=Awf(\w) = A \w, where AA is a linear map, and when both ℓ\ell and RR are convex, we can state a much stronger result.

Proposition 18.3 (Strong duality)

Let AA be a linear map from W\cW to M\cM. Let ℓ ⁣:M→R\ell \colon \cM \to \RR and R ⁣:W→RR \colon \cW \to \RR be convex functions. Let A∗A^* denote the adjoint of AA (Section 2.3). Then, min⁡w∈Wℓ(Aw)+R(w)=max⁡α∈M−R∗(A∗α)−ℓ∗(−α). \min_{\w \in \cW} \ell(A\w) + R(\w) = \max_{\alphav \in \cM} -R^*(A^*\alphav) - \ell^*(-\alphav). Furthermore, the primal solution satisfies w⋆∈arg max⁡w∈W⟨Aα⋆,w⟩−R(w). \w^\star \in \argmax_{\w \in \cW} \langle A \alphav^\star, \w \rangle - R(\w). When RR is strictly convex, the primal solution is uniquely determined by w⋆=∇R∗(A∗α⋆). \w^\star = \nabla R^*(A^* \alphav^\star).

Proof

Since f(w)=Awf(\w) = A\w, we have Rf(α)≔max⁡w∈W⟨α,f(w)⟩−R(w)=max⁡w∈W⟨α,Aw⟩−R(w)=max⁡w∈W⟨A∗α,w⟩−R(w)=R∗(A∗α).\begin{align*} R^{f}(\alphav) &\coloneqq \max_{\w \in \cW} \langle \alphav, f(\w) \rangle - R(\w) \\ &= \max_{\w \in \cW} \langle \alphav, A\w \rangle - R(\w) \\ &=\max_{\w \in \cW} \langle A^*\alphav, \w \rangle - R(\w) \\ &=R^*(A^*\alphav). \end{align*} Furthermore, the inequality in the proof of Proposition 18.2 is an equality, since the min⁡max⁡\min \max is that of a convex-concave function. ◻

The maximization problem in Proposition 18.3 is called the Fenchel dual. By strong duality, the value of the maximum and the value of the minimum are equal. We can therefore choose to equivalently solve the dual instead of the primal. This can be advantageous when the space M\cM is smaller than W\cW.

We now apply the Fenchel dual to obtain the dual of regularized multiclass linear classification.

Example 18.2 (Sum of separable loss functions)

When the loss is
ℓ(θ)≔∑i=1Nℓi(θi)\ell(\thetav) \coloneqq \sum_{i=1}^N \ell_i(\thetav_i), where θ=Aw=(A1w,…,ANw)∈MN\thetav = A\w = (A_1 \w, \dots, A_N \w) \in \cM^N and AiA_i is a linear map from W\cW to M\cM, we obtain min⁡w∈W∑i=1Nℓi(Aiw)+R(w)=max⁡α∈MN−R∗(A∗α)−∑i=1Nℓi∗(−αi), \min_{\w \in \cW} \sum_{i=1}^N \ell_i(A_i \w) + R(\w) = \max_{\alphav \in \cM^N} -R^*(A^*\alphav) - \sum_{i=1}^N \ell_i^*(-\alphav_i), where A∗α=(A1∗α1,…,AN∗αN)A^* \alphav = (A_1^* \alphav_1, \dots, A_N^* \alphav_N). Typically, we define Aiw≔Wxi, A_i \w \coloneqq \W \x_i, where W∈RM×D\W \in \RR^{M \times D} is a reshaped version of w∈W\w \in \cW, xi∈RD\x_i \in \RR^D is a training sample, and MM is the number of classes. In this case, we then have Ai∗αi=αixi⊤. A_i^* \alphav_i = \alphav_i \x_i^\top.

Examples of loss function conjugates are given in Table 18.1.

Table 18.1: Examples of loss conjugates. For regression losses (squared, absolute), where yi∈RM\y_i \in \RR^M, we define ti=ϕ(yi)=yi\t_i = \phi(\y_i) = \y_i. For classification losses (logistic, perceptron, hinge), where yi∈[M]y_i \in [M], we define ti=ϕ(yi)=eyi\t_i = \phi(y_i) = \e_{y_i}. To simplify some expressions, we defined the change of variable μi≔yi−αi\muv_i \coloneqq \y_i - \alphav_i.

  ℓi(θi)\ell_i(\thetav_i) ℓi∗(−αi)\ell_i^*(-\alphav_i)
Squared 12∥θi−ti∥22\frac{1}{2} \|\thetav_i - \t_i\|^2_2 12∥αi∥22−⟨ti,αi⟩\frac{1}{2}\|\alphav_i\|^2_2 - \langle \t_i, \alphav_i \rangle
Absolute ∥θi−ti∥1\|\thetav_i - \t_i\|_1 ι[−1,1]M(αi)−⟨ti,αi⟩\indic_{[-1,1]^M}(\alphav_i) - \langle \t_i, \alphav_i \rangle
Logistic LSE(θi)−⟨θi,ti⟩\mathrm{LSE}(\thetav_i) - \langle \thetav_i, \t_i \rangle ⟨μi,log⁡μi⟩+ι△M(μi)\langle \muv_i, \log \muv_i \rangle + \indic_{\triangle^M}(\muv_i)
Perceptron max⁡j∈[M]θi,j−θi,yi\max_{j \in [M]} \theta_{i,j} - \theta_{i, y_i} ι△M(μi)\indic_{\triangle^M}(\muv_i)
Hinge max⁡j∈[M][j≠yi]+θi,j−θi,yi\max_{j \in [M]} [j \neq y_i] + \theta_{i,j} - \theta_{i,y_i} ι△M(μi)−⟨1⁡−ti,μi⟩\indic_{\triangle^M}(\muv_i) - \langle \ones - \t_i, \muv_i \rangle

18.3 Bregman divergences

Bregman divergences are a measure of difference between two points.

Definition 18.2 (Bregman divergence)

The Bregman divergence generated by a differentiable convex function f ⁣:RD→Rf \colon \RR^D \to \RR is Bf(u,v)≔f(u)−f(v)−⟨∇f(v),u−v⟩=⟨∇f(v),v⟩−f(v)−[⟨∇f(v),u⟩−f(u)],\begin{align*} B_f(\u, \v) &\coloneqq f(\u) - f(\v) - \langle \nabla f(\v), \u - \v \rangle \\ &= \langle \nabla f(\v), \v \rangle - f(\v) - \left[\langle \nabla f(\v), \u \rangle - f(\u)\right], \end{align*} where u,v∈dom⁡(f)\u, \v \in \dom(f).

Intuitively, the Bregman divergence is the difference between f(u)f(\u) and its linearization u↦f(v)+⟨∇f(v),u−v⟩\u \mapsto f(\v) + \langle \nabla f(\v), \u - \v \rangle around v\v. This is illustrated in Fig. 18.1.

Example 18.3 (Examples of Bregman divergences)

If f(u)=12∥u∥22f(\u) = \frac{1}{2} \|\u\|^2_2, where dom⁡(f)=RD\dom(f) = \RR^D, then Bf(u,v)=12∥u−v∥22, B_f(\u, \v) = \frac{1}{2} \|\u - \v\|^2_2, the squared Euclidean distance. If f(u)=⟨u,log⁡u⟩f(\u) = \langle \u, \log \u \rangle, where dom⁡(f)=R+D\dom(f) = \RR_+^D, then Bf(u,v)=∑j=1Dujlog⁡ujvj−∑j=1Duj+∑j=1Dvj, B_f(\u, \v) = \sum_{j=1}^D u_j \log \frac{u_j}{v_j} - \sum_{j=1}^D u_j + \sum_{j=1}^D v_j, the (generalized) Kullback-Leibler divergence.

Properties

Bregman divergences enjoy several useful properties.

Proposition 18.4 (Properties of Bregman divergences)

Let f ⁣:RD→Rf \colon \RR^D \to \RR be a differentiable convex function.

  1. Non-negativity: Bf(u,v)≥0B_f(\u, \v) \ge 0 for all u,v∈dom⁡(f)\u, \v \in \dom(f).

  2. Positivity: Bf(u,v)=0B_f(\u, \v) = 0 if and only if u=v\u = \v (when ff is strictly convex).

  3. Convexity: Bf(u,v)B_f(\u, \v) is convex in u\u.

  4. Dual-space form: Bf(u,v)=Bf∗(b,a)B_f(\u, \v) = B_{f^*}(\b, \a), where b=∇f(v)∈dom⁡(f∗)\b = \nabla f(\v) \in \dom(f^*) and a=∇f(u)∈dom⁡(f∗)\a = \nabla f(\u) \in \dom(f^*).

Proof

The properties follow immediately from the convexity of f(u)f(\u).

  1. From Definition 15.6.

  2. From the uniqueness of minimizers.

  3. From the fact that u↦Bf(u,v)\u \mapsto B_f(\u, \v) is the sum of f(u)f(\u) and a linear function of u\u.

 ◻

Figure 18.1: The Bregman divergence generated by ff is the difference between f(u)f(\u) and its linearization around v\v.

The Bregman divergence can be used to define natural generalizations of the Euclidean projection and proximal operators, reviewed in Section 16.3 and Section 16.4.

Definition 18.3 (Bregman proximal and projection operators)

Let v∈dom⁡(f)\v \in \dom(f). The Bregman proximal operator is bproxf,g(v)≔arg min⁡u∈dom⁡(f)∩dom⁡(g)Bf(u,v)+g(u). \mathrm{bprox}_{f,g}(\v) \coloneqq \argmin_{\u \in \dom(f) \cap \dom(g)} B_f(\u, \v) + g(\u). In particular, the Bregman projection onto C⊆dom⁡(f)\cC \subseteq \dom(f) is bprojf,C(v)≔arg min⁡u∈CBf(u,v). \mathrm{bproj}_{f,\cC}(\v) \coloneqq \argmin_{\u \in \cC} B_f(\u, \v).

It turns out that these operators are intimately connected to the gradient mapping of the convex conjugate.

Proposition 18.5 (Link with conjugate’s gradient)

If Ω=f+g\Omega = f + g, then for all θ∈dom⁡(f∗)\thetav \in \dom(f^*) ∇Ω∗(θ)=bproxf,g(∇f∗(θ)). \nabla \Omega^*(\thetav) = \mathrm{bprox}_{f,g}(\nabla f^*(\thetav)). In particular, if Ω=f+ιC\Omega = f + \indic_{\cC}, then for all θ∈dom⁡(f∗)\thetav \in \dom(f^*) ∇Ω∗(θ)=bprojf,C(∇f∗(θ)). \nabla \Omega^*(\thetav) = \mathrm{bproj}_{f,\cC}(\nabla f^*(\thetav)).

We give two examples below.

Example 18.4 (Bregman projections on the simplex)

If f(u)=12∥u∥22f(\u) = \frac{1}{2}\|\u\|^2_2, then bprojf,△D(v)=arg min⁡u∈△D12∥u−v∥22.\begin{align*} \mathrm{bproj}_{f, \triangle^D}(\v) = \argmin_{\u \in \triangle^D} \frac{1}{2} \|\u - \v\|^2_2. \end{align*} If f(u)=⟨u,log⁡u−1⁡⟩f(\u) = \langle \u, \log \u - \ones \rangle, then bprojf,△D(v)=arg min⁡u∈△DKL(u,v)=softargmax(θ),\begin{align*} \mathrm{bproj}_{f, \triangle^D}(\v) = \argmin_{\u \in \triangle^D} \mathrm{KL}(\u, \v) = \mathrm{softargmax}(\thetav), \end{align*} where v=∇f∗(θ)=exp⁡(θ)\v = \nabla f^*(\thetav) = \exp(\thetav).

Therefore, the softmax can be seen as a projection onto the probability simplex in the Kullback-Leibler divergence sense!

18.4 Fenchel-Young loss functions

We end this chapter with a brief review of the Fenchel-Young family of loss functions (Blondel et al., 2020), which includes all loss functions in Table 18.1.

Definition 18.4 (Fenchel-Young loss)

The Fenchel-Young loss function generated by Ω\Omega is ℓΩ(θ,t)≔Ω∗(θ)+Ω(t)−⟨θ,t⟩ \ell_\Omega(\thetav, \t) \coloneqq \Omega^*(\thetav) + \Omega(\t) - \langle \thetav, \t \rangle where θ∈dom⁡(Ω∗)\thetav \in \dom(\Omega^*) and t∈dom⁡(Ω)\t \in \dom(\Omega).

Typically, we set θ=f(x,w)\thetav = f(\x, \w), where ff is a model prediction function with parameters w\w and t=ϕ(y)\t = \phi(\y), where ϕ ⁣:Y→dom⁡(Ω)\phi \colon \cY \to \dom(\Omega). For instance, suppose we work with categorical outputs y∈[M]y \in [M]. Then, we can set ϕ(y)=ey\phi(y) = \e_y, where ey\e_y is the one-hot encoding of yy.

The important point to notice is that the Fenchel-Young loss is defined over arguments in mixed spaces: θ\thetav belongs to the dual space, while t\t belongs to the primal space. In fact, the Fenchel-Young loss is intimately connected to the Bregman divergence, since BΩ(t,v)=Ω∗(θ)+Ω(t)−⟨θ,t⟩B_\Omega(\t, \v) = \Omega^*(\thetav) + \Omega(\t) - \langle \thetav, \t \rangle, if we set θ=∇Ω(v)\thetav = \nabla \Omega(\v). The key properties of Fenchel-Young loss functions are summarized below.

Proposition 18.6 (Properties of Fenchel-Young loss functions)

 

  1. Non-negativity: ℓΩ(θ,t)≥0\ell_\Omega(\thetav, \t) \ge 0 for all θ∈dom⁡(Ω∗)\thetav \in \dom(\Omega^*) and t∈dom⁡(Ω)\t \in \dom(\Omega).

  2. Positivity: ℓΩ(θ,t)=0\ell_\Omega(\thetav, \t) = 0 if and only if ∇Ω∗(θ)=t\nabla \Omega^*(\thetav) = \t, assuming Ω\Omega is strictly convex.

  3. Convexity: ℓΩ(θ,t)\ell_\Omega(\thetav, \t) is convex in θ\thetav (regardless of Ω\Omega) and in t\t (if Ω\Omega is convex).

  4. Relation with composite Bregman divergence: 0≤BΩ(t,∇Ω∗(θ))⏟possibly nonconvex in θ≤ℓΩ(θ,t)⏟convex in θ. 0 \le \underbrace{B_\Omega(\t, \nabla \Omega^*(\thetav))}_{\text{possibly nonconvex in } \thetav} \le \underbrace{\ell_\Omega(\thetav, \t)}_{\text{convex in } \thetav}.

See Blondel et al. (2020) for an in-depth study of more properties.

18.5 Summary