Stochastic Gradient Methods for Distributionally Robust Optimization with f -divergences
We develop efficient solution methods for a robust empirical risk minimization problem designed to give calibrated confidence intervals on performance and provide optimal tradeoffs between bias and variance. Our methods apply to distributionally robust optimization problems proposed by Ben-Tal et al., which put more weight on observations inducing high loss via a worst-case approach over a non-parametric uncertainty set on the underlying data distribution. Our algorithm solves the resulting minimax problems with nearly the same computational cost of stochastic gradient descent through the use of several carefully designed data structures. For a sample of size n, the per-iteration cost of our method scales as O(log n), which allows us to give optimality certificates that distributionally robust optimization provides at little extra cost compared to empirical risk minimization and stochastic gradient methods.
This paper focuses on solving the robust empirical risk minimization problem, which is in a "min-max" structure and has the ability to automatically trade between loss and variance. Previously this problem is usually solved by using SGD after taking the dual of the inner supremum, however it might not work well because of the unbounded variance of the subgradients.  This paper presents a new solver for the robust empirical risk minimization problem. It is inspired by a mirror descent based method to solve two-player convex games. The solver consists of two alternating mirror descent/ascent steps, one is for minimization and the other one is for maximization. The main difference between this work and previous works is that the authors generalize this method to Cressie-Read family f-divergence constrained cases.   The authors proved regret bounds for different cases of f-divergences in the Cressie-Read family, including important cases like KL divergence and Chi-square divergence. The convergence shown is sublinear, in O(\sqrt T), which match the regret bounds of common stochastic methods. For the special case of Chi-square divergence, the authors uses a trick proposed in [11] to run the projection step in O(log n) time.  The authors also conduct experiments on synthetic and real data, and try to show that the proposed solver is better than SGD and IPM (interior point method) in terms of CPU time and convergence, also the robust solution does provided stability as expected. 
Overall I think the work in this paper is valid and valuable. The first 3 sections are well written. However I think the experiment section looks weak and needs more refinements (see below) before the paper can be published.  In the experiments, the proposed algorithm uses the best step size given in section 3, but for SGD, Armijo's backtracking line search is used. I think this could be a reason why SGD is slower, because line search is slow. The authors should compare the two algorithms both using line search, or both using a fixed *best* step size.  In the introduction section the authors show that stochastic gradient may fail due to the unbounded objective and subgradients. It would be nice to show a dataset that has this problem, and how the two-player bandit mirror descent algorithm can improve that. This will make this paper stronger and more people will pick it up.  Some more explanations and discussions should be added for Figure 2a and 2b, and the legends on some figures can be made better (like in figure 1, "SGD-minmax" can be replaced with "proposed" to avoid confusion with the SGD algorithm being compared). Some missing references (shown as ?) should also be fixed.  In section 4, the texts do not explicitly say which Bregman divergence is used. Following the derivation (in KKT condition) I think it's $\frac{1}{2} \sum_1^n p_i^{2}$. Maybe you can make it more clear in section 4. Also, does this O(log n) trick for solving \lambda work for other Bregman divergences?