Distributionally Robust Optimization via Ball Oracle Acceleration
This work addresses efficient optimization in robust machine learning for scenarios with distributional uncertainty, representing an incremental improvement in algorithmic complexity.
The paper tackles distributionally robust optimization (DRO) for convex losses with group-structured and bounded f-divergence uncertainty sets by developing algorithms that use an accelerated ball optimization oracle, achieving an ε-accurate solution with Õ(Nε^{-2/3} + ε^{-2}) first-order oracle queries and improving complexity by up to a factor of ε^{-4/3} compared to existing methods.
We develop and analyze algorithms for distributionally robust optimization (DRO) of convex losses. In particular, we consider group-structured and bounded $f$-divergence uncertainty sets. Our approach relies on an accelerated method that queries a ball optimization oracle, i.e., a subroutine that minimizes the objective within a small ball around the query point. Our main contribution is efficient implementations of this oracle for DRO objectives. For DRO with $N$ non-smooth loss functions, the resulting algorithms find an $ε$-accurate solution with $\widetilde{O}\left(Nε^{-2/3} + ε^{-2}\right)$ first-order oracle queries to individual loss functions. Compared to existing algorithms for this problem, we improve complexity by a factor of up to $ε^{-4/3}$.