Convex Programs For Distributionally Robust Prediction

From Empirical Risk to a Convex Program

A distributionally robust predictor is assessed not only under the empirical distribution of the observed sample, but under the most unfavorable distribution in a specified ambiguity set. In the finite-sample formulation, that alternative distribution assigns probability weights to the observed cases. The resulting optimization has two distinct tasks: for a fixed predictor, find its worst-case weighted loss; then choose a predictor that minimizes this worst-case risk.

Let \(Z_1,\ldots,Z_n\) be observed cases, let \(\beta\) belong to a convex set \(B\), and let \(\ell(\beta;Z_i)\) be the loss on case \(i\). Assume throughout that each loss is finite and convex in \(\beta\). Write \(p_i=1/n\) for the empirical weights. An ambiguity set \(Q\) consists of admissible probability vectors \(q=(q_1,\ldots,q_n)\).

The probability weights reallocate mass among the observed cases; they do not create new feature values or outcomes. The choice of \(Q\) expresses which reweightings are considered plausible. It may be the full simplex, a simplex with additional linear restrictions, or a divergence neighborhood around \(p\).

Simplex and Polyhedral Ambiguity Sets

For the full simplex, the worst-case distribution puts all probability on a case with the largest loss. This is a valid but often highly conservative criterion. Restrictions such as upper bounds on individual weights can prevent complete concentration. More generally, a polyhedral ambiguity set has finitely many extreme points, so the inner maximization can be represented by finitely many linear programs evaluated at those points.

Proof. For fixed \(\beta\), the objective \(q\mapsto\sum_iq_i\ell(\beta;Z_i)\) is linear. A linear function on a nonempty compact polytope attains its maximum at a vertex, giving the stated maximum. For each vertex, \(\sum_i v_i^{(k)}\ell(\beta;Z_i)\) is a nonnegative weighted sum of convex functions, hence is convex. The pointwise maximum of finitely many convex functions is convex. Finally, \(t\) is at least every vertex objective exactly when it is at least their maximum, so minimizing \(t\) gives the robust problem. \(\square\)

The epigraph representation is a convex program when \(B\) is convex. Importantly, this does not mean that the expression \(\sum_iq_i\ell(\beta;Z_i)\) is jointly convex in \((q,\beta)\). The weights and loss values are multiplied. For a finite polytope, convexity follows instead from taking the maximum over its vertices and using the epigraph constraints.

Divergence Constraints and a Convex Prediction Objective

A divergence ball limits how far the weights can move from the empirical distribution. One common choice is relative entropy, or Kullback–Leibler divergence: \(D_{\mathrm{KL}}(q\Vert p)=\sum_iq_i\log(q_i/p_i)\), with \(0\log(0/p_i)=0\). For \(p_i>0\), the ambiguity set \(Q_\rho=\{q:q_i\geq0,\sum_iq_i=1,D_{\mathrm{KL}}(q\Vert p)\leq\rho\}\) is convex. For \(\rho>0\), the worst-case risk admits a useful dual expression.

Proof. For any \(\eta>0\), set \(C=\sum_i p_i\exp(a_i/\eta)\) and \(r_i=p_i\exp(a_i/\eta)/C\). These \(r_i\) are positive and sum to one. For any probability vector \(q\), \(\sum_iq_i a_i-\eta D_{\mathrm{KL}}(q\Vert p) =\eta\log C-\eta D_{\mathrm{KL}}(q\Vert r)\). Relative entropy is nonnegative, so for any \(q\in Q_\rho\), \(\sum_iq_i a_i\leq\eta\rho+\eta\log C\). Taking the supremum over \(q\), then the infimum over \(\eta>0\), proves one inequality.

For the reverse inequality, maximize the linear objective over the probability simplex subject to the convex constraint \(D_{\mathrm{KL}}(q\Vert p)\leq\rho\). The feasible set is compact, and \(q=p\) is strictly feasible because \(D_{\mathrm{KL}}(p\Vert p)=0<\rho\). Strong Lagrange duality therefore applies. For multiplier \(\eta\geq0\), the dual objective is \(\eta\rho+\sup_q\{\sum_iq_i a_i-\eta D_{\mathrm{KL}}(q\Vert p)\}\). For \(\eta>0\), the identity already shown, maximized over \(q\), gives \(\eta\rho+\eta\log C\); equality in that maximization occurs at \(q=r\). The dual infimum gives the claimed expression, with a possible boundary value at \(\eta=0\) understood as a limit from \(\eta>0\). Thus the infimum over positive \(\eta\) equals the strong-duality value.

To see convexity, write \(g(\eta,a)=\eta\log(\sum_i p_i\exp(a_i/\eta))\). This is the perspective of the convex log-sum-exp function, hence convex jointly in \((\eta,a)\) for \(\eta>0\). It is also nondecreasing in each \(a_i\). Substituting the convex functions \(a_i=\ell(\beta;Z_i)\) therefore preserves convexity; adding the linear term \(\eta\rho\) does as well. The infimum formulation is an optimization over the joint variables \((\beta,\eta)\), so it supplies a convex formulation of the robust prediction problem. \(\square\)

Moment Constraints

Moment restrictions constrain weighted averages of known case-level quantities. Let \(z_i\in\mathbb R^d\) be specified vectors and let \(m\in\mathbb R^d\) be a target moment. The ambiguity set \(Q_m=\{q:q_i\geq0,\sum_iq_i=1,\sum_iq_i z_i=m\}\) is a polytope whenever it is nonempty. Its worst-case risk is a linear program for fixed losses. In particular, its dual form is \(\min_{\alpha\in\mathbb R,\lambda\in\mathbb R^d}\alpha+\lambda^\mathsf{T}m\), subject to \(\alpha+\lambda^\mathsf{T}z_i\geq\ell(\beta;Z_i)\) for each \(i\). This follows from the linear-programming dual: \(\alpha,\lambda\) are multipliers for the total-mass and moment equalities, and the inequalities are the dual constraints for \(q_i\geq0\). When the primal is feasible and bounded, strong linear-programming duality gives equality. The dual constraints are convex in \(\beta\) for convex losses, so they also give a convex prediction formulation.

Formulation Checks and a Common Pitfall

The main modeling question is what information the ambiguity set is intended to preserve. A simplex alone permits arbitrary concentration; a divergence ball controls departure from a reference distribution; moment equalities preserve specified weighted averages. Constraints can also be combined, provided their intersection is nonempty. Once the set is chosen, check that its weights are nonnegative and sum to one, and that every additional restriction is imposed on the intended case-level quantities.

• Pitfall: minimizing jointly over the predictor and the adversarial weights. The expression \(\sum_iq_i\ell(\beta;Z_i)\) is generally not jointly convex, since it multiplies a weight by a loss depending on \(\beta\). Simply writing \(\min_{\beta,q}\sum_iq_i\ell(\beta;Z_i)\) is also the wrong order: it lets the predictor select favorable weights.
• Correction: The robust objective is \(\min_\beta\sup_{q\in Q}\sum_iq_i\ell(\beta;Z_i)\). Use a finite-vertex epigraph for a polytope, or a valid dual representation such as the relative-entropy formula. These formulations preserve the worst-case order and expose convexity under the stated conditions.
• Pitfall: treating a moment equality as a penalty. Replacing \(\sum_iq_i z_i=m\) by a term in the objective changes the ambiguity set and generally changes the worst-case risk. Use an equality when the moment must be preserved exactly.