Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Update to the Review after the rebuttal from the Authors:
After carefully reviewing the responses by the authors especially on my concerns about the significance of solving an instance of a given problem and the improvement in the exposition of the ideas I would like to amend my earlier decision and recommend to accept. For completeness below is the original review.
 

This paper introduces a framework to learn to generate solutions to online combinatorial optimization problems with worst case guarantees. The framework as the authors claim eliminates the need for manual hard to solve instance/data creation, which is necessary to teach the model to provide the aforementioned worst case guarantees.  Therefore the main contribution of the paper can be said that this framework shows that it is possible to train a machine learning model, which can learn an algorithm to solve hard online combinatorial optimization problems and this training can be done without knowing much about the actual optimization problem domain. The only input required is the way to calculate the objective function of the actual problem. This contribution is demonstrated on two classes of problems: Ski-Rental and Fractional AdWords. The framework requires two neural networks one for solution generation agent and one for problem instance generation. These two networks are trained jointly from scratch and the underlying algorithm for the training is provided. 

Although a generic framework that learns to solve online combinatorial optimization problems without domain knowledge is by itself a very motivational goal neither the paper successfully demonstrates that the framework the authors propose achieves this goal nor it explains well enough why one would take the machine learning approach to find good algorithms to such problems. Is it because the ML solution would be faster to compute with big instances? Is it because with the proposed approach one can curate sophisticated heuristic solutions when provable optimality is out of reach?

This paper should be rejected because proposed method demonstrates that an instance of one class of problems, Fractional Adwords, can be learned to solve without domain expertise, however fails to prove that the approach would be beneficial for any other instances of the same problem. Although they show that the Ski Rental problem can also be learned to solve though it is trivial and does not even use the framework the authors propose in its full extent, ie. problem instances are not generated by use of a machine learning model, which is one of main claims the authors are making. Therefore I do not find being able to solve this problem as a supporting evidence for the contributions claimed. In particular there is not any theoretical not experimental evidence that the approach would scale to any instances where a pure optimization approach would be slow to provide any meaningful solutions. I find this important because for combinatorial optimization usually scale matters a lot. While a small instance of a problem can be solve by a general purpose solver quickly a small increase in the problem size can turn out to be intractable. When proposing a machine learning approach to such problems I would expect the model to scale better than pure optimization approach so that there would be demonstrable benefit. Although the paper proposes an interesting framework I would argue that it is a “green apple” in the sense that authors need to motivate the approach better and expand the contribution beyond solving a particular instance. Authors acknowledge the fact that their experimental setup is rather limited in Appendix C.1, which I agree with and they also claim that there is a representation for a uniform algorithm for any number of advertisers for the AdWords problem, however they leave this as a future work, which I find unfortunate. I would recommend taking this direction rigorously and expand the contribution, which would prove to be a very sound contribution.

In order to clarify the exposition the following are some questions:
1. Authors call the approach YaoGAN due to its structural similarity to GANs. I understand the fact that they are training two neural networks in an alternating scheme, which is similar to the GAN training. How can one evaluate the solutions generated by this framework similar to how GAN generators are evaluated? Can one walk the latent distribution of the algorithm agent and draw insights, which might lead into tailoring some algorithms that would be appropriate for some input distribution although in general inferior in terms of worst case guarantees?

2. The main technical contribution claim needs to be elaborated.  I understand how the game theoretic framework is established but how does this manifest itself in the algorithm described in Section 3.1 needs more explanation.

3. Authors claim there are two shortcomings of the previous method proposed in Kong et. al 2018. They need to elaborate how their method overcomes these issues better.

4. Authors state that fractional relaxation of combinatorial mainly integer optimization problems, which is accurate. Yet their approach is only able to solve the fractional version of the AdWords problem. In addition I agree with the fact that although continuous relaxations to integer optimization problems might provide insightful directions they usually employed to to prove bounds on the heuristic approaches. Yet the authors stop at only solving this version with a machine learning approach, which does not hit the bar for me. I would have expected the authors to at least elaborate on why the current framework is not suitable for the non-relaxed problem. What are the shortcomings? 

5.In Appendix A authors talk about no-regret dynamics, which are relevant. However, they state they loosely follow this approach. What does that entail? What kind of theoretical guarantees are given up due to not following this, a better exposition on this topic would help to support the claims.

6. In appendix C.2 authors provide additional plots for the Fractional AdWords problem. However, they retain from providing any intuition about them. In particular what is the conclusion to be drawn from Figure 5.  This needs more elaboration. Is this way of training results expected? What is the lesson learned?

