Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut

Thank you very much for your thoughtful review.

Weaknesses:

1. While training can be expensive, the neural network can then be directly used on all future instances from this distribution. There is no need to do any further analysis on future instances. Compare this to the use of (weighted sums of) auxiliary scores, as has been traditionally done in previous analysis. For every new instance, one has to find the parameter that minimizes this auxiliary score. This auxiliary optimization problem can take a much longer time than the inference time for the learned neural network. See Table 1 in our Appendix A, where we show that the inference time is much smaller than solving the corresponding LP, which is usually a prerequisite to computing and optimizing these auxiliary scores.

2. Indeed, there is a trade-off between the gain obtained by instance dependent parameters and the inference time. We believe that the inference times are very small and we get a big gain in performance (much smaller branch-and-cut trees) to compensate.

Questions:

1. The aim of proving sample complexity bounds is to show that one can indeed learn good decisions within branch-and-cut in a principled way, and to give guarantees on the generalization error. Without such bounds, using neural networks (or any other learning method) may run into the problem that the amount of data needed to learn something useful is much larger than is practical for the problem at hand. Our bounds show that the question of learning neural mappings for integer programming is not out of reach in terms of the data needed to achieve good generalization guarantees.

   A useful practical insight to draw from the sample complexity bounds is that the number of data points needed is linear in the number of neural network parameters. This means that if the practitioner wishes to use a larger neural network for even better error guarantees, then the sample size needs to increase roughly by the same factor as the increase in the number of neural network parameters.

2. It is hard to say what bounds one can achieve for other activations without doing the computations. We believe that our proof techniques are general enough that they can be adapted to do the calculations for other activations as well. We illustrate with piecewise polynomial activations:

   Consider the same conditions as Theorem 2.6, but piecewise polynomial activation functions, each having at most $p \geq 1$ pieces and degree at most $d \geq 1$. By using the same proof techniques and applying Theorem 7 in Bartlett et al. (2019), the pseudo dimension is given by $\mathcal{O}(LW \log(p(U+\ell)) + L^2W \log(d) + W \log(\gamma \Gamma(\lambda + 1))).$

   We will replace Theorem 2.6 by this more general result in the final version of the paper, as well as the corresponding propositions/corollaries.

3. This is a good question. The sample complexity only gives a guarantee on the generalization error, but it provides no insight into the nature of the mapping that is learned from data. This raises a completely different, and very important and relevant, set of questions that we do not touch upon in this paper.

Limitations:

Indeed proving complementary lower bounds on the sample complexity would be good.

We agree that, in general, theoretical guarantees do not always translate into practical performance. Nevertheless, our preliminary experiments show that this approach holds promise in improving modern MIP solvers, especially since the choice of parameters within branch-and-cut is still not well understood, and may be too hard a problem to be fully resolved analytically. The learning approach then provides a good way to use historical data to find good parameters. Sample complexity bounds give guarantees on the quality of the parameters learnt, which we think is valuable.

Thank you very much for your thoughtful review.

Weaknesses:

• We think this opens up a whole new field of investigation at the intersection of integer programming and learning theory. We are currently working on other papers where the theory is extended to other families of cutting planes, as well as evaluating the effect at deeper nodes in the branch-and-cut tree. From our studies so far, it does not look like the analysis is easier because of the structure Chvátal-Gomory or GMI cuts. In fact, in previous work of Balcan et al (2022) already, the piecewise polynomial structure of the score function that is crucial for bounding the pseudo-dimension was shown to exist for very general cutting planes. Understanding the effect in deeper nodes of the tree is indeed trickier. We are actively exploring this very interesting problem.

• These constants can be explicitly tracked. The constant for Theorem 2.3 is on the order of $1000$, and the constants of the pseudo dimension results in Sections 2 and 3 are on the order of $100$.

Questions:

We would like to clarify that the neural networks don't compute the size of the branch-and-cut trees directly, but rather output the "best" instance-dependent cutting planes to produce small branch-and-cut trees on average.

Branch-and-cut tree size is generally considered a good proxy for the overall running time of the branch-and-cut algorithm. This is because most of the time is spent in solving the linear relaxations at the different nodes of the tree. Thus, minimizing the expected branch-and-cut tree size should correlate well with minimizing the overall expeected running time on the given family/distribution of instances. Having said that, there are definitely several other factors that go into the overall running time, e.g. dense versus sparse cuts etc. Your question does provide good directions to pursue in future research, by tracking other measures beyond tree size through this learning theory lens.

Thank you very much for your thoughtful review.

Weaknesses:

• A useful insight to draw from the sample complexity bounds is that the number of data samples is linear in the number of neural network parameters. This means that if the practitioner wishes to use a larger neural network for even better error guarantees, then the sample size needs to increase roughly by the same factor as the increase in the number of neural network parameters.

• We agree with your assessment that sample complexity is only one aspect of understanding this complex learning problem; nevertheless, we believe sample complexity is a good first step towards obtaining a principled understanding. There is indeed a lot more to explore here, both theoretically and computationally.

• Learning within branch-and-cut is a very challenging problem already with dozens of papers dedicated to it appearing in the last decade. Since branch-and-cut is both a challenging and a high impact problem, we focused our attention on this single use case of our general results to keep our message crisp. Other algorithmic problems merit separate careful investigation and should probably have dedicated papers to do full justice.

• The paper is indeed focused on developing the theory. The experimental section is presented more as a proof of concept. A thorough experimental evaluation is a whole project in itself and merits a separate paper, in our opinion.

Questions:

• The polynomial structure actually has wide applicability across several problem domains. This was exploited in the STOC 2021 paper "How much data is sufficient to learn high-performing algorithms?" by Balcan et al (see our bibliography). Several important problems, ranging from integer programming to computational biology, were shown to have this structure.

• We have not analyzed other measures, but most measures from the optimization literature should be amenable to our proof techniques. This will indeed form the basis for our future work.

• The sample complexity bounds in this paper show how the size of the data needs to grow as we change the architecture/number of parameters in the neural network. Changing the architecture or number of parameters allows the neural network to be more or less expressive, so the overall expected score (e.g., tree sizes for branch-and-cut) will be smaller or larger, respectively, for the optimal setting of the neural parameters. However, with larger neural networks the data size has to correspondingly grow so that the ERM solution has performance close to this optimal neural network, with high probability. The analysis shows that the data size should grow linearly with the number of parameters in the neural network. Thus, such bounds allow us to quantitatively track the tradeoff between how much error (bias) one has in the neural network architecture versus how much data one needs to generalize well.