Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes efficient algorithms for distributionally robust optimization (DRO). The objective in DRO is to minimize the worst case expected loss over a family of distributions over the population. A simple example of this problem is group DRO, where we have $N$ separate loss functions, and $m$ distributions, where each distribution assigns a weight to each of the loss functions; the objective in this case becomes to minimize the maximum over m weighted linear combinations of the loss functions.
A more challenging setting is DRO with $f$-divergence, where the family of distributions is all distributions that are close to some fixed distribution where the distance between distributions is measured by a divergence.

Assuming that each of the loss functions is Lipschitz, and that the domain has bounded diameter, the authors present an algorithm for group DRO / f-divergence DRO that can compute a point that achieves a loss at most $\epsilon$ larger than the minimum possible in roughly $N\epsilon^{-2/3} + \epsilon^{-2}$ gradient evaluations of individual loss functions. Directly applying previously known algorithms results in a bound of $N\epsilon^{-2}$ gradient evaluations.

The approach is similar to [11], and designs a "ball-optimization oracle" for regularized versions of the problems, in order to be able to apply accelerated optimization algorithm from [9]. This paper establishes the ball optimization oracle by using SGD and building unbiased gradient estimators for the the group DRO and a regularized version of $f$-divergence DRO.

[9] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y. T. Lee, A. Sidford, and K. Tian. Acceleration with a ball optimization oracle. In Advances in Neural Information Processing Systems (NeurIPS), 2020.

[11] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In Conference on Learning Theory (COLT), 2021.
strengths_and_weaknesses: **Strengths**:
- DRO is a well-studied problem from robust optimization. It is somewhat surprising that the authors are able to obtain essentially the same running time complexity as SGD for small $N,$ and the same as in the case of minimizing the maximum of $N$ loss functions
- The bound on gradient evaluations achieved by this paper matches known lower bounds even in the case of minimizing the maximum over $N$ distinct loss functions. Thus, in some parameter regimes, the presented algorithm is essentially optimal.

**Weaknesses**:
- The approach is a somewhat too similar to [11]. The main difference is the construction of gradient estimators. The estimator for group DRO is pretty straightforward.
- Even the main body of the paper is very very notation heavy, and it is difficult to parse at many places to discern the key technical ideas
questions: My main suggestion would be to work at making the key ideas in the paper more accessible. The paper gets really terse and difficult to follow a few pages in. 
As a concrete suggestion, shorter theorem statements highlight the most significant parts of the results would be helpful.
limitations: As the authors already identify and suggest, it seems likely that these bounds should extend to the case of arbitrary subsets of the simplex, but the current algorithms depend highly on the structure of the DRO problems. Obtaining such an extension would be quite impressive.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes accelerated algorithms for distributionally-robust optimization based on group-structured and bounded f-divergence sets uncertainty. The algorithm uses ball oracle technique, a multi-level monte-carlo technique and exploits specific structures associated with these uncertainty sets. These ingredients lead to improved convergence guarantees both in terms of accuracy of the iterate and the number of iterations. 

strengths_and_weaknesses: -- Strength 

Nice mixture of existing ideas for uncertainty sets are practically applicable. Further, results are improved for smooth, Lipschitz functions. 

-- Weakness:
- The results are tailored to very specific uncertainty sets. The other ingredients or their combination doesn't seem to be new. 
- Lack of numerical experiments to validate. This is crucial especially for this paper since the claims themselves are about reducing computation relative to state-of-the-art! 
questions: --
Can this be extended for Wasserstein metric which is prevalent in a lot of ML literature? 
limitations: --
Lack of numerical experiments demonstrating that the algorithm works.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposed new algorithms for two formulations of DRO, i.e. group DRO and f-divergence DRO. The new algorithms achieve better regret bound than existing ones. The key idea is to implement ball optimization oracle and plug it into state of the art optimization algorithms to solve DRO efficiently.
strengths_and_weaknesses: Strengths are the solid analyses and improved convergence rate. The weaknesses are that these algorithms are purely theoretical and not tested in practice as mentioned by authors. Also the presentation of the paper could be improved as currently there is too much content filled in the main paper. 


