Proof. Write \(\ell(\sigma):=\ell_{\mathrm{PL}}(\theta;x,y_{1:K},\sigma)\). We solve \(\max_{P\in\Delta(S_K)}\sum_\sigma P(\sigma)\ell(\sigma)\) subject to \(\mathrm{TV}(P,\delta_{\sigma^\star})\le\rho\).

Expanding the TV distance and using \(\delta_{\sigma^\star}(\sigma^\star)=1\) and \(\delta_{\sigma^\star}(\sigma)=0\) for \(\sigma\ne\sigma^\star\), \[\begin{align} \mathrm{TV}(P,\delta_{\sigma^\star}) &= \tfrac12\big(|P(\sigma^\star)-1|+\sum_{\sigma\ne\sigma^\star}P(\sigma)\big) \\ &= \tfrac12\big((1-P(\sigma^\star))+(1-P(\sigma^\star))\big) = 1-P(\sigma^\star). \end{align}\] Hence \(\mathrm{TV}\le\rho \iff P(\sigma^\star)\ge 1-\rho\). Let \(\epsilon:=1-P(\sigma^\star)\in[0,\rho]\). Then \(\sum_{\sigma\ne\sigma^\star}P(\sigma)=\epsilon\) and \[\mathbb{E}_{\sigma\sim P}[\ell(\sigma)] = (1-\epsilon)\ell(\sigma^\star) + \sum_{\sigma\ne\sigma^\star}P(\sigma)\ell(\sigma).\] For fixed \(\epsilon\), the adversary maximizes by allocating all mass \(\epsilon\) to \(\mathop{\mathrm{arg\,max}}_{\sigma\ne\sigma^\star}\ell(\sigma)\), giving \[\mathbb{E}_{\sigma\sim P}[\ell(\sigma)] \le (1-\epsilon)\ell(\sigma^\star)+\epsilon\max_{\sigma\in S_K}\ell(\sigma) = \ell(\sigma^\star)+\epsilon\cdot\Big(\max_{\sigma}\ell(\sigma)-\ell(\sigma^\star)\Big).\] Since \(\max_\sigma\ell(\sigma)\ge\ell(\sigma^\star)\) always (as \(\sigma^\star\in S_K\)), the parenthetical is \(\ge 0\), so the linear function of \(\epsilon\) is monotone non-decreasing and is maximized at \(\epsilon=\rho\). Substituting yields 5 . ◻

Proof. Write \(g_i:=g_\theta(x,y_i)\). From 2 , \[\ell_{\mathrm{PL}}(\theta;x,y_{1:K},\sigma) = -\sum_{i=1}^K g_{\sigma_i} + \sum_{i=1}^K \log\!\Big(\sum_{j=i}^K e^{g_{\sigma_j}}\Big).\] The first sum \(-\sum_i g_{\sigma_i}\) is permutation-invariant; maximizing \(\ell_{\mathrm{PL}}\) in \(\sigma\) is equivalent to maximizing \(F(\sigma)=\sum_{i=1}^K\log\sum_{j=i}^K e^{g_{\sigma_j}}\).

Suppose \(\sigma\) has an adjacent inversion at position \(t\): \(a:=g_{\sigma_t}>b:=g_{\sigma_{t+1}}\). Set \(R:=\sum_{j\ge t+2}e^{g_{\sigma_j}}\ge 0\). Only the \(t\)-th and \((t+1)\)-st suffix terms can change under the swap of positions \(t,t+1\): all later suffixes contain the same multiset and are unchanged, all earlier suffixes contain \(\{a,b\}\) jointly and are also unchanged. The \(t\)-th term is \(\log(e^a+e^b+R)\) before the swap and \(\log(e^b+e^a+R)\) after the swap, hence equal. The \((t+1)\)-st term changes from \(\log(e^b+R)\) before the swap to \(\log(e^a+R)\) after the swap. Since \(a>b\) and \(R\ge 0\), \(\log(e^a+R)>\log(e^b+R)\), so \(F\) strictly increases.

By repeated adjacent swaps that fix local inversions, every permutation can be transformed into the unique inversion-free permutation, the nondecreasing-score order. At each step \(F\) strictly increases (modulo equal scores, where the swap leaves \(F\) unchanged). Hence the ascending-score permutation attains the maximum. With ties, any consistent within-group ordering achieves the same maximum. Computing such a \(\sigma_{\mathrm{worst}}\) requires only sorting \(K\) scores, which costs \(O(K\log K)\). ◻

Proof. Under 1, the induced PL score is affine in \(\theta\). In particular, up to a prompt-dependent additive term that cancels in the PL loss, we may write \[s_\theta(x,y)=(\theta-\theta_{\rm ref})^\top\psi(x,y).\] For a fixed ranking \(\sigma\in S_K\), the PL loss is \[\ell_{\mathrm{PL}}(\theta;x,Y,\sigma) = -\sum_{i=1}^K s_\theta(x,y_{\sigma_i}) + \sum_{i=1}^K \log\sum_{j=i}^K \exp\big(s_\theta(x,y_{\sigma_j})\big).\] The first term is affine in \(\theta\). Each term in the second sum is a log-sum-exp of affine functions of \(\theta\), and is therefore convex. Hence \[\theta\mapsto \ell_{\mathrm{PL}}(\theta;x,Y,\sigma)\] is convex for every fixed \((x,Y,\sigma)\).

By 1, the robust loss admits the decomposition \[\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) = (1-\rho)\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho\max_{\sigma\in S_K} \ell_{\mathrm{PL}}(\theta;x,Y,\sigma).\] The first term is convex, and the second term is a pointwise maximum of convex functions, hence convex. Since \(\rho\in[0,1]\), \(\ell_{\mathrm{rob}}(\cdot;x,Y,\sigma^\star)\) is convex. Finally, the offline objective \[J_{\mathrm{rob}}(\theta) = \mathbb{E}_{\xi}[\ell_{\mathrm{rob}}(\theta;\xi)]\] is an expectation of convex functions and therefore convex on \(\Theta\). ◻

Proof. Fix \((x,Y,\sigma)\), where \(Y=(y_1,\ldots,y_K)\). Write \[s_i:=s_\theta(x,y_{\sigma_i}), \qquad \psi_i:=\psi(x,y_{\sigma_i}).\] The PL loss decomposes into stagewise terms: \[\ell_{\mathrm{PL}}(\theta;x,Y,\sigma) = \sum_{i=1}^K \left[ -s_i+\log\sum_{j=i}^K\exp(s_j) \right].\] For each stage \(i\), define the softmax weights \[p_{j\mid i}(\theta) := \frac{\exp(s_j)}{\sum_{m=i}^K\exp(s_m)}, \qquad j=i,\ldots,K.\] Differentiating the \(i\)-th stage gives \[\nabla_\theta \ell_i(\theta) = -\psi_i + \sum_{j=i}^K p_{j\mid i}(\theta)\psi_j.\] Since the weights \(p_{j\mid i}\) form a probability distribution and \(\|\psi(x,y)\|\le B_\psi\), we have \[\left\| \sum_{j=i}^K p_{j\mid i}(\theta)\psi_j \right\| \le \sum_{j=i}^K p_{j\mid i}(\theta)\|\psi_j\| \le B_\psi.\] Therefore \[\|\nabla_\theta \ell_i(\theta)\| \le \|\psi_i\| + \left\| \sum_{j=i}^K p_{j\mid i}(\theta)\psi_j \right\| \le 2B_\psi.\] Summing over \(i=1,\ldots,K\), we obtain \[\|\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma)\| \le \sum_{i=1}^K \|\nabla_\theta\ell_i(\theta)\| \le 2KB_\psi.\]

Now consider the robust loss. By 1, \[\ell_{\mathrm{rob}} = (1-\rho)\ell_{\mathrm{PL}}(\sigma^\star) + \rho\max_{\sigma\in S_K}\ell_{\mathrm{PL}}(\sigma).\] The subdifferential of the finite maximum is the convex hull of active PL gradients. Hence every \(g\in\partial_\theta\ell_{\mathrm{rob}}(\theta;\xi)\) can be written as a convex combination of \[\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star)\] and active gradients \[\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma), \qquad \sigma\in \mathop{\mathrm{arg\,max}}_{\sigma'\in S_K} \ell_{\mathrm{PL}}(\theta;x,Y,\sigma').\] Each such PL gradient has norm at most \(2KB_\psi\). Since convex combinations preserve the same norm bound, we conclude that \[\|g\|_2\le 2KB_\psi.\] ◻

