Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to develop new stochastic algorithms for solving the popular KL-divergence-constrained distributionally robust optimization (DRO) problem for both non-convex and convex losses. The proposed method, SCDRO or its variants, establishes (near-)optimal oracle complexities for both convex and non-convex losses. Furthermore, the said complexities are independent of per-iterate sample and batch sizes. Empirical studies further validate the effectiveness of SCDRO variants.
strength_and_weaknesses: Strength

I find this paper interesting and well-written. To me, the methodology behind SCDRO is highly innovative in deriving a primal-only formulation linked with existing compositional optimization works. The developed theory for SCDOR was designed for non-convex loss functions and further extended to convex loss functions, enjoying optimal complexities for finding $\epsilon$-accurate solutions for both convex ($O(1/\epsilon^2)$) and non-convex ($\tilde{O}(1/\epsilon^3)$) smooth loss functions $\ell_i(\mathbf{w})$. Both of these complexities are first in literature in the given settings.


Weaknesses

On pp. 3 ending part, the authors essentially indicate that DRO with KL divergence regularization enjoys shown superior performance for distributional shift. End of pp. 1, "They are either restricted to problems with no additional constraints on the dual variable p except for the simplex constraint (Qi et al., 2021; Jin et al., 2021), ..." On pp. 13 middle part the authors indicate that Qi et al. (2021) firstly cast the KL-regularized DRO problems into stochastic compositional optimization. They also indicate the difference with this work that they "solve KL-constrained DRO problems, which is more challenging than KL-regularized DRO problems."

As indicated in the paper, the hardness of their analyses lies on the non-smoothness of $F(\mathbf{x})$ and the non-Lipschitzness of outer function in the given unbounded regime, which breaks the assumptions of stochastic compositional optimization theory, hindering the achievement of optimal complexities for both convex and non-convex loss functions. I am wondering if the said challenge bring essential new difficulties for this change? From the perspectives of Lagrangian's multiplier these two formulations are essentially the same. Can the authors bring more details on this comparison?


Minor comments:

Page 2, middle part, the authors said $f$ being "monotone" which can confuse readers since this work does not involve variational inequalities.

Page 13, middle part, "(i) we do not need to maintain and update ... (i) we do not need to worry ... " the second (i) should be (ii).
clarity,_quality,_novelty_and_reproducibility: I praise the authors for good clarity and quality of this work. The SCDRO framework is innovative but I am concerned on the technical novelty on the relationship with earlier works, including Qi et al. (2021).
summary_of_the_review: As indicated above, this work enjoys strength of good clarity and quality but suffer from potential weakness of limited technical novelty. My rating is based on this, barring further rebuttals and revisions from the authors.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors study the problem of constrained DRO, and proposed a dual-free algorithm for solving the robust optimization problem, and hence the per-iteration complexity is independent of the sample size. 
strength_and_weaknesses: The algorithm for solving the constrained DRO doesn't use dual information and hence enjoys per-iteration complexity O(d). The algorithm also enjoys relatively good iteration complexiy. One drawback in the experiment is that, the per-iteration complexiy is the main improvement from this algorithm, but there is no running time comparison which would be more interesting. Also in Assumption 1 the smoothness assumption on $l$ is pretty strong.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and clear. The results are new to the reviewer though I'm not an expert in this field.
summary_of_the_review: The paper is well motivated and thoroughly discussed related literatures. The authors have made concrete contributions, especially developed a dual-free algorithm for the constrained DRO, which can be much cheaper to run especially in modern ML high dimensional regime. Although there are a few points that the paper can improve on, e.g. defining $F$ earlier in the paper to cause less confusion, and discuss about the total running time when $d$ is large in the experiment. I think the paper is still a good contribution to ML community and I would like to suggest accepting this paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes and analyzes stochastic algorithms that apply to solve a specific distributional robust optimization problem. This problem, Eq. (1), is not a general formulation solved by the existing methods. The uncertainty set of Eq. (1) must be a KL-ball, and the KL constraint in Eq. (1) seems to be too deliberate. With the help of the particular form, the proposed method shows a better complexity independent of the sample size for convex and non-convex settings. 
strength_and_weaknesses: * **Strength**
  - This paper is well-written and easy to follow.

