CS Paper Radar

Learning the Robustness Mechanism with Bilevel Optimization

Yiyang Shen, Qihang Lin, Weiran Wang

cs.LG ·submitted 2026-09-28 16:20 UTC · v1

Abstract

We propose a distributionally robust learning framework where parameters defining the robustness mechanism are learned from held-out data instead of extensively tuned. Using bilevel optimization with both upper and lower level minimax problems, we create two instances of our framework to tackle setups with and without group labels in the training set. Theoretically, we provide sample complexity analysis for our robustness mechanism learning paradigm, showing that it achieves generalization guarantees comparable to exhaustive grid search while being more computationally efficient. Empirically, we evaluate our framework under a challenging setup when both intra-group and inter-group test distribution shifts occur at the same time, thereby demonstrating the efficacy and scalability of our method.

Closest papers

Nearest neighbours by meaning across the whole index.

Generative Neural Networks for Sinkhorn Distributionally Robust Hypothesis Testing

cs.LG stat.MLmath.OC ·2026-08-24 ·Fenglin Zhang, Teyan Liu, Jie Wang
theory similarity 0.62
Abstract · 41 Pages, 7 figures

This paper studies the Sinkhorn distributionally robust hypothesis testing (SDRHT) problem, seeking a robust detector against least-favorable distributions in Sinkhorn discrepancy-based ambiguity sets centered at the empirical distributions. Existing approaches solve this problem by solving large-scale conic programs, which are not scalable. To overcome this, we propose a generative framework that learns least-favorable distributions and supports efficient training and end-to-end sampling. For the Sinkhorn discrepancy-based ambiguity sets, we first derive an equivalent conditional-KL-divergence representation with respect to kernel-smoothed reference distributions. This property allows us to prove strong duality for both constrained and unconstrained minimax SDRHT formulations. Based on the closed-form optimal detector and Brenier's theorem, we reformulate the max-min dual formulation as a maximization problem over convex potentials whose gradients characterize invertible transport maps between kernel-smoothed distributions and their least-favorable counterparts. We efficiently approximate these potentials using Hyper Input Convex Neural Networks (HyCNNs) equipped with stochastic gradient estimators and prove the representation power of HyCNNs and the distributional universality of their induced transport maps. Numerical results show that the proposed method achieves superior accuracy and robustness across different sample sizes and dimensions, while avoiding the scalability limitations of classical SDRHT methods.

0.16

Statistical Properties of Robust Learning under Distributional Shifts

cs.LG stat.ML ·2026-08-13 ·Zhiyi Li, Xiaojie Mao, Yunbei Xu, Ruohan Zhan
similarity 0.61
Abstract

Distributional shifts arise when the target deployment environment differs from the source environment that generated the training data. Robust learning frameworks such as Distributionally Robust Optimization (DRO) and Robust Satisficing (RS) aim to address this challenge, yet their finite-sample guarantees under such shifts, and their systematic comparison, remain underexplored: existing analyses typically establish guarantees either in the source environment or for adversarial worst-case performance over an ambiguity set. This paper instead studies generalization error in the target environment---the excess loss under the shifted target distribution. Our contributions are threefold. First, we derive finite-sample generalization error bounds in the shifted target environment for both DRO and RS. These bounds explicitly characterize the trade-off between reduced sensitivity to shift and the regularization penalty induced by each method's robustness hyperparameter, and they avoid the curse of dimensionality associated with Wasserstein empirical concentration. Second, when partial shift information such as shift magnitude or direction is available, we propose information-directed hyperparameter calibrations and compare the two methods given the same information. Under these calibrations, and in the partial-information regimes we study, DRO and RS exhibit complementary theoretical and empirical behavior. Finally, we apply the framework to a network lot-sizing problem, using it to interpret how robust policies respond to positive shifts in the demand distribution. Together, these results fill a gap in understanding the statistical properties of robust learning methods under distributional shifts and provide a principled basis for comparing DRO and RS.

0.04