Proof. Since \(\Theta\) is compact and \(J_{\mathrm{rob}}\) is convex and continuous, a minimizer exists. Let \[\theta^\star\in\mathop{\mathrm{arg\,min}}_{\theta\in\Theta}J_{\mathrm{rob}}(\theta).\] The projected stochastic subgradient update is \[\theta_{t+1} = \Pi_\Theta(\theta_t-\eta\widehat g_t).\] By non-expansiveness of the Euclidean projection onto the closed convex set \(\Theta\), \[\|\theta_{t+1}-\theta^\star\|^2 \le \|\theta_t-\eta\widehat g_t-\theta^\star\|^2.\] Expanding the right-hand side gives \[\|\theta_{t+1}-\theta^\star\|^2 \le \|\theta_t-\theta^\star\|^2 - 2\eta \langle \widehat g_t,\theta_t-\theta^\star\rangle + \eta^2\|\widehat g_t\|^2.\] Taking conditional expectation given \(\theta_t\), and writing \[h_t:=\mathbb{E}[\widehat g_t\mid\theta_t]\in\partial J_{\mathrm{rob}}(\theta_t),\] we obtain \[\mathbb{E}[ \|\theta_{t+1}-\theta^\star\|^2 \mid \theta_t ] \le \|\theta_t-\theta^\star\|^2 - 2\eta \langle h_t,\theta_t-\theta^\star\rangle + \eta^2 \mathbb{E}[\|\widehat g_t\|^2\mid\theta_t].\] By convexity of \(J_{\mathrm{rob}}\), \[J_{\mathrm{rob}}(\theta_t)-J_{\mathrm{rob}}(\theta^\star) \le \langle h_t,\theta_t-\theta^\star\rangle.\] Using the assumed mini-batch second-moment bound \[\mathbb{E}[\|\widehat g_t\|^2\mid\theta_t] \le 4K^2B_\psi^2+\frac{\sigma_g^2}{B_s},\] we get \[2\eta \big( J_{\mathrm{rob}}(\theta_t)-J_{\mathrm{rob}}(\theta^\star) \big) \le \|\theta_t-\theta^\star\|^2 - \mathbb{E}[ \|\theta_{t+1}-\theta^\star\|^2 \mid \theta_t ] + \eta^2 \left( 4K^2B_\psi^2+\frac{\sigma_g^2}{B_s} \right).\] Taking total expectation and summing over \(t=0,\ldots,T-1\), we obtain \[2\eta \sum_{t=0}^{T-1} \mathbb{E}[ J_{\mathrm{rob}}(\theta_t)-J_{\mathrm{rob}}(\theta^\star) ] \le \|\theta_0-\theta^\star\|^2 + T\eta^2 \left( 4K^2B_\psi^2+\frac{\sigma_g^2}{B_s} \right).\] Since \(\Theta=\{\theta:\|\theta\|\le B\}\), both \(\theta_0\) and \(\theta^\star\) belong to \(\Theta\), and hence \[\|\theta_0-\theta^\star\|\le 2B.\] Therefore \[\frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}[ J_{\mathrm{rob}}(\theta_t)-J_{\mathrm{rob}}(\theta^\star) ] \le \frac{2B^2}{\eta T} + \frac{\eta}{2} \left( 4K^2B_\psi^2+\frac{\sigma_g^2}{B_s} \right).\] By convexity of \(J_{\mathrm{rob}}\) and Jensen’s inequality, for \[\bar\theta_T := \frac{1}{T} \sum_{t=0}^{T-1} \theta_t,\] we have \[\mathbb{E}[J_{\mathrm{rob}}(\bar\theta_T)] \le \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}[J_{\mathrm{rob}}(\theta_t)].\] Hence \[\mathbb{E}[J_{\mathrm{rob}}(\bar\theta_T)] - J_{\mathrm{rob}}(\theta^\star) \le \frac{2B^2}{\eta T} + \frac{\eta}{2} \left( 4K^2B_\psi^2+\frac{\sigma_g^2}{B_s} \right).\] Choosing \[\eta = \frac{2B}{\sqrt{ T\left( 4K^2B_\psi^2+\sigma_g^2/B_s \right) }}\] balances the two terms and gives \[\mathbb{E}[J_{\mathrm{rob}}(\bar\theta_T)] - \min_{\theta\in\Theta}J_{\mathrm{rob}}(\theta) \le \frac{ 2B \sqrt{ 4K^2B_\psi^2+\sigma_g^2/B_s } }{\sqrt T}.\] Solving for \(T\) to achieve \(\varepsilon\)-suboptimality gives \[T = O\left( \frac{ 4K^2B_\psi^2+\sigma_g^2/B_s }{\varepsilon^2} \right).\] With fixed \(B_s=\Theta(1)\) independent of \(\varepsilon\), the total sample complexity satisfies \[B_sT=O(\varepsilon^{-2}).\] ◻

