Scalable Distributional Robustness in a Class of Non-Convex Optimization with Guarantees
Authors: Avinandan Bose
Arunesh Sinha
Tien Anh Mai
Venue: NeurIPS 2022 Accept (2022)
Keywords: distributional robustness
variance regularization
non-convex optimization
global optimization
fractional program
mixed-integer second order cone

Abstract: Distributionally robust optimization (DRO) has shown a lot of promise in providing robustness in learning as well as sample-based optimization problems. We endeavor to provide DRO solutions for a class of sum of fractionals, non-convex optimization which is used for decision making in prominent areas such as facility location and security games. In contrast to previous work, we find it more tractable to optimize the equivalent variance regularized form of DRO rather than the minimax form. We transform the variance regularized form to a mixed-integer second-order cone program (MISOCP), which, while guaranteeing global optimality, does not scale enough to solve problems with real-world datasets. We further propose two abstraction approaches based on clustering and stratified sampling to increase scalability, which we then use for real-world datasets. Importantly, we provide global optimality guarantees for our approach and show experimentally that our solution quality is better than the locally optimal ones achieved by state-of-the-art gradient-based methods. We experimentally compare our different approaches and baselines and reveal nuanced properties of a DRO solution.

Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees
Avinandan Bose
Arunesh Sinha Rutgers University arunesh. sinha @rutgers.edu
University of Washington avibose wee.eessssisgtnn...m
Tien Mai
Singapore Management University
atmai smu.cdu.sg
Abstract
Distributionally robust optimization (DRO) has shown lot of promise in providing robustness in learning well as sample based optimization problems. We endeavor to provide DRO solutions for a class sum of fractionals, non-convex optimization which is used for decision making in prominent areas such as facility location and security games. In contrast to previous work, we find more tractable to optimize the equivalent variance regularized form of DRO rather than the minimax form. We transform the variance regularized form to a mixed -itteer second order cone program (MISOCP), which, while guaranteeing near global optimality, does not scale enough to solve problems with real world data-sets. We further propose abstraction approaches based clustering and stratified sampling increase scalability, which we then use for real world data-sets. Importantly, we provide near global optimality guarantees for our approach and show experimentally that our solution quality is better than the locally optimal ones achieved by state-of-the the--ar gradient-based methods. We experimentally compare our different approaches and baselines, and reveal nuanced properties of a DRO solution.
Introduction
Distributionally robust optimization (DRO) is popular approach employed in robust machine learning. Mostly, if not always, these works have focussed on the task of classification or regression. However, often in practical applications the end goal of learning is decision output z, which requires .,....,,,, yet another complex optimization that uses the output .,...., &y regressor f-)). For example, in facility location problem the learning of facility values is followed by optimization using the values predicted to decide where to locate facilities and in security games adversary behavior model learned and then optimal defense allocation computed based the learned model. Often the learning output is provided as public datasets with no access to the underlying private dataset used for such learning. this set-up, we aim provide robustness at the decision making level with access to only the non-robust learning output XI,...,NN
However, often the objective F(z, x) of decision optimization is non-convex in the learning system output x unlike the convex objective of classification or regression, presenting significant scalability challenges. In general, for decision making and specifically for the problem domains global optimality is important as sub-optimal decisions can lead to large revenue loss or loss of life; thus, the local optimality provided by gradient based methods is not sufficient. As consequence, in this paper, we study the scenario of calculating DRO decisions using the given multi-dimensional real valued outputs ,,,...,8 &N of non-robust learned A first result (Theorem) 1 characterizes the
consider,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

