Proof of Proposition 3. Given the assumptions in the preamble of the proposition,

1. The function \(\Omega\) belongs to the set of proper l.s.c. convex functions \(\Gamma_0(\mathbb{R}^d)\), thus for any \(\theta \in \mathbb{R}^d\), the supremum over the compact \(\mathcal{C}\) of \(\langle \theta| \cdot \rangle - \Omega(\cdot)\) is finite and attained, thus \(\mathop{\mathrm{dom}}(\Omega^*) = \mathbb{R}^d\). Recall that, as \(\Omega\) is in \(\Gamma_0(\mathbb{R}^d)\), using the computations of [17], Theorem 23.5, \(\partial \Omega^*(\theta)=\mathop{\mathrm{argmax}}_{y} \langle \theta| y \rangle - \Omega(y)\). As \(\Omega\) is strictly convex, the argmax is reduced to a single point, and \(\Omega^*\) is differentiable over \(\mathbb{R}^d\). Therefore, we have for \((y ,\theta) \in (\mathbb{R}^d)^2\): \[\theta \in \partial \Omega(y) \iff y \in \partial \Omega^*(\theta) \iff y = \nabla \Omega^*(\theta).\] Therefore, for \(y \in \mathop{\mathrm{rel\,int}}(\mathcal{C})\), we have \(\nabla \Omega^*(\partial \Omega(y)) = y\).

2. Let \(y_0 \in \mathcal{C}\) and \(\theta \in \mathbb{R}^d\) be decomposed as \(\theta = \theta_V + \theta_{V^\perp}\). Note that for all \(y \in \mathcal{C}\) we have \(\langle \theta_{V^\perp}| y \rangle = \langle \theta_{V^\perp}| y_0 \rangle\), since \(\theta_{V^\perp}\) is orthogonal to the direction of the affine hull of \(\mathcal{C}\). Thus, \[\begin{align} \Omega^*(\theta) & = \sup_{y \in \mathcal{C}} \langle \theta_V + \theta_{V^\perp}| y \rangle - \Omega(y) = \langle \theta_{V^\perp}| y_0 \rangle + \sup_{y \in \mathcal{C}} \langle \theta_V| y \rangle - \Omega(y), \end{align}\] which yields the result.

3. Let \((y, y') \in H^2\), \(\theta \in \partial \Omega(y)\), by definition of the subgradients, we have \[\Omega(y') - \Omega(y) \geq \langle \theta| y'-y \rangle = \langle \Pi_V(\theta)| y'-y \rangle,\] since \(y'-y\) belongs to \(V\). Therefore we have shown that \({\Pi_V(\theta) \in \partial(\Omega_{|H})(y)}\).

   Conversely, let \(y \in H\) and \(\theta \in V\) be an element of \(\partial(\Omega_{|H})(y)\), for \(y' \in \mathbb{R}^d\) and \(\tilde{\theta} \in V^\perp\), \[\Omega(y') \geq \Omega(y) + \langle \theta + \tilde{\theta}| y'-y \rangle,\] since either \(y' \notin H\) and \(\Omega(y') = + \infty\), or \(y' \in H\) and \(y'-y \in V\) therefore \(\langle \tilde{\theta}| y'-y \rangle =0\). We have shown the first equality in Equation ?? .

   Equation ?? comes from the fact that \(\Omega_{|H}\) is Legendre-type, thus differentiable, and for \(y \in \mathop{\mathrm{rel\,int}}(\mathop{\mathrm{dom}}(\Omega))\), \(\partial(\Omega_{|H})(y) = \{\nabla (\Omega_{|H})(y)\}\).

 ◻

Proof of Proposition 4. Let \(\Pi_V\) be the linear orthogonal projection onto \(V\). W.l.o.g., we consider the case \(H = V\), which means the affine hull of the domain of \(\Omega\) is actually a vector subspace in \(\mathbb{R}^d\). Extending to the affine case involves a translation. We define the following map: \[\begin{align} \Psi: & \quad \mathbb{R}^d \rightarrow \mathbb{R}\\ & \quad y \mapsto \Omega(\Pi_V(y)) + \frac{1}{2} ||y - \Pi_V(y)||^2_2, \end{align}\] where \(\Pi_V(y)\) is seen as an element of \(\mathbb{R}^d\) here. When it is the input of the restriction of \(\Omega\) to \(V\), we see it as an element of \(V\). Notice that by definition, \(\Omega = \Psi + \mathbb{I}_\mathcal{C}\). We are going to prove that \(\Psi\) is a Legendre-type function. We first show that \(\Psi\) defined as such is essentially smooth by checking the three properties of the definition.

1. Since \(\mathop{\mathrm{dom}}(\Omega) = \mathcal{C}\subset V\) and \(\|\cdot\|^2_2\) is defined over \(\mathbb{R}^d\), the domain of \(\Psi\) is \({\mathop{\mathrm{dom}}(\Psi) = \mathcal{C}\oplus V^\perp}\), and \(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi)) = \mathop{\mathrm{rel\,int}}(\mathcal{C}) \oplus V^\perp\), which is not empty. We therefore have \[\mathcal{C}\subset \mathop{\mathrm{cl}}\big(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi))\big), \quad \text{and} \quad \mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi)) \cap \mathcal{C}\neq \emptyset.\]

2. By composition with linear projections and sum, \(\Psi\) is differentiable over \(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi))\). We denote by \(J_{\Pi_V}\) the Jacobian of \(\Pi_V\), that can be seen as the canonical injection of \(V\) into \(\mathbb{R}^d\). Let now \((y, h) \in \mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi)) \times \mathbb{R}^d\) be two vectors such that \(y+h \in \mathop{\mathrm{dom}}(\Psi)\), \[\begin{align} \Psi(y+h) &= \Omega(\Pi_V(y+h)) + \frac{1}{2}||y+h - \Pi_V(y+h)||^2_2,\\ & = \Omega(\Pi_V(y) + \Pi_V(h)) + \frac{1}{2}||y-\Pi_V(y) + h - \Pi_V(h)||^2_2,\\ & = \Omega_{|V}(\Pi_V(y)) + \langle J_{\Pi_V} \nabla(\Omega_{|V})(\Pi_V(y))| \Pi_V(h) \rangle + o(||\Pi_V(h)||),\\ & + \frac{1}{2}||y-\Pi_V(y)||^2_2 + \langle y-\Pi_V(y)| h-\Pi_V(h)\rangle + o(||h-\Pi_V(h)||),\\ & = \Omega(\Pi_V(y)) + \langle J_{\Pi_V} \nabla(\Omega_{|V})(\Pi_V(y)) | \Pi_V(h) + h - \Pi_V(h)\rangle + o(||h||),\\ & + \frac{1}{2}||y-\Pi_V(y)||^2_2 + \langle y-\Pi_V(y)| h-\Pi_V(h) + \Pi_V(h)\rangle + o(||h||),\\ & = \Psi(y) + \langle J_{\Pi_V} \nabla(\Omega_{|V})(\Pi_V(y)) + y-\Pi_V(y) | h \rangle + o(||h||). \end{align}\] In the computations above we use the linearity of \(\Pi_V\), the fact that \(\Omega\) and \(\Omega_{|V}\) coincide over \(V\), that \(\Omega_{|V}\) is Legendre-type thus differentiable, and the orthogonal sum \(\mathbb{R}^d = V \oplus V^\perp\). Therefore, we have shown that the gradient of \(\Psi\) is given by: \[\nabla \Psi(y) = \underbrace{J_{\Pi_V}}_{\substack{\text{Canonical}\\\text{injection} \\ V\rightarrow \mathbb{R}^d}} \nabla \Omega_{|V}(\Pi_V(y)) + y - \Pi_V(y).\]

3. The boundary of \(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi))\) is \[\mathop{\mathrm{bdry}}\big(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi))\big) = \mathop{\mathrm{cl}}\big(\mathop{\mathrm{rel\,int}}(\mathcal{C})\big) \backslash \mathop{\mathrm{rel\,int}}(\mathcal{C}) \oplus V^\perp.\] Indeed, \(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi)) = \mathop{\mathrm{rel\,int}}(\mathcal{C}) \oplus V^\perp\) is isomorphic to \(\mathop{\mathrm{rel\,int}}(\mathcal{C}) \times V^\perp\), \(\mathop{\mathrm{bdry}}(V^\perp) = \emptyset\), \(\mathop{\mathrm{cl}}(V^\perp) = V^\perp\), and for two sets \(S_1\) and \(S_2\) \[\mathop{\mathrm{bdry}}(S_1\times S_2) = \big(\mathop{\mathrm{bdry}}(S_1)\times \mathop{\mathrm{cl}}(S_2) \big) \cup \big(\mathop{\mathrm{cl}}(S_1)\times \mathop{\mathrm{bdry}}(S_2)\big),\] where the boundaries in the right-hand side above are computed with respect to the topology corresponding to each set.

   Let now \(\mu\) be in \(\mathop{\mathrm{bdry}}\big(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi))\big)\), and let \((\mu_i)_{i \in \mathbb{N}}\) be a sequence in \(\big(\mathop{\mathrm{int}}(\mathop{\mathrm{dom}}(\Psi))\big)^{\mathbb{N}}\), such that \[\lim _{i\to +\infty} \mu_i = \mu = \underbrace{\Pi_V(\mu)}_{\in \mathop{\mathrm{cl}}\big(\mathop{\mathrm{rel\,int}}(\mathcal{C})\big) \backslash \mathop{\mathrm{rel\,int}}(\mathcal{C})} + \underbrace{\mu - \Pi_V(\mu)}_{\in V^\perp}.\]

   Since \(\Pi_V\) is continuous, \[\lim_{i\to +\infty} \underbrace{\Pi_V(\mu_i)}_{\in \mathop{\mathrm{rel\,int}}(\mathcal{C})} = \Pi_V(\mu), \quad \text{and} \quad \lim_{i\to +\infty} \underbrace{\mu_i - \Pi_V(\mu_i)}_{\in V^\perp} = \mu - \Pi_V(\mu).\] Now, using the fact that \(\Omega_{|V}\) is Legendre-type, the expression of \(\nabla \Psi\) above, and the reverse triangular inequality, \[\begin{align} ||\nabla \Psi(\mu_i)|| &= || J_{\Pi_V} \nabla(\Omega_{|V})(\Pi_V(\mu_i)) + \mu_i - \Pi_V(\mu_i)||, \\ & \geq \big| \underbrace{||J_{\Pi_V} \nabla(\Omega_{|V})(\Pi_V(\mu_i))||}_{\to + \infty} - \underbrace{||\mu_i - \Pi_V(\mu_i)||}_{\to ||\mu - \Pi_V(\mu)||} \big|. \end{align}\] Therefore, we have shown that \(\lim_{i \to + \infty} ||\nabla \Psi(\mu_i)|| = +\infty\).

Let us finally show that \(\Psi\) is strictly convex. We first remark that \(\mathop{\mathrm{dom}}(\Psi)\) is convex since both \(\mathcal{C}\) and \(V^\perp\) are. Let \((y_1, y_2)\) be in \((\mathop{\mathrm{dom}}(\Psi))^2\), with \(y_1 \neq y_2\), and let \(t\) be in \((0,1)\). To ease notations, we denote \(y_i^V=\Pi_V(y_i)\), and \(y_i^\perp = y_i-\Pi_V(y_i)\), \[\begin{align} \Psi(ty_1 + (1-t)y_2) &= \Omega(ty_1^V + (1-t)y_2^V) + \frac{1}{2} ||t y_1^\perp + (1-t)y_2^\perp||^2_2,\\ & < t \Omega(y_1^V) + (1-t)\Omega(y_2^V) + t \frac{1}{2} \|y_1^\perp\|^2 + (1-t)\frac{1}{2} \|y_2^\perp\|^2 ,\\ & = t \Psi(y_1) + (1-t)\Psi(y_2). \end{align}\] The first line is by linearity of the orthogonal projection onto \(V\). Further, as \(y_1 \neq y_2\) we have \(y_1^V \neq y_2^V\) or \(y_1^\perp \neq y_2^\perp\), thus the strict convexity of \(\Omega\) over \(\mathcal{C}\) and of \(\|\cdot\|^2_2\) yields the second line. We have therefore shown that \(\Psi\) is a Legendre-type function.