Proof. Fix \(x\) and write \[A_\theta(x) := \log\sum_{y'\in\mathcal{Y}} \exp(\theta^\top\psi(x,y')).\] Under the log-linear policy class, \[\log\pi_\theta(y\mid x) = \theta^\top\psi(x,y)-A_\theta(x).\] Differentiating gives \[\nabla_\theta\log\pi_\theta(y\mid x) = \psi(x,y)-\nabla_\theta A_\theta(x).\] Moreover, \[\nabla_\theta A_\theta(x) = \frac{\sum_{y'\in\mathcal{Y}} \exp(\theta^\top\psi(x,y'))\psi(x,y')}{\sum_{y'\in\mathcal{Y}} \exp(\theta^\top\psi(x,y'))} = \mathbb{E}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ] = \bar\psi_\theta(x).\] Therefore, \[\nabla_\theta\log\pi_\theta(y\mid x) = \psi(x,y)-\bar\psi_\theta(x).\]

Since \(\|\psi(x,y)\|\le B_\psi\) for every \((x,y)\), Jensen’s inequality gives \[\|\bar\psi_\theta(x)\| = \left\| \mathbb{E}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ] \right\| \le \mathbb{E}_{y'\sim\pi_\theta(\cdot\mid x)} [ \|\psi(x,y')\| ] \le B_\psi.\] Hence \[\|\nabla_\theta\log\pi_\theta(y\mid x)\| \le \|\psi(x,y)\|+\|\bar\psi_\theta(x)\| \le 2B_\psi.\]

Now let \(Y=(y_1,\ldots,y_K)\). Since the list is sampled iid from \(\pi_\theta(\cdot\mid x)\), \[P_{\pi_\theta}(Y\mid x) = \prod_{i=1}^K\pi_\theta(y_i\mid x),\] and therefore \[S_\theta(x,Y) := \nabla_\theta\log P_{\pi_\theta}(Y\mid x) = \sum_{i=1}^K \nabla_\theta\log\pi_\theta(y_i\mid x).\] Using the bound above, \[\|S_\theta(x,Y)\| \le \sum_{i=1}^K \|\nabla_\theta\log\pi_\theta(y_i\mid x)\| \le 2KB_\psi.\]

It remains to bound \(\nabla_\theta S_\theta(x,Y)\). Since \[\nabla_\theta\log\pi_\theta(y\mid x) = \psi(x,y)-\bar\psi_\theta(x),\] and \(\psi(x,y)\) is independent of \(\theta\), \[\nabla_\theta^2\log\pi_\theta(y\mid x) = -\nabla_\theta\bar\psi_\theta(x).\] We compute \(\nabla_\theta\bar\psi_\theta(x)\). For any vector \(v\in\mathbb{R}^d\), \[\nabla_\theta \mathbb{E}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ] = \mathbb{E}_{y'\sim\pi_\theta(\cdot\mid x)} [ (\psi(x,y')-\bar\psi_\theta(x))\psi(x,y')^\top ],\] which is the covariance matrix \[\operatorname{Cov}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ] = \mathbb{E}[ (\psi-\bar\psi_\theta)(\psi-\bar\psi_\theta)^\top ].\] Thus \[\nabla_\theta^2\log\pi_\theta(y\mid x) = - \operatorname{Cov}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ].\] Consequently, \[\nabla_\theta S_\theta(x,Y) = \sum_{i=1}^K \nabla_\theta^2\log\pi_\theta(y_i\mid x) = - K\, \operatorname{Cov}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ],\] because the covariance term depends on \(x\) and \(\theta\), but not on the particular sampled response \(y_i\).

Finally, for any unit vector \(v\), \[v^\top \operatorname{Cov}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ] v = \operatorname{Var}_{y'\sim\pi_\theta(\cdot\mid x)} ( v^\top\psi(x,y') ) \le \mathbb{E}[ (v^\top\psi(x,y'))^2 ] \le B_\psi^2.\] Therefore, \[\left\| \operatorname{Cov}_{y'\sim\pi_\theta(\cdot\mid x)} [ \psi(x,y') ] \right\|_\mathrm{op} \le B_\psi^2.\] Hence \[\|\nabla_\theta S_\theta(x,Y)\|_\mathrm{op} \le K B_\psi^2.\] ◻

Proof. Fix \((x,Y,\sigma)\), where \(Y=(y_1,\ldots,y_K)\). Recall that the induced affine score can be written as \[s_\theta(x,y) = (\theta-\theta_{\rm ref})^\top\psi(x,y),\] up to an additive term depending only on \(x\), which cancels in the PL loss. For notational simplicity, write \[s_i:=s_\theta(x,y_{\sigma_i}), \qquad \psi_i:=\psi(x,y_{\sigma_i}).\] The PL loss decomposes into \(K\) stagewise losses: \[\ell_{\mathrm{PL}}(\theta;x,Y,\sigma) = \sum_{i=1}^K \ell_i(\theta),\] where \[\ell_i(\theta) := -s_i+\log\sum_{j=i}^K \exp(s_j).\]

13.1.0.1 Convexity.

For each \(i\), the term \(-s_i\) is affine in \(\theta\), and \[\theta\mapsto \log\sum_{j=i}^K \exp(s_\theta(x,y_{\sigma_j}))\] is a log-sum-exp of affine functions, hence convex. Therefore each \(\ell_i\) is convex, and so \(\ell_{\mathrm{PL}}=\sum_{i=1}^K\ell_i\) is convex. Since it is finite-valued and convex, it is Clarke regular.

13.1.0.2 Magnitude bound.

For each stage \(i\), \[\ell_i(\theta) = \log\sum_{j=i}^K \exp(s_j-s_i).\] Since \(\theta\in\Theta\) and \[D:=\sup_{\theta\in\Theta}\|\theta-\theta_{\rm ref}\|,\] we have, for any \(j\), \[|s_j-s_i| = |(\theta-\theta_{\rm ref})^\top(\psi_j-\psi_i)| \le \|\theta-\theta_{\rm ref}\|\,\|\psi_j-\psi_i\| \le 2DB_\psi.\] Also, the term \(j=i\) equals \(\exp(s_i-s_i)=1\), so \[\ell_i(\theta) = \log\sum_{j=i}^K \exp(s_j-s_i) \ge 0.\] For the upper bound, \[\ell_i(\theta) \le \log\sum_{j=i}^K \exp(2DB_\psi) \le \log K+2DB_\psi.\] Summing over \(i=1,\ldots,K\) gives \[0\le \ell_{\mathrm{PL}}(\theta;x,Y,\sigma) \le K(\log K+2DB_\psi) = C_L.\]

13.1.0.3 Gradient bound.

For each stage \(i\), define the stagewise softmax weights \[p_{j|i}(\theta) := \frac{\exp(s_j)}{\sum_{m=i}^K\exp(s_m)}, \qquad j=i,\ldots,K.\] Then \[\nabla_\theta \ell_i(\theta) = -\psi_i+\sum_{j=i}^K p_{j|i}(\theta)\psi_j.\] Since the weights \(p_{j|i}\) form a probability distribution over \(\{i,\ldots,K\}\), \[\left\| \sum_{j=i}^K p_{j|i}(\theta)\psi_j \right\| \le \sum_{j=i}^K p_{j|i}(\theta)\|\psi_j\| \le B_\psi.\] Thus \[\|\nabla_\theta \ell_i(\theta)\| \le \|\psi_i\| + \left\| \sum_{j=i}^K p_{j|i}(\theta)\psi_j \right\| \le 2B_\psi.\] Summing over \(i\) yields \[\|\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma)\| \le \sum_{i=1}^K \|\nabla_\theta\ell_i(\theta)\| \le 2KB_\psi = C_G.\]

13.1.0.4 Hessian bound.

For each stage \(i\), differentiating the stagewise softmax gradient gives \[\nabla_\theta^2\ell_i(\theta) = \sum_{j=i}^K p_{j|i}(\theta) (\psi_j-\bar\psi_i)(\psi_j-\bar\psi_i)^\top,\] where \[\bar\psi_i := \sum_{j=i}^K p_{j|i}(\theta)\psi_j.\] Equivalently, \[\nabla_\theta^2\ell_i(\theta) = \operatorname{Cov}_{j\sim p_{\cdot|i}} [ \psi_j ].\] Therefore \[\nabla_\theta^2\ell_i(\theta)\succeq 0.\] Moreover, for any unit vector \(v\), \[v^\top\nabla_\theta^2\ell_i(\theta)v = \operatorname{Var}_{j\sim p_{\cdot|i}}(v^\top\psi_j) \le \mathbb{E}_{j\sim p_{\cdot|i}}[(v^\top\psi_j)^2] \le B_\psi^2.\] Hence \[0\preceq \nabla_\theta^2\ell_i(\theta)\preceq B_\psi^2 I.\] Summing over \(i=1,\ldots,K\), we obtain \[0 \preceq \nabla_\theta^2\ell_{\mathrm{PL}}(\theta;x,Y,\sigma) = \sum_{i=1}^K\nabla_\theta^2\ell_i(\theta) \preceq KB_\psi^2 I = C_H I.\] This completes the proof. ◻

Proof. Fix \((x,Y)\) and write \[\ell_\sigma(\theta) := \ell_{\mathrm{PL}}(\theta;x,Y,\sigma), \qquad \sigma\in S_K.\] Then \[M_\tau(\theta;x,Y) = \tau\log \sum_{\sigma\in S_K} \exp\left( \frac{\ell_\sigma(\theta)}{\tau} \right).\]

(i) Let \[m(\theta) := \max_{\sigma\in S_K}\ell_\sigma(\theta).\] Then \[\sum_{\sigma\in S_K} \exp\left( \frac{\ell_\sigma(\theta)}{\tau} \right) = \exp\left(\frac{m(\theta)}{\tau}\right) \sum_{\sigma\in S_K} \exp\left( \frac{\ell_\sigma(\theta)-m(\theta)}{\tau} \right).\] Since \(\ell_\sigma(\theta)-m(\theta)\le 0\) for every \(\sigma\), and at least one maximizer attains zero, we have \[1 \le \sum_{\sigma\in S_K} \exp\left( \frac{\ell_\sigma(\theta)-m(\theta)}{\tau} \right) \le |S_K| = K!.\] Taking \(\tau\log(\cdot)\) gives \[m(\theta) \le M_\tau(\theta;x,Y) \le m(\theta)+\tau\log K!,\] which proves (i).

(ii) By 4, for every \(\sigma\in S_K\), the map \[\theta\mapsto \ell_\sigma(\theta)\] is convex and \(C^\infty\). Since \(S_K\) is finite, \(M_\tau\) is a finite log-sum-exp composition of \(C^\infty\) functions, and hence is \(C^\infty\).

To prove convexity, take any \(\theta_1,\theta_2\) and \(\alpha\in[0,1]\). Since each \(\ell_\sigma\) is convex, \[\ell_\sigma(\alpha\theta_1+(1-\alpha)\theta_2) \le \alpha \ell_\sigma(\theta_1)+(1-\alpha)\ell_\sigma(\theta_2).\] Therefore, \[\exp\left( \frac{\ell_\sigma(\alpha\theta_1+(1-\alpha)\theta_2)}{\tau} \right) \le \exp\left( \frac{\alpha \ell_\sigma(\theta_1)}{\tau} \right) \exp\left( \frac{(1-\alpha)\ell_\sigma(\theta_2)}{\tau} \right).\] Summing over \(\sigma\) and applying Hölder’s inequality gives \[\sum_{\sigma\in S_K} \exp\left( \frac{\ell_\sigma(\alpha\theta_1+(1-\alpha)\theta_2)}{\tau} \right) \le \left[ \sum_{\sigma\in S_K} \exp\left( \frac{\ell_\sigma(\theta_1)}{\tau} \right) \right]^\alpha \left[ \sum_{\sigma\in S_K} \exp\left( \frac{\ell_\sigma(\theta_2)}{\tau} \right) \right]^{1-\alpha}.\] Taking \(\tau\log(\cdot)\) yields \[M_\tau(\alpha\theta_1+(1-\alpha)\theta_2) \le \alpha M_\tau(\theta_1) + (1-\alpha)M_\tau(\theta_2).\] Thus \(M_\tau\) is convex.

(iii) Define the softmax weights over rankings \[w_\sigma(\theta) := \frac{ \exp(\ell_\sigma(\theta)/\tau) }{ \sum_{\sigma'\in S_K} \exp(\ell_{\sigma'}(\theta)/\tau) }.\] Then \(w_\sigma(\theta)\ge0\) and \(\sum_{\sigma\in S_K}w_\sigma(\theta)=1\). Differentiating \(M_\tau\) gives \[\nabla_\theta M_\tau(\theta;x,Y) = \sum_{\sigma\in S_K} w_\sigma(\theta) \nabla_\theta\ell_\sigma(\theta).\] By 4, \(\|\nabla_\theta\ell_\sigma(\theta)\|\le C_G\) for every \(\sigma\). Hence \[\|\nabla_\theta M_\tau(\theta;x,Y)\| \le \sum_{\sigma\in S_K} w_\sigma(\theta) \|\nabla_\theta\ell_\sigma(\theta)\| \le C_G.\]

For the Hessian, differentiating the gradient gives \[\nabla_\theta^2 M_\tau(\theta;x,Y) = \sum_{\sigma\in S_K} w_\sigma(\theta) \nabla_\theta^2\ell_\sigma(\theta) + \frac{1}{\tau} \left[ \sum_{\sigma\in S_K} w_\sigma(\theta) \nabla_\theta\ell_\sigma(\theta) \nabla_\theta\ell_\sigma(\theta)^\top - \nabla_\theta M_\tau(\theta;x,Y) \nabla_\theta M_\tau(\theta;x,Y)^\top \right].\] The second bracket is the covariance matrix of the random vector \(\nabla_\theta\ell_\sigma(\theta)\) under \(\sigma\sim w(\theta)\), and is therefore positive semidefinite. Since each \(\nabla_\theta^2\ell_\sigma(\theta)\succeq0\), we get \[\nabla_\theta^2 M_\tau(\theta;x,Y)\succeq0.\]

For the upper bound, by 4, \[\sum_{\sigma\in S_K} w_\sigma(\theta) \nabla_\theta^2\ell_\sigma(\theta) \preceq C_H I.\] For the covariance term, for any unit vector \(v\), \[v^\top \left[ \sum_{\sigma} w_\sigma \nabla\ell_\sigma\nabla\ell_\sigma^\top - \nabla M_\tau\nabla M_\tau^\top \right] v = \operatorname{Var}_{\sigma\sim w(\theta)} \left( v^\top\nabla_\theta\ell_\sigma(\theta) \right) \le \mathbb{E}_{\sigma\sim w(\theta)} \left[ (v^\top\nabla_\theta\ell_\sigma(\theta))^2 \right].\] Using \(\|\nabla_\theta\ell_\sigma(\theta)\|\le C_G\), we have \[\mathbb{E}_{\sigma\sim w(\theta)} \left[ (v^\top\nabla_\theta\ell_\sigma(\theta))^2 \right] \le C_G^2.\] Therefore the covariance term is bounded by \(C_G^2 I\), and hence \[\nabla_\theta^2M_\tau(\theta;x,Y) \preceq \left(C_H+\frac{C_G^2}{\tau}\right)I.\] This proves (iii). ◻

Proof. Fix \(\tau>0\). Recall that the smoothed online objective is \[J_{\mathrm{rob}}^{\mathrm{on},\tau}(\theta) = \mathbb{E}_{x\sim\mathcal{D}_x} \sum_{Y\in\mathcal{Y}^K} P_{\pi_\theta}(Y\mid x) L_\tau(\theta;x,Y),\] where \[L_\tau(\theta;x,Y) := \mathbb{E}_{\sigma^\star\sim p^\star(\cdot\mid x,Y)} [ \ell_{\mathrm{rob}}^{\tau}(\theta;x,Y,\sigma^\star) ].\] Since \(\mathcal{Y}\) and \(S_K\) are finite, all sums over \(Y\) and \(\sigma^\star\) are finite. Moreover, \[\ell_{\mathrm{rob}}^{\tau}(\theta;x,Y,\sigma^\star) = (1-\rho)\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho M_\tau(\theta;x,Y),\] with \[M_\tau(\theta;x,Y) := \tau\log \sum_{\sigma\in S_K} \exp\left( \frac{\ell_{\mathrm{PL}}(\theta;x,Y,\sigma)}{\tau} \right).\] By 4, each \(\ell_{\mathrm{PL}}(\cdot;x,Y,\sigma)\) is convex and \(C^\infty\) in \(\theta\). The log-sum-exp smoothing \(M_\tau\) is therefore convex and \(C^\infty\). Hence \(\ell_{\mathrm{rob}}^{\tau}\) and \(L_\tau\) are convex and \(C^\infty\) in \(\theta\).

For each fixed \(x\), define \[H_x(\theta) := \sum_{Y\in\mathcal{Y}^K} P_{\pi_\theta}(Y\mid x)L_\tau(\theta;x,Y).\] Because the log-linear softmax policy is \(C^\infty\) and \(\mathcal{Y}^K\) is finite, \(H_x\) is \(C^2\). The uniform bounds from 4, 5, and 3 imply that the first and second derivatives of \(H_x\) are dominated uniformly over \(x\) and \(\theta\in\Theta\). Therefore differentiation may be interchanged with the expectation over \(x\), and \[J_{\mathrm{rob}}^{\mathrm{on},\tau}(\theta)=\mathbb{E}_x[H_x(\theta)]\] is \(C^2\) on \(\Theta\).

We now lower bound the Hessian. For \(Y=(y_1,\ldots,y_K)\), write \[P_\theta(Y\mid x) := P_{\pi_\theta}(Y\mid x) = \prod_{i=1}^K \pi_\theta(y_i\mid x),\] and define the list score function \[S_\theta(x,Y) := \nabla_\theta\log P_\theta(Y\mid x) = \sum_{i=1}^K\nabla_\theta\log\pi_\theta(y_i\mid x).\] Then \[\nabla_\theta P_\theta(Y\mid x) = P_\theta(Y\mid x)S_\theta(x,Y).\] Differentiating once more gives \[\nabla_\theta^2P_\theta(Y\mid x) = \nabla_\theta\!\left(P_\theta(Y\mid x)S_\theta(x,Y)\right) = P_\theta(Y\mid x) \left[ S_\theta(x,Y)S_\theta(x,Y)^\top + \nabla_\theta S_\theta(x,Y) \right].\]

Applying the product rule twice to \[H_x(\theta) = \sum_{Y\in\mathcal{Y}^K} P_\theta(Y\mid x)L_\tau(\theta;x,Y),\] we obtain \[\begin{align} \nabla_\theta^2 H_x(\theta) &= \sum_{Y\in\mathcal{Y}^K} P_\theta(Y\mid x) \bigg[ \underbrace{\nabla_\theta^2L_\tau(\theta;x,Y)}_{T_1} \notag\\ &\qquad + \underbrace{ S_\theta(x,Y)\nabla_\theta L_\tau(\theta;x,Y)^\top + \nabla_\theta L_\tau(\theta;x,Y)S_\theta(x,Y)^\top }_{T_2} \notag\\ &\qquad + \underbrace{ L_\tau(\theta;x,Y) \left( S_\theta(x,Y)S_\theta(x,Y)^\top + \nabla_\theta S_\theta(x,Y) \right) }_{T_3} \bigg]. \label{eq:hessian-Hx} \end{align}\tag{12}\]

We bound the three terms from below. Since \(L_\tau(\cdot;x,Y)\) is convex, \[T_1=\nabla_\theta^2L_\tau(\theta;x,Y)\succeq 0.\] For the cross term \(T_2\), for any unit vector \(v\), \[v^\top T_2 v = 2\langle v,S_\theta(x,Y)\rangle \langle v,\nabla_\theta L_\tau(\theta;x,Y)\rangle.\] Therefore, by Cauchy–Schwarz, \[v^\top T_2 v \ge -2\|S_\theta(x,Y)\| \|\nabla_\theta L_\tau(\theta;x,Y)\|.\] Equivalently, \[T_2 \succeq -2\|S_\theta(x,Y)\| \|\nabla_\theta L_\tau(\theta;x,Y)\|I.\]

For \(T_3\), note that \(L_\tau(\theta;x,Y)\ge 0\) and \[S_\theta(x,Y)S_\theta(x,Y)^\top\succeq 0.\] Hence \[T_3 \succeq L_\tau(\theta;x,Y)\nabla_\theta S_\theta(x,Y).\] By 3, \[\|\nabla_\theta S_\theta(x,Y)\|_\mathrm{op}\le KB_\psi^2,\] and thus \[\nabla_\theta S_\theta(x,Y) \succeq -KB_\psi^2 I.\] Therefore, \[T_3 \succeq -L_\tau(\theta;x,Y)KB_\psi^2I.\]

Now use the uniform bounds \[\|S_\theta(x,Y)\|\le 2KB_\psi, \qquad \|\nabla_\theta L_\tau(\theta;x,Y)\|\le C_G=2KB_\psi,\] and \[0\le L_\tau(\theta;x,Y)\le C_L+\rho\tau\log K!.\] The gradient bound follows because \(\nabla M_\tau\) is a softmax-weighted convex combination of the gradients \(\nabla\ell_{\mathrm{PL}}(\theta;x,Y,\sigma)\), each of which has norm at most \(C_G\). The loss bound follows from \[M_\tau(\theta;x,Y) \le \max_{\sigma\in S_K}\ell_{\mathrm{PL}}(\theta;x,Y,\sigma) + \tau\log K!,\] together with the uniform PL loss bound.

Combining the bounds, for every unit vector \(v\), \[\begin{align} v^\top \nabla_\theta^2H_x(\theta)v &\ge -2(2KB_\psi)(2KB_\psi) - (C_L+\rho\tau\log K!)KB_\psi^2 \notag\\ &= -8K^2B_\psi^2 - (C_L+\rho\tau\log K!)KB_\psi^2. \end{align}\] Since the bound is uniform in \(Y\) and \(x\), summing over \(Y\) with weights \(P_\theta(Y\mid x)\) and taking expectation over \(x\) preserve the same lower bound. Hence \[\nabla_\theta^2J_{\mathrm{rob}}^{\mathrm{on},\tau}(\theta) \succeq - \left[ 8K^2B_\psi^2 + (C_L+\rho\tau\log K!)KB_\psi^2 \right]I.\] Therefore \(J_{\mathrm{rob}}^{\mathrm{on},\tau}\) is \(\kappa^\tau\)-weakly convex with \[\kappa^\tau \le 8K^2B_\psi^2 + (C_L+\rho\tau\log K!)KB_\psi^2.\] Indeed, for a \(C^2\) function, the Hessian lower bound \(\nabla^2 f\succeq -\kappa I\) is equivalent to convexity of \(f+\frac{\kappa}{2}\|\cdot\|^2\), which is precisely \(\kappa\)-weak convexity. ◻

Proof of 2. For \(\tau>0\), define \[\bar\kappa_\tau := 8K^2B_\psi^2 + (C_L+\rho\tau\log K!)KB_\psi^2.\] By 3, \(J_{\mathrm{rob}}^{\mathrm{on},\tau}\) is \(\bar\kappa_\tau\)-weakly convex on \(\Theta\). Equivalently, the function \[\Phi_\tau(\theta) := J_{\mathrm{rob}}^{\mathrm{on},\tau}(\theta) + \frac{\bar\kappa_\tau}{2}\|\theta\|^2\] is convex on \(\Theta\).

We first verify convergence of the smoothed objectives. By the log-sum-exp bound in 5(i), \[0 \le M_\tau(\theta;x,Y)-M(\theta;x,Y) \le \tau\log K!.\] Since \[\ell_{\mathrm{rob}}^{\tau} = (1-\rho)\ell_{\mathrm{PL}}(\sigma^\star) + \rho M_\tau, \qquad \ell_{\mathrm{rob}} = (1-\rho)\ell_{\mathrm{PL}}(\sigma^\star) + \rho M,\] we have, for every \((\theta,x,Y,\sigma^\star)\), \[0 \le \ell_{\mathrm{rob}}^{\tau}(\theta;x,Y,\sigma^\star) - \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) \le \rho\tau\log K!.\] Taking expectation over \(x\), \(Y\sim\pi_\theta^{\otimes K}(\cdot|x)\), and \(\sigma^\star\sim p^\star(\cdot|x,Y)\) gives the uniform bound \[0 \le J_{\mathrm{rob}}^{\mathrm{on},\tau}(\theta) - J_{\mathrm{rob}}^{\mathrm{on}}(\theta) \le \rho\tau\log K!, \qquad \forall \theta\in\Theta.\] Hence \(J_{\mathrm{rob}}^{\mathrm{on},\tau}\to J_{\mathrm{rob}}^{\mathrm{on}}\) uniformly on \(\Theta\).

Now define \[\kappa := \lim_{\tau\downarrow0}\bar\kappa_\tau = 8K^2B_\psi^2+C_LKB_\psi^2.\] Since \(C_L=K(\log K+2DB_\psi)\), this becomes \[\kappa = K^2B_\psi^2(8+\log K+2DB_\psi).\]

It remains to prove that \[\Phi(\theta) := J_{\mathrm{rob}}^{\mathrm{on}}(\theta) + \frac{\kappa}{2}\|\theta\|^2\] is convex on \(\Theta\). Let \(\theta_1,\theta_2\in\Theta\) and \(\alpha\in[0,1]\). Since \(\Theta\) is convex, \[\theta_\alpha := \alpha\theta_1+(1-\alpha)\theta_2 \in\Theta.\] For every \(\tau>0\), convexity of \(\Phi_\tau\) gives \[\Phi_\tau(\theta_\alpha) \le \alpha\Phi_\tau(\theta_1) + (1-\alpha)\Phi_\tau(\theta_2).\] Taking \(\tau\downarrow0\), using the uniform convergence \(J_{\mathrm{rob}}^{\mathrm{on},\tau}\to J_{\mathrm{rob}}^{\mathrm{on}}\) and \(\bar\kappa_\tau\to\kappa\), yields \[\Phi(\theta_\alpha) \le \alpha\Phi(\theta_1) + (1-\alpha)\Phi(\theta_2).\] Therefore \(\Phi\) is convex on \(\Theta\). Equivalently, \(J_{\mathrm{rob}}^{\mathrm{on}}\) is \(\kappa\)-weakly convex on \(\Theta\), with \[\kappa = K^2B_\psi^2(8+\log K+2DB_\psi).\] ◻

Proof. The Moreau-envelope properties above are standard for proper lower semicontinuous \(\kappa\)-weakly convex functions with parameter \(\hat{\lambda}<1/\kappa\); see, e.g., [18] and [19].

By 2, \(J_{\mathrm{rob}}^{\mathrm{on}}\) is \(\kappa\)-weakly convex on \(\Theta\). Since \(\Theta\) is closed and convex, the indicator \(I_\Theta\) is proper, lower semicontinuous, and convex. Therefore \[F=J_{\mathrm{rob}}^{\mathrm{on}}+I_\Theta\] is proper, lower semicontinuous, bounded below by assumption, and \(\kappa\)-weakly convex. Here is the detailed statement:

We first prove single-valuedness of the proximal map. Since \(F\) is \(\kappa\)-weakly convex, the function \[u\mapsto F(u)+\frac{\kappa}{2}\|u\|^2\] is convex. For fixed \(\theta\), the proximal objective is \[u \mapsto F(u)+\frac{1}{2\hat{\lambda}}\|u-\theta\|^2.\] Adding and subtracting \(\frac{\kappa}{2}\|u\|^2\), we can write it as \[\left( F(u)+\frac{\kappa}{2}\|u\|^2 \right) + \frac{1}{2} \left( \frac{1}{\hat{\lambda}}-\kappa \right) \|u\|^2 - \frac{1}{\hat{\lambda}}\langle u,\theta\rangle + \frac{1}{2\hat{\lambda}}\|\theta\|^2.\] The first term is convex, and the second quadratic term is strongly convex because \[\frac{1}{\hat{\lambda}}-\kappa>0.\] Hence the proximal objective is strongly convex. Since it is also proper, lower semicontinuous, and coercive, it has a unique minimizer. Thus \(\mathop{\mathrm{prox}}_{\hat{\lambda} F}\) is single-valued.

The standard Moreau-envelope calculus for weakly convex functions then gives \[F_{\hat{\lambda}}\in C^1, \qquad \nabla F_{\hat{\lambda}}(\theta) = \hat{\lambda}^{-1} \left( \theta-\mathop{\mathrm{prox}}_{\hat{\lambda} F}(\theta) \right) = \hat{\lambda}^{-1} \left( \theta-\hat{\theta}(\theta) \right).\] This proves the differentiability and gradient formula.

The same weakly-convex Moreau calculus gives the Lipschitz bound \[\|\nabla F_{\hat{\lambda}}(\theta)-\nabla F_{\hat{\lambda}}(\theta')\| \le \frac{1}{\hat{\lambda}(1-\kappa\hat{\lambda})} \|\theta-\theta'\|,\] for all \(\theta,\theta'\in\mathbb{R}^d\). Hence \(\nabla F_{\hat{\lambda}}\) is Lipschitz with constant at most \[L_{\mathrm{env}} = \frac{1}{\hat{\lambda}(1-\kappa\hat{\lambda})}.\]

It remains to prove the near-stationarity claim. Let \[\hat{\theta} := \hat{\theta}(\theta) = \mathop{\mathrm{prox}}_{\hat{\lambda} F}(\theta).\] By the first-order optimality condition for the proximal problem, \[0 \in \partial_C F(\hat{\theta}) + \frac{1}{\hat{\lambda}}(\hat{\theta}-\theta).\] Equivalently, \[\frac{1}{\hat{\lambda}}(\theta-\hat{\theta}) \in \partial_C F(\hat{\theta}).\] Using the gradient formula, \[\nabla F_{\hat{\lambda}}(\theta) = \frac{1}{\hat{\lambda}}(\theta-\hat{\theta}),\] we obtain \[\nabla F_{\hat{\lambda}}(\theta) \in \partial_C F(\hat{\theta}(\theta)).\] Therefore, \[\mathop{\mathrm{dist}}\!\left( 0, \partial_C F(\hat{\theta}(\theta)) \right) \le \|\nabla F_{\hat{\lambda}}(\theta)\|.\] This proves the lemma. ◻

Proof. Fix \((x,Y)\) throughout the proof and write \[f_\sigma(\theta) := \ell_{\mathrm{PL}}(\theta;x,Y,\sigma), \qquad \sigma\in S_K.\] By 4, each \(f_\sigma\) is convex and continuously differentiable in \(\theta\). Since \(S_K\) is finite, the pointwise maximum \[M(\theta;x,Y)=\max_{\sigma\in S_K} f_\sigma(\theta)\] is also convex. Moreover, a finite maximum of continuously differentiable functions is locally Lipschitz. Since every finite-valued convex function is Clarke regular, \(M(\cdot;x,Y)\) is Clarke regular, and its Clarke subdifferential coincides with its convex subdifferential: \[\partial_C M(\theta;x,Y)=\partial M(\theta;x,Y).\]

It remains to identify this subdifferential. Define the active maximizer set \[\mathcal{A}(\theta;x,Y) := \mathop{\mathrm{arg\,max}}_{\sigma\in S_K} f_\sigma(\theta).\] This set is nonempty because \(S_K\) is finite. We prove both inclusions.

First, let \(\sigma\in\mathcal{A}(\theta;x,Y)\). Since \(f_\sigma\) is convex and differentiable, for every \(u\), \[f_\sigma(u) \ge f_\sigma(\theta) + \left\langle \nabla_\theta f_\sigma(\theta),u-\theta \right\rangle.\] Because \(\sigma\) is active, \(f_\sigma(\theta)=M(\theta;x,Y)\). Also, \(M(u;x,Y)\ge f_\sigma(u)\). Hence \[M(u;x,Y) \ge M(\theta;x,Y) + \left\langle \nabla_\theta f_\sigma(\theta),u-\theta \right\rangle \qquad \text{for all }u.\] Therefore, \[\nabla_\theta f_\sigma(\theta)\in\partial M(\theta;x,Y).\] Since \(\partial M(\theta;x,Y)\) is convex, we obtain \[\mathop{\mathrm{conv}} \left\{ \nabla_\theta f_\sigma(\theta): \sigma\in\mathcal{A}(\theta;x,Y) \right\} \subseteq \partial M(\theta;x,Y).\]

We now prove the reverse inclusion. For any direction \(d\), the one-sided directional derivative of \(M\) at \(\theta\) satisfies \[M'(\theta;d) = \lim_{t\downarrow 0} \frac{M(\theta+td;x,Y)-M(\theta;x,Y)}{t}.\] We claim that \[M'(\theta;d) = \max_{\sigma\in\mathcal{A}(\theta;x,Y)} \left\langle \nabla_\theta f_\sigma(\theta),d \right\rangle.\] To see this, note first that for every active \(\sigma\in\mathcal{A}(\theta;x,Y)\), \[M(\theta+td;x,Y) \ge f_\sigma(\theta+td),\] and therefore \[\liminf_{t\downarrow 0} \frac{M(\theta+td;x,Y)-M(\theta;x,Y)}{t} \ge \left\langle \nabla_\theta f_\sigma(\theta),d \right\rangle.\] Taking the maximum over active \(\sigma\) gives the lower bound.

For the upper bound, choose for each \(t>0\) a maximizer \[\sigma_t\in \mathop{\mathrm{arg\,max}}_{\sigma\in S_K} f_\sigma(\theta+td).\] Since \(S_K\) is finite, along any sequence \(t_n\downarrow 0\) there is a subsequence, still denoted \(t_n\), such that \(\sigma_{t_n}=\bar\sigma\) is constant. By continuity, \[f_{\bar\sigma}(\theta) = \lim_{n\to\infty} f_{\sigma_{t_n}}(\theta+t_n d) = \lim_{n\to\infty} M(\theta+t_n d;x,Y) = M(\theta;x,Y),\] so \(\bar\sigma\in\mathcal{A}(\theta;x,Y)\). Hence, along this subsequence, \[\lim_{n\to\infty} \frac{M(\theta+t_n d;x,Y)-M(\theta;x,Y)}{t_n} = \left\langle \nabla_\theta f_{\bar\sigma}(\theta),d \right\rangle \le \max_{\sigma\in\mathcal{A}(\theta;x,Y)} \left\langle \nabla_\theta f_\sigma(\theta),d \right\rangle.\] Since this argument applies to every vanishing sequence \(t_n\downarrow 0\), the claimed directional derivative formula follows.

Now let \(v\in\partial M(\theta;x,Y)\). By the characterization of the convex subdifferential through directional derivatives, \[\langle v,d\rangle \le M'(\theta;d) \qquad \text{for every direction }d.\] Using the formula above, \[\langle v,d\rangle \le \max_{\sigma\in\mathcal{A}(\theta;x,Y)} \left\langle \nabla_\theta f_\sigma(\theta),d \right\rangle \qquad \text{for every }d.\] We show that this implies \[v\in \mathop{\mathrm{conv}} \left\{ \nabla_\theta f_\sigma(\theta): \sigma\in\mathcal{A}(\theta;x,Y) \right\}.\] Indeed, if \(v\) were not in this closed convex hull, then by the finite-dimensional separating hyperplane theorem there would exist a direction \(d\) such that \[\langle v,d\rangle > \max_{\sigma\in\mathcal{A}(\theta;x,Y)} \left\langle \nabla_\theta f_\sigma(\theta),d \right\rangle,\] contradicting the previous inequality. Therefore, \[\partial M(\theta;x,Y) \subseteq \mathop{\mathrm{conv}} \left\{ \nabla_\theta f_\sigma(\theta): \sigma\in\mathcal{A}(\theta;x,Y) \right\}.\] Combining the two inclusions gives \[\partial_C M(\theta;x,Y) = \partial M(\theta;x,Y) = \mathop{\mathrm{conv}} \left\{ \nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma) : \sigma\in \mathop{\mathrm{arg\,max}}_{\sigma'\in S_K} \ell_{\mathrm{PL}}(\theta;x,Y,\sigma') \right\}.\]

Finally, by 1, any selected worst-case ranking \(\sigma_{\mathrm{worst}}\) belongs to the active maximizer set. Therefore its gradient is one of the active gradients and hence belongs to \(\partial_C M(\theta;x,Y)\). ◻

Proof. We prove the three claims separately.

(a) Fix \((x,Y,\sigma^\star)\). By the robust-TV decomposition, \[\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) = (1-\rho)\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho M(\theta;x,Y),\] where \[M(\theta;x,Y) = \max_{\sigma\in S_K} \ell_{\mathrm{PL}}(\theta;x,Y,\sigma).\] By 4, for every \(\sigma\in S_K\), the map \[\theta\mapsto \ell_{\mathrm{PL}}(\theta;x,Y,\sigma)\] is convex and continuously differentiable. Therefore \(\ell_{\mathrm{PL}}(\cdot;x,Y,\sigma^\star)\) is convex and Clarke regular. By 7, \(M(\cdot;x,Y)\) is also convex and Clarke regular. Since \(\rho\in[0,1]\), the function \(\ell_{\mathrm{rob}}(\cdot;x,Y,\sigma^\star)\) is a nonnegative linear combination of convex functions, and hence is convex. Since it is finite-valued and convex on the parameter space, it is Clarke regular.

It remains to compute the subdifferential. The convex subdifferential sum rule gives \[\partial \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) = (1-\rho)\partial \ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho\,\partial M(\theta;x,Y).\] Because \(\ell_{\mathrm{PL}}(\cdot;x,Y,\sigma^\star)\) is differentiable, \[\partial \ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) = \{\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star)\}.\] Moreover, since all the functions involved are convex and Clarke regular, their Clarke subdifferentials coincide with their convex subdifferentials. Hence \[\partial_C\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) = (1-\rho)\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho\,\partial_C M(\theta;x,Y).\] This proves (a).