Robust Satisficing Ensemble: Scalable Model Aggregation Under Distribution Shifts

cs.LG cs.AIstat.ML ·2026-11-07 ·Ahmet Faruk Cetinkaya, Enes Agirman, Cem Tekin
top venuetheory similarity 0.61
Abstract · Accepted at NeurIPS 2026 (Spotlight)

Standard ensemble methods can improve robustness by mitigating individual model stochasticity, but they frequently fail to generalize beyond the training distribution, leaving systems vulnerable to out-of-distribution (OOD) data. We introduce the Robust Satisficing Ensemble (RSE), a scalable probabilistic aggregation framework designed to secure model combinations by minimizing their fragility against distributional changes. By bridging a robust satisficing objective with a quadratic risk surrogate, RSE derives an analytical inner adversary. This fundamental reformulation enables highly efficient weight updates without the computational bottleneck of standard minimax optimization, crucially decoupling optimization complexity from sample size to scale effectively to large datasets. In particular, we prove a geometrically decaying truncation error for the fragility approximation via Lagrange-Burmann expansion and establish stationarity guarantees for RSE. We evaluate RSE across a comprehensive spectrum of distribution shifts, including adversarial label shift (SST-5, TREC), natural subpopulation and temporal shifts (CivilComments, HuffPost). Our results demonstrate that RSE consistently outperforms strong robust baselines, including GroupDRO, IRM, and SRM. These findings establish RSE as a practical, theoretically grounded safeguard for reliable model aggregation in dynamic environments.

0.43

Efficient Robust Learning at the Information-Theoretic Limit

cs.DS cs.LGstat.ML ·2026-09-15 ·Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan
similarity 0.60
Abstract · Corrected the arXiv abstract to match the pdf

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of $η+ \varepsilon$ where $η$ is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than $2η+ \varepsilon$. Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). Here we resolve this problem and give such an algorithm. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits low-degree polynomial approximators with respect to hypercontractive distributions. This captures basic settings including halfspaces with respect to Gaussian marginals. Our techniques make new connections to various types of online convex optimization algorithms. As a surprising consequence, we show that efficient SQ learnability in the agnostic setting implies efficient learning with contamination (with respect to Gaussians or uniform over the hypercube).

0.19

Multiaccuracy as an Error Benchmark for Learning with Distribution Shift

cs.LG cs.DS ·2026-11-15 ·Konstantinos Stavropoulos
benchmarkposition similarity 0.60
Abstract

Agnostic learning has a well-developed theory of computational and statistical complexity. For learning with distribution shift, even the choice of an appropriate error benchmark remains challenging. Testable learning with distribution shift (TDS) was introduced to develop computational foundations for this setting: using labeled training data and unlabeled test data, the learner must either produce a predictor with low test error or detect distribution shift. However, standard agnostic TDS guarantees allow a constant-factor amplification of the optimum error even when the training and test distributions coincide. They therefore do not directly recover the guarantee of classical agnostic learning. We introduce shift multiaccuracy, a stronger error benchmark inspired by multiaccuracy from algorithmic fairness. This yields a TDS formulation that becomes equivalent to multiaccuracy when there is no shift. Using a recent nontrivial reduction from agnostic learning to multiaccurate prediction from prior work, we obtain the first TDS framework that formally generalizes agnostic learning through an efficient reduction preserving the training marginal. The framework retains existing algorithmic upper bounds and inherits computational lower bounds from agnostic learning. Moreover, we establish a direct connection between our model and identity testing, yielding the first statistical characterization of agnostic TDS learning, in terms of Rademacher complexity. More broadly, we argue that shift multiaccuracy might be of independent interest in unsupervised domain adaptation, as it leads to sharper out-of-distribution generalization guarantees, and can be minimized directly, since its definition does not involve the unobserved test labels.

0.15

A Unified Perspective on Conformal Prediction and Wasserstein Distributionally Robust Optimization for Uncertainty Quantification

cs.LG math.OCeess.SY ·2026-08-30 ·Kehan Long, Yiqi Zhao, Pol Mestres, Lars Lindemann, Nikolay Atanasov +1 more
similarity 0.60
Abstract

Uncertainty quantification from finite data is central to machine learning, optimization, and automation systems, where decisions must remain reliable under limited samples and test-time distribution shift. Conformal prediction (CP) and distributionally robust optimization (DRO) offer two complementary approaches: CP constructs data-dependent prediction sets with distribution-free finite-sample validity under exchangeability, while DRO optimizes worst-case performance over an ambiguity set around an empirical distribution. We develop a unified probabilistic perspective on CP and DRO by viewing both as ways to turn finite calibration data into a data-dependent quantile estimator that a test score falls below with high probability. From this perspective, CP and DRO correct the empirical quantile along two coordinates of the same family of estimators: CP inflates the quantile level, whereas DRO shifts the quantile value through an ambiguity radius. Both methods provide the same calibration-conditional guarantee for the true distribution, requiring the target coverage to hold with high probability over the calibration sample. Their constructions differ, however: CP uses a closed-form, distribution-free level correction, while DRO uses a value-space correction whose certified radius depends on properties of the unknown distribution and additionally guarantees coverage uniformly over the ambiguity set. This distinction emerges in the tails of the score distribution. Because CP relies on sparse upper-tail order statistics of the calibration samples, its level inflation barely moves the estimator when those samples are dense near the target quantile but overshoots when they are sparse, whereas a well-chosen DRO radius corrects in value space and may avoid this overshoot.

0.30

TPO: Tri-level Distributionally Robust Learning for OOD Direct Preference Optimization

cs.LG cs.AI ·2026-10-20 ·Chengtao Jian, Kai Yang
top venue similarity 0.59
Abstract · Accepted at NeurIPS 2026

Direct Preference Optimization (DPO) minimizes empirical risk over observed preference comparisons, implicitly assuming that the training preference distribution matches the deployment preference distribution. In practice, this distributional assumption often fails, as preference distribution shifts can arise at three levels: group-level shift, prompt-level shift, and preference-level shift. Such multi-level distributional mismatch poses a critical challenge for safe LLM deployment, yet existing robust DPO methods typically either model uncertainty over the joint preference distribution or focus on individual sources of shift, leaving the hierarchical structure of OOD preference shifts underexplored. We propose TPO, a tri-level distributionally robust framework for OOD preference alignment, which jointly models all three levels of distributional uncertainty through a hierarchically structured rectangular ambiguity set. By instantiating it with Wasserstein distance, we derive a tractable and interpretable objective that combines a preference-level margin penalty, prompt-level adversarial embedding perturbation, and worst-case group reweighting, each governed by an independent radius. We establish finite-sample convergence guarantees and empirically validate the effectiveness of TPO across diverse OOD environments.

0.33

Communication-Efficient Distributionally Robust Federated Averaging with Multi-Source Data

cs.LG math.OC ·2026-11-15 ·Yingzhu Liu, Zhongkui Li, Pengcheng You, Ashish Cherukuri
similarity 0.58
Abstract

Federated learning trains a shared model from distributed client data. The deployment risk is typically specified through two approximations: each unknown local distribution is replaced by its empirical distribution, and the unknown deployment mixture across clients is replaced by empirical or prescribed training weights. Existing robust methods usually address one approximation at a time through local distributional ambiguity sets or worst-case client mixtures. However, joint treatment of both approximations remains underexplored. To address this gap, we construct a global ambiguity set formed by admissible mixtures of client-wise Wasserstein ambiguity sets, yielding a distributionally robust optimization formulation. The construction allows client-dependent ambiguity radii, preserves client-wise separability of the objective function, and yields a high-probability out-of-sample guarantee for the resulting robust problem. We then introduce a penalty-based approximation of this formulation and develop a communication-efficient algorithm called BiDRO-FedAvg, for which we establish a convergence guarantee. We validate the proposed framework through a market-demand prediction simulation.

0.12