Distributionally robust optimization (DRO) trains a model against the worst distribution in a neighborhood of the training data, not against the training data itself. One attractive choice of neighborhood is a ball measured by maximum mean discrepancy (MMD), which compares two distributions through their average similarity under a kernel. These balls shrink at a rate that does not depend on input dimension, and they let the adversary place probability mass on points never seen in training. To make them scale, the leading algorithm replaces the kernel with a few hundred random Fourier features, which are random cosine functions whose inner products approximate the kernel. It then reports the optimized dual objective as a bound on worst-case risk.
This proposal argues that the reported number is not a bound on the risk practitioners care about. With a fixed number $m$ of random features, the optimization is exactly DRO over a different ball, defined by a random, finite-rank kernel. That kernel is not "characteristic": unlike the original kernel, it cannot tell all pairs of distributions apart. Its ball therefore neither contains nor sits inside the intended one. We propose to measure how far the two diverge, to derive how many features are needed before the random-feature value upper-bounds the true worst case, and to build a cheap recipe: train with random features, then certify with a valid in-kernel dual. We will then test whether the gap matters on the benchmarks where kernel DRO has been evaluated.
Core Claim
The Stochastic Functional Gradient DRO method of Kernel Distributionally Robust Optimization: Generalized Duality Theorem and Stochastic Approximation dualizes the MMD-ball adversary into a search over a smooth function $g$ that lies above the loss everywhere, with the RKHS norm of $g$ as the price. It then parameterizes $g(x)=w^\top z(x)$ with $m$ fixed random Fourier features $z$ and uses $\|w\|_2$ as that norm. Here the RKHS, or reproducing kernel Hilbert space, is the function space whose geometry the kernel defines. The quantity $\|w\|_2$ is not the original RKHS norm of $g$. Pure cosines are not even in a Gaussian RKHS on $\mathbb{R}^d$. It is the norm in the RKHS of the random kernel $k_m(x,y)=z(x)^\top z(y)$. Two errors follow, and they push in opposite directions.
The first error makes the method too pessimistic. Because $k_m$ has rank $m$, its ball contains distributions that match the training data on all $m$ sampled frequencies and differ arbitrarily elsewhere. The second error makes it too optimistic. The ball's radius is calibrated for the exact kernel, and the lying-above constraint is enforced only at sampled points.
The theoretical starting point is an elementary containment. For distributions supported on a compact set $S$, let $\eta_m=\sup_{x,y\in S}|k(x,y)-k_m(x,y)|$ be the worst-case kernel approximation error. Then
$$ \big|\mathrm{MMD}_m^2(P,Q)-\mathrm{MMD}^2(P,Q)\big|\le 4\eta_m , $$
where $\mathrm{MMD}$ uses the exact kernel and $\mathrm{MMD}_m$ uses $k_m$. The inequality holds because each of the three kernel expectations in the squared MMD is off by at most $\eta_m$ in a way that sums to $4\eta_m$. So the exact ball of radius $\epsilon$ sits inside the random-feature ball of radius $\sqrt{\epsilon^2+4\eta_m}$. Inflating the radius this way turns the random-feature dual into a valid upper bound, provided the lying-above constraint holds on all of $S$.
Optimal Rates for Random Fourier Features gives $\eta_m=O(\sqrt{\log|S|/m})$. Kernel DRO sets $\epsilon\sim n^{-1/2}$ for $n$ training points, and we want the inflation to stay within a constant factor of $\epsilon$. That requires $\eta_m\lesssim 1/n$, hence $m\gtrsim n^2\log|S|$. This is far more features than anyone uses.
A pointwise variance argument points to a much smaller requirement. For a single fixed pair of distributions, each feature's contribution to $\mathrm{MMD}_m^2$ has mean $\mathrm{MMD}^2$ and variance at most of order $\mathrm{MMD}^2$. This suggests that $m\sim n$ suffices for the one distribution the adversary actually picks. The central question is where the true requirement lies between $n$ and $n^2$, and how it depends on the kernel's spectrum. Our conjecture is that a localized analysis gives $m=\tilde O(n)$ for Gaussian kernels. We further conjecture that kernels with heavier spectral tails or spectral troughs need more features. Troughs are frequency bands where the kernel's Fourier weight is nearly zero. Laplacian, Matérn and B-spline kernels have these features, and random sampling rarely draws frequencies from such bands.
Research Program
The theory strand has three goals. First, we will tighten the uniform containment above into a localized bound that controls the random-feature error only over distributions the adversary could favor, using empirical-process tools from Optimal Rates for Random Fourier Features. Second, we will prove a matching lower bound: an explicit loss and data distribution for which, with $m=o(n)$ features, the random-feature value falls below the exact worst-case risk with constant probability. Third, we will express both bounds in terms of the kernel's spectral measure.
The lower-bound construction borrows from the injectivity theory of Injective Hilbert Space Embeddings of Probability Measures. That paper shows a translation-invariant kernel separates distributions exactly when its spectral measure has full support. It also shows that low spectral density creates finite-sample blind spots. Our construction places the adversary's perturbation where the random features are least likely to look. A finite-feature map cannot be injective. This mirrors the result of Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features that fixed-feature MMD tests are inconsistent. We carry that observation from testing, where the cost is lost power, to robust optimization, where the cost is an invalid safety claim.
The algorithmic strand separates training from certification. Training uses Stochastic Functional Gradient DRO with random features as before. Certification then fits a separate dual function $g=\sum_j\alpha_j k(c_j,\cdot)$ built from exact kernel functions at landmark points $c_j$. Its true RKHS norm $\sqrt{\alpha^\top K\alpha}$ is computable, so restricting to this subspace yields a genuine upper bound on the exact-ball worst case. This bound is valid for any number of landmarks, provided the lying-above constraint is verified on a cover of $S$. Verifying it on a finite set of points is enough to show a certificate is wrong, but proving one right also needs a Lipschitz margin, which is computable for smooth kernels. Combined with the radius calibration of Maximum Mean Discrepancy Distributionally Robust Nonlinear Chance-Constrained Optimization with Finite-Sample Guarantee, this gives an end-to-end finite-sample guarantee that random features alone do not.
The audit strand computes an independent lower bound on the exact worst-case risk for any trained model. In low dimensions we discretize $S$ into a grid and let the adversary choose weights on grid points and training points. Maximizing expected loss subject to the exact-kernel MMD constraint is then a convex quadratically constrained program. This follows the reduction to convex quadratic programs in Worst-Case Risk Quantification under Distributional Ambiguity using Kernel Mean Embedding in Moment Problem. If the audited value exceeds a method's reported certificate, that certificate has been violated, with no approximation on the auditor's side working in the method's favor.
Baselines
The naive reference point is empirical risk minimization (ERM) with the same model, which makes no robustness claim. It shows whether any robust method buys anything under the audited worst case. On WILDS, WILDS: A Benchmark of in-the-Wild Distribution Shifts reports ERM accuracy on Camelyon17 dropping from about 93% in-distribution to about 70% out-of-distribution. We use that only as context for a stretch experiment.
The strongest existing method is Stochastic Functional Gradient DRO from Kernel Distributionally Robust Optimization: Generalized Duality Theorem and Stochastic Approximation (also Kernel Distributionally Robust Optimization). It is the only method in the file that scales MMD DRO to neural networks. It is run with its fixed-$m$ features at $m\in\{64,256,1024,4096\}$, the same radius, and the same optimizer budget as our variants. No reported result was found on Lacuna for it on any benchmark: the uncertain least-squares and MNIST 0/1 comparisons are qualitative only. We will therefore reproduce it rather than quote it.
The exact-kernel reference is the full-Gram dual of Distributionally Robust Optimization and Generalization in Kernel Methods, including its $\|f^2\|_{\sigma/\sqrt2}$ ridge regularizer, run at small $n$ where it is feasible. A second reference is the landmark-subspace dual trained end to end, which is the main simple competitor.
The key ablation varies the certification pipeline while holding training fixed: no inflation, uniform $\eta_m$ inflation, our localized inflation, and landmark certification. A second ablation swaps the Gaussian kernel for Laplacian, Matérn and B-spline kernels at matched bandwidth, isolating the role of spectral tails. All methods share data splits, a fixed wall-clock and tuning budget, and a radius chosen by the same MMD bootstrap.
Beating the strongest baseline has a specific meaning. Our pipeline should achieve zero audited certificate violations at a feature count where fixed-$m$ Stochastic Functional Gradient DRO shows violations. It should also do so with certified values no more than a stated factor above the audited worst case, and nominal loss within the noise of the baseline.
Why not just…?
Why not just use a landmark (Nyström-style) dual for training as well, and skip random features? This is a real threat. Landmark functions lie in the true RKHS, so the restricted dual is automatically a valid, if conservative, bound. The reason to keep random features for training is the one the file gives: they provide a fixed closed-form basis that supports streaming stochastic gradients without storing exemplars. Whether that advantage matters is an empirical question. We run landmark-dual training as a full baseline. If it matches our train-random, certify-landmark pipeline at equal compute, the honest conclusion is to recommend it. The paper's contribution then becomes the diagnosis and the $m(n)$ theory rather than the algorithm.
Why not just increase $m$ until the reported objective stops changing? A plateau in the random-feature value says nothing about the second, optimistic error: the lying-above constraint is enforced only at sampled points. It also cannot reveal how far the random-kernel ball sits from the exact one at a given radius. The audit tests this directly. We plot reported value and audited worst case against $m$ and check whether the reported value plateaus while violations persist. If violations disappear exactly when the plateau appears, this heuristic is adequate and we will say so.
Why not just use Wasserstein or KL-divergence DRO, which avoid kernel approximation entirely? These answer a different question. KL-type neighborhoods only reweight observed points, so they assign zero probability to unseen failure regions. This is the zero-count problem highlighted in Worst-Case Risk Quantification under Distributional Ambiguity using Kernel Mean Embedding in Moment Problem. Wasserstein balls must grow like $n^{-1/d}$ to cover the truth, as discussed in Distributionally Robust Optimization and Generalization in Kernel Methods. Our proposal does not claim MMD DRO beats these methods. It asks whether MMD DRO's advertised guarantee survives its standard scalable implementation, so these methods appear only as context in the chance-constrained experiment.
Proposed Experiments
The decisive experiment is the certificate-violation study on settings where the audit is exact enough to trust. These include the one-dimensional Gaussian ridge regression of Distributionally Robust Optimization and Generalization in Kernel Methods, with $10^4$ points subsampled to $n\in\{50,\dots,2000\}$. They also include the synthetic uncertain least-squares task and the 100-sample one-dimensional tail-risk and Van der Pol settings of Worst-Case Risk Quantification under Distributional Ambiguity using Kernel Mean Embedding in Moment Problem. For each $(n,m,\text{kernel})$ we run 50 random feature draws. We record two quantities: the violation rate, meaning the fraction of runs where the audited exact worst case exceeds the reported certificate, and the conservatism ratio of certificate to audited value.
The theory predicts how violations should behave. Violations should vanish once $m$ crosses a threshold growing with $n$. That threshold should be near-linear in $n$ for the Gaussian kernel and steeper for Laplacian and B-spline kernels. Uniform inflation should eliminate violations but be visibly over-conservative. Fitting the empirical threshold against $n$ on a log-log plot tests the conjectured $\tilde O(n)$ scaling directly against the $n^2$ worst case.
The consequential experiment is the 3-asset portfolio chance-constrained program of Maximum Mean Discrepancy Distributionally Robust Nonlinear Chance-Constrained Optimization with Finite-Sample Guarantee, solved with random features instead of exact Gram matrices. We then measure the realized constraint-violation rate on test distributions drawn from within the exact MMD radius, against the target level. That paper reports only qualitative safety and profit comparisons, so we reproduce its exact-kernel solver as the reference.
The scaling experiment is MNIST digits 0 versus 1 with a two-layer network under projected gradient descent (PGD) attacks, the setting of Kernel Distributionally Robust Optimization: Generalized Duality Theorem and Stochastic Approximation. There the grid audit is replaced by a particle-based adversary that gives a lower bound, so violations can still be proven. Clean accuracy and accuracy under PGD perturbation serve as secondary metrics against ERM and PGD training.
As a stretch, frozen-feature Camelyon17-WILDS tests whether certified radii translate into any out-of-distribution accuracy relative to ERM's reported ~70%. We treat a null result there as informative, not as a failure of the certification question.
The project fails cleanly if fixed-$m$ certificates are never violated at the feature counts practitioners use. In that case the result is a reassurance with a quantified safety margin, which is still worth publishing.
References
- Kernel Distributionally Robust Optimization: Generalized Duality Theorem and Stochastic Approximation
- Optimal Rates for Random Fourier Features
- Injective Hilbert Space Embeddings of Probability Measures
- Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features
- Maximum Mean Discrepancy Distributionally Robust Nonlinear Chance-Constrained Optimization with Finite-Sample Guarantee
- Worst-Case Risk Quantification under Distributional Ambiguity using Kernel Mean Embedding in Moment Problem
- WILDS: A Benchmark of in-the-Wild Distribution Shifts
- Kernel Distributionally Robust Optimization
- Distributionally Robust Optimization and Generalization in Kernel Methods