(b) Fix \((x,Y)\). Since \(S_K\) is finite, the conditional expectation over \(\sigma^\star\sim p^\star(\cdot\mid x,Y)\) is a finite weighted sum: \[L_{\mathrm{rob}}(\theta;x,Y) = \sum_{\sigma^\star\in S_K} p^\star(\sigma^\star\mid x,Y) \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star).\] By part (a), each summand is convex and Clarke regular. The weights \(p^\star(\sigma^\star\mid x,Y)\) are nonnegative, sum to one, and are independent of \(\theta\). Therefore \(L_{\mathrm{rob}}(\cdot;x,Y)\) is convex and finite-valued, hence Clarke regular.

For the subdifferential, the finite convex-sum rule yields \[\partial L_{\mathrm{rob}}(\theta;x,Y) = \sum_{\sigma^\star\in S_K} p^\star(\sigma^\star\mid x,Y) \partial \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star).\] Equivalently, \[\partial_C L_{\mathrm{rob}}(\theta;x,Y) = \sum_{\sigma^\star\in S_K} p^\star(\sigma^\star\mid x,Y) \partial_C \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star).\] Writing the finite weighted sum in expectation notation gives \[\partial_C L_{\mathrm{rob}}(\theta;x,Y) = \mathbb{E}_{\sigma^\star\sim p^\star(\cdot\mid x,Y)} [ \partial_C\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) ].\] This is the finite-dimensional Aumann identity in the present setting. Since the label space \(S_K\) is finite and the subgradients are uniformly bounded by 4, measurability and integrability are automatic. This proves (b).