We now consider its Fenchel conjugate \(\Psi^*\), and study its domain. Let \(\theta \in \mathbb{R}^d\), decomposed as \(\theta = \theta_V + \theta_{V^\perp}\), where \(\theta_V = \Pi_V(\theta)\) and \(\theta_{V^\perp} = \theta - \theta_V\), \[\begin{align} \Psi^*(\theta) &= \sup_{y \in \mathbb{R}^d} \{\langle \theta | y \rangle - \Psi(y)\},\\ & =\sup_{y \in \mathbb{R}^d} \Big\{ \langle \theta_V | \Pi_V(y) \rangle - \Omega(\Pi_V(y)) + \langle \theta_{V^\perp} | y - \Pi_V(y) \rangle - \frac{1}{2} ||y - \Pi_V(y)||^2_2 \Big\},\\ & =\sup_{\substack{y_V \in V, \\ y_{V^\perp} \in V^\perp}} \Big\{ \langle \theta_V | y_V \rangle - \Omega(y_V) + \langle \theta_{V^\perp} | y_{V^\perp} \rangle - \frac{1}{2} ||y_{V^\perp}||^2_2 \Big\},\\ & = \Omega^*(\theta_V) + \frac{1}{2}||\theta_{V^\perp}||^2_2. \end{align}\] Now, since \(\Omega^*\) has full domain using Proposition 3, we have \(\mathop{\mathrm{dom}}(\Psi^*) = \mathbb{R}^d\).

We eventually show the property on the composition of the gradients of \(\Psi\) and \(\Omega^*\). First, we highlight that by Proposition 3, \(\Omega^*\) is indeed differentiable over \(\mathbb{R}^d\). Its gradient corresponds to the regularized prediction defined by Equation 40 , and belongs to the relative interior of the convex compact set \(\mathcal{C}\). Let \(\theta \in \mathbb{R}^d\) be a vector decomposed as \(\theta = \theta_V + \theta_{V^\perp}\), where \(\theta_V = \Pi_V(\theta)\) and \(\theta_{V^\perp} = \theta - \theta_V\). Then we have \[\nabla \Omega^*(\theta) = \nabla \Omega^*(\theta_V) = \underbrace{J_{\Pi_V}}_{\substack{\text{Canonical}\\\text{injection} \\ V\rightarrow \mathbb{R}^d}} \nabla \Omega^*_{|V}(\theta_V).\] Therefore, applying the gradient of \(\Psi\) leads to \[\begin{align} \nabla \Psi \big(\nabla \Omega^*(\theta)\big) &= \nabla \Psi \big(\underbrace{J_{\Pi_V} \nabla \Omega^*_{|V}(\theta_V)}_{\in \mathop{\mathrm{rel\,int}}(\mathcal{C})} + \underbrace{0}_{\in V^\perp}\big), \\ & = J_{\Pi_V} \nabla \Omega_{|V} \big(\nabla \Omega^*_{|V}(\theta_V) \big) + 0,\\ & = \theta_V = \theta \underbrace{- \theta_{V^\perp}}_{z \in V^\perp}. \end{align}\] In the computations above, we use the expression of the gradient of \(\Psi\), and the fact that the restriction \(\Omega_{|V}\) of \(\Omega\) to \(V\) is a Legendre-type function with Fenchel conjugate \(\Omega^*_{|V}\). Therefore, we have shown that there exists a vector \(z \in V^\perp\) such that \(\nabla \Psi \big(\nabla \Omega^*(\theta)\big) = \theta + z\). ◻

Proof.

1. Immediate.

2. By definition, \[\begin{align} \Omega_\mathcal{C}^*(\theta) = \max_{\mu}\Big( \theta^\top \mu + \max_{q \colon Yq = \mu}- \Omega(q)\Big) &= \max_{\mu, q\colon \mu = Yq}\underbrace{\theta^\top \mu}_{s_\theta^\top q} - \Omega(q), \\ & = \max_{q} s_\theta^\top q - \Omega(q) = \Omega^*_\Delta(s_\theta). \end{align}\] Applying Proposition 3.[lem:Fenchel95conjugate95subdimension95diff] to \(\Omega_\Delta\), we get that \({\mathop{\mathrm{dom}}(\Omega_\Delta^*) = \mathbb{R}^{\mathcal{Y}}}\), and it is differentiable over \(\mathbb{R}^{\mathcal{Y}}\). Composing with a linear map gives the domain and differentiability results. Applying Proposition 3.[lem:conjugate95constant95perp] to \(\Omega_\Delta^*\) with \(V_\Delta^\perp = \mathop{\mathrm{span}}(\mathbf{1})\), we have \(\Omega^*_\Delta\) affine over \(\mathop{\mathrm{span}}(\mathbf{1})\). Besides, \[s_\theta \in \mathop{\mathrm{span}}(\mathbf{1}) \iff \exists \alpha \in \mathbb{R}, \forall y \in \mathcal{Y}, \langle \theta| y \rangle = \alpha \iff \theta \in V^\perp.\]

3. An immediate consequence of the definition of \(\Omega_\mathcal{C}\) and the previous points.

4. It follows from properties [prop:objectivesEquality] and [prop:FenchelDualsEquality] that the two minimization problems are equivalent up to a constant.

5. Consequence of the equality of the losses up to a constant that does not depend on \(\theta\).

 ◻

Proof of Proposition [prop:Perturbation]. Let \(\varepsilon \in \mathbb{R}_{++}\),

1. Let \((\theta, Z) \in (\mathbb{R}^d)^2\), since \(\mathcal{C}\) is compact and non-empty, the maximum in the definition 32 of \(F_{\varepsilon, \mathcal{C}}\) is well-defined. The expectation with respect to the normal distribution remains finite, and thus \(\mathop{\mathrm{dom}}(F_{\varepsilon, \mathcal{C}}) = \mathbb{R}^d\). Further, the function \(\theta \mapsto \max_{y \in \mathcal{C}}(\theta + \varepsilon Z)^\top y\) is convex as a maximum of affine functions. Finally, recall that finite convex functions are continuous.

2. The strict convexity of \(F_{\varepsilon, \mathcal{C}}\) over \(V\) stems directly from the proof of [4], Proposition 2.2. Let now \(\theta = \theta_V + \theta_{V^\perp}\) be any vector in \(\mathbb{R}^d\), and \(y_0\) be any vector in \(\mathcal{C}\), \[\begin{align} F_{\varepsilon, \mathcal{C}}(\theta) = \mathbb{E}[\max_{y \in \mathcal{C}}(\theta_V + \theta_{V^\perp} + \varepsilon \mathbf{Z})^\top y] &= \mathbb{E}[\theta_{V^\perp}^\top y_0 + \max_{y \in \mathcal{C}}(\theta_V + \varepsilon \mathbf{Z})^\top y],\\ & = \theta_{V^\perp}^\top y_0 + F_{\varepsilon, \mathcal{C}}(\theta_V). \end{align}\]

3. As highlighted by [4], Proposition 3.1, we can apply the technique of [30], Lemma 1.5 using the smoothness of the distribution of the noise variable \(\mathbf{Z}\) to show the smoothness of \(F_{\varepsilon, \mathcal{C}}\). It involves a simple change of variable \(u = \theta + \varepsilon Z\). The expression of the gradient comes from Danskin’s lemma and swap of integration and differentiation.