* **Weakness**
  - This method is only applicable to solving problems with a particular form.  
  - The KL regularization on $\boldsymbol{p}$ is not a common regular term. Eq. (1) is not a generic objective function but a deliberate one. 
  - Computational complexity of the proposed method is not well portrayed in the experimental studies.  
clarity,_quality,_novelty_and_reproducibility: * **Clarity**
  - This paper is well-written and easy to follow.

* **Quality**
  -  It fails to meet the requirements of ICLR. 

* **Novelty**
  - The novelty is limited as the objective is too specific. 

* **Reproducibility**
  - The study reported in sufficient detail to allow for its reproducibility.
summary_of_the_review: This target problem, Eq. (1), is not a general formulation solved by the existing methods. The uncertainty set of Eq. (1) must be a KL-ball. The KL regularization on $\boldsymbol{p}$ is not a common regular term. Eq. (1) is not a generic objective function but a deliberate one. 
Consequently, the reviewer suggests "marginally below the acceptance threshold" as the recommendation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes new stochastic algorithms to solve both nonconvex and convex KL divergence constrained Distributionally Robust Optimization (DRO) problems. The proposed methods are dual-free, which means the per-iteration computational complexity is independent of sample size. By utilizing the recursive variance-reduced technique and stagewise step size scheme, optimal convergence rates are also established in both nonconvex and convex cases. Empirical results demonstrate both the effectiveness of the proposed methods and the privilege of the underlying model.
strength_and_weaknesses: Strength:
Overall, the paper is clear and well-organized. This work proposes four efficient dual-free algorithms to solve nonconvex and convex KL divergence constrained DRO problems. Optimal convergence rates are also established in both nonconvex and convex cases. The proposed ASCDRO and BASCDRO methods are the first optimal dual-free algorithms for the KL divergence constrained DRO problem.

Weakness:
1. It seems that there are both a Kullback-Leibler (KL) divergence constraint and a KL penalty. Is there a particular reason for doing this?

2. The author claims primal-dual algorithms require maintaining and updating an O(n) dimensional vector for updating the dual variable. But I believe some stochastic primal-dual methods can take coordinate steps on the dual side and have per-iteration complexity O(d). Please correct me if I am wrong.

3. In the convex part of Table 1, The complexity of Dual SGM is the same as the proposed method. Could the author discuss the advantage of their method compared to Dual SGM?

clarity,_quality,_novelty_and_reproducibility: Clarity, Quality, and Reproducibility are good. Novelty is minor.
summary_of_the_review: I am confused about why there are both KL penalty and constraint in the problem setting. In addition, the author basically reformulates the minimax problem to a minimization problem by using convex conjugate, which does not require much technical effort.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers stochastic distributionally robust optimization problems under KL constraint and penalty and with both convex and nonconvex loss functions. The proposed algorithms improve upon primal-dual algorithms in terms of their dependence on the sample size (complexity of primal-dual algorithms would scale with the number of samples, whereas there is no such dependence in the proposed algorithms) and overall either match or improve upon the state of the art. The paper argues that the proposed algorithms are (near-)optimal in terms of the target error epsilon for approximately solving convex/nonconvex problems (finding an eps-stationary point for nonconvex problems or eps-optimal solutions for convex problems).

The overall evaluation of this work was that technically there were new results that appeared nontrivial. However, even following a discussion, it was not completely clear what was the motivation for studying the specific setting, which contained both a KL penalty and a KL constraint. The authors clarified in the discussion that the KL penalty was necessary for making the problem well posed, however, the significance of using the KL constraint remained unclear. It appeared as if the KL constraint was there only to make alternative algorithms non-competitive. However, from a modeling perspective and under the right parameter choice, there should be no difference between imposing the constraint and imposing the penalty. The paper itself did not provide a good explanation for using the KL constraint. Hence, the problem setting gave the impression of being contrived making it hard to accept the paper as is. Additionally, technical novelty compared to the cited paper Qi et al. (2021) was not completely clear and the authors are advised to more carefully compare to this work in a revision.
justification_for_why_not_higher_score: Even after all the discussion on Open Review and on Zoom, and after looking at the paper myself, I still do not understand why the paper considers this specific problem. I do think the paper has some novelty, but in its current state it is hard to judge the significance of the results.
Decision: Reject