(c) Fix \((x,Y)\) and define \[q(\theta) := P_{\pi_\theta}(Y\mid x), \qquad L(\theta) := L_{\mathrm{rob}}(\theta;x,Y).\] Under 1, \(q\) is continuously differentiable in \(\theta\). In fact, because the softmax policy assigns strictly positive probability to every response in the finite response set, \[q(\theta)>0.\] By part (b), \(L\) is convex and Clarke regular. Moreover, \(L(\theta)\ge 0\), since \(\ell_{\mathrm{PL}}\ge 0\) and \(\ell_{\mathrm{rob}}\) is a convex combination of nonnegative PL losses.

We first verify Clarke regularity of the product \(qL\). For any direction \(d\), since \(q\) is \(C^1\) and \(L\) is directionally differentiable and Clarke regular, \[(qL)'(\theta;d) = \langle \nabla q(\theta),d\rangle L(\theta) + q(\theta)L'(\theta;d).\] Because \(L\) is Clarke regular, \[L'(\theta;d) = \max_{v\in\partial_C L(\theta)} \langle v,d\rangle.\] Therefore \[(qL)'(\theta;d) = \max_{v\in\partial_C L(\theta)} \left\langle L(\theta)\nabla q(\theta)+q(\theta)v, d \right\rangle.\] The right-hand side is the support function of the compact convex set \[L(\theta)\nabla q(\theta) + q(\theta)\partial_C L(\theta).\] Hence the Clarke directional derivative of \(qL\) agrees with its ordinary directional derivative, so \(qL\) is Clarke regular. Its Clarke subdifferential is exactly the set whose support function appears above: \[\partial_C(qL)(\theta) = L(\theta)\nabla q(\theta) + q(\theta)\partial_C L(\theta).\] Substituting back \[q(\theta)=P_{\pi_\theta}(Y\mid x), \qquad L(\theta)=L_{\mathrm{rob}}(\theta;x,Y),\] we obtain \[\partial_C \left[ P_{\pi_\theta}(Y\mid x)L_{\mathrm{rob}}(\theta;x,Y) \right] = P_{\pi_\theta}(Y\mid x)\partial_C L_{\mathrm{rob}}(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)\nabla_\theta P_{\pi_\theta}(Y\mid x).\] This proves (c). ◻