4. We first show that the domain of \(F_{\varepsilon, \mathcal{C}}^*\) is \(\mathcal{C}\). Let \(y \in \mathbb{R}^d\), by definition \[F_{\varepsilon, \mathcal{C}}^*(y) = \sup_{\theta \in \mathbb{R}^d}\{\theta^\top y - \mathbb{E}[\max_{y' \in \mathcal{C}}(\theta + \varepsilon \mathbf{Z})^\top y']\}.\]

   • If \(y \in \mathbb{R}^d \backslash \mathcal{C}\), we can separate it from \(\mathcal{C}\): there exists \(\bar \theta \in \mathbb{R}^d\), and \(\eta >0\) such that for all \(y' \in \mathcal{C}\), \(\langle \bar \theta| y - y'\rangle \geq \eta\). Thus, for any \(Z \in \mathbb{R}^d\), and \(\lambda >0\), we have \[\begin{align} \langle \lambda \bar \theta + \varepsilon Z| y-y'\rangle &\geq \lambda \eta + \langle \varepsilon Z| y-y' \rangle \geq \lambda \eta - ||\varepsilon Z||_2 ||y-y'||_2, \quad \forall y' \in \mathcal{C}. \end{align}\] Since \(\mathcal{C}\) is compact in \(\mathbb{R}^d\), we can consider \(D_{\mathcal{C}, y} :=\sup_{y' \in \mathcal{C}} ||y-y'||_2 < + \infty.\) Minimizing with respect to \(y' \in \mathcal{C}\) yields \[\begin{align} \langle \lambda \bar \theta + \varepsilon Z| y \rangle - \max_{y' \in \mathcal{C}} \langle \lambda \bar \theta + \varepsilon Z | y'\rangle & \geq \lambda \eta - ||\varepsilon Z|| D_{\mathcal{C}, y}. \end{align}\]

     Now, we recall that \(\mathbf{Z}\) is centered with distribution \(\nu\) (typically a multivariate standard normal distribution) with finite variance. We thus denote \(N_\nu:= \mathbb{E}_{\mathbf{Z}\sim \nu}[||\mathbf{Z}||_2]< + \infty\) and \(\mathbb{E}[||\varepsilon \mathbf{Z}||_2] = |\varepsilon| N_\nu < + \infty\). Taking the expectation with respect to \(\nu\) of the inequality above we get \[\begin{align} \langle \lambda \bar \theta| y \rangle - \mathbb{E}[\max_{y' \in \mathcal{C}} \langle \lambda \bar \theta + \varepsilon \mathbf{Z}|y'\rangle] & \geq \lambda \eta - |\varepsilon|N_\nu D_{\mathcal{C}, y}. \end{align}\] Therefore, since \(F_{\varepsilon, \mathcal{C}}^*(y)\geq \langle \lambda \bar \theta| y \rangle - \mathbb{E}[\max_{y' \in \mathcal{C}} \langle \lambda \bar \theta + \varepsilon \mathbf{Z}|y'\rangle]\) and considering the limit \(\lambda \to +\infty\) gives us \(F_{\varepsilon, \mathcal{C}}^*(y) = + \infty\).

   • If \(y \in \mathcal{C}\), since \(\mathbf{Z}\) is centered, \[\begin{align} F_{\varepsilon, \mathcal{C}}^*(y) &= \sup_{\theta \in \mathbb{R}^d}\{\theta^\top y - \mathbb{E}[\max_{y' \in \mathcal{C}}(\theta + \varepsilon \mathbf{Z})^\top y']\},\\ &= \sup_{\theta \in \mathbb{R}^d}\{\mathbb{E}[(\theta+\varepsilon \mathbf{Z})^\top y] - \mathbb{E}[\max_{y' \in \mathcal{C}}(\theta + \varepsilon \mathbf{Z})^\top y']\},\\ & = \sup_{\theta \in \mathbb{R}^d}\{\mathbb{E}[\underbrace{(\theta+\varepsilon \mathbf{Z})^\top y - \max_{y' \in \mathcal{C}}(\theta + \varepsilon \mathbf{Z})^\top y'}_{\leq 0 \text{ since } y \in \mathcal{C}}]\} < +\infty.\\ \end{align}\]

   Therefore, we have shown that \(\mathop{\mathrm{dom}}(F_{\varepsilon, \mathcal{C}}^*) = \mathcal{C}\). Point \(2.\) shows that \((F_{\varepsilon, \mathcal{C}})_{|V}\) is strictly convex over \(V\). Using the computations of point \(3.\), we show that \((F_{\varepsilon, \mathcal{C}})_{|V}\) is differentiable over \(V\). It is thus a Legendre-type function with \(\mathop{\mathrm{dom}}\big((F_{\varepsilon, \mathcal{C}})_{|V}\big) = V\). Indeed, point 3 of the essentially smooth definition holds vacuously. To show that \((F_{\varepsilon, \mathcal{C}}^*)_{|H}\) is Legendre-type, we use the fact that it is the conjugate (up to a translation) of \((F_{\varepsilon, \mathcal{C}})_{|V}\) in \(V\). Then, Remark 1 shows that \((F_{\varepsilon, \mathcal{C}}^*)_{|H}\) with domain \(\mathcal{C}\) is a Legendre-type function (with respect to the metric of \(H\)).

This concludes the proof. ◻

Proof of Theorem [prop:SparsePerturbation].

1. Let \(s_1, s_2 \in \mathbb{R}^{\mathcal{Y}}\). As \(\Delta^{\mathcal{Y}}\) is a polytope, there exists \(q^\sharp_1\) such that \[\begin{align} \max_{q_1 \in \Delta^{\mathcal{Y}}} \langle s_1 | q_1 \rangle - \max_{q_2 \in \Delta^{\mathcal{Y}}} \langle s_2 | q_2 \rangle &= \langle s_1 | q_1^\sharp \rangle - \max_{q_2 \in \Delta^{\mathcal{Y}}} \langle s_2 | q_2 \rangle \leq \langle s_1 - s_2 | q_1^\sharp \rangle \\ &\leq \max_{q \in \Delta^{\mathcal{Y}}}\langle s_1 - s_2 | q \rangle \\ &\leq \max_{q \in \Delta^{\mathcal{Y}}}\| s_1 - s_2\|_2 \|q\|_2 = \| s_1 - s_2\|_2 \end{align}\] where the last equality comes from the definition of \(\Delta^{\mathcal{Y}}\). Thus, \[\begin{align} F_\Delta(s_1) - F_\Delta(s_2) &= \mathbb{E}_{\mathbf{Z}} \big[\max_{q \in \Delta^{\mathcal{Y}}} \langle s_1 + \varepsilon Y^\top \mathbf{Z}| q \rangle - \max_{q \in \Delta^{\mathcal{Y}}} \langle s_2 + \varepsilon Y^\top \mathbf{Z}| q \rangle \big] \leq ||s_1 - s_2||. \end{align}\] By symmetry, we have shown that \(F_\Delta\) is 1-Lipschitz continuous.

2. The proof relies on the following technical lemma provided just below.

   Lemma 6. Let \(\mathcal{Y}\subset \mathbb{R}^d\) be a finite set satisfying Assumption 2. For any vector \(s \in \mathbb{R}^{\mathcal{Y}}\), we denote by \(s(y) \in \mathbb{R}\) the component of \(s\) indexed by \(y \in \mathcal{Y}\). We also consider \(\varepsilon >0\) a positive real number, and \(\mathbf{Z}\), a random variable with standard multivariate normal distribution over \(\mathbb{R}^d\).

   For \(i\in\{1,2\}\), let \(f_i(y;Z):=s_i(y)+\varepsilon Z^\top y\). Then, for any distinct \(s_1,s_2\in V_\Delta\), there is not almost surely a point \(y^\star\in\mathcal{Y}\) that maximizes both \(f_i(\cdot;\mathbf{Z})\) over \(\mathcal{Y}\). Then, for any distinct \(s_1,s_2\in V_\Delta\), the event \(\mathop{\mathrm{argmax}}_{y\in\mathcal{Y}}f_1(y;\mathbf{Z})\cap\mathop{\mathrm{argmax}}_{y\in\mathcal{Y}}f_2(y;\mathbf{Z})=\emptyset\) has positive probability.

   Let \(t \in (0, 1)\), the lemma above leads to \[\begin{align} \mathbb{P}_{\mathbf{Z}} \Bigg[\max_{y \in \mathcal{Y}} \bigg(t f_1(y; \mathbf{Z}) + (1-t) f_2(y;\mathbf{Z}) \bigg) < & \max_{y \in \mathcal{Y}} t f_1(y; \mathbf{Z}), \\ & + \max_{y \in \mathcal{Y}} (1-t) f_2(y;\mathbf{Z}) \Bigg] > 0. \end{align}\] Since \(F_\Delta\) is convex, this strict inequality with positive probability leads to the strict convexity of \(F_\Delta\) over \(V_\Delta\). Last, using the decomposition \(\mathbb{R}^{\mathcal{Y}} = V_\Delta + \mathop{\mathrm{span}}(\mathbf{1})\), we get the affine property over \(V_\Delta^\perp = \mathop{\mathrm{span}}(\mathbf{1})\) with the same arguments as for Proposition [prop:Perturbation] Point 2.

3. We first show that the \(\mathop{\mathrm{argmax}}\) in the definition of \(F_{\varepsilon, \Delta}\) is reduced to a singleton almost surely. Indeed, assume that for a pair of vectors \((y,y')\in\mathcal{Y}^2\), \[P_{\mathbf{Z}}\big[ s(y) + \varepsilon \mathbf{Z}^\top y = s(y') + \varepsilon \mathbf{Z}^\top y'\big] > 0,\] then, as \(\varepsilon\mathbf{Z}\) is a non-degenerate Gaussian, it implies that \(\langle \cdot| y-y'\rangle\) is constant (equal to \(s(y')-s(y)\)) on a ball of positive radius, and thus that \(y=y'\).

   Note that the uniqueness of the \(\mathop{\mathrm{argmax}}\) in \(\mathcal{Y}\) implies the uniqueness of the corresponding \(\mathop{\mathrm{argmax}}\) in the distribution space \(\Delta^{\mathcal{Y}}\) (see Equation 33 ). Now, as the argmax is almost surely unique, using Danskin’s theorem [37] Theorem 10.31, and swapping integration with respect to the density of \(\mathbf{Z}\) and differentiation with respect to \(s\), we get: \[\nabla_s\mathbb{E}[\max_{q \in \Delta^{\mathcal{Y}}} (s +\varepsilon Y^\top \mathbf{Z})^\top q] = \mathbb{E}[\mathop{\mathrm{argmax}}_{q \in \Delta^{\mathcal{Y}}} (s +\varepsilon Y^\top \mathbf{Z})^\top q].\]

4. The domain property is proved in the same way as for Proposition [prop:Perturbation] point 4, the rest also yields similarly.

 ◻

Proof of Lemma 6. Let \((s_1, s_2) \in (V_\Delta)^2, \, s_1 \neq s_2\) be two vectors. We are going to show that \[\mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} \{s_1(y) + \varepsilon Z^\top y \} \,\cap \, \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} \{s_2(y) + \varepsilon Z^\top y \} = \emptyset,\]

for \(Z\) almost everywhere with respect to the Lebesgue measure in an open ball in \(\mathbb{R}^d\). Since \(\mathbf{Z}\) follows a non-degenerate normal distribution, this open ball has positive Gaussian measure, and the result yields.

Suppose first that \(\mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} s_1(y) \cap \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} s_2(y) = \emptyset.\) Then, a ball centered on \(0_{\mathbb{R}^d}\) with sufficiently small radius gives the result.

Let now \(y^*\) be a common maximizer of \(s_1\) and \(s_2\). Since \(s_1\) and \(s_2\) are elements of \({V_\Delta = \mathop{\mathrm{span}}(\mathbf{1})^\perp}\), and they are distinct, they are not equal up to a constant. We can thus fix a \(\bar{y} \in \mathcal{Y}\) such that \(s_1(\bar{y}) - s_1(y^*) \neq s_2(\bar{y}) - s_2(y^*).\)

In particular, it implies that \(\bar y\) does not belong to the intersection of the \(\mathop{\mathrm{argmax}}\), \(\bar y \notin \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} s_1(y) \cap \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} s_2(y).\) Let \(\bar Z\) be in the relative interior of the normal cone of \(\mathop{\mathrm{conv}}(\mathcal{Y})\) at \(\bar y\), such that the function g defined as \(g: y \mapsto \varepsilon \bar Z^\top y,\) is injective over \(\mathcal{Y}\). It is possible since the normal cone is full dimensional, and the union of the hyperplanes where two dot products are equal is not full dimensional. Then, for \(\lambda \in \mathbb{R}_+\) sufficiently large, \(\mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} s_1(y) + \varepsilon \lambda \bar Z^\top y = \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} s_2(y) + \varepsilon \lambda \bar Z^\top y = \{\bar y \}.\)

For \(i \in \{1,2\}\), let us define \(F_i\) as \(F_i : \lambda \in \mathbb{R}\mapsto \max_{y \in \mathcal{Y}}\big(s_i(y) + \varepsilon \lambda \bar Z^\top y \big) - s_i(y^*).\) Note that if there exists \(\lambda^* \in \mathbb{R}\) such that \(\mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} \big(s_i(y) + \lambda^* \varepsilon \bar Z^\top y \big)\) for \(i \in \{1,2\}\) are disjoint singletons, then considering a small enough open ball around the vector \(\lambda^* \bar Z\) gives the result. We now show that such a \(\lambda^*\) exists.

Since \(\mathcal{Y}\) is finite, for \(i\in\{1,2\}\), \(F_i\) is a maximum of a finite number of affine functions in \(\lambda\), it is therefore a piecewise affine function. Since \(g\) is injective, for \(i \in \{1,2\}\), there exists a collection of \(k_i +1\) real numbers, \(k_i \in \mathbb{N}, \, k_i >1\), denoted as \(0=\lambda_0^i< \ldots < \lambda_{k_i}^i\) and a unique collection \(y^* = y_1^i, \ldots, y_{k_i}^i = \bar{y}\) of two-by-two distinct vectors such that \[F_i(\lambda) = s_i(y_j^i) + \varepsilon \lambda \bar Z^\top y_j^i - s_i(y^*), \quad \forall \lambda \in [\lambda_{j-1}^i, \lambda_j^i].\]

Furthermore, the fact that \(g\) is injective implies that \(y_j^i\) is the unique maximizer over \(\mathcal{Y}\) of \(y \mapsto s_i(y) + \varepsilon \lambda \bar Z^\top y\) for \(\lambda \in ]\lambda_{j-1}^i,\lambda_j^i[\). If the collections for \(i \in \{1,2\}\) are not identical, the proof is finished. By contradiction, we assume that the two collections are identical and denote by \({0=\lambda_0< \ldots < \lambda_k}\) and \({y^* = y_1, \ldots, y_k = \bar{y}}\) the common collections.

