Research map / Learning theory and algorithms / Sample complexity

Group Distributionally Robust Optimization with Flexible Sample Queries

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of ranking and selection · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes GDRO with flexible per-round sample queries by casting it as a two-player game, with an FTRL-based GDRO learner and a new non-oblivious prediction-with-limited-advice algorithm (hybrid and unified variants) that yields an anytime optimization error bound of O((1/t)sqrt(sum m/r_j log m)).

Problem

Group distributionally robust optimization (GDRO) is usually solved with a fixed number of samples per round (1 or m), which cannot handle varying or resource-limited sample budgets and converges slowly with 1 sample per round.

Approach

Cast GDRO as a two-player game where the w-player runs FTRL on stochastic gradients and the q-player solves a non-oblivious prediction-with-limited-advice problem; the q-player combines Exp3-IX (r_t=1) and PrLiA-style unbiased estimators (r_t>=2) into one FTRL update, giving a high-probability regret bound that improves the optimization error by a log t factor over prior anytime SMD methods.

Key results

• Under dynamic sample sizes r_t in [1, m-1], HYB and UNI reduce max risk faster than Online(1) per iteration and per unit of running time, and are comparable to Online(1)'.
• The paper proves a high-probability optimization error O((1/t) sqrt(sum_j m/r_j log m)), which for fixed r gives O(sqrt(m log m/(rt))), improving the O(log t) factor of prior anytime SMD bounds by O(log t).
• Time-uniform bound adds only an O(sqrt(log log t)) cost rather than O(sqrt(log t)) from union bounds.

Surprising findings

• Online(1)' (performing r_t sequential single-sample updates) converges slower than Online(1) despite identical per-update cost, attributed to lacking a principled step-size schedule.

Limitations

• Experiments are limited to a synthetic linear setting and one real tabular dataset with m=12 groups.
• Theoretical results assume bounded losses, bounded gradients, and convexity of each risk function.

Experimental setup

Datasets: synthetic binary dataset diabetes readmission dataset (UCI)

Benchmarks: synthetic binary dataset diabetes readmission dataset

Metrics: maximum risk running time number of iterations

Baselines: SMD(m) Online(1) Online(1)' HYB UNI

Builds on: Exp3-IX PrLiA Exp3 DepRound ghost iterate

Closest papers by meaning

• Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity (ICML 2025 · similarity 0.92)
• Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond (ICML 2024 · similarity 0.91)
• MixMax: Distributional Robustness in Function Space via Optimal Data Mixtures (ICLR 2025 · similarity 0.88)
• Communication-Efficient Federated Group Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.87)
• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization (ICML 2025 · similarity 0.86)