USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
Authors: Guangmo Tong
Venue: NeurIPS 2021 Poster (2021)
Keywords: structured prediction
combinatorial optimization
generalization bound

Abstract: Real-world decision-making systems are often subject to uncertainties that have to be resolved through observational data. Therefore, we are frequently confronted with combinatorial optimization problems of which the objective function is unknown and thus has to be debunked using empirical evidence. In contrast to the common practice that relies on a learning-and-optimization strategy, we consider the regression between combinatorial spaces, aiming to infer high-quality optimization solutions from samples of input-solution pairs -- without the need to learn the objective function. Our main deliverable is a universal solver that is able to handle abstract undetermined stochastic combinatorial optimization problems. For learning foundations, we present learning-error analysis under the PAC-Bayesian framework using a new margin-based analysis. In empirical studies, we demonstrate our design using proof-of-concept experiments, and compare it with other methods that are potentially applicable. Overall, we obtain highly encouraging experimental results for several classic combinatorial problems on both synthetic and real-world datasets.

USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems
Guangmo Tong
Department of Computer and Information Sciences
University of Delaware
amotong@udel.cm edu
Abstract
Real-world decision-making systems are often subject to uncertainties that have to be resolved through observational data. Therefore, with combinatorial optimization problems which the objective function is un- known and thus has to be debunked using empirical evidence. In contrast to the common practice that relies on sarning-and-opiiiizatie strategy, we consider the regression between combinatorial spaces, aiming infer high-quality opti- mization solutions from samples of input-solution pairs without the need to learn the objective function. Our main deliverable is universal solver that is able handle abstract undetermined stochastic combinatorial optimization problems. For learning foundations, we present learning-error analysis under the PAC-Bayesian framework using a new margin-based analysis. In empirical studies, we demon- strate our design using proof-of-concept experiments, and compare it with other methods that are potentially applicable. Overall. we obtain highly encouraging experimental results for several classic combinatorial problems on both synthetic and real-world datasets.
frequently confronted
Introduction
Combinatorial optimization problems are not only of great theoretical interest but also central to enormous applications. Traditional research assumes that the problem settings (i.e., objective function) are completely known [1, but the reality is that the underlying system is often very complicated and only partial knowledge (from historical data) is provided. item-user similarities could be unknown
recommendation system, the [2], which makes it impossible to compute the optimal recommendation scheme. In the study of wireless communications, on stochastic node connections 3. incurring extra difficulties in designing management strategies. In the most general sense, we can formalize such scenarios by assuming that the objective function is governed by configuration space associated with an unknown distribution, where goal is to maximize the expected objective. For example, the configuration space may specify possible item-user similarities or candidate network structures. We call such problems undetermined stochastic combinatorial optimization (USCO) problems.
backbone network depends
Since the distribution of the configuration space is unknown, one can adopt the learning-ane and optimization strategy [4], where the unknown distribution first learned from data so that the subsequent optimization problem can be solved using existing methods. While such strategy is natural and proved successful several applications (5). it may require a large amount of data to leam excessive number of parameters for example, the weight between each pair of nodes in network or the similarity between each pair of user and item in a recommendation system. In the worst case, may not even have access to such kind of data (due to, for example, privacy issues
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

[6]. Furthermore, a more technical concern is that the learning process is often independent of the optimization process, causing the situation that optimizing the learned objective function does not produce a good approximation to the true objective function, which is theoretically possible 77 These concerns motivate us think of the settings that can eschew model learning and can address USCO problems aiming right at the approximation guarantees. To this end, we consider the regression between the input space and solution space, and wish to directly compute the solution for future inputs without learning the hidden objective function.
USCO-Solver. In this paper, we present USCO-Solver, general-purpont solver to USCO problems. Our framework is designed through two main techniques: randomized function approximation and approximate structured prediction. The key idea is to construct hypothesis space composed of affine combinations of combinatorial kernels generated using random configurations, from which a large-margin machine trained using input-solution pairs via approximate inference. The main advantage of USCO-Solver is that it can handle an abstract USCO problem as long as an oracle to solve its deterministic counterpart is given. Another significance of USCO-Solver lies in our use of combinatorial kernels, which suggests a novel and principled way for incorporating approximation algorithm into a learning process. In doing so, we are able to handle combinatorial objects easily without worrying much about their indifferentiability or the inherited symmetries, which is often not possible for mainstream learning methods [8].
Theoretical analysis. For USCO-Solver, we present learning-ern error analysis under the PAC- Bayesian framework, where we introduce the multiplicative margin dedicated to bounding the approximation guarantees. In particular, we prove that the approximation ratio of the predictions is essentially bounded by O(a²), whenever the considered problem admits an a-approximation in the deterministic sense. Such result is possible due to the fact the hypothesis space of ISSOO-Solve can approximate the configuration space arbitrarily well. To our knowledge, this is the first result of such kind.
Empirical studies. We conduct experiments with USCO problems concerning three classic combina- torial objects: path, coverage, and matching. On various real-world datasets, we consistently observe that USCO-Solve Solver not only works the way supposed to, but also outperforms other competitors by an evident margin in most cases. In many case studies, near-optimal solutions can be computed without consulting the true configuration distribution.
Supplementary material. The proofs, together with more results and discussions on the experiments, can be found in the supplementary material. In addition, release the experimental materials, including source code, datasets, and pretrain models, as well as their instructions. The experiment materials can be found online"]
2
Preliminaries
2.1 Undetermined stochastic combinatorial optimization problems
We are concerned with abstract combinatorial optimization problem associated with three finite combinatorial spaces: the input space X, the output space V, and a configuration space C; in addition, are given bounded non-negative function f(z y, c) X 3' x C + IR+ denoting the objective value to be maximized. Let O be the set of all distributions over C. We consider stochastic combinatorial optimization problem in the sense that seek maximize f in terms of distribution Ótrue E & rather than a fixed configuration in C. This is desired because the system that defines the objective values is often essentially probabilistie, which may stem from random networks or functions with random parameters. Therefore, the objective function is given by
ff Derae (c) [xx ys e) de.
Fax, y, (true)
Given x and Otraes we are interested the problem
max F(x, y, Ptrue). yEy
We may wish to compute either the optimal solution H Otrue) arg max F(x, y, Strae) or its a-approximation (I, @true) for some E (0. 1). Such problems are fundamental and also
htttp:://githubccomm/ce http://gghhaboooooodddaaaaaooons

---

ubiquitous, ranging from the stochastic version of classic combinatorial problems (9] to applications subject to environmental uncertainties, such as commercial recommendation [TO], viral marketing [II] and behavioral decision making in autonomous systems [12] Taking the stochastic longest path problem [13] as an example, the length of each edge could follow certain distribution, and therefore, each configuration e C' corresponds to weighted graph; in such case, x (u, v) denotes a pair of source and destination, denotes a path from u to v, and f(z, y, c) amounts to the length of y in c.
While the above formulation is natural, we are always limited by our imperfect understanding of the underlying system, which could be formalized by assuming that the distribution óirue over the configuration is not known to us. Since the true distribution Otrue is unknown, the objective function F(z, y, (true) cannot be directly optimized. Essentially, learning process is required. In such a sense, we call these problems undetermined stochastic combinatorial optimization (USCO) problems.
Oracle. In general, USCO problems are made difficult by a) the learning challenges in dealing with the unknown distribution étrue and b) the approximation hardness in solving Equation [ We focus on the learning challenges and thus assume the approximation hardness (if any) can be resolved by oracles. Notice that the objective function (Equation I lies in the positive affine closure of its discretizations, which is
Upe Σ wi f( : my E E , ,9E)]
For some fixed E (0, 1], assume the access polynomial oracle for computing an a- approximation to maximizing any function in the above class, which implies that (x, ø) is obtainable for each æ X' and ø. We can think of as the best ratio that one can obtain by polynomial algorithm, with a = denoting the scenario when the optimal solution can be efficiently computed.
For a vector w = (W1..... wk) E R and a subset C = -fc,,..,Ca cx S of configurations, we denote the induced kernel function
(o(r,y)== (1)
and the associated affine combination as
k
Fw cl,, v) = Σ wi (z) = w Kc(2,y).
Finally, we denote the a-approximation to maxyey Pw, y) as h c(x).
2.2 Learning settings
We consider samples of input-solution pairs:
Sm == { (1i. [m) x2x
where uf := H., @true) is o-approximation associated with the input V,. Such samples intuitively offer the historical experience in which we successfully obtained good solutions to some inputs. From learning perspective, we have formulated a regression task between two combinatorial spaces X' and y. Some formal treatments are given as follows.
Let us assume that the true distribution over X. Our goal is to design a learning framework Ag X' > y that can leverage a set S of samples y for each future X. For a prediction an input x, let l(x, 9) E [0. 1] be a general loss function. Since we aim to examine if 9 is a good approximation to Equation the loss 7 is determined jointly by and x. Consequently, we measure the performance of A by
étrue is unknown but fixed, and there is a distribution Dx
to compute prediction Ag(2)
) associated with
(A,s := Ex As()))(()))
3 A learning framework
In this section, we first present the learning framework and then analyze its generalization bounds. Finally, we discuss training algorithms.
3

