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: In this paper the authors provide a reformulation for a non convex DRO problem with a fractional objective. Specifically, they focus on scalability and leverage existing results on reformulation and extend them to their setting. To achieve further scalability they apply clustering to the original data points. 
They illustrate the benefits of their results on a variety of different applications and illustrate them through numerical data. 
strengths_and_weaknesses: Originality: I believe that the paper is quite original. It showcases an important way forward for the application of DRO in practical settings by focusing on problem structure and leveraging the same to allow for better scalability. 
Quality: I feel the paper is sounds. The claims are well illustrated by numerical experiments as well as relevant theoretical results. The paper presents a complete picture of their work. 
Clarity: I feel the paper is fine though the compactness with which some results are written makes them difficult to read. 
Significance: I feel the paper takes an important step in the direction extending the applicability of DRO to more practical problems. 
questions: Are there potential ways of extending this DRO method (which seems to primarily relay the Duchi reformulation) to other ambiguity sets? 
What are the limitations of this particular ambiguity sets?

limitations: The discussion on limitations is quite limited focusing primarily on scalability. It would be good to see some discussion outside this domain as well such as about the limitations of the DRO model etc.
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 authors propose an approach for a distributionally robust solution to a class of non-convex sum of fractional solutions. The theoretical analysis of the solution’s global optimality is provided. To further enhance the scalability of the design, several techniques are applied. The effectiveness of the mechanism is presented in simulations.
strengths_and_weaknesses: Strength:
1. The paper studies an interesting topic and proposes a new algorithm for global optimum。
2. The analysis of the results is solid.



Weakness
1. The incremental contribution of the work is not clearly stated. The authors should highlight their novelty compared with the ones mentioned in the work.
2. The explanation of the theoretical results is insufficient, making the related parts hard to follow.

questions: 1. The work exists as an incremental contribution on, e.g., (Duchi and Namkoong, 2019, based on which the critical variance regularizer is applied. Please highlight the new and more challenging things considered. 
2. In DRO, what is the specific meaning of \delta_{\xi,n}? Please clarify.
3 In Sec.4, the clustering approach is applied. As Lemma 1 only states the property among clusters, why would we still have the guarantee for each sample? Do you have any assumptions about the divergence among the cluster?

limitations: NA
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 optimizes the non concave fractional objectives with variance regularizer, and reformulate it as a mixed integer concave program with all constraints linear. The key observation is when the individual objective $F_i$ can be written approximately as a linear fraction with affine numerator and denominator, the non-convex constraints can be converted into convex constraints by applying the McCormick technique. The MICP can be further converted into a MISOCP for better scalability. Such approximation of the fractional objective is possible via PWLA with sub-linear approximation rate. To further relax the number of constraints in solving MISOCP, this paper consider two more techniques. The first technique is the clustering approach, where cluster centers are used as new data points, the approximation error depends sub-linearly on the clustering radius and the number of original data points. The second technique is stratified sampling, which is similar as the cluster approach but real data points are used rather than the cluster centers. Three application problems are given to conduct experiments. The SSG with quantal response application is conducted on small synthetic datasets. Both clustering approach and stratified sampling approach outperform baseline algorithms. Both MC-FLP and MC-FCP applications uses real data, and the clustering approach is considered. Their method outperforms ERM in most of the cases.
strengths_and_weaknesses: Strengths:
1. Clever idea and solid analysis. For the idea part, the main contribution is to convert the original non-concave problems into a mixed integer concave program, therefore the near global optimality can be guaranteed. Furthermore, as programming approach is usually less favored due to the scalability, this paper proposes two relaxation techniques and seems effective in the experiments. For the analysis, every transformation of the problem comes with analysis on the approximation error, and dependence on the hyperparameters are clearly presented.
2. Well written paper for experienced readers. I am not very familiar with mix integer concave program but I find the paper is easy to follow, as the motivation and technical tools are well explained.

Weaknesses:
The paper provides a whole package on this particular optimization problem and I do not see obvious weaknesses. 
questions: 1. I have seen the idea of convex relaxations elsewhere in learning, namely, in robust optimization and adversarial learning. Can the author comment on the origin of this idea?

Wong and Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. ICML 2018.
Raghunathan et al. Certified Defenses against Adversarial Examples. ICLR 2018.

2. For the experiment, it is not clear to me why PGA is chosen for VR and TT-GAD is chosen for DRO, not vice versa. A follow up question,  why these two algorithms are chosen? As they seem to be preliminary methods in the first-order optimization algorithm family, there are other algorithms tailored for DRO.

Qi et al. An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives. NeurIPS 2021.
limitations: 1. Theorem 1 for learning with DRO directly should be compared in depth with the bound obtained by the proposed MISOCP if possible. For example, does Theorem 1 shed light on how to choose the number of piecewise linear functions, the number of cluster centers and the cluster radius?
2. While the experiments focuses the performance of the proposed MISOCP, I think the computational time should also be consider, especially the time consumed during the clustering process, then compare the total computational time with baselines.
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: The paper considers optimization problems for decision variables with a robust requirement to the observed data.
Thus the authors consider distributionally robust optimization and recast it via the variance regularized form into a mixed-integer second-order cone program (MISOCP). This formulation allows to efficiently obtain a solution while retaining the guarantees of the original formulation.
To further improve scalability the authors propose two approaches: i) clustering and ii) stratified subsampling. Both approaches can be shown to be close to the original solution (depending on the number of clusters or the samples taken).

