Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond

Area of Science:

• Machine Learning
• Optimization Theory
• Robust Statistics

Background:

• Group distributionally robust optimization (GDRO) aims to develop models with strong performance across diverse data distributions.
• Existing methods often require a high number of samples per iteration, limiting practical application.
• Handling heterogeneous distributions with outliers presents a significant challenge in robust optimization.

Purpose of the Study:

• To develop efficient algorithms for group distributionally robust optimization (GDRO) with improved sample complexity.
• To extend GDRO to effectively address heterogeneous distributions containing outliers.
• To introduce anytime algorithms that can provide solutions at any iteration.

Main Methods:

• Formulating GDRO as a stochastic convex-concave saddle-point problem solved by stochastic mirror descent (SMD).
• Casting GDRO as a two-player game to reduce sample requirements from m to 1 per iteration.
• Extending GDRO to optimize average top-k risk for outlier mitigation, using SMD and online bandit algorithms.

Main Results:

• Achieved nearly optimal sample complexity for vanilla GDRO using SMD with m samples per iteration.
• Developed a novel approach reducing sample complexity to 1 per iteration while maintaining performance.
• Proposed and analyzed methods for optimizing top-k risk in heterogeneous distributions, with two distinct algorithmic approaches.

Conclusions:

• The proposed GDRO methods offer significant improvements in sample efficiency for learning across multiple distributions.
• The novel top-k risk optimization effectively mitigates the impact of outlier distributions.
• Anytime versions of the algorithms provide flexibility, allowing solutions to be obtained at any point during computation.