questions: I think this is a solid paper, I do not have much questions. One suggestion is to move less important content into Appendix and add more discussions in the main paper.
limitations: Limitations are well-discussed.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper deals with distributionally robust optimization, in two specific settings : group DRO and f-divergence DRO. Distributionally robust optimization can minimizes a supremum over distributions in a set of test distributions, which is finite in the case of group DRO and a ball of finite radius for a certain similarity measure in the case of f-divergence DRO. This supremum makes the optimization harder : one cannot readily apply available techniques for minimisation of convex losses.

The contributions of the paper are : 

1. To present methods to compute ball oracles in a fast way in both cases for potentially non smooth function
2. To present methods to compute ball oracles in an accelerated way when dealing with a certain degree of smoothness
3. To use these ball oracles to design an optimization with low complexity in terms of gradient evaluations, relying on a MLMC methods.
Point 1 and 2 are crucially involve the introduction of a way of computing a gradient estimator which differs from previous work (and which also relies one a MLMC method).
strengths_and_weaknesses: For me, the methods are in general not new even if the gradient estimate seems new. 

I believe the related works are adequately cited for the technical part, and it is pretty clear the this work is essentially an application of a set of technique (MLMC + BROO optimization) to the problem of DRO (even if that application calls for the introduction of some “new” machinery”)

I believe the work on DRO could be more cited, in particular the more applicable work, as this work does not contain any sort of simulation.

    * Quality: 

I did not read the entire proofs but a large part of them, and they are correct. 

For me, while these theoretical results are interesting, as the lower bounds are known, the goal is to reach them with an implementable algorithm (at least in a conference like NeurIPS). The complete lack of experiments is disturbing, especially as the proposed methods seem to have a very high constant hidden. 

Moreover, the papers on which this relies are also of a theoretical nature, and very few experiments convince me of the quality of the method. While this drawback is underlined in the paper, I believe it to be a very crucial lack of the MCML methods. 



    * Clarity:

In terms of organisation, the paper is clear

In terms of claims, I believe the references are not clear enough : algorithm 1 mentioned in the main paper has to be found manually, and no detail is given about it. Also, the bounds involve many complex terms. I believe that part of this complexity should be moved to the appendix, to better present the results (as this paper is completely concentrated in the appendices in any case), especially for part 2. 


Technically, the paper is involved for a novice in the field, and cannot be followed easily without looking into the references. I believe doing sketches of proofs or algorithm in a more self contained way (for example the lambda bisection is completely skipped) would help understanding. 



    * Significance:

Without any kind of applications, even on toy problems, it is very hard for me to evaluate the significance of the results. For me, for NeurIPS, the lack of ANY kind of non-theoretical work is disturbing. 
questions: - Can you provide any kind of experiment ? case where BROO has been use even in a non DRO setting
- Could you provide more information about working (or non-working) DRO techniques
- NB : the fact that regularisation transforms the dual to a smooth thing is not new at all (see Nesterov books for instance)

limitations: For me, the clear limitation is the apparent complexity of the algorithms (there are a lot of logarithmic bricks but which add up) and no experiment to support their applicability.
review_title: null

Meta-review: metareview: The paper provides new complexity guarantees for distributionally robust optimization (DRO) in two main settings: (i) when the ambiguity set is discrete and consists of a finite number of possible distributions (group DRO) and (ii) when the ambiguity set is based on f-divergence. The algorithmic techniques build on the recent results on ball oracle acceleration by Carmon et al., (2021). The key technical contribution is building a novel unbiased gradient oracle estimator and combining it with SGD & ball oracle acceleration to obtain tight gradient oracle complexity guarantees. The same results cannot be recovered by simply applying existing algorithms. The improvement over existing algorithms in terms of the gradient oracle complexity is reducing it from $N/\epsilon^2$ to $N/\epsilon^{2/3} + 1/\epsilon^2$. The obtained improvements seem to be primarily of theoretical interest at this point, as they require an exact minimizer over a ball of a given radius (i.e., an exact ball oracle); however, this contribution is within the scope of the conference. While numerical experiments are not   a requirement for NeurIPS papers, if the authors do decide to add them, they are advised to ensure that any comparison to other algorithms they make is a fair apple-to-apple comparison. The paper would also benefit from being made more accessible to novice readers who may not be familiar with prior closely related results on ball oracle acceleration. 
confidence: Certain
Decision: Accept