As applications, the paper presents 3 game theoretic optimization tasks (a Bayesian version of Stackelberg Security games and two versions of max-capture facility assignment) that can be phrased to match this setting.
Experimentally, the paper shows that i) the proposed algorithm outperforms several baselines and that the clustering and sampling approaches perform close to the original problem while only utilizing s small amount of data.


strengths_and_weaknesses: This paper is outside my area of expertise, which I reflected by a low confidence score.

Strengths:
- Overall well written. Small improvements are possible (see "Presentation" below).
- Approach seems mathematically sound.
- Clustering and stratified sampling seem surprisingly simple yet elegant solutions for speed-ups.

Weaknesses:
- Evaluation on only 2 datasets (one synthetic, one real).
- Some motivation is unclear (see below).

Presentation:  
I found the applications section hard to follow, some small examples or illustrations might benefit the reader.

Motivation & Evaluation:  
While I know (though not well) that SSGs are important applications in some areas and DRO may be important settings, I think the paper did not motivate well why SSG-style decision problems need DRO on both a conceptual and an empirical level. All baselines use some version of DRO or variance reduction. It would be interesting to see how these compare to non-DRO approaches to justify why the setting is important. 

Further, can you clarify the need for the optimizations (clustering, stratified sampling) you discuss? The cost of solving the unoptimized MISCOP is a one-time cost.
Even in the setting in 5.2 one could either ju1st spend the one time for optimization once or else just subsample $S$ samples from $N$ (in a non-stratified way).

questions: Based on the above:
- Can you motivate the setting: SSG-style decision problems + DRO?
- Can you compare to a non-DRO (and non-VR) baseline to show the benefit of the distributional approach empirically? 
- Can you motivate the need for speed-up/scalability for the one-time optimization cost?
- Wouldn't subsampling, e.g. at uniformly, $S$ of $N$ samples (without stratification) be another baseline? How does stratification improve upon this?


limitations: Technological limitations seem sufficiently contextualized.
The paper does not discuss the negative societal impact of the work, but I don't think particular consideration for this is needed.
review_title: null

Meta-review: metareview: This paper studies distributionally robust optimization for a class of non-convex problems motivated by applications to decision problems such as security games and facility location. The reviewers agree that the paper is novel, studies an interesting topic, and proposes non-trivial algorithms with sound analysis. Reviewer bkf3 writes that the clustering and stratified sampling scaling approaches are simple yet elegant solutions. The main common concern among all reviewers i that some sections of the paper are compactly written and somewhat difficult to read. Based on the reviewer feedback, this paper is above the bar for NeurIPS.

Below are a number of typos and clarifications that should be made in the final version of the paper:

- Lines 37, 43: It looks like some citations here need \citep instead of \citet.
- Line 51: Should “location facility” be “facility location”?
- Line 91: Missing 1/n factor (though obviously this does not affect the optimal decision variables z).
- Line 93, 96: I think \mathcal{P}_{\zeta, n} should be \mathcal{P}_{\zeta, N}. I realize this notation is borrowed from the Duchi and Namkoong paper, but in their setting the number of samples was little n.
- Paragraph starting on line 86: I think it would be worth clarifying the various distributions at play. My understanding is that there is an (currently unmentioned) distribution D over feature vectors. The distribution P is the distribution over x* corresponding to the following sampling procedure: Sample a feature vector b from D, then set x* = f*(b), where f is the Bayes optimal classifier. Next, fix a sample b_1, …, b_N from D. hat P is the empirical distribution of f(b_i), where f is a learned approximation to f*, and P* is the empirical distribution of f*(b_i). 
- Theorem 1: I think it should be explicitly stated that this theorem applies when the function f is an empirical risk minimizer. 
- Line 107: I think \mathcal{H} should be the function class \mathcal{F} from the previous paragraph.
- Equation (1) and line 132: variable i is used twice for different purposes (i.e., two different sum indices in equation (1) and as the index of l_i and the sum index in line 132).
- Line 141: Should this be a piecewise *constant* approximation? I.e., if we use the components of the v variable as indicators for which piece of the approximation I am in, an expression of the form dot(a,v) + b can only represent piecewise constant functions instead of piecewise linear functions. I might not be seeing the intended transformation, but nevertheless it would be good to clarify this.
- Line 174: Are the functions n and d assumed to be Lipschitz with respect to both arguments, or just x?
- Theorem 2: It might be good to clarify how the bound depends on the Lipschitz constant of the functions n and d. I assume this contributes to the number of pieces needed in the piecewise linear approximation.

confidence: Less certain
Decision: Accept