quality of DRO decision output compared to the scenario where we know the true fr Our main focus on addressing the scalability issue for the DRO decision making problem for particular, but widely used, class of sum of fractionals non-convex objective. This objective arises from the well-known discrete choice models [Train 2003) of human behavior, which is known to not have scalable globally optimal solutions [Schaible] 1995| Li et al. 2019]; we use this for tackling two different decision optimization problem in facility location and a robust version of Bayesian Stackelberg security games problem with quantal response. As far as we know, this is first attempt to solve the aforementioned non-convex problems in a DRO setting to near global optimality.
Our first contribution is a modelling construct, where we reformualate the variance regularized form [Duchi and Namkoong 2019] of our non-convex sum of fractionals objective as a mixed integer second order cone program (MISOCP). While the MISOCP form provides more scalability than the original formulation and guaranteed solution quality (Theorem 2), still does not scale to real world sized datasets. Our second contribution is a pair of approaches that achieves further scalability by splitting the problem space into sub-regions and solving a smaller MISOCP over representative samples from the sub-regions. Under mild conditions, both approaches provide global optimality guarantees (Theorem
Our final contribution is detailed experiments validating the scalability of our approaches on a simu- lated security game problem as well as two variants of facility location using park and ride data-sets from New York [Holguin- Veras et al. (012). We compare with two gradient-based approaches (Lin ct al., 2020] and show the superior solution quality achieved by our approach, which also reveals the need for global optimality. We further show nuanced property of the DRO solution in providing better decisions for low probability scenarios over non-robust versions. Overall, our work provides desired robustness with globally optimal solution guarantees.
Related work: Our work is built on a recent line of research that connects the concepts of DRO and variance regularization (Duchi and Namkoong, 2019 Duchi et al. 2021 Lam 2016 Maurer and Pontil 2009 [Staib et al.) 2019). While most the previous studies along this research line focus on convex and continuous problems or problems with submodular objectives, our work concerns a class of DRO problems with fractional structures, which are highly non-convex and requires new technical developments for globally optimal solution. Recent work Yan et al. [2020), Qi et al. [202T] has addressed non-convex objectives in DRO using gradient based methods that converge to stationary points, which is insufficient for decision making as we experimentally show that stationary points and globally optimal points can yield very different decision utilities.
The literature on DRO is vast and we refer the reader to Rahimian and Mchrotra 2019 for a review. DRO methods can be classified by different ways define ambiguity sets of distributions, for instance, ambiguity sets based on @-divergences [Ben- Tal et al. [001)] Duchi and Namkoong
2019 Staib et al.] 2019] or Wasserstein distances (Pilug and Wozabal [007] Esfahani and Kuhn 2018 Shafieezadeh- Abadeh et al.) 2015 Blanchet and Murthy [2019]. In this work, we focus on o-divergence based models, motivated by their interesting connections with variance regularization and the tractability of the resulting non-convex DRO models.
be used in some popular Decision-making problems such as Stackelberg security game (SSG) with Quantal Response (Tambe [011 I Xu] 2016 Fang et al.] 2017] Sinha et al., 2018 Yang et al.) 22012 Haghtalab al., 2016 or competitive facility location under random utilities [Benati and Hansen 2002 Freire et al. 2016 Mai and Lodi 2020 Dam et al. 2021]. To the best of our knowledge, DRO Bayesian model has not been studied in existing SSG works. In the context of competitive facility location under random utilities, we seem to be the first to bring DRO as a consideration. We handle a DRO version of a facility cost optimization problem, which has also never been studied in prior work.
We show that DRO methods
2 Background, Preliminary Notation and Result
We use bold fonts for vectors and non-bold font for vector components and scalars, e.g., xy is a component of x. [N] denotes as (II,,..,, The positive part of vector x is xt (max(0, æ; s)edd and the negative part is x (min(0, z, s)44 0, represent the all zero and all one vector.
N). A d-dimensional vector is written as = (xy))ee4 or
2

---

Distributionally Robust Optimization: Consider a function F with inputs being decision variable z and parameter x X. Both and x lie in an Euclidean space and both are constrained by linear constraints; for notational ease we skip writing the constraints in the general formulation. We seek to maximize the following objective function max, E [ [F(2, x)], where x is distributed according to P. The details of how P arises from an underlying regression problem is stated later in the text just before Theorem [ For many classes of distributions the above is generally not tractable and one needs to sample from P. Let XI...., XN be N samples, we can solve the sample average approximation (SAA) problem instead max, N Ene(N] F(z, X,). Let PN be the empirical distribution induced by the samples. The SAA above is same as max, E p, [F x)]. A distributionally robust version of the SAA problem is max, min PEP { [ (z, x) where the is the x² divergence: (P(l)) = [dP/ddQ - dQ. The above optimization can be written equivalently as (Ag.N defined below)
ambiguity set Pg.N = { (a((I(PN) <//T) and
{ Σ (...(.)))) iE[N]
max min
(DRO)
DEDg.n
where Ag,N = (D R E 1p- 1/N1 S 2 25²= }. We have earlier stated that &, is output by a regressor, say E F for some function class F trained using loss L with Nr datapoints, but this implies that x, - ((;;) might not exactly same as x = -b,b)) for some underlying feature values by and best function I" E F. We assume I* is deterministic and has zero Bayes risk.
Let D be the probability distribution from which the feature values 6; are sampled. Then, let l be the true distribution on X induced by f acting on the feature values that are distributed according to D (i.e., the pushforward measure). Similarly, 1 is the distribution on X induced by f acting on the feature values that are distributed according to D. Thus, the (unknown) samples x" are obtained from Pt; hence, the true utility of any decision z Ep. F(Z, We prove an end end guarantee about the output decision ** using X, 's which reveals that 2 is not much worse than the decision z² that would be learned if x 's would be available and used. The result shows that larger training data Ny helps.
Theorem 1. Let x²; (b.)) for true function f and let x, 5(be) for the learned empirical risk minimizer! f. Suppose the optimal decision when solving DRO is z using x²'s 's and Zt using F; 's. Also, let F be r-Lipschitz in x, X be bounded, and a scaled C upper bound 1l2 (i.e., 1x xx'll2 I max((_(xxxx)) e) for constants k. E) then, the following holds with probability 1 1- 26 - 26,; [F-[F(E" xx)] 2 Ep- [F(x**,)
C//NN - (1 + 2VE)Te - EN - CNyy where EK- = ( + C2/VK and Rg is the Rademacher complexity with K samples and C, C1, C2 are constants dependent on 6, ò1 &, T.
Variance Regularizer: As a large number of samples are needed for a low variance approximation of the true distribution, another proposed robust version of the SAA [Maurer and Pontil 2009 Duchi and Namkoong 2019 is to optimize the following variance- regulaaze (VR) objective function
Var p.y (F(z,
max [F - -CV
(VR)
N
The above allows to directly optimize the trade-off between bias and variance. In a fundamental result, Duchi and Namkoong [2019, Theorem 1] show that, with high probability, problem (VR) is equivalent to the problem (DRO). Further, Duchi and Namkoong (209 argue for solving the DRO version of the problem for concave F (note we are solving maximization SAA problem) since concave F results in concavity of minppe n. ΣiEN Pt (z. x,), thus, the overall DRO problem is a concave maximization problem. In contrast, the objective in (VR) is not concave.
In this paper, our focus is on F that is not concave, thus, the choice of DRO or variance regularized form is not obvious. For the class of functions F that we analyze, we argue the variance regularized version is more promising as far as scalability for global optimality is concerned. We work with the assumption that the variance regularized form is equivalent to DRO, which holds under the mild condition shown in Equation (9) in Duchi and Namkoong [2019]
3

---

3 Towards a Globally Optimal Solution
In this section, we present results for general class non-concave functions that has a fractional form with non-linear numerator and denominator and that can be approximated by linear fractional form with binary variables. Then, we show three prominenl applications of our approach.
Notation: For ease of notation, we use shorthand to denote F Fz,, &,) by F; and 2 Nz by p.
3.1 General Recipe to Form MISOCP
We perform a sequence of variable and constraint transformations of (VR). leading to a MISOCP.
Mixed Integer Concave Program: The variance regularized objective in shorthand notation is:
g(z) Σ F
Fs N
F.)
(I)
We substitute 4= F. P; and Σ, F2 for all i [N], such that Σ, 4, and F; = 4.
N
The objective in Equation I thus becomes q - VI which concave in the variables q and {4). We add the new constraints 4,4= and F. =
q- 4, for all i E [N] Note that, while the objective is now concave with above changes, we have pushed the non-convexity into the constraints F. + 4 0 for all i E [N] that are added to the optimization.
If F; can be written (or approximated) can convert the constraint F; q + 4 = 0 into a convex constraint, giving us an overall con- cave program. The conversion explained next. Suppose F; can be written (or approximated) as of r+d, aTT++&
fraction with affine numerator and denominator,
where v represents binary variables after conversion (v completely replaces z and a, a/. b,, bj
are dependent on X, 's). Typically, such a linear fractional form is constructed by discretizing the arguments of the original non-linear functions the numerator and denominator of F. As- sume v is of dimension d; typically d will depend on the number of pieces. Define y; = vt; where t; = .// Then, we can (re)write the fractional form for F, as F; a. y: + b,t.-
This yields the linear constraints below with the non-linearity now restricted to y; vt,.
N
a y; + b,t, - 4
Vi [N]
(3)
Σ
4=0
(2)
a y, + 0,44 1-
W [N]
(4)
We handle y, vt; using McCormick relaxation technique McCormick 1976). Typically, Mc- Cormick relaxation is applied for bilinear terms that are the product of two continuous variables, in which case, it is approximation. However, in case since is binary vector variable, the McCormick relaxation yields an exact reformulation of the bilinear term. For applying McCormick technique, we need an upper and lower bound of v and 4. Since a vector of binary variables, we have lower bound v² = 0 and upper bound vd = 1. Similarly, 1 ( and 1
1141) (recall superscript + and - indicate positive and negative part of vector respectively). Further, is assumed ! and if exist. Note that these bounds are not variables but fixed constants that depend on the fixed parameters a,, a/, b, b/. hence these need to be computed just once. Using the upper and lower bounds of v and t; in McCormick technique we get:
y. ve! S O;
Vi E [N] (5)
- y, + 0o; v (0.1)
Vie
(8)
y. (If, + vt! - 1141 50
Vi E [N] (6)
(9)
-,, + (It, + vE! 1 O;
Vi E [N] (7)
st
vi [N]
(10)
is straightforward to check the above set of equations is equivalent to y; With the changes, we obtain a mixed integer concave program (with all constraints linear). Next, while the above can be solved using branch and bound with general purpose convex solvers for intermediate problem, we show that further transformation to MISOCP is possible. Specialized SOCP's solvers provide much more scalability than general purpose convex solvers [Bonami and Tramontani 2015 and hence partially address the scalability challenge.

---

Mixed Integer SOCP: We transform further by introducing another variable to stand for vpΣ, We use (s. (4)) v. (f)))e(M): .1.............................. .x) denote all the variables of the optimization. Thus, the objective becomes the linear function g with an additional constraint that
/ Σ SS
(11)
The above is same as ||rr|| S r for the constant matrix A (with entries or vp) and constant vector с (with 1 in the component, rest 0's) that picks the 4s' and respectively. This is SOCP form of constraint, and the linear objective q makes the problem after this transformation a MISOCP. In the above reformulation, the only approximation is introduced in writing F; as linear fractional term. One way of such approximation is via discretization. Suppose the fraction function
F(z, X:) has a separable (in z) numerator and denominator of the form 2, Kc) where j ranges Σ, d(z;,x,)
over the components of and n(zj, xx) and d(zj. x,) are non-negative and Lipschitz continuous in 2j with Lipschitz constants C", Odd respectively. In this case, a general approximation via discretization is possible with the following guarantee:
E, m(2;8t)
Theorem 2. For &,z, = E, d(=))t)) as stated above and approximated as d' an approxima-
tion via discretization of zj with K pieces yields (9(2*) - G(²"") ) S Omax (Cm, Gd)/ where g(z") and )( are the optimal objective values with approximation (MISOCP) and withou the approximation respectively.
Next, we show instantiation of the just presented general recipe for three widely studied problems.
3.2 Applications
Notation: In the SSG (facility location) application resources (facility) are allocated to M targets (locations). x maps to type o of adversary, and type o of defender SSG, and type 0x of clients of facility or directly V. utility for each client type in facility location.
Bayesian Stackelberg Security Game with Quantal Response: SSG models a Stackelberg game where a defender moves first to allocate m security resources for protecting M targets. The randomized allocation is specified by decision variables z of dimension M with the constraints
that Σ 24 S m (2, E [0, 1)); 2; is interpreted as the protection probability of the target i. Past works have used the model of quantal responding adversary [Sinha et al., [018]]. We generalize this to Bayesian game version where there is continuum of attackers types with the type specified by a parameter and an unknown prior distribution over these types. The attacker's utility in attacking the target j is a function of the protection probability of target j and type: Mz,,02) (Q). Similarly, the defender's utility when target is attacked is: u(zy. 0g) for some player- specific parameters 0 that depend on x. Following quantal response model (for attacker only), the exp(h(e,,
attacker of type x attacks target with probability Eyeta exp(h(az; ())) and the defender utility
is F F(z, x) = Ejecan als, (8)) exp(h(s,, Note that in case the defender's 's utilities u(2j, ( take Eyj(M] exp(h(e,
negative values and the assumptions of Theorem 2 will be violated. This issue can be simply fixed by choosing a such that a max,x(-u(( {()) and replacing F(z,x) by F(z, x)
(Me (()+a)
This will make all the numerators and enumerators of the objective exp(k(= (x)h))))(()(ee
Σyelm exp(h(e,, (2))
function non-negative, while keeping the same optimization problem. We also note that quantal response is also known as multinomial logit model in the discrete choice model literature [Train 2003]. Our generalization here to multiple types of adversary makes the problem akin the mixed logit model in discrete choice models, which is generally considered intractable. As a consequence, our solution addresses basic problem in discrete choice models also.
Following our set-up, we observe N samples of the types of attackers 8,,..., &N (which gives of...., 0g 1; .... 02 and we solve a robust version of the problem. Further, following our general recipe for solving the robust problem, we piecewise approximate the numerator and denominator of F using K pieces, where the dimension of v is d K. For this approximation, require two
5

---

additional linear constraints over the constraints in Equations
35p. The optimization then is:
max -
(SSG)
subject to Constraints (5,5,,
Σ
Usk- mk < 0, UiA 2 2/44411
VA E [K]
jEIM] kE[K]
The overall additive solution bound of O(1/K) can be readily inferred from Theorem 2
Max-Capture Competitive Facility Location (MC-FLP): In this problem [Mai and Lodi 2020 firm has M locations ([M)) to set up at most m < M facilities. The aim is to maximize the number of clients using this firm's 's facilities. The competitor(s) already have facilities running locations Y C. [M] There are different types of clients, where types are denoted by x. The number of clients of type is known and equal to sx. However, the distribution over types is unknown. The firm's m's decision which location to choose is given by binary variables E {0, }} for j E [M]. A utility of any client of type for visiting location j is V.j-- The choice probability of client of type
EjEty s,e
choosing any of this firm's location is given as a quantal response model
ΣJE(M] Kje +. jej e'c."
For shorthand, we abuse notation and use Vx5 to replace eV and Y to replace Σjer Bas, This gives F(z, x) * EIEM 2y choosing this firm 's facilities.
Σjaa 33 +u, which is interpreted as the expected number of clients of type
Following our set-up, we observe N samples of the types of clients samples
(V (VIJ))EMM)--- (Wn.....,,,VVN)).)) (VNJ)JE[MN and we solve a robust version of the problem. Here, we get F; 2 R,, ΣSEMM 23 Vi,+
Next, following our general recipe for solving the robust problem, we note
that F; is already in the form v-v. a.vv& where z plays the role of v. Thus, the dimension of v is M and
approximation is needed here for F; by Theorem [ we achieve the global optimal solution by
solving MISOCP optimally. The full MISOCP with an additional number of location constraint is:
max q - subject to Constraints 350
U/ - m S 0. JE(M]
Σ
Max-Captum Facility Cost Optimization (MC-FCP): In the previous MC-FLP problem, the budget was specified as a constraint on the number of facilities. However, often a more realistic set-up where there is monetary constraint and the attractiveness of a facility depends the investment into the facility. Thus, modifying the previous problem slightly, takes a different meaning of facility). Given
the amount of investment into facility location (zero investment indicates this investment, the attractiveness of a facility j for the client of type x is given as lı(z,, 0x.)) for some parameter 0 dependent on and j. And the choice probability of client of type x choosing
Ejcta (.3)
any of this firm's location is given as quantal response model
ΣSe(a e Maay +u, This gives
6x Eyj (as)
F(z,x) x)
Eyean (13) 43, which is interpreted similar to MC-FLP. As stated, observe
N samples of the types of clients which gives (fI.))s(M))..,.O...)) (ONJ))ee and we solve a robust
version of the problem. Here, we get F; = 5: ESCII (,5)
ΣjEJa Maay ML5) Next, as can be seen from the form, this similar to the SSG problem and, following our general recipe, with two additional linear constraints the optimization formulation is exactly same as Equation (SSG).
4 Scaling up in Number of Samples
The transformation to a MISOCP helps in scalability over a general mixed integer concave program, but for real world dataset sizes ge. 80, 000 data points our experiments) we need further scalability, We explore two related techniques towards this end: clustering and stratified sampling. For both approaches, we obtain a representative subset of S data points (S << N) and modified weighted objective, which converts to much smaller tractable MISOCP compared to the original problem.

---

For solution guarantees, we need mild assumptions: in particular, for the rest of this section we assume bounded F. i.e., for some fixed & max, (F. x)] min,(F(z, x)) and r-lipschitzzeess of F in the argument x: [F F(z, x)) - - vz.
S ei
vx!...., Xy
Clustering Approach: We cluster the N points XN into 5 groups and for each group we have ||x; x S e, where x" is the cluster center of cluster s. We call the clustering radius. Let C. be the number of points in the cluster s, hence Exc(s] C' N. We use shorthand for the original objective function of the MISOCP G(z):
F(Z,X; Σ F N
E
F Zz x,)
F(2, Mean( v (F,,x((,,)))
Vo
where Mean is empirical mean and Var unnormalized variance. After clustering, we solve for the same problem but only with cluster centers and appropriate weighing, to get modified objective ((z):
CC.
F(z, N
c..
F(,,
F(Z,x²)) MMean (F(z,x) Vo (F(z,x))
The conversion to MISOCP is exactly the same, except for F,'s being weighted shown above; details of conversion are in the appendix. We bound the approximation incurred by the two terms above (weighted mean and unnormalized weighted variance) separately below
Lemma 1. Under assumptions stated above, we have Mean Mean(F(z.xx Fzz.x)) Mean (F(z,x)) s TE and
V (Vvrr(F(z.x)) VVVar (F(z,x)) I (v) 22
20 N
The next result is obtained by using the lemma above
Theorem 3. Given 2 an optimal solution for max; (z)) (clustering approximation) and x" optimal for MISOCP max, G(z), the following holds: (G) G(z")l 2(T v/ 27C
27c8
N
Stratified Sampling: Similar in spirit to clustering, the space of x space is divided into T strata. Each strata has C, samples, such that Exerry C = N. Next, distinct from the clustering approach, draw N₂ samples randomly from the tt stratum with total of Σ, N2 S samples (note same number of total samples as in clustering). For each stratum t we have ||x; x,yl I d, for any X; X, in stratum t. We denote random sample in stratum as X where j E [NN]] (note superscript is to distinguish from the subscript used to index all the X's). This approach is the preferred one the clustering approach results in cluster centers that are not allowed as parameter values (e.g., cluster center may be fractional where x can only be integral).
x) for Let 4 = N. Use Mean (F x)) to stand for & EvEryy 4 EjE(NA Flz, x') and Var (z,8)
ExE(T) 4e () (Mean(F(z,x)) F(), After stratified sampling our modified weighted objective G(z)) is Mean T (F(z,x)) pvar ar T
(z. x). Next, similar to clustering, bounds for Mean T
and Var but with high probability (Lemma 2 in appendix) lead to the main result:
Theorem 4. Let D = max,, F (z,xx) for bounded function F. Under mild assumptions, and 2 an optimal solution for max, (z) and z" optimal for MISOCP max; G(z), and N, min, Nr, the
2,372
following statement holds with probability 2 - 2-, exp
E, exp D2
( - 9(>") (N.)1/4
2e
(1
VV
Var(F(z,
Thus, with increasing samples in all strata, optimality gap approaches 0 with prob. approaching 1.
7

---

% of Optimal objective
100
Mm4
time in seconds
M=5
percentage
M-6
M=
M=7
M
M=
M=7
No. samoles
Number of clusters
Number of clusters
10
15
20
Figure 1: (Left) % gap between the utility of decisions using true and learned regressor with varying training data size Nr- (Middle) Objective value achieved using clustering approach % of OPT. (Right) Time to solve each optimization to optimality, Middle and right results are shown for varying alternatives number M. Underlying parameters are 500, m 1, =1E6.
Table We use clustering/strattiied sampling to approximately solve a problem (Approx-OPT), The table shows the mean percentage: A00xApproXOOPT and standard deviation over different synthetic OPT SSG datasets with underlying parameters N 500, M 6, K, 10.
Total no. of samples (S)
Method
16
24
Clustering
80.17 + 2.14
90.74 1: 1.20
94,03 + 0.57
per strata
85,49 + 1.94
94.59 1 0.76
99.25
0.39
per strata
91.78 1.33
94.55 1 0.64
99.54 0.25
per strata
78.89 = 1.73
94.86 0.94
98.77 0.39
per strata
92.19 = 0.67
95.85 + 0.80
99.37 + 0.25
Uniform sampling (no cluster/strata)
73.92 33.71
78.08 + 28.62
79.86 + 26.81
Table 2: Objective values datasets with parameters N = 500, M N 500, m 1, 1E6 for varying no. of targets (M, on right). The no. of clusters/strata is 50.
OPT across various methods repeated over 5 synthetic SSG
10, m 1 for varying regularization (E. on left) and
Regularization (E)
No. of Alternatives (M)
Method
1E3
IE4
IES
1B6
10
25
50
TA
99.8+0.1
99.4+0.1
92.7+10.3
82.610.4
82.6 = 0.4
90.2 + 0.5
92.2 + 0.3
PGA
98.9=t.11
98.1
87.7+0.5
49.2+009
49.2 = 0.9
90.9
93.5 : 0.4
Clustering
99.910.1
99.91
99.810.11
99.610.1
99.4 0.2
Sampling
100.0+10.0
99.9+
99.94-0.1
99.8+-0.1
99.8 +
99.6 0.1
99.5 0.2
Experiments
We evaluate our methods on (a) Stackleberg Security Games (SSG) with Quantal Response (synthetic data). (b) Maximum capture Facility Location Planning (MC-FLP) and (c) Maximum capture Facility Cost Planning (MC-FCP). Empirically we demonstrate (i) better solution quality of our method compared to baselines, (ii) practical scalability of our method, and (iii) improvement non-robust optimization on those data points that contribute least to the objective (akin to rare classes in classification) while not sacrificing average performance. We fix K 10 in approximation via discretization as we find that objective increase saturates for this K (see Appendix K GHz CPU with 128GB RAM.
We use a 2.
Baselines: We use the following two methods as baselines: (i) Projected Gradient Ascent (PGA) on
the formulation (VR), (ii) Two Time Scale Gradient Ascent Descent (TT-GAD) [Lin et al.) 2020
the formulation (DRO) where the inner minimization is convex and the outer maximization is non- concave. The numbers reported for baselines are the best values 10 random initializations.
5.1 SSG with Quantal Response (Synthetic Data)
We generate attacker and defender utilities following Yang et al. 2012 a complete description of data generation and choice f in Appendix | We generate five datasets of size N 500 each in order to observe the variance of every result reported in this sub-section; this is also the largest size

---

Table 3: Average client choice probabilities for availing the facility across various settings. H denotes average over those 5% of the clients in test data with the lowest choice probabilities, A denotes average over all the samples in the test set.
MC-FCP
MC-FLP
m=
7
m=10
m= 13
m=
10
m=12
m=
H
A
H
A
H
A
A
H
H
A
ERM
0.069
0.692
0.150
0.719
0.420
0.758
0.175
0.741
0.426
0.769
0.469
0.772
1F2
0.069
0.692
0.417
0.751
0.4170
0.751
0.418
0.763
0.426
0.769
0.469
0.772
IE3
0.093
0.697
0.416
0.747
0.417
0.757
0.418
0.763
0.425
0.768
0.533
0.777
IF4
0.093
0.697
0.416
0.747
0.446
0.750
0.417
0.759
0.531
0.767
0.539
0.769
96 inprovemen ouer FRM
% innrrvvemen over ERM
E-1
{ 1E2
E-
{ 1C3
C-:
ç- 1E4
-30 -00 <230 Cumulative % of sorted choice probabilties
-20
-20
-10
<50
di
230 <3 <de -6 <59 <d
22 di -i <10
Cumulative 76 of sorted chaice probabilities
(A) MC-FCP
(B) MC-FLP
Figure 2: The bar plots show the percentage improvement of choice probabilities of our clustering approach over ERM over cumulative buckets of choice probabilities in ascending order with varying regularization & with fixed budget m=10. The buckets are made by sorting all the clients in the test set by ascending choice probabilities and then considering cumulative buckets as the first 5%, the first 10% and so on.
that we could solve exactly optimally within an hour using all the data points. First, we empirically validate Theorem by plotting in Figure [left) the relative gap between the true utility Ep- [F(. x)] of the decisions output by running DRO on the output (xx) JE(NN of the true f (assumed fixed linear function) versus on (ENN) from learned f, as the training data size Ny for learning f varied.
Next, we focus only using (R)sE[N] and the optimal solution for (N))E[N] is named OPT. Figure (middle) demonstrates empirically that the solution of the optimization problem on cluster centers converges OPT with only few number of clusters and the time for the optimization shown in Figure (right) is reasonable. Next, the results in Table show a comparison of the clustering and stratified sampling approach using the metric of how close they get to OPT. We find stratified sampling to be better than clustering in almost all cases and simple uniform sampling (no cluster/strata) fails return a solution close to OPT. Table 2 (1eft) demonstrates that the baselines struggle reach the optimal value objective as the magnitude of regularization (5) increases. Intuitively, as & increases the variance term (which is highly non-convex) contributes more the objective and stationary points reached by the baselines are quite sub-optimal compared to the global optimal. In addition, with increasing the ambiguity set becomes larger possibly containing more local optimal solutions. We also study varying the parameter M (m fixed) and Table 2 (right) shows that our approaches outperform the gradient-baser baselines across different values of M.
5.2 MC-FLP and MC-FCP (Real Data)
P&R-NYC Dataset We use large and challenging Park-and-ride (P&R) dataset collected in New York City, which provides utilities for 82341 clients (N) for 59 park and ride locations (M)), along with their incumbent utilities for competing facilities [Holguin-
et al. 2012]; ; this data was directly used for MC-FLP. For MC-FCP we additionally use generated costs, which are not present in the P&R data. A complete description of data generation is in Appendix [ Both these problems could not be solved at all with our MISOCP alone (no clustering) as the optimization did not finish in 24 hours. Hence,
clustering approach with 50 clusters.
We compare to a baseline solution of the non-robust empirical risk minimization (ERM) (also called the sample average approximation or SAA). We split the data (randomly) into training and test (80:20) and then obtain the decision 2 using the training data. Then, we obtain the choice probability (recall this as probability of a client choosing any of the firm's 's facility) for every client in the test data for the

---

decision 2. We compare the performance of ERM and our method for clients (in test set) bucketed by choice probabilities in Figure ( and Table The buckets are made by sorting all the clients in the test set by ascending choice probabilities and then considering cumulative buckets as the first 5%, the first 10% and so on. Fig. we show that the average percentage improvement in choice probabilities of our robust approach over ERM is considerably higher for clients with lower choice probability (these clients contribute least to the objective) and the over all average over all clients (rightmost on x-axis) is slightly better than ERM. In Table note the significantly increased probabilities for low choice probability clients (low choice prob, using Z) without compromising the average performance across all clients for varying M. Additional results in Appendix J
6 Conclusion
We presented approach for a distributionally robust solution to a class of non-convex sum of fractional solutions, with guaranteed near global optimality. We presented application to three prominent practical problems and the connection discrete choice models opens up possibilities of applying our approach to even more problems. Further investigation on how to cluster or stratify more effectively (than k-means) to achieve even more scalability is possible future research direction. Further, we used X² -iveergeee based ambiguity set, which only covers nearby distributions with same support as the given data samples; exploring Wasserstein ambiguity is possible future research direction. We hope that our work inspires tackling robust formulation of more classes of non-convex problems, with guarantees for global optimality.
Acknowledgement
This research/project is supported by the National Research Foundation, Singapore under its Al Singapore Programme (AISG Award No: LISG2-RP-2020-0177 2020-017).
References
Felipe Aros- Vera, Vladimir Marianov, and John E Mitchell. p-hub approach for the optimal park- and-ride facility location problem. European Journal of Operational Research, 226(2):277-285. 2013.
Aharon Ben-Tal, Dick Den Hertog, Anja De Wacgenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2):341-357, 2013.
Stefano Benati and Pierre Hansen. The maximum capture problem with random utilities: Problem formulation and algorithms. European Journal of Operational Research, 143(3), 2002.
Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-60) 2019.
Pierre Bonami and A Tramontani. Recent improvement to misoep in eplex. INFORMS, Philadelphia, PA, USA, Tech. Rep, 2015.
Tien Thanh Dam, Thuy Anh Ta, and Tien Mai. Submodularity and local search approaches for maximum capture problems under generalized extreme value models. European Journal of Operational Research, 2021. ISSN 0377-2217.
John Duchi and Hongscok Namkoong. Variance-based regularization with convex objectives. The Journal of Machine Learning Research, 20(1) 2019.
John C Duchi, Peter W Glynn, and Hongseok Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. Mathematics of Operations Research, 2021.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization
using the wasserstein metrie: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115-166 2018.
10

---

Fei Fang, Thanh H Nguyen, Rob Pickles, Wai Y Lam, Gopalasamy R Clements, Bo An, Amandeep Singh, Brian Schwedock, Milin Tambe. and Andrew Lemieux. PAWS A deployed game- theoretic application to combat poaching. Al Magazine, 38(1), 2017.
Alexandre S Freire, Eduardo Moreno, and Wilfredo F Yushimito. A branch-and-boume algorithm for the maximum capture problem with random utilities. European journal of operational research, 252(1), 2016.
Nika Haghtalab, Fei Fang, Thanh H. Nguyen, Arunesh Sinha, Ariel D. Procaccia, and Milind Tambe. Three strategies to success: Learning adversary models security games. In 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016.
Jose Holguin-Verte Jack Reilly, Felipe Aros-Vera, et al. New york city park and ride study. Technical report, University Transportation Research Center, 2012.
Henry Lam. Robust sensitivity analysis for stochastic systems. Mathematics of Operations Research, 41(4):1248-122 1275, 2016.
Hongmin Li, Scott Webster, Nicholas Mason, and Karl Kempf. Product-line pricing under discrete mixed multinomial logit demand: winner-2017 m&som practice-based research competition. Manufacturing & Service Operations Management, 21(1): 114)2244-8,, 2019.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083-6093, PMLR, 2020.
Tien Mai and Andrea Lodi. A multicut outer-approximation approach for competitive facility location under random utilities. European Journal of Operational Research, 234(3), 2020.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample-variange variance penaliza- tion. In COLT, 2009.
Garth P McCormick. Computability of global solutions to factorable nonconvex programs: Part convex underestimating problems. Mathematical programming, 10(1):147-175, 1976.
Georg Pflug and David Wozabal. Ambiguity in portfolio selection. Quantitative Finance, 7(4): 435-442, 2007.
Qi Qi. Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang. An online method for class of distributionally robust optimization with non-convex objectives. Advances in Neural Information Processing Systems, 34, 2021.
Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.0566 2019.
Henry WJ Reeve and Ata Kaban. Optimistic bounds for multi nulti-output prediction. In 37th International Conference on Machine Learning (ICML 2020), 2020.
Siegfried Schaible. Fractional programming. In Handbook of global optimization, pages 495-608. Springer, 1995.
Soroosh Shaficezadeh-Abadel Peyman Mohajerin Esfahani, and Daniel Kuhn. robust logistic regression. arXiv preprint arXiv:1509.092) 09259, 2015.
Distributionally
Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: Looking beyond a decade of success. In 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018
Matthew Staib, Bryan Wilder, and Stefanie Jegelka. Distributionally robust submodular maximization. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 506-516. PMLR, 2019.
Milind Tambe. Security and game theory: algorithms, deployed systems, lessons learned. Cambridge university press, 2011.
Kenneth Train. Discrete Choice Methods with Simulation. Cambridge University Press, 2003.
11

---

Haifeng Xu. The mysteries of security games: Equilibrium computation becomes combinatorial algorithm design. In Proceedings of the 2016 ACM Conference on Economics and Computation. pages 497-514, 2016.
Yan Yan, Yi Xu, Lijun Zhang, Wang Xiaoyu, and Tianbao Yang. Stochastic optimization for non-convex projeetjntinon problems. International Conference on Machine Learning, pages 10660-10669. PMLR, 2020.
Rong Yang, Fermando Ordonez, and Milind Tambe. Computing optimal strategy against quantal response in security games. In AAMAS, pages 847-854, 2012.
Rong Yang, Benjamin J Ford, Milind Tambe, and Andrew Lemieux. Adaptive resource allocation for wildlife protection against illegal poachers. In Aamas, pages 453-460, 2014.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (c.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] It is public use
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "u71tQdMHiur", "reviewer": "Reviewer_CQhS", "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.", "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. \n2. In DRO, what is the specific meaning of \\delta_{\\xi,n}? Please clarify.\n3 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?\n", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper studies an interesting topic and proposes a new algorithm for global optimum。\n2. The analysis of the results is solid.\n\n\n\nWeakness\n1. The incremental contribution of the work is not clearly stated. The authors should highlight their novelty compared with the ones mentioned in the work.\n2. The explanation of the theoretical results is insufficient, making the related parts hard to follow.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "pzSvHKX8nkp", "reviewer": "Reviewer_bkf3", "summary": "The paper considers optimization problems for decision variables with a robust requirement to the observed data.\nThus 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.\nTo 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).\n\nAs 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.\nExperimentally, 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.\n\n", "questions": "Based on the above:\n- Can you motivate the setting: SSG-style decision problems + DRO?\n- Can you compare to a non-DRO (and non-VR) baseline to show the benefit of the distributional approach empirically? \n- Can you motivate the need for speed-up/scalability for the one-time optimization cost?\n- Wouldn't subsampling, e.g. at uniformly, $S$ of $N$ samples (without stratification) be another baseline? How does stratification improve upon this?\n\n", "limitations": "Technological limitations seem sufficiently contextualized.\nThe paper does not discuss the negative societal impact of the work, but I don't think particular consideration for this is needed.\n\n", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is outside my area of expertise, which I reflected by a low confidence score.\n\nStrengths:\n- Overall well written. Small improvements are possible (see \"Presentation\" below).\n- Approach seems mathematically sound.\n- Clustering and stratified sampling seem surprisingly simple yet elegant solutions for speed-ups.\n\nWeaknesses:\n- Evaluation on only 2 datasets (one synthetic, one real).\n- Some motivation is unclear (see below).\n\nPresentation:  \nI found the applications section hard to follow, some small examples or illustrations might benefit the reader.\n\nMotivation & Evaluation:  \nWhile 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. \n\nFurther, 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.\nEven 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).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HPzszYSqowt", "reviewer": "Reviewer_TpEB", "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. \nThey illustrate the benefits of their results on a variety of different applications and illustrate them through numerical data. ", "questions": "Are there potential ways of extending this DRO method (which seems to primarily relay the Duchi reformulation) to other ambiguity sets? \nWhat are the limitations of this particular ambiguity sets?\n", "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. \n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \nQuality: 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. \nClarity: I feel the paper is fine though the compactness with which some results are written makes them difficult to read. \nSignificance: I feel the paper takes an important step in the direction extending the applicability of DRO to more practical problems. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "03_4d6IZNI2", "reviewer": "Reviewer_tnSW", "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.", "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?\n\nWong and Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. ICML 2018.\nRaghunathan et al. Certified Defenses against Adversarial Examples. ICLR 2018.\n\n2. 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.\n\nQi 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?\n2. 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. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. 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.\n2. 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.\n\nWeaknesses:\nThe paper provides a whole package on this particular optimization problem and I do not see obvious weaknesses. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept