Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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".

USCO-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.

Experiments 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.

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.

Originality: 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:
- [Pogančić, Marin Vlastelica, et al. "Differentiation of blackbox combinatorial solvers." International Conference on Learning Representations. 2019.];
- [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.]
- [Nair, Vinod, et al. "Learning Fast Optimizers for Contextual Stochastic Integer Programs." UAI. 2018.]

Clarity: 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.

Quality: The technical quality seems good given how difficult the problem setting is. The experimental setup is satisfactory.

Significance: As mentioned earlier, I think the main limiting factor is that the USCO setting is not realistic in two ways:
- The training data must include approximate solutions;
- One cannot sample from the true configuration distribution.

These 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.
Without 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.

Nonetheless, I look forward to the authors' rebuttal. I think this is a crucial point.

Other comments:
- Training complexity: can you provide running time complexity for the training procedure as a function of the various hyperparameters?

- 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}}$?

- 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? 

limitations_and_societal_impact: not applicable
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

1. 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. 

2. 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.

limitations_and_societal_impact: The limitations are addressed in the paper and there is no potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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:

1. Running time is an important aspect in solving optimization problems. How is the running time of the proposed USCO Solver compared to baselines? 

2. 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. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: Strengths of this paper:
1. A unified approach for stochastic combinatorial optimization is demanding and appealing.
1. Detailed analysis of training and generalization bounds of the proposed method.
1. Involving an oracle (polynomial-time solver) in the learning to optimization pipeline.

The limitations of this paper are mainly about the experiment part:
1. 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.
1. The baseline linear programming method [43] is missing for the stochastic bipartite matching experiment.

Some points that are unclear to me:
1. 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.
1. 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}$.
1. 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? 
limitations_and_societal_impact: yes
review_title: null

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)