Proof. Fix \(\theta\in\Theta\). The set \(\mathcal{Y}\) is finite, and hence \[J_{\mathrm{rob}}^{\mathrm{on}}(\theta) = \mathbb{E}_{x\sim\mathcal{D}_x} \left[ H(\theta;x) \right],\] where \[H(\theta;x) := \sum_{Y\in\mathcal{Y}^K} P_\theta(Y\mid x) L_{\mathrm{rob}}(\theta;x,Y), \qquad P_\theta(Y\mid x) := \pi_\theta^{\otimes K}(Y\mid x).\] Writing \(Y=(y_1,\ldots,y_K)\), the policy-induced list probability is \[P_\theta(Y\mid x) = \prod_{i=1}^K \pi_\theta(y_i\mid x).\] Therefore, \[\nabla_\theta \log P_\theta(Y\mid x) = \sum_{i=1}^K \nabla_\theta \log \pi_\theta(y_i\mid x) =:S_\theta(x,Y).\] Since \(P_\theta(Y\mid x)\) is continuously differentiable in \(\theta\), we obtain the score-function identity \[\label{eq:score-prob-identity} \nabla_\theta P_\theta(Y\mid x) = P_\theta(Y\mid x)S_\theta(x,Y).\tag{14}\]

We first establish the subdifferential inclusion. Fix \(x\) and \(Y\). By construction, \(L_{\mathrm{rob}}(\theta;x,Y)\) is locally Lipschitz and Clarke regular in \(\theta\). Let \[V(\theta;x,Y)\in \partial_C L_{\mathrm{rob}}(\theta;x,Y)\] be an arbitrary measurable selection. Since \(P_\theta(Y\mid x)\) is \(C^1\), the Clarke product rule in 8(c) gives \[P_\theta(Y\mid x)V(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)\nabla_\theta P_\theta(Y\mid x) \in \partial_C \Big( P_\theta(Y\mid x)L_{\mathrm{rob}}(\theta;x,Y) \Big).\] Using 14 , this becomes \[P_\theta(Y\mid x) \Big[ V(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y) \Big] \in \partial_C \Big( P_\theta(Y\mid x)L_{\mathrm{rob}}(\theta;x,Y) \Big).\] Since \(\mathcal{Y}^K\) is finite, we may sum over \(Y\). By the Clarke sum rule, \[\sum_{Y\in\mathcal{Y}^K} P_\theta(Y\mid x) \Big[ V(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y) \Big] \in \partial_C H(\theta;x).\] Equivalently, \[\mathbb{E}_{Y\sim\pi_\theta^{\otimes K}(\cdot\mid x)} \Big[ V(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y) \Big] \in \partial_C H(\theta;x).\]

Now take expectation over \(x\sim\mathcal{D}_x\). The selection above is measurable by the deterministic tie-breaking rule used in the definition of the worst-case ranking, and it is integrable by the uniform bounds on \(\partial_C L_{\mathrm{rob}}\), \(L_{\mathrm{rob}}\), and \(S_\theta\). Hence the Aumann expectation rule yields \[\mathbb{E}_x \mathbb{E}_{Y\sim\pi_\theta^{\otimes K}(\cdot\mid x)} \Big[ V(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y) \Big] \in \partial_C J_{\mathrm{rob}}^{\mathrm{on}}(\theta).\] Since \(V(\theta;x,Y)\) was an arbitrary measurable selection from \(\partial_C L_{\mathrm{rob}}(\theta;x,Y)\), this proves the set-valued inclusion \[\partial_C J_{\mathrm{rob}}^{\mathrm{on}}(\theta) \;\supseteq\; \mathbb{E}_x\,\mathbb{E}_{Y\sim\pi_\theta^{\otimes K}} \big[ \partial_C L_{\mathrm{rob}}(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y) \big].\]

It remains to verify the stated Lipschitz bound. By the PL gradient bound and the robust-loss construction, \[\sup_{V\in\partial_C L_{\mathrm{rob}}(\theta;x,Y)} \|V\| \le C_G.\] Moreover, \[0\le L_{\mathrm{rob}}(\theta;x,Y)\le C_L, \qquad \|S_\theta(x,Y)\|\le 2KB_\psi.\] Therefore, every vector in the set \[\partial_C L_{\mathrm{rob}}(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y)\] has norm at most \[C_G+2KB_\psi C_L.\] Averaging over \(Y\sim\pi_\theta^{\otimes K}(\cdot\mid x)\) and then over \(x\sim\mathcal{D}_x\) preserves this bound. Hence every element constructed in the right-hand side of 13 has norm at most \(C_G+2KB_\psi C_L\). Since \(J_{\mathrm{rob}}^{\mathrm{on}}\) is locally Lipschitz and its Clarke subgradients are uniformly bounded by this quantity, \(J_{\mathrm{rob}}^{\mathrm{on}}\) is locally Lipschitz on \(\Theta\) with constant at most \[C_G+2KB_\psi C_L.\] The same argument holds on any bounded neighborhood of \(\Theta\), with \(D\) in \(C_L\) replaced by the corresponding radius on that neighborhood. ◻

Proof. Fix \(\theta\in\Theta\). Throughout the proof, all expectations are conditional on the current parameter \(\theta\) unless otherwise stated. Recall that \[G(\theta;Z)=G_1(\theta;Z)+G_2(\theta;Z),\] where \[G_1(\theta;Z) := (1-\rho)\nabla_\theta \ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho \nabla_\theta \ell_{\mathrm{PL}}(\theta;x,Y,\sigma^{\mathrm{sel}}),\] and \[G_2(\theta;Z) := \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star)S_\theta(x,Y).\]

(a) Fix \((x,Y,\sigma^\star)\). Define the pointwise worst-case PL loss \[M(\theta;x,Y) := \max_{\sigma\in S_K}\ell_{\mathrm{PL}}(\theta;x,Y,\sigma).\] Then \[\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) = (1-\rho)\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho M(\theta;x,Y).\] Since \(S_K\) is finite and, for each \(\sigma\in S_K\), \(\theta\mapsto \ell_{\mathrm{PL}}(\theta;x,Y,\sigma)\) is continuously differentiable, the function \(M(\theta;x,Y)\) is locally Lipschitz and Clarke regular. By the finite-max Danskin theorem in 7, \[\partial_C M(\theta;x,Y) = \operatorname{conv} \left\{ \nabla_\theta \ell_{\mathrm{PL}}(\theta;x,Y,\sigma) : \sigma\in \arg\max_{\tilde{\sigma}\in S_K} \ell_{\mathrm{PL}}(\theta;x,Y,\tilde{\sigma}) \right\}.\] By construction, \(\sigma^{\mathrm{sel}}\) is selected from the active maximizer set: \[\sigma^{\mathrm{sel}} \in \arg\max_{\sigma\in S_K} \ell_{\mathrm{PL}}(\theta;x,Y,\sigma).\] Therefore, \[\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^{\mathrm{sel}}) \in \partial_C M(\theta;x,Y).\] Using the Clarke sum rule in 8(a), we obtain \[(1-\rho)\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star) + \rho\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^{\mathrm{sel}}) \in \partial_C\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star).\] The left-hand side is exactly \(G_1(\theta;Z)\). Hence \[G_1(\theta;Z)\in\partial_C\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star).\] This argument also covers ties: when the active maximizer set is not a singleton, the deterministic tie-breaking rule selects one active maximizer, and every active gradient is a valid element of the Clarke subdifferential of the finite maximum.

