Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper propose an online algorithm to solve a class of Distributionally Robust Optimization problem with non-convex objective functions. The standard primal-dual method typically suffer from optimization over high dimensional variable, which is impractical in many real world applications. The sota complexity of proposed method is provided with and without the PL condition. Empirical experiments demonstrate the superiority of the proposed algorithm.
main_review: This paper is in general well written, the complexity analyses and numerical experiments are seems to be promising. I only have some comments related to the model.

1. The problem studied in this paper seems to be slightly different from the standard literature. For example, the problem in [1] aims to maximize probability distribution p over a KL-ball center at the empirical distribution, while the problem in this paper maximize p over probability simplex. As a result, the \lambda in eq(2) is a fixed parameter, while in [1] we still need to optimize over \lambda. So, intuitively, the problem in this paper should be easier to solve compare to standard KL-based DRO problem. From the modeling prospective, the model in this paper is less informative if we want to understand the relationship between regularization parameter \lambda and the level of distributional robustness. 

2. Have the authors thought about generalizing the current framework to Wasserstein-based DRO (where the inner maximization typically do not have a closed form representation)? What would be the main challenges for doing so? 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the family of distributionally robust optimization (DRO) problems with non-convex objectives and KL-divergence. With the motivation of improving the computational efficiency on existing methods and applying to online settings, the authors proposed a new duality-free online stochastic methods for solving the considered DRO problem. Theoretical analyses on complexities are provided for the proposed algorithm with and without a PL condition. Comparisons with state-of-the-art DRO methods are presented over ERM on imbalanced datasets.
main_review: The paper has a clear motivation of improving the complexities of existing DRO methods from a theoretical perspective. Comparisons are summarized clearly in Table 1 in the related work section. The structure of the paper is generally easy to follow, though many parameters and variables are defined to simplify the arguments. I appreciate that the authors lay out the list of required assumptions in Section 3. Overall, I think this paper is written with good quality and has theoretical contributions to the field of DRO. 

One question I have for the paper is regarding the algorithmic design of COVER in Section 4. I have a hard time understand why the update rules of u and v designed in line 7 of Algorithm 1 lead to a better convergence result, compared with existing state-of-the-art methods for DRO. Can you briefly discuss the motivations for this algorithmic design?

Moreover, I think the notations introduced in this paper seem to be a little bit complicated. It would be better to include a table to summarize the core parameters. Other suggestions regarding the paper are listed below:

1.	It would be better to introduce some specific examples of typical DRO problems, apart from the general framework. This will help readers better understand the assumptions and the user cases for the proposed framework.

2.	As for the experiments, is there any reason why you only focus on the imbalanced datasets? It would be great if you can provide empirical studies on other types of DRO problems, such as noisy data and adversarial data. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work proposes a practical online optimization method COVER and RECOVER for solving DRO with f-divergence, see eq(1).  They propose an online algorithm (RECOVER) for solving a more general formulation, by recasting the formulation into a composition minimization problem via fully exploiting the hidden structure. Moreover, they present the convergence result for the proposed method under the PL condition. Finally, the authors conduct experiments for several deep learning problems.
main_review: 

In this paper, the authors consider an online method for distributionally robust optimization, which gets rid of the difficulty of high dimensional dual variable, which is usually used in the primal-dual type methods. The paper is overall well written and easy to follow. The main concerns raised by the reviewer are listed as follows:


1. The title misleads the contents of the paper. The paper shows a particular regularized version of distributionally robust optimization (DRO) with f-divergence--which is not the general DRO problem, and develops a online method for this. Although the studied problem (the author claimed) is a generalization of the DRO problem, it seems that the problem eq(1) in this paper is a relaxed/ regularized form, which may sacrifice the advantages of DRO’s modeling power. Actually, the algorithm scheme developed in this paper doesn't actually really tackle DRO in the constrained case (i.e. when one constrains $D_{KL}(P||P_0) \leq \delta$, rather than a regularization-based formulation), which is the hard case and the case that most researchers in DRO actually consider.

In details, I think the paper [11] cannot support your claim. It shows that the DRO formulation is equivalent to a variance-based regularization form in an asymptotic sense. Compared to the formulation (1) in Namkoong & Duchi, 2016, the considered formulation in eq (1) penalizes the divergence measure into the objective function and adds a convex regularizer. Then, are these two formulations equivalent? We can only obtain the equivalence result under certain conditions, see the reference [1, section 4] for details. 

[1] Friedlander M P, Tseng P. Exact regularization of convex programs[J]. SIAM Journal on Optimization, 2008, 18(4): 1326-1350.

2. The author claims that the proposed method can be applied to eq(3) with a non-smooth regularizer, the theoretical analysis using the PL conditions requires the regularization term to be smooth. In Assumption 3, the gradient notion has been invoked in the PL inequality. Could you please elaborate the details how your analysis can be trivially extended to non-smooth problems? 

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: A new two sequence distributionally robust optimization algorithm and some modifications presented for a class of KL divergence regularized problems.

main_review: 
Strength: + Online algorithm to solve compositional optimization problem in the context of deep learning.
+ Does not require to store the high dimensional variable p.

Weakness: - Writing can be improved quite a bit, and is some times unclear how exactly reformulations are defined or derived. 


Justification: The overall idea is that the inner maximization problem, under some technical assumptions, can be solved in closed form. The paper mentions this but does not provide. This part of the paper is not fully clear -- -- the optimal solution of the inner maximization problem depends on w, and so it is not clear how we obtain F_dro from (1). In particular, it is not clear how r(w) changes from (1) to (2). I believe it is correct, essentially it follows from convex duality but there is no justification given in the paper.


It is very interesting to see that simple estimators such as the one proposed where they maintain two sequences to compute the gradient of the composite optimization problem can provide optimal convergence for the overall optimization problem. And moreover, the paper also shows how to exploit smooth in terms of PL condition to match the practical deep network instantiations of the training algorithm.

Experiments: The paper has fairly detailed experiments on a well studied classification task. The paper considers several other first order methods, and compares with some standard datasets including imbalanced datasets. The hyperparameters settings are described well and the algorithm may be implemented on standard deep learning frameworks by a practitioner from the description given in the paper. However, the experiments presented have nothing in connection with the theory presented. For example, the theoretical justifications presented are for the (expected) gradient norm and objective function values, whereas the experiments presented show convergence in test error. In this sense, in fact, (i) there are no experiments presented from an optimization perspective to valid the algorithm presented; (ii) even from the machine learning (generalization) perspective in the deep network context, the paper shows no experiments or even attempt to address some of the dependency relationship between the loss landscape and convergence, see https://papers.nips.cc/paper/2019/file/95e1533eb1b20a97777749fb94fdb944-Paper.pdf for example.




limitations_and_societal_impact: Have addressed them appropriately.
review_title: null

Meta-review: Although there is some concern about how to best compare this work with prior efforts on robust optimization, overall it seems there are some interesting ideas and a new contribution presented that provides a more efficient alternative to standard distributionally robust methods.
Decision: Accept (Poster)