7.In Figure 8 they provide example data from experience array. What are the significance of these examples? How they help us understand the problem instance generation was actually able to find interesting instances? What kind of dynamics are under covered? These are not directly revealed by only looking at the pictures one needs more explanation to support the claims. 
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper introduces a new approach to solve optimization problems without relying on any human-provided data beyond the specification of the optimization problem itself. The approach is inspired by the two-player zero-sum game paradigm and follow a generative adversarial network (GAN) setting. One network is trained to output the optimal behavior for a given problem, while the other is trained to output difficult instances of the given problem. These two networks are trained simultaneously and compete against the other until some equilibrium is achieved.
This approach is tested on two small problems for which the optimal behavior is known and seems to perform near theoretical optimality.

I weakly reject this paper because although the approach is indeed interesting, the paper is lacking some structure, as described below:

- The paper clearly mentions that no optimization of the training setup or the hyperparameters has been done because the authors are not interested in extending ML techniques. However, hyperparameter searching is not extending any ML technique, it is just an approach to find a good training configuration and show robustness in different hyperparameters settings. It is thus unclear if the approach is robust against different hyperparameter settings.
- Very little details (apart from the optimization algorithm) are given regarding the architecture used (types of input, output, neural units, activation functions, number of hidden layers, loss function, etc...), which makes it very hard to reproduce this approach.
- Section 1.1 presents results with too many details without introducing the problem. I would suggest the authors to either introduce the two problems earlier or to simply say that near-optimal results are achieved, without giving detailed results, because it is very hard to understand them without any introduction of the task being achieved.
- One task is presented in Section 2 "Preliminaries" while the other task is presented in Section 4 "AdWords". It is hard to follow the flow of ideas present in the paper when similar things are not together. I would suggest restructuring the paper into a more classical structure such as: <intro without detailed results - previous work & problematic - approach taken with more details for reproducibility - description of the two tasks - description of experiments with more details for reproducibility - results - conclusion>.
- The paper mentions the MSVV algorithm twice but no reference or explanation is provided. It is very hard to understand sentences referring to this.
- This work only considers problems for which the optimal input distribution is known, but is motivated by the fact that it could be applied to problems for which the optimal distribution is unknown and thus being able to discover new algorithms. It is hard to support this motivation when no experiments are done in its favor.
- No comparison has been made between their approach and other previous approaches. We only know that the proposed approach finds near-optimal solutions with a difference of 0.01 competitive ratio. It is thus very hard to know if this new approach brings any improvement to previous work.

Below are a few things that were not considered to make a decision, but are only details that would make the paper slightly better:
- typo at the beginning of section 3.1: missing 'be' in  "This can either *be* by an ..."
- typo at the beginning os section 4:  missing 'be' in "... the algorithm must irrevocably *be* allocated to ..."
- Axis' names to the different plots in the Figures would help understand them better. Also, the description of some figures could benefit more details that could be taken off from the text.

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This papers tackles the following question. Is it possible to learn the "most" complex instance of a class of (combinatorial) problem while finding (or recovering) algorithms with strong minimax rate.

This is very interesting and clearly a nice line of work (in theory though).

The techniques used rely on GANs since it can be shown that finding the best (random) algorithm and the worst (deterministic) instance is equivalent to finding the worst random instance against the best deterministic algorithm. This is actually a direct consequence of any minmax theorem in game theory; the authors decided to credit that result to Yao (I tend to *strongly* disagree with that point as, even if he stated this fact in CS, this result was quite standard several decades before him - anyway.).

Then this idea is evaluated in two examples. A toy problem (the ski rental) and a more or less concrete ones (adwords pb of Mehta). This is the major disappointment in the paper. The basic idea is very interesting, but I would have expect more interesting use cases as teased by the first sentence of the abstract "find algorithms with strong worst-case guarantees for online combinatorial optimization problems".

So at the end, I am a bit puzzled. I really like the idea, but I have the feeling that this technique should have been developed for more complicated setting. Or maybe it is actually not working on more difficult combinatorial problem (and this is hidden in the paper). I believe that this paper is thus not in its final form and could be largely improved.






review_title: Official Blind Review #1

Meta-review: The authors propose an intriguing way to designing competitive online algorithms. However, the state of the paper and the provided evidence of the success of the proposed methodology is too preliminary to merit acceptance.
Decision: Reject