(b) For fixed \((x,Y)\), define the conditional robust loss \[L_{\mathrm{rob}}(\theta;x,Y) := \mathbb{E}_{\sigma^\star\sim p^\star(\cdot|x,Y)} \left[ \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) \right].\] Since \(S_K\) is finite, the expectation over \(\sigma^\star\) is a finite sum. Moreover, by part (a), for every possible \(\sigma^\star\), \[G_1(\theta;x,Y,\sigma^\star) \in \partial_C\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star).\] Therefore, by the Aumann expectation rule in 8(b), \[H(\theta;x,Y) := \mathbb{E}_{\sigma^\star} \left[ G_1(\theta;Z) \,\middle|\, x,Y,\theta \right] \in \partial_C L_{\mathrm{rob}}(\theta;x,Y).\] The measurability of \(H\) follows from the deterministic tie-breaking rule used to define \(\sigma^{\mathrm{sel}}\), and integrability follows from the uniform gradient bound.

Next, since \(S_\theta(x,Y)\) depends only on the policy-generated list \((x,Y)\) and not on the oracle label \(\sigma^\star\), we have \[\mathbb{E}_{\sigma^\star} \left[ G_2(\theta;Z) \,\middle|\, x,Y,\theta \right] = \mathbb{E}_{\sigma^\star} \left[ \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) \,\middle|\, x,Y,\theta \right] S_\theta(x,Y) = L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y).\] Combining the two conditional expectations gives \[\mathbb{E}_{\sigma^\star} \left[ G(\theta;Z) \,\middle|\, x,Y,\theta \right] = H(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y),\] with \[H(\theta;x,Y)\in\partial_C L_{\mathrm{rob}}(\theta;x,Y).\]

Now take expectation over \(x\sim\mathcal{D}_x\) and \(Y\sim\pi_\theta^{\otimes K}(\cdot|x)\). We obtain \[\mathbb{E}[G(\theta;Z)\mid\theta] = \mathbb{E}_{x,Y} \left[ H(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y) \right],\] where \(H(\theta;x,Y)\in\partial_C L_{\mathrm{rob}}(\theta;x,Y)\) is a measurable selection. By the score-function identity in 9, \[\mathbb{E}_{x,Y} \left[ H(\theta;x,Y) + L_{\mathrm{rob}}(\theta;x,Y)S_\theta(x,Y) \right] \in \partial_C J_{\mathrm{rob}}^{\mathrm{on}}(\theta).\] Therefore, \[\mathbb{E}[G(\theta;Z)\mid\theta] \in \partial_C J_{\mathrm{rob}}^{\mathrm{on}}(\theta).\]

(c) By the PL gradient bound, for every ranking \(\sigma\in S_K\), \[\|\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma)\| \le C_G.\] Since \(G_1\) is a convex combination of two PL gradients, we have \[\|G_1\| \le (1-\rho) \|\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^\star)\| + \rho \|\nabla_\theta\ell_{\mathrm{PL}}(\theta;x,Y,\sigma^{\mathrm{sel}})\| \le (1-\rho)C_G+\rho C_G = C_G.\] Moreover, by the uniform loss bound and the score-function bound, \[0\le \ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star) \le C_L, \qquad \|S_\theta(x,Y)\| \le 2KB_\psi.\] Hence \[\|G_2\| = \|\ell_{\mathrm{rob}}(\theta;x,Y,\sigma^\star)S_\theta(x,Y)\| \le 2KB_\psi C_L.\] Using the elementary inequality \[\|a+b\|^2\le 2\|a\|^2+2\|b\|^2,\] we obtain the pointwise bound \[\|G(\theta;Z)\|^2 \le 2\|G_1\|^2+2\|G_2\|^2 \le 2C_G^2 + 2(2KB_\psi C_L)^2 = G_{\mathrm{tot}}^2.\] Taking conditional expectation given \(\theta\) preserves the bound: \[\mathbb{E}[\|G(\theta;Z)\|^2\mid\theta] \le G_{\mathrm{tot}}^2.\] This proves (c). ◻

Proof. We first record the mini-batch oracle properties. Conditional on \(\theta_t\), the samples \(Z_1,\ldots,Z_{B_s}\) are iid from the policy-induced online sampling distribution. By 10(b), \[\mathbb{E}[G(\theta_t;Z_i)\mid\theta_t] \in \partial_CJ_{\mathrm{rob}}^{\mathrm{on}}(\theta_t) \qquad \text{for every }i.\] Since the Clarke subdifferential is convex, \[\bar G_t := \mathbb{E}[\widehat G_t\mid\theta_t] = \frac{1}{B_s} \sum_{i=1}^{B_s} \mathbb{E}[G(\theta_t;Z_i)\mid\theta_t] \in \partial_CJ_{\mathrm{rob}}^{\mathrm{on}}(\theta_t).\] Moreover, by Jensen’s inequality and 10(c), \[\mathbb{E}[\|\widehat G_t\|^2\mid\theta_t] = \mathbb{E}\left[ \left\| \frac{1}{B_s}\sum_{i=1}^{B_s}G(\theta_t;Z_i) \right\|^2 \,\middle|\, \theta_t \right] \le \frac{1}{B_s}\sum_{i=1}^{B_s} \mathbb{E}[ \|G(\theta_t;Z_i)\|^2 \mid \theta_t ] \le G_{\mathrm{tot}}^2.\]

Let \[\hat{\theta}_t := \hat{\theta}(\theta_t) = \mathop{\mathrm{prox}}_{\hat{\lambda} F}(\theta_t).\] Since \(\hat{\theta}_t\in\Theta\), it is feasible for the constrained Moreau envelope at \(\theta_{t+1}\). Therefore, \[F_{\hat{\lambda}}(\theta_{t+1}) \le J_{\mathrm{rob}}^{\mathrm{on}}(\hat{\theta}_t) + \frac{1}{2\hat{\lambda}} \|\hat{\theta}_t-\theta_{t+1}\|^2.\] By definition of \(\hat{\theta}_t\), \[F_{\hat{\lambda}}(\theta_t) = J_{\mathrm{rob}}^{\mathrm{on}}(\hat{\theta}_t) + \frac{1}{2\hat{\lambda}} \|\hat{\theta}_t-\theta_t\|^2.\] Subtracting yields \[F_{\hat{\lambda}}(\theta_{t+1})-F_{\hat{\lambda}}(\theta_t) \le \frac{1}{2\hat{\lambda}} \left( \|\hat{\theta}_t-\theta_{t+1}\|^2 - \|\hat{\theta}_t-\theta_t\|^2 \right). \label{eq:env-step}\tag{17}\]

Because \(\Theta\) is closed and convex, the projection \(\Pi_\Theta\) is nonexpansive. Since \(\hat{\theta}_t\in\Theta\), \[\|\theta_{t+1}-\hat{\theta}_t\|^2 = \|\Pi_\Theta(\theta_t-\eta\widehat G_t)-\Pi_\Theta(\hat{\theta}_t)\|^2 \le \|\theta_t-\eta\widehat G_t-\hat{\theta}_t\|^2.\] Expanding the right-hand side, \[\|\theta_{t+1}-\hat{\theta}_t\|^2 \le \|\theta_t-\hat{\theta}_t\|^2 - 2\eta\langle \widehat G_t,\theta_t-\hat{\theta}_t\rangle + \eta^2\|\widehat G_t\|^2. \label{eq:proj-expand}\tag{18}\] Combining 17 and 18 , then taking conditional expectation given \(\theta_t\), gives \[\begin{align} \mathbb{E}[ F_{\hat{\lambda}}(\theta_{t+1})-F_{\hat{\lambda}}(\theta_t) \mid\theta_t ] &\le -\frac{\eta}{\hat{\lambda}} \langle \bar G_t,\theta_t-\hat{\theta}_t\rangle + \frac{\eta^2}{2\hat{\lambda}} \mathbb{E}[\|\widehat G_t\|^2\mid\theta_t] \notag\\ &\le -\frac{\eta}{\hat{\lambda}} \langle \bar G_t,\theta_t-\hat{\theta}_t\rangle + \frac{\eta^2G_{\mathrm{tot}}^2}{2\hat{\lambda}}. \label{eq:env-cond} \end{align}\tag{19}\]

It remains to lower bound \(\langle \bar G_t,\theta_t-\hat{\theta}_t\rangle\). The proximal point satisfies \[\hat{\theta}_t \in \mathop{\mathrm{arg\,min}}_{u\in\Theta} \left\{ J_{\mathrm{rob}}^{\mathrm{on}}(u) + \frac{1}{2\hat{\lambda}}\|u-\theta_t\|^2 \right\}.\] The first-order optimality condition over \(\Theta\) gives some \[\zeta_t\in\partial_CJ_{\mathrm{rob}}^{\mathrm{on}}(\hat{\theta}_t), \qquad n_t\in N_\Theta(\hat{\theta}_t),\] such that \[0 = \zeta_t + \frac{1}{\hat{\lambda}}(\hat{\theta}_t-\theta_t) + n_t.\] Using the normal-cone convention \[\langle n_t,u-\hat{\theta}_t\rangle\le0, \qquad \forall u\in\Theta,\] and taking \(u=\theta_t\in\Theta\), we get \[\left\langle \zeta_t + \frac{1}{\hat{\lambda}}(\hat{\theta}_t-\theta_t), \theta_t-\hat{\theta}_t \right\rangle = -\langle n_t,\theta_t-\hat{\theta}_t\rangle \ge0.\] Therefore, \[\langle \zeta_t,\theta_t-\hat{\theta}_t\rangle \ge \frac{1}{\hat{\lambda}} \|\theta_t-\hat{\theta}_t\|^2. \label{eq:prox-foc}\tag{20}\]