Let \(\tilde{j}\) be the smallest \(j' \in [k]\) such that \(s_1(y_{j'}) - s_1(y^*) \neq s_2(y_{j'}) - s_2(y^*)\). It exists since the inequality holds for \(\bar{y}\). Without loss of generality, we can assume from now on that \(s_1(y_{\tilde{j}}) - s_1(y^*) > s_2(y_{\tilde{j}}) - s_2(y^*)\). For \(i \in \{1,2\}\), we define \(\tilde{\lambda}_i\) as:

\[\tilde{\lambda}_i := \min \{\lambda \;|\; y_{\tilde{j}} \in \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} \big( s_i(y)+\varepsilon \lambda \bar Z^\top y \big)\}.\]

We eventually get a contradiction by proving \(\tilde{\lambda}_1 < \tilde{\lambda}_2\) with the following inequality. \[\begin{align} & s_2(y_{\tilde{j}}) - s_2(y^*) + \tilde{\lambda}_1 g(y_{\tilde{j}}), \\ &< s_1(y_{\tilde{j}}) - s_1(y^*) + \tilde{\lambda}_1 g(y_{\tilde{j}}), && (\text{hypothesis right above}), \\ &= s_1(y_{\tilde{j}-1}) - s_1(y^*) + \tilde{\lambda}_1 g(y_{\tilde{j}-1}), && \text{(Both y_{\tilde{j}} and y_{\tilde{j}-1} are optimal at the junction)}, \\ &= s_2(y_{\tilde{j}-1})- s_2(y^*) + \tilde{\lambda}_1 g(y_{\tilde{j}-1}), && \text{(by definition of \tilde{j})}. \end{align}\] Hence, for \(\lambda = \tilde{\lambda}_1 + \eta\) with \(\eta> 0\) sufficiently small, \(y_{\tilde{j}}\) is the unique \(\mathop{\mathrm{argmax}}\) of \(s_1(y) + \lambda g(y)\) and \(y_{\tilde{j}-1} \neq y_{\tilde{j}}\) is the unique \(\mathop{\mathrm{argmax}}\) of \(s_2(y) + \lambda g(y)\). ◻

Proof of Proposition [prop:strongConvexitySparsePerturbation] (strong convexity of \(\Omega_{\varepsilon,\Delta}\)). Let \((s_a, s_b) \in (\mathbb{R}^{\mathcal{Y}})^2\). By Theorem [prop:SparsePerturbation], the gradient of \(F_{\varepsilon, \Delta}\) is given by: \[\begin{align} \nabla_s F_{\varepsilon, \Delta}(s) &= \mathbb{E}\left[\mathop{\mathrm{argmax}}_{q \in \Delta^{\mathcal{Y}}} (s + \varepsilon \mathbf{Z})^\top q\right] = \mathbb{E}\left[ \sum_{y \in \mathcal{Y}} e_y \mathbb{1}\left\{ y = \mathop{\mathrm{argmax}}_{y' \in \mathcal{Y}} (s(y') + \varepsilon \langle\mathbf{Z}|{y'}\rangle) \right\} \right], \end{align}\] where \(e_y\) denotes the standard basis vector in \(\mathbb{R}^{\mathcal{Y}}\) corresponding to \(y\). Note that the \(\mathop{\mathrm{argmax}}\) is reduced to a singleton almost surely, as detailed in the proof of Theorem [prop:SparsePerturbation]. Thus, we can bound the distance between the two gradients: \[\begin{align} \|\nabla F_{\varepsilon, \Delta}(s_a) - \nabla F_{\varepsilon, \Delta}(s_b)\|_2 &= \Big\| \mathbb{E}\Big[ \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} (s_a(y) + \varepsilon \langle\mathbf{Z}|y\rangle) - \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} (s_b(y) + \varepsilon \langle\mathbf{Z}|y\rangle) \Big] \Big\|_2 \\ &\leq \mathbb{E}\Big[ \Big\| \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} (s_a(y) + \varepsilon \langle\mathbf{Z}|y\rangle) - \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} (s_b(y) + \varepsilon \langle\mathbf{Z}|y\rangle) \Big\|_2 \Big] \\ &\leq \sum_{(y_1, y_2) \in \mathcal{Y}^2} \|e_{y_1} - e_{y_2}\|_2 P_{y_1, y_2}, \end{align}\]

where \[\begin{align} P_{y_1, y_2} := \mathbb{P}\Big( &y_1 = \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} (s_a(y) + \varepsilon \langle\mathbf{Z}|y\rangle), y_2 = \mathop{\mathrm{argmax}}_{y \in \mathcal{Y}} (s_b(y) + \varepsilon \langle\mathbf{Z}|y\rangle) \Big). \end{align}\] Since \(e_{y_1}\) and \(e_{y_2}\) are vertices of the standard simplex, for any \(y_1 \neq y_2\), we have \(\|e_{y_1} - e_{y_2}\|_2 = \sqrt{2}\).

If the \(\mathop{\mathrm{argmax}}\) shifts from \(y_1\) under \(s_a\) to \(y_2\) under \(s_b\), then the relative order of the scores of \(y_1\) and \(y_2\) must have swapped. In particular: \[\begin{align} s_a(y_1) + \varepsilon \langle\mathbf{Z}|{y_1}\rangle &\geq s_a(y_2) + \varepsilon \langle\mathbf{Z}|{y_2}\rangle \implies \varepsilon(\langle\mathbf{Z}|{y_1}\rangle - \langle\mathbf{Z}|{y_2}\rangle) \geq s_a(y_2) - s_a(y_1) \\ s_b(y_1) + \varepsilon \langle\mathbf{Z}|{y_1}\rangle &\leq s_b(y_2) + \varepsilon \langle\mathbf{Z}|{y_2}\rangle \implies \varepsilon(\langle\mathbf{Z}|{y_1}\rangle - \langle\mathbf{Z}|{y_2}\rangle) \leq s_b(y_2) - s_b(y_1) \end{align}\] Therefore, the probability \(P_{y_1, y_2}\) is upper-bounded by the probability that the random variable \(\varepsilon(\langle\mathbf{Z}|{y_1}\rangle - \langle\mathbf{Z}|{y_2}\rangle)\) falls between \(s_a(y_2) - s_a(y_1)\) and \(s_b(y_2) - s_b(y_1)\). Up to reordering \(a\) and \(b\) to form a valid interval, we obtain: \[\begin{align} P_{y_1, y_2} &\leq \mathbb{P}\left( \varepsilon(\langle\mathbf{Z}|{y_1}\rangle - \langle\mathbf{Z}|{y_2}\rangle) \text{ is strictly between } s_a(y_2) - s_a(y_1) \text{ and } s_b(y_2) - s_b(y_1) \right) \\ &= \mathbb{P}\left( \frac{\langle\mathbf{Z}|{y_1}\rangle - \langle\mathbf{Z}|{y_2}\rangle}{\sqrt{2}} \in I_{y_1, y_2} \right), \end{align}\] where \(I_{y_1, y_2}\) is an interval of length: \[\begin{align} \frac{1}{\varepsilon \sqrt{2}} |(s_b(y_2) - s_b(y_1)) - (s_a(y_2) - s_a(y_1))| &\leq \frac{2}{\varepsilon \sqrt{2}} \|s_a - s_b\|_{\infty} \\ &= \frac{\sqrt{2}}{\varepsilon} \|s_a - s_b\|_{\infty} \leq \frac{\sqrt{2}}{\varepsilon} \|s_a - s_b\|_2. \end{align}\]

Since \(\mathbf{Z}\sim \mathcal{N}(0, I_d)\) is a standard Gaussian in \(\mathbb{R}^d\) and \(\langle\mathbf{Z}|y\rangle := y^\top\mathbf{Z}\), we have \[\frac{\langle\mathbf{Z}|{y_1}\rangle - \langle\mathbf{Z}|{y_2}\rangle}{\sqrt{2}} \sim \mathcal{N}\!\left(0, \frac{||y_1 - y_2||_2^2}{2}\right).\] Given a Gaussian \(X \sim \mathcal{N}(0,\sigma^2)\), we have \(\mathbb{P}(X \in [\alpha, \beta]) \leq \frac{|\beta - \alpha|}{\sqrt{2\pi}\,\sigma}\) since the density is uniformly bounded by \(1/(\sqrt{2\pi}\,\sigma)\).

Applying this to our probability bound yields for \(y_1 \neq y_2\): \[P_{y_1, y_2} \leq \frac{1}{\sqrt{2\pi}} \frac{\sqrt{2}}{||y_1-y_2||_2}\frac{\sqrt{2}}{\varepsilon} \|s_a - s_b\|_2.\]

Let \(m_\mathcal{Y}:= \min_{(y, y') \in \mathcal{Y}^2, y \neq y'}||y-y'||_2\) be the minimum distance between two distinct points in \(\mathcal{Y}\). Substituting this back into the sum, which contains at most \(|\mathcal{Y}|^2\) non-zero terms (since \(P_{y,y}\) doesn’t change relative distance but \(\|e_y-e_y\|_2=0\), we just upper bound the sum generously by considering all \(|\mathcal{Y}|^2\) pairs): \[\begin{align} \|\nabla_s F_{\varepsilon, \Delta}(s_a) - \nabla_s F_{\varepsilon, \Delta}(s_b)\|_2 &\leq \sum_{(y_1, y_2) \in \mathcal{Y}^2} \sqrt{2} \left( \frac{1}{\sqrt{2\pi}} \frac{\sqrt{2}}{m_\mathcal{Y}} \frac{\sqrt{2}}{\varepsilon} \|s_a - s_b\|_2 \right) \\ &\leq \frac{2|\mathcal{Y}|^2}{\varepsilon m_\mathcal{Y}\sqrt{\pi}} \|s_a - s_b\|_2 \end{align}\] which gives the desired Lipschitz constant \(L\).

Finally, knowing that \(F_{\varepsilon, \Delta}\) is a convex function with an \(L\)-Lipschitz continuous gradient, standard duality results in convex analysis dictate that its Fenchel conjugate \(\Omega_{\varepsilon, \Delta}\) is \((1/L)\)-strongly convex. This strong convexity is on \(H_\Delta\) and with respect to \(||\cdot||_2\). Therefore, \(\Omega_{\varepsilon, \Delta}\) is strongly convex on \(H_\Delta\) with respect to \(||\cdot||_2\) with parameter: \(\mu = \frac{1}{L} = \frac{\varepsilon m_\mathcal{Y}\sqrt{\pi}}{2|\mathcal{Y}|^{2}}.\) ◻

Proof of Proposition [prop:structuredPredictionSparsePerturbation] (structured prediction regularizer with sparse perturbation). By definition, \(F_{\varepsilon, \mathcal{C}}(\theta) = F_{\varepsilon, \Delta}(Y^\top \theta)\). Besides, since \(\Omega_{\varepsilon, \mathcal{C}}\) and \(\Omega_{\varepsilon, \Delta}\) are proper convex lower-semicontinuous, they are bi-conjugate by Fenchel-Moreau theorem. Applying the computations of [38], Corollary 15.28 with \(g = F_{\varepsilon, \Delta}\) and \({L : x \mapsto Y^\top x}\) leads to the result. ◻

Proof of Proposition [prop:computations95primal95dual95dist]. To derive Equation 24 remark the following. First, \(\mathcal{S}_{\Omega_\Delta,N}\) is defined as the sum of \(S_{\Omega_\Delta}\), and since \(\bar w^{(t)}\) is fixed, we obtain \(N\) independent problems. Now, using the expression of \(S_{\Omega_\Delta}\), we see that \(q_i^{(t+1)}\) belongs to the minimizers of \[\Omega_{\Delta^{\mathcal{Y}(x_i)}}(\cdot) - \langle Y(x_i)^\top\varphi_{\bar w^{(t)}}(x_i) - \frac{1}{\kappa}\gamma_i | \cdot \rangle.\] Using Fenchel duality, we recognize \(\nabla \Omega_{\Delta^{\mathcal{Y}(x_i)}}^*\big(Y(x_i)^\top\varphi_{\bar w^{(t)}}(x_i) - \frac{1}{\kappa}\gamma_i\big)\).

For the dual update in Equation 25 , using the expression of \(S_{\Omega_\Delta}\), and omitting the term that does not depend on \(w\), we can first recast Equation 23 as \[\bar w^{(t+1)} \in \mathop{\mathrm{argmin}}_{w \in \mathcal{W}} \frac{1}{N} \sum_{i=1}^N \mathcal{L}_{\Omega_{\Delta(x_i)}}\big(Y(x_i)^\top \varphi_w(x_i); q_i^{(t+1)}\big).\] Now, we leverage the computations of Section 6.3. In particular, based on the regularization function \(\Omega_{\Delta^{\mathcal{Y}(x)}}\) on distributions in \(\Delta^{\mathcal{Y}(x)}\), we define a regularization function \(\Omega_{\mathcal{C}(x)}\) on the moment space \({\mathcal{C}(x) = \mathop{\mathrm{conv}}(\mathcal{Y}(x))}\) as in Equation ?? . We then use Proposition 5, more precisely Points [prop:objectivesEquality]-[prop:FenchelDualsEquality], to get Equation 25 . ◻

Proof of Proposition [prop:primal95dual95perturbation]. For the primal update in Equation 26 , we can reformulate Equation 24 in this perturbation setting \[\begin{align*} \mu_i^{(t+1)} &= Y(x_i)q_i^{(t+1)} = Y(x_i)\nabla F_{\varepsilon, \Delta(x_i)}\big(Y(x_i)^\top\varphi_{\bar w^{(t)}}(x_i) - \frac{1}{\kappa}\gamma_i \big),\\ &= Y(x_i)\mathbb{E}_\mathbf{Z}\big[\mathop{\mathrm{argmax}}_{q_i \in \Delta^{\mathcal{Y}(x_i)}} \langle Y(x_i)^\top\varphi_{\bar w^{(t)}}(x_i) - \frac{1}{\kappa}\gamma_i + \varepsilon Y(x_i)^\top \mathbf{Z}| q_i \rangle \big],\\ &= \mathbb{E}_\mathbf{Z}\big[Y(x_i)\mathop{\mathrm{argmin}}_{q_i \in \Delta^{\mathcal{Y}(x_i)}}\langle \big(\frac{1}{\kappa}c(x_i,y,\xi_i) - (\varphi_{\bar w^{(t)}}(x_i) + \varepsilon \mathbf{Z})^\top y\big)_{y \in \mathcal{Y}(x_i)}| q_i \rangle \big],\\ &= \mathbb{E}_\mathbf{Z}\big[\mathop{\mathrm{argmin}}_{y_i \in \mathcal{Y}(x_i)} c(x_i,y_i,\xi_i) - \kappa (\varphi_{\bar w^{(t)}}(x_i) + \varepsilon \mathbf{Z})^\top y_i \big]. \end{align*} \label{eq:decomposition95dist95pert}\tag{41}\] In the computations above, we use Theorem [prop:SparsePerturbation] for the expression of the gradient of the function \(F_{\varepsilon, \Delta(x_i)}\), and the fact that the minimum of the linear optimization problem in \(q_i\) is attained (almost surely) at a vertex of the simplex \(\Delta^{\mathcal{Y}(x_i)}\), corresponding to a Dirac on a point \(y_i \in \mathcal{Y}(x_i)\). We see that the two constants \(\kappa\) and \(\varepsilon\) play similar roles in this setting; a formal equivalence between tuning one parameter versus the other is established in Appendix 7.5. Up to a re-normalization of the statistical model \(\varphi_w\), we keep the hyper-parameter \(\varepsilon\) to tune the regularization scale.

For the dual update in Equation 25 , we simply use the expression of the Fenchel–Young loss in the perturbation setting and omit the terms that do not depend on \(w\). ◻

Proof of Proposition [prop:barOmegaProperties]. Recall that \(H_i:=\mathop{\mathrm{aff}}(\mathcal{P}_i)\), that \(V_i\) is its direction space, and that \(\bar\mathcal{W}=\sum_{i=1}^N A_iV_i\). We regard \(\bar\mathcal{W}\) as a Euclidean space with the inner product inherited from \(\mathbb{R}^d\). Set \[\bar F(\bar w) := \frac{1}{N}\sum_{i=1}^N \Omega_{\mathcal{P}_i}^* \big(A_i^\top J_{\Pi_{\bar\mathcal{W}}}\bar w\big), \qquad \Phi(\pi_\otimes) := \frac{1}{N}\sum_{i=1}^N\Omega_{\mathcal{P}_i}(\pi_i),\] and define \(B\pi_\otimes:=N^{-1}\sum_i\Pi_{\bar\mathcal{W}}A_i\pi_i\).

For each \(i\), choose \(a_i\in H_i\) and define, for \(v\in V_i\), \(\widetilde{\Omega}_i(v) := \Omega_{\mathcal{P}_i}(a_i+v).\) On \(V_i\), \(\widetilde{\Omega}_i\) is closed, proper, and of Legendre type. Since its domain \(\mathcal{P}_i-a_i\) is compact, its conjugate is finite on all of \(V_i\). Hence, by [17], Theorem 26.5, \(\widetilde{\Omega}_i^*\) is of Legendre type and, in particular, strictly convex on \(V_i\).

Moreover, for every \(s\in\mathbb{R}^{d_i}\), \(\Omega_{\mathcal{P}_i}^*(s) = \langle s,a_i\rangle + \widetilde{\Omega}_i^*(\Pi_{V_i}s).\) Thus \(\Omega_{\mathcal{P}_i}^*\) is finite and continuously differentiable on \(\mathbb{R}^{d_i}\), affine along \(V_i^\perp\), and strictly convex along every segment whose direction does not belong to \(V_i^\perp\).

Let \(\bar w_a\neq\bar w_b\) and set \(u:=J_{\Pi_{\bar\mathcal{W}}}(\bar w_a-\bar w_b)\). If \(A_i^\top u\in V_i^\perp\) for every \(i\), then \(\langle u,A_iv_i\rangle=0\) for every \(v_i\in V_i\). Hence \(u\perp\sum_iA_iV_i=\bar\mathcal{W}\). Since \(u\in\bar\mathcal{W}\), this would give \(u=0\), a contradiction. Thus at least one summand of \(\bar F\) is strictly convex along \([\bar w_a,\bar w_b]\), while all the others are convex. Therefore \(\bar F\) is strictly convex. Since it is differentiable on its whole domain \(\bar\mathcal{W}\), it is of Legendre type. Furthermore, \(\bar F\) is closed, and hence \(\bar F=\bar F^{**}=\Omega_{\bar\mathcal{M}}^*\) by [17], Theorem 12.2.

Now let \(p:=B\Phi\) be the image function \[p(\bar\nu) := \inf\{\Phi(\pi_\otimes)\colon B\pi_\otimes=\bar\nu\}.\] Since \(\mathop{\mathrm{dom}}\Phi=\prod_i\mathcal{P}_i\) is compact, \(p\) is proper and lower semicontinuous, and its infimum is attained whenever it is finite; it is convex by [17], Theorem 5.7. Moreover, [17], Theorem 16.3 gives \(p^*=\Phi^*\circ B^*\). Since \(B^*\bar w=(N^{-1}A_i^\top J_{\Pi_{\bar\mathcal{W}}}\bar w)_i\), the scaling rule for conjugates yields \[p^*(\bar w) = \frac{1}{N}\sum_{i=1}^N \Omega_{\mathcal{P}_i}^* \big(A_i^\top J_{\Pi_{\bar\mathcal{W}}}\bar w\big) = \bar F(\bar w).\] Therefore, again by [17], Theorem 12.2, \(\Omega_{\bar\mathcal{M}}=\bar F^*=p^{**}=p\), which proves 37 . It also gives \[\mathop{\mathrm{dom}}\Omega_{\bar\mathcal{M}} = B\Big(\prod_{i=1}^N\mathop{\mathrm{dom}}\Omega_{\mathcal{P}_i}\Big) = \bar\mathcal{M}.\]

Finally, let \(\bar\nu\in\mathop{\mathrm{rel\,int}}(\bar\mathcal{M})\). By [17], Theorem 26.5, \[\bar w:=\nabla\Omega_{\bar\mathcal{M}}(\bar\nu) \quad\text{satisfies}\quad \bar\nu=\nabla\bar F(\bar w).\] Define \(\pi_i := \nabla\Omega_{\mathcal{P}_i}^* \big(A_i^\top J_{\Pi_{\bar\mathcal{W}}}\bar w\big).\) Differentiating \(\bar F\) gives \(B\pi_\otimes=\bar\nu\). Furthermore, Fenchel’s equality [17] Theorem 23.5, applied to each \(i\), gives \[\Phi(\pi_\otimes) = \langle\bar w,B\pi_\otimes\rangle-\bar F(\bar w) = \langle\bar w,\bar\nu\rangle-\bar F(\bar w) = \Omega_{\bar\mathcal{M}}(\bar\nu).\] Thus \(\pi_\otimes\) attains the minimum in 37 , with the claimed expression. ◻

Proof of Proposition [prop:FYLandCalM]. We first prove Equation 38 . By definition, the parameter \(w\) minimizes the empirical average of the Fenchel–Young losses. Expanding the loss, the objective to minimize is: \[\frac{1}{N} \sum_{i=1}^N \mathcal{L}_{\Omega_{\mathcal{P}_i}}(A_i^\top w, \pi_i) = \frac{1}{N} \sum_{i=1}^N \Big( \Omega_{\mathcal{P}_i}(\pi_i) + \Omega_{\mathcal{P}_i}^*(A_i^\top w) - \langle A_i^\top w, \pi_i \rangle \Big).\] Because \(\pi_i\) is fixed, minimizing this objective with respect to \(w\) is equivalent to minimizing: \[\frac{1}{N} \sum_{i=1}^N \Omega_{\mathcal{P}_i}^*(A_i^\top w) - \Big\langle w, \frac{1}{N} \sum_{i=1}^N A_i \pi_i \Big\rangle.\] By introducing the aggregated moment \(\nu = \frac{1}{N} \sum_{i=1}^N A_i \pi_i\), the unconstrained minimization problem for the full parameter \(w\) is exactly the minimization of \(\frac{1}{N} \sum_{i=1}^N \Omega_{\mathcal{P}_i}^*(A_i^\top w) - \langle w, \nu \rangle\).

We restrict our attention to the identifiable parameter \(\bar w = \Pi_{\bar \mathcal{W}}(w)\) via the canonical injection \(w = J_{\Pi_{\bar \mathcal{W}}} \bar w\). The objective mapped to the identifiable space \(\bar \mathcal{W}\) becomes: \[\underbrace{\frac{1}{N} \sum_{i=1}^N \Omega_{\mathcal{P}_i}^*(A_i^\top J_{\Pi_{\bar \mathcal{W}}} \bar w)}_{= \bar F(\bar w)} - \langle J_{\Pi_{\bar \mathcal{W}}} \bar w, \nu \rangle.\] Using the adjoint property of the canonical injection \(J_{\Pi_{\bar \mathcal{W}}}\), we have \(\langle J_{\Pi_{\bar \mathcal{W}}} \bar w, \nu \rangle = \langle \bar w, \Pi_{\bar \mathcal{W}}(\nu) \rangle = \langle \bar w, \bar \nu \rangle\). Thus, \(\bar w\) minimizes the strictly convex function \(\bar F(\bar w) - \langle \bar w, \bar \nu \rangle\). The first-order optimality condition yields: \[\nabla \bar F(\bar w) - \bar \nu = 0 \implies \bar \nu = \nabla \bar F(\bar w).\] Because \(\bar F\) is of Legendre type on the identifiable space, its gradient map is a bijection and we can invert it using the Fenchel conjugate \(\Omega_{\bar \mathcal{M}} = \bar F^*\). This gives \(\bar w = \nabla \Omega_{\bar \mathcal{M}}(\bar \nu)\), which is precisely \(\Pi_{\bar \mathcal{W}}(w) = \nabla \Omega_{\bar \mathcal{M}}\big(\Pi_{\bar \mathcal{W}}(\nu)\big)\), proving Equation 38 .

We now prove Equation 39 . Let us evaluate the average Fenchel–Young loss on the identifiable space using \(\bar w\): \[\begin{align} \frac{1}{N} \sum_{i=1}^N \mathcal{L}_{\Omega_{\mathcal{P}_i}}\big(A_i^\top J_{\Pi_{\bar \mathcal{W}}}\bar w, \pi_i\big) &= \frac{1}{N} \sum_{i=1}^N \Omega_{\mathcal{P}_i}(\pi_i) + \underbrace{\frac{1}{N} \sum_{i=1}^N \Omega_{\mathcal{P}_i}^*(A_i^\top J_{\Pi_{\bar \mathcal{W}}}\bar w)}_{= \bar F(\bar w)} \\ &\quad - \Big\langle J_{\Pi_{\bar \mathcal{W}}}\bar w, \frac{1}{N} \sum_{i=1}^N A_i \pi_i \Big\rangle. \end{align}\] Substituting \(\nu = \frac{1}{N} \sum_{i=1}^N A_i \pi_i\) and reusing the adjoint property \(\langle J_{\Pi_{\bar \mathcal{W}}}\bar w, \nu \rangle = \langle \bar w, \bar \nu \rangle\), the equation simplifies to: \[\frac{1}{N} \sum_{i=1}^N \mathcal{L}_{\Omega_{\mathcal{P}_i}}\big(A_i^\top J_{\Pi_{\bar \mathcal{W}}}\bar w, \pi_i\big) = \frac{1}{N} \sum_{i=1}^N \Omega_{\mathcal{P}_i}(\pi_i) + \bar F(\bar w) - \langle \bar w, \bar \nu \rangle.\] From the first part of the proof, we established that \(\bar w = \nabla \Omega_{\bar \mathcal{M}}(\bar \nu)\) and \(\bar \nu = \nabla \bar F(\bar w)\). Because \((\bar w, \bar \nu)\) form a conjugate pair linked by the gradient of the Legendre-type function \(\bar F\), Fenchel’s equality holds tightly: \[\bar F(\bar w) + \Omega_{\bar \mathcal{M}}(\bar \nu) = \langle \bar w, \bar \nu \rangle \implies \bar F(\bar w) - \langle \bar w, \bar \nu \rangle = - \Omega_{\bar \mathcal{M}}(\bar \nu).\] Substituting this relation back into our expanded loss expression yields: \[\frac{1}{N} \sum_{i=1}^N \mathcal{L}_{\Omega_{\mathcal{P}_i}}\big(A_i^\top J_{\Pi_{\bar \mathcal{W}}}\bar w, \pi_i\big) = \frac{1}{N} \sum_{i=1}^N \Omega_{\mathcal{P}_i}(\pi_i) - \Omega_{\bar \mathcal{M}}(\bar \nu),\] which establishes Equation 39 , concluding the proof. ◻

Proof of Proposition [prop:contextualRegularization]. The first four statements of the proposition follow directly as a corollary of Proposition [prop:barOmegaProperties]. By setting the polytopes \(\mathcal{P}_i = \Delta^{\mathcal{Y}(x_i)}\), and the linear operators \(A_i = \phi_i Y(x_i)\), the function \(\bar{F}(\bar{w})\) defined in this section perfectly matches the aggregate dual regularizer \(\bar{F}\) of Proposition [prop:barOmegaProperties]. Since the restriction of \(\Omega_{\Delta^{\mathcal{Y}(x_i)}}\) to its affine hull \(H_{\Delta}\) is of Legendre type, it satisfies all structural requirements of Proposition [prop:barOmegaProperties]. Consequently, \(\bar{F}\) is of Legendre type, \(\Omega_{\bar{\mathcal{M}}} = \bar{F}^*\), the infimal convolution expression 27 holds, the domain is \(\bar{\mathcal{M}}\), and the minimum is attained at \(q_i = \nabla \Omega_{\Delta^{\mathcal{Y}(x_i)}}^*(Y(x_i)^\top \phi_i^\top J_{\Pi_{\bar\mathcal{W}}} \nabla \Omega_{\bar{\mathcal{M}}}(\bar{\nu}))\).

We now prove Equations 28 and 29 . These equations follow directly as a corollary of the Proposition [prop:FYLandCalM] using the same definition of \(\mathcal{P}_i\), \(\Omega_{\mathcal{P}_i}\), and \(A_i\) as above. The unconstrained minimization of the coordination loss and the definition of the aggregated moment \(\nu = \frac{1}{N} \sum_{i=1}^N \phi_i Y(x_i) q_i\) exactly match the premises of the proposition. Applying the proposition immediately yields the dual parameter mapping \(\Pi_{\bar \mathcal{W}}(w) = \nabla \Omega_{\bar \mathcal{M}}\big(\Pi_{\bar \mathcal{W}}(\nu)\big)\) of Equation 28 and the cross Jensen gap equality of Equation 29 , concluding the proof. ◻

Proof of Theorem [theo:proximalPointOperator]. We proceed by induction. The base case \(t=0\) holds by construction: both algorithms are initialized at \(\bar \nu^{(0)} = \nabla \Omega_{\bar \mathcal{M}}^*(\bar w^{(0)})\). Assume that at step \(t\), \(\bar \nu^{(t)} = \nabla \Omega_{\bar \mathcal{M}}^*(\bar w^{(t)})\), where we denote the identifiable parameter as \(\bar w^{(t)} = \Pi_{\bar \mathcal{W}}(w^{(t)})\). Because \(\Omega_{\bar \mathcal{M}}\) is of Legendre type on the full-dimensional \(\bar\mathcal{M}\), we have \(\bar w^{(t)} = \nabla \Omega_{\bar \mathcal{M}}(\bar \nu^{(t)})\) and \(D_{\Omega_{\bar \mathcal{M}}}(\bar \nu \mid \bar \nu^{(t)}) = \mathcal{L}_{\Omega_{\bar \mathcal{M}}}(\bar w ^{(t)}, \bar \nu)\).

The update rule for the Bregman proximal algorithm is: \[\bar \nu^{(t+1)} = \mathop{\mathrm{argmin}}_{\bar \nu \in \bar \mathcal{M}} f_\kappa(\bar \nu) + \kappa D_{\Omega_{\bar \mathcal{M}}}\big(\bar \nu \mid \bar \nu^{(t)}\big) = \mathop{\mathrm{argmin}}_{\bar \nu \in \bar \mathcal{M}} f_\kappa(\bar \nu) + \kappa \mathcal{L}_{\Omega_{\bar \mathcal{M}}}(\bar w ^{(t)}, \bar \nu) .\] Let us now detail the minimization problem \[\begin{align} &\min_{\bar \nu \in \bar \mathcal{M}} f_\kappa(\bar \nu) + \kappa \mathcal{L}_{\Omega_{\bar \mathcal{M}}}(\bar w ^{(t)}, \bar \nu)\\ &= \left| \begin{aligned} \min_{\bar \nu, \bar q} \frac{1}{N} \,&\sum_{i=1}^N \Big( \langle \gamma_i, q_i \rangle + \big(\kappa \Omega_{\Delta^{\mathcal{Y}(x_i)}}(q_i) + \kappa\overbrace{\Omega_{\Delta^{\mathcal{Y}(x_i)}}^*(Y_i^\top\phi_i^\top J_{\Pi_{\bar \mathcal{W}}} \bar w^{(t)} )}^{\text{constant}} \\ &\qquad - \kappa\langle Y_i^\top\phi_i^\top J_{\Pi_{\bar \mathcal{W}}} \bar w^{(t)} | q_i \rangle \big) \Big) \\ s.t.\colon\, & \frac{1}{N} \sum_{i=1}^N \Pi_{\bar \mathcal{W}}\big(\phi_i Y(x_i) q_i\big) = \bar \nu \end{aligned} \right. \end{align}\] where we have used the definition of \(f_{\kappa}\) and \(\Omega_{\bar \mathcal{M}}^*(\bar w^{(t)})\) (Proposition [prop:barOmegaProperties].1 and Equation 36 ), brought the Fenchel–Young loss within the minimization in \(q_{\otimes}\), merged the two minimizations in \(\bar \nu\) and \(q_{\otimes}\), and simplified \(\kappa \Omega_{\bar \mathcal{M}}(\bar \nu)\), which appears with a negative sign in \(f_\kappa(\bar \nu)\) and a positive sign in the Fenchel–Young loss. Observe that since we minimize jointly in \(q_{\otimes}\) and \(\bar \nu\), we can just minimize in \(q_{\otimes}\) without constraint and define \(\bar \nu = \frac{1}{N} \sum_{i=1}^N \Pi_{\bar \mathcal{W}}\big(\phi_i Y(x_i) q_i\big)\) a posteriori. Furthermore, the minimization decomposes by \(i\), and we get \[\begin{align} \tilde{q}_i &= \mathop{\mathrm{argmin}}_{q_i} \langle \gamma_i, q_i \rangle + \kappa\big( \Omega_{\Delta^{\mathcal{Y}(x_i)}}(q_i) - \langle Y_i^\top\phi_i^\top J_{\Pi_{\bar \mathcal{W}}} \bar w^{(t)} | q_i \rangle \big) \\ &= \mathop{\mathrm{argmin}}_{q_i \in \Delta^{\mathcal{Y}(x_i)}} \langle \gamma_i, q_i \rangle + \kappa\mathcal{L}_{\Omega_{\Delta^{\mathcal{Y}(x_i)}}}(Y_i^\top\phi_i^\top J_{\Pi_{\bar \mathcal{W}}} \bar w^{(t)},q_i) \\ &= \mathop{\mathrm{argmin}}_{q_i \in \Delta^{\mathcal{Y}(x_i)}} \langle \gamma_i, q_i \rangle + \kappa \mathcal{L}_{\Omega_{\Delta^{\mathcal{Y}(x_i)}}}(Y_i^\top\phi_i^\top w^{(t)},q_i)\\ \bar \nu^{(t+1)} &= \frac{1}{N}\Pi_{\bar \mathcal{W}} \sum_{i=1}^N \phi_iY_i\tilde{q}_i,\\ \Pi_{\bar \mathcal{W}}(\tilde{w}) &= \nabla \Omega_{\bar \mathcal{M}}(\bar \nu^{(t+1)}) \quad \text{where} \quad\tilde{w} \in \mathop{\mathrm{argmin}}\frac{1}{N}\sum_{i=1}^N \mathcal{L}_{\Omega_{\Delta^{\mathcal{Y}(x_i)}}}(Y_i^\top\phi_i^\top w,\tilde{q}_i) \end{align}\] where the first two minima are equal up to a constant by definition of Fenchel–Young losses, and the last two are again equal up to a constant by Proposition 3.2. The remaining equalities follow from Proposition [prop:contextualRegularization]. These are exactly the iterates of our alternating minimization, and we therefore obtain the induction hypothesis and the theorem. ◻

Proof of Proposition [prop:convexityfkappa]. Set \(Aq_\otimes:=\bar\nu(q_\otimes)\) and define \[H(q_\otimes):= \frac{1}{N}\sum_{i=1}^N\langle\gamma_i,q_i\rangle +\kappa\left( \frac{1}{N}\sum_{i=1}^N\Omega_{\Delta^{\mathcal{Y}(x_i)}}(q_i) -\Omega_{\bar\mathcal{M}}(Aq_\otimes) \right) +\mathbb{I}_{\Delta_\otimes}(q_\otimes).\] By assumption, the cross Jensen gap is convex; hence \(H\) is convex. Moreover, by 30 , \(f_\kappa(\bar\nu)=\inf\{H(q_\otimes)\colon Aq_\otimes=\bar\nu\}\). Thus \(f_\kappa\) is the image function of \(H\) under the linear map \(A\), and is convex by [17], Theorem 5.7. ◻

Proof. We first consider a single observation and omit the dependence on \(x\) and \(\xi\) to alleviate notation. Set \(F:=\Omega_\Delta^*\) and \(s:=Y^\top\theta\). As the partial surrogate 17 is obtained by partially minimizing the surrogate 14 , we have \[\begin{align} \underline{\mathcal{S}_{\Omega_\Delta}}(\theta) &= \min_{q\in\Delta^\mathcal{Y}} \left\{ \langle\gamma\mid q\rangle + \kappa\big( \Omega_\Delta(q)+F(s)-\langle s\mid q\rangle \big) \right\} \\ &= \kappa F(s) + \kappa \min_{q\in\Delta^\mathcal{Y}} \left\{ \Omega_\Delta(q)-\langle s-\gamma/\kappa\mid q\rangle \right\} = \kappa\Big(F(s)-F(s-\gamma/\kappa)\Big), \end{align}\] where the last equality follows from the definition of the Fenchel conjugate.

The policy associated with \(s\) is \(\nabla F(s)\), so its expected cost is \(R_\Delta(\nabla F(s))=\langle\gamma\mid\nabla F(s)\rangle\) (see 11 ). Consequently, \[\begin{align} R_\Delta(\nabla F(s)) - \underline{\mathcal{S}_{\Omega_\Delta}}(\theta) &= \kappa\left( F(s-\gamma/\kappa)-F(s) + \langle\nabla F(s)\mid\gamma/\kappa\rangle \right) = \kappa D_F(s-\gamma/\kappa\mid s). \end{align}\] This quantity is nonnegative by convexity of \(F\). Since \(\nabla F\) is \(1/L_x\)-Lipschitz-continuous, the descent lemma (see e.g. [16] Lemma 3.1), applied at \(u=s-\gamma/\kappa\) and \(v=s\), gives \(D_F(s-\gamma/\kappa\mid s)\leq\|\gamma/\kappa\|^2/(2L_x)\). This proves 18 .

Applying this identity to each observation and averaging proves 19 . In particular, \(\underline{\mathcal{S}_{\Omega_\Delta,N}}(\varphi_w) \leq\mathcal{R}_{\Omega_\Delta,N}(\varphi_w)\) for every \(w\in\mathcal{W}\). Finally, by optimality of \(w_{\mathcal{S}}\) and the preceding one-sided inequality, \(\underline{\mathcal{S}_{\Omega_\Delta,N}}(\varphi_{w_{\mathcal{S}}}) \leq \underline{\mathcal{S}_{\Omega_\Delta,N}}(\varphi_{w_{\mathcal{R}}}) \leq \mathcal{R}_{\Omega_\Delta,N}(\varphi_{w_{\mathcal{R}}}).\) It follows that \[\mathcal{R}_{\Omega_\Delta,N}(\varphi_{w_{\mathcal{S}}}) - \mathcal{R}_{\Omega_\Delta,N}(\varphi_{w_{\mathcal{R}}}) \leq \mathcal{R}_{\Omega_\Delta,N}(\varphi_{w_{\mathcal{S}}}) - \underline{\mathcal{S}_{\Omega_\Delta,N}}(\varphi_{w_{\mathcal{S}}}),\] and 20 follows from 19 . ◻

Proof. Step 1: invariance of the primal update. Fix \(i\in[N]\), \(t\ge0\), and let \(\theta \in \mathbb{R}^d\). For every \(\lambda>0\) and every realization of \(\mathbf{Z}\), \[c_i(y) - \kappa(\theta + \varepsilon \mathbf{Z})^\top y \;= \;c_i(y) - \frac{\kappa}{\lambda}\big(\lambda\theta + \lambda\varepsilon \mathbf{Z}\big)^\top y, \qquad \forall y \in \mathcal{Y},\] the two sides are identical as functions of \(y\), so their \(\mathop{\mathrm{argmin}}\) over \(y \in \mathcal{Y}\), and thus its expectation under \(\mathbf{Z}\), coincide. Writing \(\mu_i^{(t+1)}(\kappa,\varepsilon,\theta)\) for the corresponding primal update, we get \[\label{eq:primal95invariance} \mu_i^{(t+1)}(\kappa,\varepsilon,\theta) \;= \;\mu_i^{(t+1)}\Big(\frac{\kappa}{\lambda},\;\lambda\varepsilon,\;\lambda\theta\Big), \qquad \forall \lambda>0.\tag{42}\]

Step 2: scaling law of \(F_{\varepsilon,\mathcal{C}}\) and \(\Omega_{\varepsilon,\mathcal{C}}\). By definition 32 , for every \(\theta\in\mathbb{R}^d\) and \(\varepsilon>0\), \[F_{\varepsilon,\mathcal{C}}(\theta) = \mathbb{E}\big[\max_{y \in \mathcal{Y}}(\theta+\varepsilon \mathbf{Z})^\top y\big] = \varepsilon\, \mathbb{E}\big[\max_{y \in \mathcal{Y}}(\theta/\varepsilon+\mathbf{Z})^\top y\big] = \varepsilon\, F_{1,\mathcal{C}}(\theta/\varepsilon).\] Taking Fenchel conjugates on both sides (using that conjugation of \(\theta \mapsto \varepsilon g(\theta/\varepsilon)\) yields \(\varepsilon g^*\) for any \(g\)), \[\Omega_{\varepsilon,\mathcal{C}} = \varepsilon\,\Omega_{1,\mathcal{C}}, \qquad \text{hence} \qquad \nabla\Omega_{\varepsilon,\mathcal{C}|_V} = \varepsilon\,\nabla\Omega_{1,\mathcal{C}|_V}.\]

Step 3: dual update. The coordination step reads, with \(\bar\mu^{(t+1)} := \frac{1}{N}\sum_{i=1}^N \mu_i^{(t+1)}\), \[\theta^{(t+1)} \in \mathop{\mathrm{argmin}}_{\theta \in \mathbb{R}^d} \frac{1}{N}\sum_{i=1}^N\mathcal{L}_{\Omega_{\varepsilon,\mathcal{C}}}\big(\theta; \mu_i^{(t+1)}\big) = \frac{1}{N}\sum_{i=1}^N\Omega_{\varepsilon,\mathcal{C}}\big(\mu_i^{(t+1)}\big) + F_{\varepsilon,\mathcal{C}}(\theta) - \langle \theta \,|\, \bar\mu^{(t+1)}\rangle,\] using \(\Omega_{\varepsilon,\mathcal{C}}^* = F_{\varepsilon,\mathcal{C}}\). Write \(\theta = \theta_V + \theta_{V^\perp}\) with \(\theta_V = \Pi_V(\theta)\). By Point 2 of Theorem [prop:SparsePerturbation], for any fixed \(y_0 \in \mathcal{C}\), \[F_{\varepsilon,\mathcal{C}}(\theta) = \langle y_0 \mid \theta_{V^\perp}\rangle + F_{\varepsilon,\mathcal{C}}(\theta_V).\] Since \(\bar\mu^{(t+1)} \in \mathcal{C}\subset H = y_0 + V\), its \(V^\perp\)-component equals \(y_0\), so \(\langle \theta \mid \bar\mu^{(t+1)}\rangle = \langle \theta_V \mid \bar\mu^{(t+1)}\rangle + \langle \theta_{V^\perp} \mid y_0\rangle\). The two \(\theta_{V^\perp}\)-terms cancel in the objective, which reduces to minimizing \(F_{\varepsilon,\mathcal{C}}(\theta_V) - \langle \theta_V \mid \bar\mu^{(t+1)}\rangle\) over \(\theta_V \in V\) alone. Since \(F_{\varepsilon,\mathcal{C}}|_V\) is Legendre-type (Theorem [prop:SparsePerturbation], Point 4), the minimizer in \(V\) is unique and given by gradient inversion; taking the canonical representative \(\theta^{(t+1)} \in V\) and using Step 2, \[\theta^{(t+1)} = \nabla\Omega_{\varepsilon,\mathcal{C}|_V}\big(\bar\mu^{(t+1)}\big) = \varepsilon\, \nabla\Omega_{1,\mathcal{C}|_V}\big(\bar\mu^{(t+1)}\big) \in V.\]

Step 4: induction. We show by induction on \(t\) that \(\mu_i^{(t)}(\kappa,\varepsilon) = \mu_i^{(t)}(1,\kappa\varepsilon)\) for every \(i\), and \(\theta^{(t)}(\kappa,\varepsilon) = \theta^{(t)}(1,\kappa\varepsilon)/\kappa\). The base case \(t=0\) holds since both trajectories start at \(0 \in V\). Note that Step 3 maps every iterate to \(V\), so we consider \(\theta^{(t)} \in V\) for all \(t \geq 0\). Assume it holds at \(t\). By 42 with \(\lambda=\kappa\) and \(\theta = \theta^{(t)}(\kappa,\varepsilon) = \theta^{(t)}(1,\kappa\varepsilon)/\kappa\), \[\mu_i^{(t+1)}(\kappa,\varepsilon) = \mu_i^{(t+1)}\Big(\kappa,\varepsilon,\;\tfrac{1}{\kappa}\theta^{(t)}(1,\kappa\varepsilon)\Big) = \mu_i^{(t+1)}\Big(1,\;\kappa\varepsilon,\;\theta^{(t)}(1,\kappa\varepsilon)\Big) = \mu_i^{(t+1)}(1,\kappa\varepsilon), \qquad \forall i\in[N].\] Averaging over \(i\) and applying Step 3 at \((\kappa,\varepsilon)\) and at \((1,\kappa\varepsilon)\) – both evaluated, by the previous display, at the same \(\bar\mu^{(t+1)}\) –, \[\theta^{(t+1)}(\kappa,\varepsilon) = \varepsilon\,\nabla\Omega_{1,\mathcal{C}|_V}\big(\bar\mu^{(t+1)}\big), \qquad \theta^{(t+1)}(1,\kappa\varepsilon) = \kappa\varepsilon\,\nabla\Omega_{1,\mathcal{C}|_V}\big(\bar\mu^{(t+1)}\big),\] so the two right-hand sides differ exactly by the factor \(\kappa\), i.e.,\(\theta^{(t+1)}(\kappa,\varepsilon) = \theta^{(t+1)}(1,\kappa\varepsilon)/\kappa\), which closes the induction.

Finally, for arbitrary \(\lambda>0\), both \((\kappa,\varepsilon)\) and \((\kappa/\lambda,\lambda\varepsilon)\) have the same product \(\kappa\varepsilon\), so the induction above (applied once to each pair against the common reference \((1,\kappa\varepsilon)\)) yields \(\mu_i^{(t)}(\kappa,\varepsilon)=\mu_i^{(t)}(1,\kappa\varepsilon)=\mu_i^{(t)}(\kappa/\lambda,\lambda\varepsilon)\), and similarly \(\theta^{(t)}(\kappa,\varepsilon) = \theta^{(t)}(1,\kappa\varepsilon)/\kappa = \theta^{(t)}(\kappa/\lambda,\lambda\varepsilon)/\lambda\), which is the claimed identity. ◻

Proof of Theorem 8. Set \(\Delta_{t+1}:=u^{(t+1)}-u^{(t)}\). Since \(f\) is lower semicontinuous and finite on the compact set \(\mathcal{U}\), it is bounded below. Using \(u^{(t)}\) as a feasible point in 43 and (H2), we obtain, with \(a:=\kappa/(2L)\), \[f(u^{(t)})-f(u^{(t+1)}) \ge \kappa D_h(u^{(t+1)}\mid u^{(t)}) \ge a\|\Delta_{t+1}\|^2 .\label{eq:generic95SD}\tag{44}\]

Hence \(f(u^{(t)})\downarrow f_*:=\lim_t f(u^{(t)})\), \(\sum_t\|\Delta_{t+1}\|^2<+\infty\), and \(\|\Delta_{t+1}\|\to0\).

Since \(u^{(t+1)}\in\operatorname{relint}(\mathcal{U})\), the first-order optimality condition for 43 , together with the exact sum rule ([37] Ex. 8.8) for the limiting subdifferential, gives \[\xi^{(t+1)} := \kappa\big(\nabla h(u^{(t)})-\nabla h(u^{(t+1)})\big) \in \partial f(u^{(t+1)}).\label{eq:generic95RE0}\tag{45}\] Moreover, by (H1), \(\nabla h\) is Lipschitz on every compact subset of \(\operatorname{relint}(\mathcal{U})\).

Assume that there exists an accumulation point \(\tilde{u}\) of \((u^{(t)})\) in \(\operatorname{relint}(\mathcal{U})\). Then by continuity of \(f\) on \(\operatorname{relint}(\mathcal{U})\), \(f_*=f(\tilde{u})\). Let \(\rho>0\) be such that \(\bar B(\tilde{u},2\rho)\subset\operatorname{relint}(\mathcal{U})\), and let \(b\) be a Lipschitz constant of \(\kappa\nabla h\) on this ball. Whenever \(u^{(t)},u^{(t+1)}\in\bar B(\tilde{u},2\rho)\), 45 therefore gives \[\operatorname{dist}(0,\partial f(u^{(t+1)})) \le b\|\Delta_{t+1}\|.\label{eq:generic95RE}\tag{46}\]

By (H3), \(f\) is real analytic near \(\tilde{u}\in\operatorname{relint}(\mathcal{U})\), hence it satisfies the KL inequality there. Choose a KL neighborhood \(U\), a level \(\eta>0\), and a desingularizer \(\varphi\). Shrinking \(\rho>0\) if necessary, assume \(\bar B(\tilde{u},2\rho)\subset U\cap\operatorname{relint}(\mathcal{U})\).

If \(f(u^{(t_0)})=f(\tilde{u})\) for some \(t_0\), then 44 makes the sequence stationary from \(t_0\) onward, and the capture conclusion is immediate. We therefore assume below that \(f(u^{(t)})>f(\tilde{u})\) for every \(t\).

Since \(\tilde{u}\) is an accumulation point, there is a subsequence \(u^{(t_j)}\to\tilde{u}\). Along this subsequence, \(\|\Delta_{t_j+1}\|\to0\), \(f(u^{(t_j)})\to f(\tilde{u})\), and \(\varphi(f(u^{(t_j)})-f(\tilde{u}))\to0\). Hence we may choose \(t_1=t_j\) large enough so that \(u^{(t_1)}\in B(\tilde{u},\rho)\), \(u^{(t_1+1)}\in B(\tilde{u},2\rho)\), \(0<f(u^{(t_1)})-f(\tilde{u})<\eta\), and \[\|u^{(t_1)}-\tilde{u}\| +2\|\Delta_{t_1+1}\| +\frac{b}{a}\varphi(f(u^{(t_1)})-f(\tilde{u})) <2\rho .\label{eq:generic95capture95condition}\tag{47}\]

We now prove the KL capture. Suppose that \(u^{(t)},u^{(t+1)}\in\bar B(\tilde{u},2\rho)\). Since \(f(u^{(t+1)})>f(\tilde{u})\), the KL inequality applies at \(u^{(t+1)}\). Moreover, \(\|\Delta_{t+1}\|>0\): otherwise 46 would give \(\operatorname{dist}(0,\partial f(u^{(t+1)}))=0\), contradicting the KL inequality because \(f(u^{(t+1)})>f(\tilde{u})\). Combining KL with 46 , the concavity of \(\varphi\), and the global sufficient decrease 44 gives \[\|\Delta_{t+2}\|^2 \le \frac{b}{a}\|\Delta_{t+1}\| \big( \varphi(f(u^{(t+1)})-f(\tilde{u})) - \varphi(f(u^{(t+2)})-f(\tilde{u})) \big).\] The AM–GM inequality then yields \[2\|\Delta_{t+2}\| \le \|\Delta_{t+1}\| +\frac{b}{a} \big( \varphi(f(u^{(t+1)})-f(\tilde{u})) - \varphi(f(u^{(t+2)})-f(\tilde{u})) \big).\label{eq:generic95KL95step}\tag{48}\]

Let \[T^*:=\sup\{T\ge t_1+1: u^{(s)}\in\bar B(\tilde{u},2\rho) \text{ for all }t_1\le s\le T\}.\] Then \(T^*\ge t_1+1\). If \(T^*<+\infty\), summing 48 for \(t=t_1,\ldots,T^*-1\) gives \[\sum_{s=t_1+1}^{T^*+1}\|\Delta_s\| \le 2\|\Delta_{t_1+1}\| +\frac{b}{a}\varphi(f(u^{(t_1+1)})-f(\tilde{u})) \le 2\|\Delta_{t_1+1}\| +\frac{b}{a}\varphi(f(u^{(t_1)})-f(\tilde{u})).\] Therefore, by 47 , \[\|u^{(T^*+1)}-\tilde{u}\| \le \|u^{(t_1)}-\tilde{u}\| + \sum_{s=t_1+1}^{T^*+1}\|\Delta_s\| <2\rho,\] contradicting the maximality of \(T^*\). Hence \(T^*=+\infty\), the whole tail remains in \(\bar B(\tilde{u},2\rho)\), and as \(T^*=\infty\) in the same estimate gives \(\sum_{t\ge t_1}\|u^{(t+1)}-u^{(t)}\|<+\infty\).

Thus \(u^{(t)}\) is Cauchy and converges to \(\tilde{u}\), as a subsequence was already shown to converge to \(\tilde{u}\). Since \(\xi^{(t+1)}\to0\), \(u^{(t+1)}\to\tilde{u}\), and \(f(u^{(t+1)})\to f(\tilde{u})\), the closedness of the limiting-subdifferential [37] Prop. 8.7 graph yields \(0\in\partial f(\tilde{u})\).

It remains to record the value rate. If \(f(u^{(t_0)})=f(\tilde{u})\) for some \(t_0\), then 44 makes the sequence stationary from \(t_0\) onward. Otherwise, after the KL capture, the tail satisfies the standard sufficient-decrease and relative-error assumptions in a fixed KL neighborhood. Since \(f\) is analytic near \(\tilde{u}\), the KL inequality can be taken in power form; equivalently, for some \(\theta\in[\tfrac12,1)\) and \(c>0\), \(\operatorname{dist}(0,\partial f(u)) \ge c\big(f(u)-f(\tilde{u})\big)^\theta\) near \(\tilde{u}\). Applying the standard KL rate estimate [39] Thm. 4 to \(r_t:=f(u^{(t)})-f(\tilde{u})\) gives a linear rate when \(\theta=\tfrac12\), and \(r_t=\mathcal{O}\!\left(t^{-1/(2\theta-1)}\right)\) when \(\theta>\tfrac12\). In particular, \(r_t=\mathcal{O}(1/t)\).

We now prove the boundary alternative. If \(\omega\subseteq\operatorname{rbd}(\mathcal{U})\) and \((v^{(t)})\) had a bounded subsequence, then, up to extraction, \(v^{(t_j)}\to\bar v\in E\). By (H1), \(u^{(t_j)}=\nabla h^*(v^{(t_j)})\to\nabla h^*(\bar v)\in \operatorname{relint}(\mathcal{U})\), contradicting \(\omega\subseteq\operatorname{rbd}(\mathcal{U})\). Hence \(\|v^{(t)}\|\to+\infty\).

Finally, in the capture case, the tail of \((u^{(t)})\) lies in a compact subset of \(\operatorname{relint}(\mathcal{U})\), where \(\nabla h\) is Lipschitz. Thus \(v^{(t)}=\nabla h(u^{(t)})\to\nabla h(\tilde{u})\), and finite length of \((u^{(t)})\) transfers to finite length of \((v^{(t)})\). ◻

Proof. The formula for \(G_\kappa^*\) follows by eliminating the affine image variable in ?? : \(G_\kappa^*(\lambda)=\sup_{q_\otimes\in\Delta_\otimes} \tfrac1N\sum_i\{\langle A_i^\top J\lambda-\gamma_i,q_i\rangle -\kappa\Omega_i(q_i)\}\), and the product structure of \(\Delta_\otimes\) gives the stated sum of conjugates. Using \(f_\kappa=G_\kappa-\kappa\Omega_{\bar{\mathcal{M}}}\), Fenchel duality, and the identity \(G_\kappa^*(\kappa\bar w)=\kappa\tilde{\bar F}(\bar w)\), we get \[\min_{\bar\nu\in\bar{\mathcal{M}}} \{f_\kappa(\bar\nu)+\kappa\mathcal{L}_{\Omega_{\bar{\mathcal{M}}}}(\bar w^{(t)},\bar\nu)\} = \underline{S_{\Delta,N}}(\bar w^{(t)}).\] Evaluating the minimum at \(\bar\nu^{(t)}=\nabla\Omega_{\bar{\mathcal{M}}}^*(\bar w^{(t)})\) gives the upper bound, since the Fenchel–Young loss vanishes there. Moreover, \(\mathcal{L}_{\Omega_{\bar{\mathcal{M}}}}(\bar w^{(t)},\bar\nu) =D_{\Omega_{\bar{\mathcal{M}}}}(\bar\nu\mid\bar\nu^{(t)})\), so the minimum is the proximal objective in 31 , attained at \(\bar\nu^{(t+1)}\). Positivity of the Bregman divergence gives the lower bound. Since \(f_\kappa(\bar\nu^{(t)})\) decreases to \(f_\kappa(\bar\nu^*)\), the sandwich implies \(\underline{S_{\Delta,N}}(\bar w^{(t)})\to f_\kappa(\bar\nu^*).\) Moreover, \(\bar w^{(t)}=\nabla\Omega_{\bar{\mathcal{M}}}(\bar\nu^{(t)})\to\bar w^*\), and \(\underline{S_{\Delta,N}}\) is continuous. Hence \(\underline{S_{\Delta,N}}(\bar w^*)=f_\kappa(\bar\nu^*)\). Finally, \(0\le \underline{S_{\Delta,N}}(\bar w^{(t)})-\underline{S_{\Delta,N}}(\bar w^*) \le f_\kappa(\bar\nu^{(t)})-f_\kappa(\bar\nu^*),\) so any upper rate for the primal value gap transfers to the dual value gap. ◻

Proof. By [4], Prop. 3.1 (adapting [30], Lemma 1.5), \(\nabla^2F_{\varepsilon,\mathcal{C}}(\theta)=\frac{1}{\varepsilon}\mathbb{E}[y^*(\theta+\varepsilon\mathbf{Z})\mathbf{Z}^\top]\) with \(y^*(\theta)\in\mathop{\mathrm{argmax}}_{y\in\mathcal{C}}\theta^\top y\) (any fixed measurable selection; the tie set where the argmax is not a singleton is Lebesgue-null). For \(v\in V\setminus\{0\}\), \(\|v\|=1\), decomposing \(\mathbf{Z}=\mathbf{r}v+\mathbf{Z}_\perp\) with \(\mathbf{r}\sim\mathcal{N}(0,1)\) independent of \(\mathbf{Z}_\perp\) reduces \(v^\top\nabla^2F_{\varepsilon,\mathcal{C}}(\theta)v\) to \(\frac{1}{\varepsilon}\mathbb{E}_{\mathbf{Z}_\perp}\mathbb{E}_\mathbf{r}[g(\mathbf{r})\mathbf{r}]\) with \(g(r):=v^\top y^*(\theta+\varepsilon\mathbf{Z}_\perp+\varepsilon rv)\) non-decreasing in \(r\) by monotonicity of the subdifferential of the support function \(F(\theta):=\max_{y\in\mathcal{C}}\theta^\top y\) [17] Thm. 24.8; since \(\mathbb{E}[\mathbf{r}]=0\) this makes \(\mathbb{E}_\mathbf{r}[g(\mathbf{r})\mathbf{r}]\ge0\) pointwise in \(\mathbf{Z}_\perp\), strictly so unless \(g\) is a.e.constant, which is excluded since \(v\ne0\) and \(V\) has dimension \(\ge1\) give distinct limits of \(g\) at \(\pm\infty\). The same argument applies to \(F_{\varepsilon,\mathcal{C},c}\) by replacing the support function with the convex function \(\theta\mapsto\max_{y\in\mathcal{C}}\{\theta^\top y-c(y)\}\); the subdifferential is still monotone, and the linear term \(\varepsilon rv^\top y\) dominates the bounded shift \(c(y)\) as \(r\to\pm\infty\). ◻

Proof. Define, for \(\theta\in\mathbb{C}^d\), \[\tilde{F}_{\varepsilon,\mathcal{C}}(\theta) = \frac{1}{(2\pi)^{d/2}\varepsilon^d} \int_{\mathbb{R}^d} F(u) \exp\!\left(-\frac{(u-\theta)^\top(u-\theta)}{2\varepsilon^2}\right) \,du,\] with \(F(u):=\max_{y\in\mathcal{C}}\{u^\top y-c(y)\}\). Note that, for \(\theta\in\mathbb{R}^d\), \(\tilde{F}_{\varepsilon,\mathcal{C}}(\theta)=F_{\varepsilon,\mathcal{C},c}(\theta)\), by the change of variable \(u=\theta+\varepsilon z\).

We first establish a compact-uniform domination bound. Since \(\mathcal{C}\) is compact and \(c\) continuous, \(|F(u)|\le R\|u\|+\|c\|_\infty\le C_0(1+\|u\|)\) with \(R:=\max_{y\in\mathcal{C}}\|y\|<+\infty\), \(\|c\|_\infty:=\max_{y\in\mathcal{C}}|c(y)|<+\infty\), and \(C_0:=\max\{R,\|c\|_\infty\}\). Let \(K\subset\mathbb{C}^d\) be compact and write \(\theta=\alpha+i\beta\), with \(\alpha,\beta\in\mathbb{R}^d\). On \(K\), there exist constants \(A_K,B_K<+\infty\) such that \(\|\alpha\|\le A_K\) and \(\|\beta\|\le B_K\) for all \(\theta=\alpha+i\beta\in K\). By bilinearity, and since \(u-\alpha,\beta\in\mathbb{R}^d\), \((u-\theta)^\top(u-\theta)=\|u-\alpha\|^2-\|\beta\|^2 -2i(u-\alpha)^\top\beta .\) Hence \[\left| \exp\!\left(-\frac{(u-\theta)^\top(u-\theta)}{2\varepsilon^2}\right) \right| = \exp\!\left(\frac{\|\beta\|^2}{2\varepsilon^2}\right) \exp\!\left(-\frac{\|u-\alpha\|^2}{2\varepsilon^2}\right).\] Moreover, \(\|u-\alpha\|^2 = \|u\|^2-2u^\top\alpha+\|\alpha\|^2 \ge \frac{1}{2}\|u\|^2-\|\alpha\|^2 \ge \frac{1}{2}\|u\|^2-A_K^2.\) Therefore, uniformly for \(\theta\in K\), \(\left| F(u) \exp\!\left(-\frac{(u-\theta)^\top(u-\theta)}{2\varepsilon^2}\right) \right| \le C_K(1+\|u\|) \exp\!\left(-\frac{\|u\|^2}{4\varepsilon^2}\right)\) for some finite constant \(C_K\). The right-hand side is integrable on \(\mathbb{R}^d\). Hence \(\tilde{F}_{\varepsilon,\mathcal{C}}\) is well defined and continuous on \(\mathbb{C}^d\) by dominated convergence.

Fix \(u\in\mathbb{R}^d\). Note that the map \(\theta\mapsto \exp\!\left(-\frac{(u-\theta)^\top(u-\theta)}{2\varepsilon^2}\right)\) is entire on \(\mathbb{C}^d\). Thus, for \(j\in[d]\), we have \[\frac{\partial}{\partial \theta_j} \exp\!\left(-\frac{(u-\theta)^\top(u-\theta)}{2\varepsilon^2}\right) = \frac{u_j-\theta_j}{\varepsilon^2} \exp\!\left(-\frac{(u-\theta)^\top(u-\theta)}{2\varepsilon^2}\right).\] On the same compact set \(K\), let \(M_K:=\sup_{\theta\in K}\|\theta\|<+\infty\). Since \(|u_j-\theta_j| \le \|u\|+\|\theta\| \le \|u\|+M_K,\) the differentiated integrand is dominated by \(C_K'(1+\|u\|)(\|u\|+M_K) \exp\!\left(-\frac{\|u\|^2}{4\varepsilon^2}\right),\) which is integrable on \(\mathbb{R}^d\). Differentiation under the integral sign is therefore justified, and \[\frac{\partial \tilde{F}_{\varepsilon,\mathcal{C}}}{\partial \theta_j}(\theta) = \frac{1}{(2\pi)^{d/2}\varepsilon^d} \int_{\mathbb{R}^d} F(u) \frac{u_j-\theta_j}{\varepsilon^2} \exp\!\left(-\frac{(u-\theta)^\top(u-\theta)}{2\varepsilon^2}\right) \,du.\] By Mattner’s theorem on complex differentiation under the integral [41], applied coordinatewise, \(\tilde{F}_{\varepsilon,\mathcal{C}}\) is separately holomorphic. Since the compact-uniform domination above also gives joint continuity, Osgood’s lemma [40, p. I.A.2] yields joint holomorphy on \(\mathbb{C}^d\).

Consequently, \(\tilde{F}_{\varepsilon,\mathcal{C}}\) admits a convergent complex Taylor expansion around every point of \(\mathbb{C}^d\). Restricting this expansion around each real point \(\theta_0\in\mathbb{R}^d\) to real increments gives a convergent real power-series expansion of \(F_{\varepsilon,\mathcal{C},c}\) around \(\theta_0\). Hence \(F_{\varepsilon,\mathcal{C},c}\) is real analytic on \(\mathbb{R}^d\).

Finally, this yields (A\(_3\)) for the sparse perturbation: since \(\Omega^*_{\Delta}(s)=\mathbb{E}[\max_{y\in\mathcal{Y}}\{s_y+\varepsilon(Y^\top\mathbf{Z})_y\}]\), the composed map satisfies \(\Omega^*_{\Delta}(Y^\top\theta-c)=\mathbb{E}[\max_{y\in\mathcal{Y}}\{(\theta+\varepsilon\mathbf{Z})^\top y-c_y\}]=F_{\varepsilon,\mathcal{Y},c}(\theta)\), real analytic for every fixed \(c\in\mathbb{R}^{\mathcal{Y}}\) by the above. ◻

Proof. Negentropy. \(\Omega_i^*\) is the log-sum-exp function; its gradient, the softmax map, has Jacobian equal to a categorical covariance matrix, hence operator norm at most \(1\), so the softmax map is \(1\)-Lipschitz, giving (A\(_2\)). The same Hessian is positive semidefinite with kernel \(\operatorname{span}(\mathbf{1})\); since \(\Omega^*_{\mathcal{C}_i}=\Omega^*_{\Delta_i}(Y_i^\top\cdot)\), for any direction \(v\) we get \(v^\top\nabla^2\Omega^*_{\mathcal{C}_i}(\theta)v =(Y_i^\top v)^\top\nabla^2\Omega^*_{\Delta_i}(Y_i^\top\theta)(Y_i^\top v)\), which vanishes if and only if \(Y_i^\top v\in\operatorname{span}(\mathbf{1})\), i.e., \(\langle v,y-y'\rangle=0\) for all \(y,y'\in\mathcal{Y}(x_i)\), i.e., \(v\in V_i^\perp\). Hence \(\nabla^2\Omega^*_{\mathcal{C}_i}\succ0\) on \(V_i\), which is (A\(_1\)). The same kernel computation with \(Y_i^\top\theta-c\) in place of \(Y_i^\top\theta\) gives the shifted part of (A\(_1\)). Log-sum-exp is real analytic on \(\mathbb{R}^{\mathcal{Y}(x_i)}\), so for every \(c\) the composed map \(\theta\mapsto\operatorname{logsumexp}(Y_i^\top\theta-c)\) is real analytic (affine precomposition), which is (A\(_3\)).

Sparse perturbation. (A\(_2\)) is Proposition [prop:strongConvexitySparsePerturbation]; (A\(_1\)) is the Gaussian non-degeneracy Lemma 10 above including its shifted statement, and from Proposition 11, which gives the required \(C^2\)-regularity; for (A\(_3\)), the generalized Proposition 11 gives, for every \(c\in\mathbb{R}^{\mathcal{Y}(x_i)}\), that \(\Omega^*_{\Delta_i}(Y_i^\top\theta-c)=F_{\varepsilon,\mathcal{Y}(x_i),c}(\theta)\) is real analytic. ◻