---

3.1 USCO-Solver
Following the standard idea of structured prediction 14 15
16, we wish for score function F(x:, y)
such that, for each æ E X. the y E Y that can maximize Fix, y) is a good solution to maximizing F(r, y, (tree). Suppose that we are provided with set Sm of e samples. USCO-Solver consists of the following steps:
Step 1. Select distribution dem E d over C and decide a hyperparameter K E Z.
Step 2. Sample configurations CK = {C1, CK) independently following Pem-
Step 3. Compute seed vector W (11, ... (x) E R using the training data.
Step 4. Sample vector w E RR from @(w] w.T). which is an isotropic Gaussian with identity convariance and a mean of B w, with B being
2mK
2
(4)
minp Tpl a²
|W|
Score function. With Ck and w = [1 wk), we adopt the score function
Fw.Ck (z, v)
Σ w. f(I,3.C)).
Inference. For each input X, the prediction is given by Cw (x), which can be computed by the oracle.
Given that the framework is randomized, the error of interest is C(USCO-Solvers,
(2,1):=Bw-a Cx [1x hw. (x))]-
(5)
So far, have not seen how to determine the distribution dem. the parameter K, and the seed vector
w. We will first analyze how they may affect the generalization bound (Sec. 3.2 and then discuss how to make selections towards minimizing the generalization bound (Sec. 3.3
3.2 Generalization bound
We first study the general loss functions and then consider a particular loss function for measuring the approximation effect in terms of Equation
3.2.1 General loss
The generalization error in general be decomposed into training error and approximation
[7]: the PAC-Bayesian framework gives a particular bound of such kind [8 19. For USCO-Solver, since the decision boundary probabilistic (as is sampled from the seed vector w), the training error has to be bounded by considering the amount by which A w.cx (z;) can deviate from h Cx (z;)
for each training input z;- To this end, we measure the similarity of two outputs yı E y through the concept of margin, which is given by
m(w, Cx I, F1, 32) F..cx (I, v1) Fw.Cix U2).
(6)
For an input x, the potentially good solutions are those in
T(I, w. Ck) == {y E m(w, CK, Nr Nw. (z). S Pw.cn (x (x))
Intuitively, these are the solutions that are similar to the suboptimal one h Cg (x) in terms of the score function associated with and Cx. For each w, the training error then taken by the worst-case loss over the possible y within the margin, which is
L(w, CK. Sm)
m Σ
max 111,, y).
veI(x....Ox)
Notice that the loss L(W, Cx. Sm) associated with the seed vector w can be used to bound the training error with respect to w, provided that the predictions are within the margin (with high probability). With such intuitions, we have the first learning bound.

---

Theorem 1. For each w. Ck, and 8 > 0, with probability at least - ô, we have
[[USCO-Solvers, Dx,1) S L(w, CK. Sm)
W
+
In
2 ||
min,
4||
/iyl )
+ In
m
2(m
The proof is inspired by the PAC-Bayesian framework 20
21
applying to approximate structured
prediction 222 19 where our contribution lies in the analysis of the multiplicative margin.
3.2.2
Approximation loss
In line with Equation 2
natural loss function is the approximation ratio of the predictions, which
is
Tapprox (z, 9) == - min( F(x. U, (true)
1) E [0.
(
F(xr, (I, @truc)
Essentially, we seek to generalize the approximation guarantee from the training samples to future inputs, and the guarantees the training samples are limited by the oracle. With such, we hope to compare the generalization error under lapprox with a. According to Theorem [1 with an unlimited supply of training data (i.e., m + 20), the generalization error is bounded by Z(w, CK, Sm). and therefore, the learning error of the ERM solution is concentrated on
inf Ex
max (w,((,
lapprox ( y)
Relating the above quantity with a not possible for the general case because the score function Pw,cs Cx (x, y) defining the margin independent of the objective function F(x, y, (towe) inducing the error. However, more concrete results can be obtained for the approximation loss, by leveraging subtle relationship between our construction of the kernel function and the stochastic combinatorial optimization problem. The next result characterizes the relationship between Equation 9 and
Theorem 2. Suppose that f(z, y, c) E [A, B] and sup 0 and den, when K is no less than
dermefe) Dem
For each e > 0, 1 > 82 >
2. C B²
max In |n
(10)
2. 83 A2
with probability at least 1 - 81 over the selection of CK. there exists w such that
(approx v) < (1+e) -2l-elo () 2 1- 62.
Pr Z>Dx vEI(K..OOx))
max
(1 E)
The above result shows that the approximation ratio in generalization is essentially bounded by a²/2. It is intuitive that the bound on K depends on the deviation of Φem from dtrue (i.e., C), the range of the objective function (i.e.. B/A), and the size of the output space.
3.3 Training algorithms
Theorems 1 and 2 have explained how m, K and dem may affect the generalization performance in theory. Practically, K can be conveniently taken as a hyperparameter, and dem is often the uniform distribution over C' (unless prior knowledge about dirwe is given). Now, for the four steps Sec. 3.1 the only problem left is to compute the seed vector w.
Relaxed margin. While Theorem indicates that there exists a desired weight, are not able to search for such a weight directly because the loss function lapprox is not accessible under our setting. In practice, one adopt the zero-one loss other loss function preferred by the considered problem. For example, when the output space a family of sets, the loss function can be induced by the set similarity (23). For general loss function ((r;, y). Theorem 1 suggests computing the weight
w by minimizing the upper bound L(W, Ck, Sm) + [[
min max (1, 8) 1 1(x,, w, Ck)) +//wl/
5

---

where 1 is the indicator function. Notice that the above problem is not only non-convex but also complicated by the fact that w and hw,co ww (z) are convoluted with each other. For ease of optimization, relaxed margin will be useful, seen shortly. Notice that have Fw,cs (2i, h &w,Ck (24)) 2 Fw (Ii, ), and therefore, for each 3) E 1(xi, w, Cx) implies that
a² y E I( w. Ck) (v E 2 Fw,cx (14, Fw,Ck (Te, v) 50].
where the new margin I measured with respect to of instead of l Cx (xi). Immediately, we have I(z;, w. Ck) S I(z,, w, Ck), which indicates that the error is further upper bounded by
max max (xx v) (y I(z,, w, Ck)) + l/w/|?
(11)
which is less challenging minimize.
Large-margin training, Seeking a large- margin solution and scaling the margin proportional to the loss function, Equation II
amounts to solving the following problem:
C' 2m
min
|||
Σ<
&
a² w
Kex (ft w Kox (2,,8) 2 11,,1(1,,,) v) E.s ViE [m], Vy V.y y. + of
s.t.
w w
where C and y hyperparameters. Notably, this is the vanilla structured SVM 16 24
Viewing KCx as a score function, the constrains enforces that the solution yf provided by the training data should have high score. The above formulation appears to be standard quadratic programming, but it in fact contains | number constrains, which can be prohibitively large (c.g.. exponential in the coding length of the configuration). Since the constraints equivalent to
a² w Kox (Is, vf) + &i, Vi e [m],
max w Kox (I v) + (I v) S yEy
2
the number constraints could be reduced as linear in sample size we can effectively solve the loss-augmented inference problem:
w/ KCx (2t, 3) + ((z1,)) 2)
yEy
For the zero-one loss, this is exactly to solve max T Kc2, x (z,, v), which, to delight, can be solved using the oracle in Sec. [.1 Once such loss-augmented inference problem can be solved, the entire programming
be readily solved by existing methods, such as the cutting cutting-plane algorithm 25 This completes the learning framework.
Remark 1. While our discussion so far is focused on maximization problems, the theoretical analysis can be adapted to minimization problems easily. In the training part for minimization problems, the major adaption to reverse w Kcx (2,, and w Kcx (I,, y), which also turns the loss- augmented inference into minimization problem.
For the stochastic shortest path problem, dem denotes a distribution over a collection of weighted graphs, and assuming the weights are nonnegative, we may use Dijkstra algorithm the oracle, as maxzey Fw.c(a, y) amounts to computing the shortest path in the combining graph the sampled weighted graphs.
Remark 2.
4 Empirical studies
This section presents experiments across a variety combinatorial problems, including stochastic shortest path (SSP), stochastic set cover (SSC), and stochastic bipartite matching (SBM). In to supporting the theoretical analysis, our empirical studies are of interest also because none of the existing methods is known to be effective for solving any USCO problem.
addition

---

Table 1: SSP results. Each cell shows the mean of performance ratio with the standard deviation.
UCSO-Solver
Other Methods
K
16
160
1600
3200
6400
NB
DSPN
Base
eepp
1.942 (0.11)
1.952 (0.00) 1.565 (0.02)
1.129 (001)
1.148 (0.00)
2.064 (0.16) 2.009 (0.12) 1.956 (0.10)
Col
Otruc
1.300
1.015 (..0)) 1.016 (001)) 1.010 (oon) 1.022 (0.01)
K
80
160
640
3200
6400
NB
DSPN
Basc
Deep
1.613 (0.0))
1.571 (0.0))
1.353 (0.0)) 1.303 (002)
1.192 (0.01)
3.155 (0.35) 2.469 (0.07) 2.853 (0.28)
NY
Ótrue
1.205 (0.01)
1.177 (0.00) 1.017 (0.01) 1.031 (001) 1.048 (0.01)
K
160
1600
3200
6400
9600
NB
DSPN
Base
dexp
7.599 (0.15)
5.829
(0.22) 5,858 (0.18) 4.613 (0.18)
4.323 (0.19)
10.08 (0.57) 7.451 (L.55) 10.92 (2.45)
Kro
Ótrue
1.361 (0.09) 1.026 oon 1.022 (0.1) 1.042 (001) 1.051 (0.01)
Evaluation metric. For each training pair (x,,0,) and a prediction ÿ. the performance ratio is defined F(a.y? &xrue) for maximization problems and F(zz:))tess)) F
Flav.y" (errue) for minimization problems. Therefore, lower is better both cases. The performance measured over five random testings. We here present the main experimental settings and discuss key observations, deferring the complete analysis to Appendix
4.1 Stochastic shortest path (SSP)
Problem definition and oracle. In the stochastic version of the shortest path problem, given source u and a destination v in graph G (V, E), we wish to find the path (from u to v) that is the shortest in terms of a distribution over the possible edge weights. In this case, the configuration space C denotes family of weighted graphs associated with a distribution Ptrue. the input x = (u, v) is a pair of nodes, the output y is path from and v, and f(z, y, c)c) denotes the length of y in graph c. We construct instances where the edge weights are non-negative, and thus, each function in Equation 3 be minimized optimally using the Dijkstra algorithm (26), which is the oracle we samples and solve the inference problem in USCO-Solver.
generate
Instance construction. To setup concrete instance, we first fix a graph structure, where two real-world graphs (Col and NY) and one synthetic graph (Kro) are adopted. Col and NY are USA road networks complied from the benchmarks of DIMACS Implementation Challenge 277 and Kro a Kronecker graph (8)). Following the common practice (29), we assign each edge Weibull distribution with parameters randomly selected from { 10). which together with the graph structure induces the configuration space and ótrue- For each instance, we generate the pool of all possible input-solution pairs (æ, y), where, for input (u, v), y is the optimal solution to minyey F F(x, y, Φtrue). For each considered method, we randomly select 160 training samples and 6400 testing samples from the pool.
Implementing USCO-Solver. We setup two realizations (dezp and òirue) of dem that will be used in USCO-Solver. Deap assigns each edge in E an exponential distribution normalized in [1, 1e5), and Otrue exactly the true underlying distribution that defines the instance. Notice that @trae is not obtainable under our learning setting, and it is used only to verify our designs. For each distribution, we sample a pool of 10000 configurations (i.c., weighted graphs). The number of configurations (i.c., K) is enumerated from small to large, with different ranges for different datasets. Given the size K, the configurations are randomly selected from the pool in each run of USCO-Solver. We use the zero-one loss, and the training algorithm is implemented based on Pystruct [30].
Implementing other competitors. For a baseline, we implement the Base method which, given an input x = (u, v), outputs the shortest path from u to in G where the edge weights are randomly sampled from [0, 1]. Conceptually, our problem can be perceived as a supervised learning problem from V x V to the space of the paths, and thus, off-the-shelf learning methods appear to be applicable, which however turns out to be non-trivial. We managed to implement two methods based respectively
on Naive Bayes (NB) (1] and Deep Set Prediction Networks (DSPN) [32], where the idea is to
7

---

Table 2: SSC results. The table shows the results on two datasets Cora and Yahoo.
UCSO-Solver
Other Methods
K
16
160
320
640
GNN
DSPN
Rand
Dunk Otruc
1.480 (0.12) 1,452 (0.12)
1.230 (0.06)
1.147 (0.06)
1.083 (0.01)
1.036 (0.02)
1.782 (0.85) 16.57 (0:12)
Cora
1.029 (0.0) 1.033 0.01)
1.003 (c0.0)
1.000
(00.1) 1.000 (<0.01)
K
16
160
320
640
GNN
DSPN
Rand
Puni
1.294 (0.03) 1.356 (0.03)
1.151 00.01
1.146 (0.07)
1.093 (0:03)
1.076 (0.10 1.387 (0.142) 6.58 (0.17)
Yahoo
Otrue
1.036 (0.02)
1.013 (0.01) 1.003 (=0.01) 1.009 (-0001) 0.999 (<0.01)
leverage them to learn the node importance in the shortest path and then build the prediction based on the node importance.
Observations. The main results are presented in Table 1 We highlight two important observations: a) the performance of USCO-Solver smoothly increases when more configurations are provided, and b) when fed with configurations from the true distribution Otraes USCO-Solver can easily output near-optimal solutions on all the datasets. These observations confirm that USCO-Solver indeed functions the way is supposed to. In addition, the efficacy of USCO-Solver is significant and robust in terms of the performance ratio. On datasets like Col and NY, it can produce near-optimal solutions using Pezp. Meanwhile, other methods are not comparable USCO-Solver, though DSPN offers non-trivial improvement compared with Base on NY and Kro. It is also worth noting that different instances exhibit different levels of hardness with respect to the number of configurations needed by USCO-Solver. 3200 configurations are sufficient for USCO-Solver to achieve low ratio on Col, while the ratio is still larger than 4.0 on Kro even though 9600 configurations have been used. See Appendix B.2 for complete discussion.
4.2 Stochastic set cover (SSC)
In network science, coverage problems often require to compute set of terminals that can maximally cover the target area [33; in applications like recommendation system or document summarization [3], one would like to select certain number of items that can achieve the maximum diversity by covering topics as many as possible. These problems can be universally formulated as a maximal coverage problem (35). where each instance is given by family U of subsets of ground set, where our goal is to select a k-subset of U of which the union is maximized. In its stochastic version, we assume that item will appear in subset with certain probability 36) The oracle we use is the greedy algorithm, which is a (1 approopproiiiatiinn [37]. We construct two instances based on two real-world bipartite graphs Cora (38) and Yahoo [39]. Similar the setup for SSP, we first generate the ground truth distribution Øtrue and then generate samples. We implement two learning methods based on Graph neural network (GNN) and DSPN, together with a baseline method Rand that randomly selects the nodes in ÿ. For USCO-Solver, we consider distribution Puni that generates a configuration by generating subsets uniformly at random. See Appendix B.3 for details.
The results are presented in Table 2 First, the observations here are similar to those in the SSP problem LLSCO-Solver works in manner as we expect, and it can produce high-quality solutions when a sufficient number of configurations are provided. We can see that GNN and DSPN are also effective compared with Rand, which suggests that, compared to SSP, SSC is much easier for being handled by existing learning methods.
4.3 Stochastic bipartite matching (SBM)
Our last problem is bipartite matching, which is regularly seen in applications such as public housing allocation 440, semantic web service [41 and image feature analysis [42]. We consider the minimum weight bipartite matching problem. Given a weighted bipartite graph G (L, R, E), the input I = (L* R*) consists of two subsets L* C and Re C with |L'1 = |R²1, and the output is perfect matching between I." and R² such that the total cost is minimized. In other words, bijection between I." and R In its stochastic version, the weight w. for each edge e E follows certain distribution, and we aim to compute the matching that can minimize the expected
8

---

Table 3: SBM results with Puni and @truc.
16
160
1600
3200
6400
12800
19200
Rand
Duni
3.627 (0.1)) 3.582 (001) 3.407 (0.0)) 3.261 (o01) 3.107 (001) 2.874 (0.0) 2.696 (0.01)
3.670 (0.01)
Otruc
1.029 (001)) 1.033 (001) 1.003 (<0.01) 1.000 (c0.0)) 1.000 (c001)
Table 4: SBM results with d10s ds. Φ1 and Φ0.3.
16
160
320
640
16
160
320
640
Φ10
4.889 (009)
3.602 (0.06)
1.831 (0.04) 1.271 (0.01)
Φ 4.321 (0.07)
1.403 (o01)
1.120 (e.0)) 1.040 (<0.01)
11
1.038 (<00l) 1.008 (4001) 1.003 (<0.0)) 1.002
60.3 1.008 (<0.0)) 1.003 (c0.0) 1.002 (<001) (.002(c00))
cost Fxx y,, Strue). Notice that the minimum weight bipartite matching problem can be solved in polynomial time by linear programming [43], which is natural oracle to use in USCO-Solver. We adopt synthetic bipartite graph with 128 nodes. The weight we for each edge E follows a Gaussian distribution N (jte, Ge) with Me sampled uniformly from [1, 10] and a. = 0.3 Me, which induces the true distribution Oerue- See Appendix [.44 for details.
Results under duns- For USCO-Solver, we consider dunt that generates the configuration e by giving each edge a weight from [1, 10] uniformly at random. We also test USCO-Solver with features from the true distribution Strue. The baseline method Rand produces for a given input x = (L* by randomly generating permutation of Rt. The result of this part is shown in Table We see that USCO-Solver can again produce a better ratio when more configurations are provided, but different from SSP and SSC, cannot achieve a ratio that is close 1 even when 19200 configurations have been used. Plausibly, this is because the output space of SBM is more structured compared with SSP and SSC.
Incorporating prior knowledge into USCO-Solver. For problems like bipartite matching where uniform configurations cannot produce near-optimal solution, it would he interesting to investigate if USCO-Solver can easily benefit from domain expertise. To this end, given a parameter q E 1,,3,,,5, 10). we consider the distribution o, that samples the weight for edge from [Me - q- Me, + q Mee, which accounts for the case that a confidence interval of the weight we is known. The performance ratios produced by such distributions are shown in Table As we can see from the table, the result indeed coincides with the fact that the prior knowledge is strong when is small. More importantly, with the help of such prior knowledge, the ratio can reduced to nearly using no more than 160 configurations under Φ1 while under the uniform distribution @uni. the ratio was not much better than Rand with the same amount of configurations (as seen Table 3).
5
Further discussions
Related work. The
framework has been used widely (e.g.. 44 45 46
47
48
For example, Du er al. 49 and He al. (50] study the problem of learning influence function recision-focused learning framework based on continuous relaxation of the discrete problem. In contrast to these works, we consider the input-solution regression without attempting to learn the objective function. similar setting was adopted [52 for studying a special application in social network analysis, but our paper targets abstract problems and provides generalization bounds on the approximation ratio. There have been recent efforts to develop learning methods that can handle combinatorial spaces (c.g., 54 32), where the key is to preserve the inherited combinatorial structures during the learning process. Our research is different because the problem we consider involves a hidden optimization problem; in other words, we target the optimization effect rather than the prediction accuracy. Our research is also related to the existing works that attempt to solve combinatorial optimization problems using reinforcement learning [55 56 57 58); however, the objective function is known in their settings, while we study the model-free setting.
which is used in influence maximization; recently. Wilder et al. (51) proposes
Limitations. Our theoretical analysis is based on the assumption that is approximation solution in each input-solution (ar, y), but in practice, may be impossible to prove such guarantees for real datascts. Thus, it is left to experimentally examine USCO-SA Solver using the training pairs (I, y) where

---

is produced using heuristic but not approximation algorithms. In another issue, we have shown that DSSCO-Solver effective for three classic combinatorial problems, but remains unknown if USCO-Solver is universally effective, although it is conceptually applicable to an arbitrary USCO problem. In addition, our experiments do not rule out the possibility that off-the-shelf learning methods can be effective for some USCO problems (e.g., SSC), which suggests a future research direction. Finally, we hope to extend our research by studying more practical applications involving highly structured objects, such as Steiner trees, clustering patterns, and network flows. See Appendix C for a more comprehensive discussion.
Acknowledgments and Disclosure of Funding
We thank the reviewers for their time and insightful comments. Funding in direct support of this work: support from the University of Delaware.
References
[T] V. V. Vazirani, Approximation algorithms. Springer Science & Business Media, 2013.
[2] H.-N. Kim and Saddik, "A stochastic approach to group recommendations social media systems," Information Systems, vol. 50, pp. 73-93, 2015.
[3] Y. Deng, L.. Wang, M. Elkashlan, A. Nallanathan, and R. K. Mallik, "Physical layer security in three-tier wireless sensor networks: A stochastic geometry approach," IEEE Transactions on Information Forensics and Security, vol. 11, no. 6, pp. 1128-1 1138, 2016.
[4] E. Horvitz and T. Mitchell, "From data to knowledge to action: A global enabler for the 21st century," arXiv preprint arXiv:2008.0000 2020.
[5] F. Horvitz, "From data to predictions and decisions: Enabling evidence-based healthcare," Computing Community Consortium, vol. 6, 2010.
[6] A. Askinadze and S. Conrad, "Respecting data privacy in educational data mining: an approach to the transparent handling of student data and dealing with the resulting missing value problem," " in 2018 IEEE 27th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE). IEEE, 2018, pp. (60-164.
[7] E. Balkanski, A. Rubinstein, and Y. Singer, "The limitations of optimization from samples," in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 1016-1021
[8] Y. Zhang, J. Hare, and A. Prügel-Bennett, "Fspool: Learning set representations with featurewise sort pooling," in International Conference on Learning Representations, 2019.
[9] L. Bianchi, M. Dorigo, L. M. Gambardella, and W. J. Gutjahr, "A survey metaheuristics for
stochastic combinatorial optimization," Natural Computing, vol. 8, no. 2, pp. 239-287, 2009.
[10] Y. Kim and K. Shim, "Twitobi: A recommendation system for twitter using probabilistic modeling," in 2011 IEEE 11th International Conference on Data Mining. IEEE, 2011, pp. 340-349.
[11] Leskovec, L. A. Adamic, and B. A. Huberman, "The dynamics of viral marketing," ACM Transactions on the Web (TWEB), vol. 1, no. 1, pp. 5-es, 2007.
[12] W. Chen and L. Kloul, "Stochasti modelling of autonomous vehicles driving scenarios using pepa," in International Symposium on Model-Based Safety and Assessment. Springer, 2019, pp. 317-331.
[13] E. Ando, H. Ono, K. Sadakane, and M. Yamashita, "Computing the exact distribution function of the stochastic longest path length in a dag." in International Conference Theory and Applications of Models of Computation. Springer, 2009, pp. 98-107.
[14] H. Daumé, J. Langford, and D. Marcu, "Search-basee structured prediction," " Machine learning. vol. 75, no. 3, pp. 297-325, 2009.
[15] D. Weiss and B. Taskar, "Structured prediction cascades." in Proceedings of the Thirleenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 2010, pp. 916-923.
10

---

[16] B. Taskar, V. Chatalbashev, D. Koller, and C. Guestrin, "Learning structured prediction models: large margin approach," in Proceedings of the 22nd international conference on Machine learning, 2005, pp. 896-903.
[17] S. Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
[18] D. McAllester, "Generalization bounds and consisteney," Predicting structured data, pp. 247- 261, 2007.
[19] Y. Wu, M. Lan, S. Sun, Q. Zhang, and X. Huang, "A learning emror analysis for structured prediction with approximate inference," in Proceedings of the 31t International Conference on Neural Information Processing Systems, 2017, pp. 6131-6141.
[20] D. A. McAllester, "Some pac-bayesian theorems." Machine Learning, vol. 37, no. 3, PP- 355-363, 1999.
[21] D. McAllester, "Simplified pac-bayesian margin bounds," in Learning theory and Kernel machines. Springer, 2003, pp. 203-215,
[22] A. Kulesza and F. Pereira, "Structured learning with approximate inference," 2008.
[23] S. Zhou, J. Wang, R. Shi, Q. Hou, Y. Gong, and N. Zheng, "Large margin learning in set-to-set similarity comparison for person reidentification," IEEE Transactions on Multimedia, vol. 20,
no. 3, pp. 593-604, 2017.
[24] I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun, and Y. Singer, "Large margin methods for structured and interdependent output variables." Journal of machine learning research, vol. no. 9, 2005.
[25] T. Joachims, T. Finley, and C. Yu, "Cutting-plane training of structural svms," Machine learning, vol. 77, no. pp. 27-59, 2009.
[26] Cormen, E. Leiserson, R. L.. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2009.
[27] C. Demetrescu, A. V. Goldberg, and D. S. Johnson, "Implementation challenge for shortest paths." Encyclopedia of Algorithms, vol. 15, p. 54, 2008.
[28] Leskovec, D. Chakrabarti, J. Kleinberg. C. Faloutsos, and Ghahramani, "Kronecker graphs: an approach to modeling networks." Journal of Machine Learning Research, vol. 11, no. 2, 2010.
[29] H. Rinne, The Weibull distribution: a handbook.
CRC press, 2008
[30] A. C. Müller and S. Behnke, "Pystruct: learning structured prediction in python." Mach.
Learn. Res., vol. 15, no. 1, pp. 2055-2060, 2014.
[31] K. P. Murphy, Machine learning: a probabilistic perspective.
MIT press, 2012.
[32] Y. Zhang, J. Hare, and A. Prugel-Bennett, "Deep set prediction networks," in NeurlPS, 2019,
pp. 3207-3217.
[33] C.-F. Huang and Y.-C. Tseng, "The coverage problem in a wireless sensor network," Mobile networks and Applications, vol. 10, no. 4, pp. 519-528, 2005.
[34] H. Lin and J. Bilmes, "A class of submodular functions for document summarization." in Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 2011, pp. 510-520.
[35] S. Khuller, A. Moss, and J. S. Naor, "The budgeted maximum coverage problem," Information processing letters, vol. 70, no. 1, pp. 39-45, 1999.
[36] A. Deshpande, L. Hellerstein, and D. Kletenik, "Approximation algorithms for stochastic boolean function evaluation and stochastic submodular set cover," in Proceedingy of the twenty- fifth annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2014, pp. 1453-1466.
[37] S. Fujishige, Submodular functions and optimization. Elsevier, 2005.
[38] Sen, G. Namata, M. Bilgic, L.. Getoor, B. Galligher, and T. Fliassi-Rad, "Collective classifica- tion in network data," Al magazine, vol. 29, no. 3, pp. 93-93, 2008.
[39] "Yahoo! search marketing advertiser bidding data." https://webccoop.smmbbb........

---

[40] N. Benabbou, M. Chakraborty, X.-V. Ho. J. Sliwinski, and Y. Zick, "Diversity constraints in public housing allocation," " in 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018), 2018.
[41] U. Bellur and R. Kulkarni, "Improved matchmaking algorithm for semantic web services based on bipartite graph matching," in IEEE international conference on web services (ICWS 2007). IEFF, 2007, pp. 86-93.
[42] Y.-Q. Cheng, V. Wu, R. Collins, A. R. Hanson, and E. M. Riseman, "Maximum-weight bipartite matching technique and its application in image feature matching." in Visual Communications and Image Processing 96, vol. 2727. International Society for Optics and Photonics, 1996, pp.
453 462.
[43] H. W. Kuhn, "The hungarian method for the assignment problem," Naval research logistics quarterly, vol. 2, no. 1-2, pp. 83-97, 1955.
[44] A. N. Elmachtoub and P. Grigas, "Smart "predict, then optimize"," Management Science, 2021.
[45] Y.hh. Kao, B. Roy, and X. Yan, "Directed regression," Advances in Neural Information Process- ing Systems, vol. 22, pp. 889-897, 2009.
[46] L. Donti, B. Amos, and Z. Kolter, "aase end-to-end model learning in stochastic optimization." arXiv preprint arXiv: 04522,, 2017.
[47] G.- Y. Ban and C. Rudin, "The big data newsvendor: Practical insights from machine learning." " Operations Research, vol. 67, no. pp. 90-108, 2019.
[48] D. Bertsimas and N. Kallus, "From predictive to prescriptive analytics," Management Science, vol. 66, no. 3. pp. 1025-1044, 2020.
[49] N. Du, Y. Liang, M. Balcan, and L.. Song. "Influence function learning in information diffusion networks," " in International Conference on Machine Learning. PMLR, 2014, pp. 2016-2024.
[50] X. He, K. Xu, D. Kempe, and Y. Liu, "Learning influence functions from incomplete observa- tions," arXiv preprint arXiv: 1.02305, 2016.
[51] B. Wilder, B. Dilkina, and M. Tambe. "Melding the decisiinsssnns pipeline: Decision-focused learning for combinatorial optimization." " in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, 2019, pp. 1658-1665.
[52] G. Tong, "Stratlearner: Learning a strategy for misinformation prevention in social networks," Advances in Neural Information Processing Systems, vol. 33, 2020.
[53] H. Maron, O. Litany, G. Chechik, and E. Fetaya, "On learning sets of symmetric elements," in International Conference on Machine Learning. PMLR, 2020, pp. 6734-6744.
[54] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póczos, R. R. Salakhutdinov, and A. J. Smola, "Deep sets," in NIPS, 2017.
[55] E. B. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song, "Learning combinatorial optimization algorithms over graphs," in NIPS, 2017.
[56] Y. Li, "Deep reinforcement learning: An overview," arXiv preprint arXiv:1701.07277 2017.
[57] M. Nazari, A. Oroojlooy, L. V. Snyder, and M. Takáč, "Reinforcement learning for solving the vehicle routing problem," arXiv preprint /rXiv:/802.04220 2018.
[58] Y. Bengio, A. Lodi, and A. Prouvost, "Machine learning for combinatorial optimization: a methodological tour d' horizzo,," " European Journal of Operational Research, 2020.
[59] C. McDiarmid, "On the method of bounded differences," Surveys in combinatorics, vol. 141, no. 1, pp. 148-188, 1989. [60] T. N. Kipf and M. Welling, 'Spmi-supervised classification with graph convolutional networks," arXiv preprint 1rXiv:1609.0200000 1609.02997 2016.
[61] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, Peterson, W. Weckesser, J. Bright, S. van der Walt, M. Brett, J. Wilson, K. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, i. Polat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and SciPy 1.0 Contributors, "SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python," " Nature
Methods, vol. 17, pp. 261-272, 2020.
12

---

[62] Y. Li, R. Bu, M. Sun, W. Wu, X. Di, and B. Chen, "Pointenn: Convolution on x- x-transformed points," Advances neural information processing systems, vol. 31, pp. $20-830, 2018.
[63] Lee, Lee, J. Kim, A. Kosiorek, Choi, and Y. W. Teh. "Set transformer: A framework neural networks," in International Conference on
for attention- based Machine Learning. PMLR, 2019, pp. 3744-3753.
[64] Y. Wang and J. M. Solomon, "Deep closest point: Learning representations for point cloud registration," in Proceedings of the IEEF/CVF International Conference on Computer Vision,
2019, pp. 3523-3532.
[65] M. Weiler, M. Geiger, M. Welling, W. Boomsma, and T. Cohen, "3d steerable enns: Learning rotationally equivariant features in volumetric data," arXiv preprint 187.005507.0254,, 2018.
[66] A. Parmentier, "Learning to approximate industrial problems by operations research classic problems." Operations Research, 2021.
[67] M. Vlastelica, A. Paulus, V. Musil, G. Martius, and M. Rolínek, "Differentiation of blackbox combinatorial solvers," arXiv preprint arXiv:1912.02117 2019.
[68] Y. Bengio, Frejinger, A. Lodi, R. Patel, and Sankaranarayanan, learning-based algorithm to quickly compute good primal solutions for stochastic integer programs," in International Conference on Integration of Constraint Programming. Artificial Intelligence, and Operations Research. Springer, 2020, pp. 99-111.
[69] Nair, D. Dvijotham, I. Dunning, and O. Vinyals, "Learning fast optimizers for contextual stochastic integer programs." in UAI, 2018, pp. 591-600.
[70] A. Sauer, N. Savinov, and A. Geiger, "Conditional affordance learning for driving in urban environments," in Conference on Robot Learning. PMLR, 2018, pp. 237-252.
[71] C. Chen, A. Seff, A. Kornhauser, and J. Xiao, "Deepdriving: Learning affordance for direct perception in autonomous driving," in Proceedings of the IEEE international conference on computer vision, 2015, pp. 2722-2730.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ?.
Did you include the license to the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. 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] Please Sec.
(c) Did you discuss any potential negative societal impacts of your work? [No] We study abstract stochastic combinatorial problems, focusing on learning foundations. Thus, we believe our research foundational and not tied to particular applications.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
13

---

(b) Did you include complete proofs of all theoretical results? [Yes] They are in appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [Yes] Due to the 100MB limitation, we provide code, data, and pretrain models for selected experi- ments in the supplemental material. The entire project will be published later after the reviewing period.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they chosen)? [Yes] To our best, have provided all the training details.
(c) Did you report error bars (e-g.. with respect the random seed after running experi- ments multiple times)? [Yes] We report standard deviations.
(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] Such information can be found in appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes] We use public dataset and source code following their licenses. (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] Our dataset is purely numerical and does not have any personally identifiable information offensive content.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not use crowdsourcing, and research is not related to any human subject.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "bSk_En1jYdF", "reviewer": "Reviewer_SRyD", "summary": "The paper presents USCO-Solver, a new solver that is able to handle abstract undetermined stochastic combinatorial optimisation problems. The main contribution is a learning framework that allows the solver to infer high quality solutions from samples of input-output pairs without having to learn the objective function. This approach seems to contrast the well known learning-and-optimisation strategy. An empirical evaluation on several classic combinatorial problem domains demonstrate the effectiveness of the proposed approach.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "The paper is fairly well written and organised. The quality of the presentation is overall fairly good. However, there are a couple of issues that I think need to be addressed.\n\n1. The solver assumes the existence of an oracle to do the actual inference, namely to compute the prediction for each input x. This may be a serious limitation because many realistic problems it's actually very hard to compute a good quality solution. Moreover, it may actually be impossible to come up with a reliable oracle unless the decision maker knows enough about the structure of the optimisation problem. Perhaps a deeper discussion on the choice of the oracle is warranted. \n\n2. I suggest accompanying the presentation of the learning framework in section 3 with a more concrete running example (maybe use the stochastic shortest path example from the experimental section). This would be really helpful to get a better understanding of the proposed approach.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are addressed in the paper and there is no potential negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "ZfMUlBjKFQ", "reviewer": "Reviewer_ToTX", "summary": "In this paper, the authors propose USCO-Solver, a unified approach to solving stochastic combinatorial optimization by learning the weights of the kernel function. The learning step is similar to SVM. The authors conduct experiments on 3 stochastic problems. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "Strengths of this paper:\n1. A unified approach for stochastic combinatorial optimization is demanding and appealing.\n1. Detailed analysis of training and generalization bounds of the proposed method.\n1. Involving an oracle (polynomial-time solver) in the learning to optimization pipeline.\n\nThe limitations of this paper are mainly about the experiment part:\n1. The problems considered in this paper do not fully reflect the ubiquitous challenging NP-hard combinatorial problems. The non-stochastic versions of shortest path and bipartite matching both can be solved in polynomial time. I have some concerns about the performance when generalizing USCO-Solver to more challenging combinatorial problems, especially the authors claim that they propose a general approach.\n1. The baseline linear programming method [43] is missing for the stochastic bipartite matching experiment.\n\nSome points that are unclear to me:\n1. The authors write that their algorithm learns a mapping from the input space to the solution space. However, it seems that only a combination of kernels is learned, and the mapping to the solution space is done by the oracle. In my opinion, only the methods like [55] which directly predict the solution by a deep neural network can be regarded as learning a mapping from the input space to the solution space.\n1. Why shall we sample $\\bar{\\mathbf w}$ in Step 4 of the proposed approach? It seems that the analysis in Sec 3.2 is not related to $\\bar{\\mathbf w}$, but mainly related to $\\widetilde{\\mathbf w}$.\n1. The results in Table 2 seem to be computed by optimal solutions. How do you compute the optimal solution for Stochastic set cover (SSC) since the oracle is an approximate algorithm? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "NE36zGMcvD", "reviewer": "Reviewer_pDuR", "summary": "This paper proposes a learning method, USCO_Solver, to solve undetermined stochastic combinatorial optimization problems. Approximation errors of the proposed method are established, and empirical results demonstrate the success of the proposed method. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "This paper is well written and theoretically sound. Personally, I like the error analysis and the adoption of large-margin training. I only have two questions listed below:\n\n1. Running time is an important aspect in solving optimization problems. How is the running time of the proposed USCO Solver compared to baselines? \n\n2. Is it possible to train the USCO Solver on one graph (problem instance), and test it on multiple different graphs? If this can be done, the method would be more useful and of practical relevance. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "5Q-6ARbVVr", "reviewer": "Reviewer_fagS", "summary": "This paper proposes a framework for learning to predict approximate solutions to stochastic combinatorial optimization problems. The class of problems is referred to as \"undetermined\" stochastic combinatorial optimization. \"Undetermined\" here refers to the following assumption on the available training data: each data point is a pair (x, y), where x is the input to the stochastic optimization problem (e.g., source-target pairs in an s-t shortest path problem on a fixed graph), and y is an approximate solution; notice how information about the probability distribution over which the true stochastic objective function is defined (e.g., edge weights) is not available in the training set (neither via a set of sample scenarios nor a generator), hence \"undetermined\".\n\nUSCO-Solver does the following in the training phase: it selects an arbitrary distribution over the unknown stochastic parameters of the problems (e.g., edge weights in a graph), samples K configurations, then searches for a weight vector for the K samples such that the true solution (y) is also near-optimal in another optimization problem whose objective function is a linear combination of the K configurations' objectives. This training problem is framed as a structured prediction task which is amenable to structured SVM-style optimization algorithms. Key to the training is the use of an oracle for the deterministic counterpart of the stochastic problem.\n\nExperiments on randomly generated datasets for stochastic shortest path, set cover, and bipartite matching show that USCO-Solver performs significantly better than \"direct\" ML methods that are trained to simply fit the training set without regard to the combinatorics or stochastic nature of the true optimization problem.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_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": "Assessment: I find it truly remarkable that any bounds can be derived for the proposed method, though I am unable to verify the proofs fully. The USCO setting is very challenging and USCO-Solver is simple, principled, and effective in practice. However, the USCO setting is also not realistic, which limits the impact and applicability of USCO-Solver.\n\nOriginality: There is a closely related line of work by Parmentier [Parmentier, A. (2021). Learning to approximate industrial problems by operations research classic problems. Operations Research.] which is not discussed. Although this paper appeared only recently in OR, I believe earlier versions have been online for 2+ years (https://hal.archives-ouvertes.fr/hal-02396091/). Other relevant work which could potentially be applied to USCO problems and compared to include:\n- [Pogančić, Marin Vlastelica, et al. \"Differentiation of blackbox combinatorial solvers.\" International Conference on Learning Representations. 2019.];\n- [Bengio, Yoshua, et al. \"A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs.\" International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. Springer, Cham, 2020.]\n- [Nair, Vinod, et al. \"Learning Fast Optimizers for Contextual Stochastic Integer Programs.\" UAI. 2018.]\n\nClarity: The core technical parts of the paper (3.2, 3.3) are a bit difficult to follow as there many parameters that affect the bounds. Other sections are clearer.\n\nQuality: The technical quality seems good given how difficult the problem setting is. The experimental setup is satisfactory.\n\nSignificance: As mentioned earlier, I think the main limiting factor is that the USCO setting is not realistic in two ways:\n- The training data must include approximate solutions;\n- One cannot sample from the true configuration distribution.\n\nThese two are somewhat contradictory, in the sense that I cannot imagine computing the approximate solutions if I cannot observe a sample from the true configuration distribution.\nWithout the approximate solutions, the USCO framework falls apart as there are no labels to supervise the training; if one can sample, then one can also sample at test time and use Sample Average Approximation [Kleywegt, Anton J., Alexander Shapiro, and Tito Homem-de-Mello. \"The sample average approximation method for stochastic discrete optimization.\" SIAM Journal on Optimization 12.2 (2002): 479-502.], the standard method for stochastic optimization with expectations in the objective.\n\nNonetheless, I look forward to the authors' rebuttal. I think this is a crucial point.\n\nOther comments:\n- Training complexity: can you provide running time complexity for the training procedure as a function of the various hyperparameters?\n\n- line 188: why do you only minimize the sum of the first two terms in the RHS of the inequality in Theorem 1? What happens with the third term, which is non-negative and also depends on $\\widetilde{\\boldsymbol{w}}$?\n\n- line 220: \"The performance is measured over ﬁve random testings.\"; I am not sure what you mean here, random testings with respect to which distribution? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers learning to solve the stochastic combinatorial optimization problem, where the underlying distribution over configuration space is unknown---a problem class which the authors refer to as *undetermined* stochastic combinational problem. 

Assuming that a deterministic (approximation) oracle and the corresponding input-solutions pairs are given as training data, the authors propose to use combinatorial kernels (with random configurations) to train a large-margin machine. There was initial disagreement among the reviewers in the applicability of the proposed algorithms beyond the combinatorial optimization problems mentioned in the paper; however, all reviewers find the proposed approach interesting and the theoretical analysis of training and generalization bounds (which is applied to the approximation ratio of the learned solution) insightful. 

The authors are encouraged to address the concerns raised in the reviews; in particular, to clarify the missing references, algorithmic details, computation complexity, and applicability to realistic domains.

Decision: Accept (Poster)