By \(\kappa\)-weak convexity of \(J_{\mathrm{rob}}^{\mathrm{on}}\), the function \[\Phi(\theta) := J_{\mathrm{rob}}^{\mathrm{on}}(\theta) + \frac{\kappa}{2}\|\theta\|^2\] is convex on \(\Theta\). Since \[\bar G_t\in\partial_CJ_{\mathrm{rob}}^{\mathrm{on}}(\theta_t), \qquad \zeta_t\in\partial_CJ_{\mathrm{rob}}^{\mathrm{on}}(\hat{\theta}_t),\] we have \[\bar G_t+\kappa\theta_t\in\partial_C\Phi(\theta_t), \qquad \zeta_t+\kappa\hat{\theta}_t\in\partial_C\Phi(\hat{\theta}_t).\] By monotonicity of the convex subdifferential of \(\Phi\), \[\left\langle (\bar G_t+\kappa\theta_t) - (\zeta_t+\kappa\hat{\theta}_t), \theta_t-\hat{\theta}_t \right\rangle \ge0.\] Equivalently, \[\langle \bar G_t-\zeta_t,\theta_t-\hat{\theta}_t\rangle \ge -\kappa\|\theta_t-\hat{\theta}_t\|^2. \label{eq:weak-mon}\tag{21}\] Adding 20 and 21 , \[\langle \bar G_t,\theta_t-\hat{\theta}_t\rangle \ge \left( \frac{1}{\hat{\lambda}}-\kappa \right) \|\theta_t-\hat{\theta}_t\|^2 = \frac{1-\kappa\hat{\lambda}}{\hat{\lambda}} \|\theta_t-\hat{\theta}_t\|^2. \label{eq:gbar-bound}\tag{22}\]

By 6, \[\nabla F_{\hat{\lambda}}(\theta_t) = \hat{\lambda}^{-1} (\theta_t-\hat{\theta}_t).\] Hence \[\|\theta_t-\hat{\theta}_t\|^2 = \hat{\lambda}^2 \|\nabla F_{\hat{\lambda}}(\theta_t)\|^2.\] Substituting into 22 gives \[\langle \bar G_t,\theta_t-\hat{\theta}_t\rangle \ge (1-\kappa\hat{\lambda})\hat{\lambda} \|\nabla F_{\hat{\lambda}}(\theta_t)\|^2.\] Plugging this into 19 , we obtain \[\mathbb{E}[ F_{\hat{\lambda}}(\theta_{t+1})-F_{\hat{\lambda}}(\theta_t) \mid\theta_t ] \le -\eta(1-\kappa\hat{\lambda}) \|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 + \frac{\eta^2G_{\mathrm{tot}}^2}{2\hat{\lambda}}.\] Since \(1-\kappa\hat{\lambda}>0\), this stronger bound implies 16 . ◻

Proof of 3. If \(\Delta_0=0\), then \(F_{\hat{\lambda}}(\theta_0)=F_{\inf}\), and the desired bound is trivial. Hence assume \(\Delta_0>0\). By 11, for every \(t=0,\ldots,T-1\), \[\mathbb{E}\!\left[ F_{\hat{\lambda}}(\theta_{t+1}) \,\middle|\, \theta_t \right] \le F_{\hat{\lambda}}(\theta_t) - \frac{\eta(1-\kappa\hat{\lambda})}{2} \|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 + \frac{\eta^2G_{\mathrm{tot}}^2}{2\hat{\lambda}}.\] Taking total expectation gives \[\mathbb{E}[ F_{\hat{\lambda}}(\theta_{t+1}) ] \le \mathbb{E}[ F_{\hat{\lambda}}(\theta_t) ] - \frac{\eta(1-\kappa\hat{\lambda})}{2} \mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 + \frac{\eta^2G_{\mathrm{tot}}^2}{2\hat{\lambda}}.\] Rearranging, \[\frac{\eta(1-\kappa\hat{\lambda})}{2} \mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 \le \mathbb{E}[ F_{\hat{\lambda}}(\theta_t) ] - \mathbb{E}[ F_{\hat{\lambda}}(\theta_{t+1}) ] + \frac{\eta^2G_{\mathrm{tot}}^2}{2\hat{\lambda}}.\] Summing over \(t=0,\ldots,T-1\), we obtain \[\frac{\eta(1-\kappa\hat{\lambda})}{2} \sum_{t=0}^{T-1} \mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 \le F_{\hat{\lambda}}(\theta_0) - \mathbb{E}[ F_{\hat{\lambda}}(\theta_T) ] + \frac{T\eta^2G_{\mathrm{tot}}^2}{2\hat{\lambda}}.\] Since \[F_{\hat{\lambda}}(\theta) = \min_u \left\{ F(u)+\frac{1}{2\hat{\lambda}}\|u-\theta\|^2 \right\} \ge \inf_u F(u) = F_{\inf},\] we have \[F_{\hat{\lambda}}(\theta_0) - \mathbb{E}[ F_{\hat{\lambda}}(\theta_T) ] \le F_{\hat{\lambda}}(\theta_0)-F_{\inf} = \Delta_0.\] Therefore, \[\frac{\eta(1-\kappa\hat{\lambda})}{2} \sum_{t=0}^{T-1} \mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 \le \Delta_0 + \frac{T\eta^2G_{\mathrm{tot}}^2}{2\hat{\lambda}}.\] Dividing by \(\eta T\) gives \[\frac{1-\kappa\hat{\lambda}}{2} \cdot \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 \le \frac{\Delta_0}{\eta T} + \frac{\eta G_{\mathrm{tot}}^2}{2\hat{\lambda}}.\] With the choice \[\eta = \sqrt{ \frac{2\hat{\lambda}\Delta_0}{G_{\mathrm{tot}}^2T} },\] the two terms on the right-hand side are equal: \[\frac{\Delta_0}{\eta T} = \frac{\eta G_{\mathrm{tot}}^2}{2\hat{\lambda}} = \sqrt{ \frac{\Delta_0G_{\mathrm{tot}}^2}{2\hat{\lambda} T} }.\] Hence \[\frac{1-\kappa\hat{\lambda}}{2} \cdot \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_t)\|^2 \le \sqrt{ \frac{2\Delta_0G_{\mathrm{tot}}^2}{\hat{\lambda} T} }.\] Let \(R\sim\mathrm{Uniform}\{0,\ldots,T-1\}\) be sampled independently of the algorithmic randomness. Then \[\mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_R)\|^2 = \frac{1}{T} \sum_{t=0}^{T-1} \mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_t)\|^2.\] Therefore, \[\mathbb{E}\|\nabla F_{\hat{\lambda}}(\theta_R)\|^2 \le \frac{2}{1-\kappa\hat{\lambda}} \sqrt{ \frac{2\Delta_0G_{\mathrm{tot}}^2}{\hat{\lambda} T} },\] which is exactly 10 . ◻

Proof of 1. By 3, it suffices to require \[\frac{2}{1-\kappa\hat{\lambda}} \sqrt{ \frac{2\Delta_0G_{\mathrm{tot}}^2}{\hat{\lambda} T} } \le \varepsilon.\] Squaring both sides gives \[\frac{4}{(1-\kappa\hat{\lambda})^2} \cdot \frac{2\Delta_0G_{\mathrm{tot}}^2}{\hat{\lambda} T} \le \varepsilon^2.\] Equivalently, \[T \ge \frac{ 8\Delta_0G_{\mathrm{tot}}^2 }{ \hat{\lambda}(1-\kappa\hat{\lambda})^2\varepsilon^2 }.\] This proves the first claim.

Now set \[\hat{\lambda}=\frac{1}{2\kappa}.\] Then \[1-\kappa\hat{\lambda} = \frac{1}{2},\] and hence \[T \ge \frac{ 8\Delta_0G_{\mathrm{tot}}^2 }{ (1/(2\kappa))(1/2)^2\varepsilon^2 } = \frac{ 64\kappa\Delta_0G_{\mathrm{tot}}^2 }{ \varepsilon^2 }.\] Therefore, \[T = O\left( \frac{\kappa\Delta_0G_{\mathrm{tot}}^2}{\varepsilon^2} \right).\]

It remains to substitute the explicit constants. From ?? , \[\kappa = K^2B_\psi^2 (8+\log K+2DB_\psi) = \tilde{O}\!\left( K^2B_\psi^2(\log K+DB_\psi) \right).\] From 15 , \[G_{\mathrm{tot}}^2 = 2C_G^2 + 2(2KB_\psi C_L)^2,\] where \[C_G=2KB_\psi, \qquad C_L=K(\log K+2DB_\psi).\] Thus \[2C_G^2 = O(K^2B_\psi^2),\] and \[2(2KB_\psi C_L)^2 = O\!\left( K^2B_\psi^2 \cdot K^2(\log K+DB_\psi)^2 \right) = O\!\left( K^4B_\psi^2(\log K+DB_\psi)^2 \right).\] The second term dominates for the relevant asymptotic regime, so \[G_{\mathrm{tot}}^2 = O\!\left( K^4B_\psi^2(\log K+DB_\psi)^2 \right).\] Combining the bounds gives \[\kappa G_{\mathrm{tot}}^2 = \tilde{O}\!\left( K^6B_\psi^4(\log K+DB_\psi)^3 \right).\] Therefore, \[T = \tilde{O}\!\left( \frac{ K^6B_\psi^4(\log K+DB_\psi)^3 }{ \varepsilon^2 } \right),\] which proves 11 . ◻

Proof. Write \(\ell_{\mathrm{PL}}=\sum_{i=1}^{K-1}\ell_i\) where \(\ell_i(\theta) = -\theta^\top\phi(x,y_{\sigma^\star_i})+\log\sum_{j\in R_i}\exp(\theta^\top\phi(x,y_j))\) is the negative log-likelihood of the \(i\)-th stagewise multinomial choice. Differentiating gives \(\nabla\ell_i = -\phi(x,y_{\sigma^\star_i})+\mu_i\) and \(\nabla^2\ell_i=\sum_{j\in R_i}p_i^\theta(j)(\phi(x,y_j)-\mu_i)(\phi(x,y_j)-\mu_i)^\top = \mathrm{Cov}_{j\sim p_i^\theta}[\phi(x,y_j)]\succeq 0\). Sum over \(i\). ◻