Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut
Authors: Hongyu Cheng
Sammy Khalife
Barbara Fiedorowicz
Amitabh Basu
Venue: NeurIPS 2024 poster (2024)
Keywords: Integer programming
branch-and-cut
branch-and-bound
sample complexity
neural networks
learning theory
data-driven algorithm design
Primary area: optimization

Abstract: Data-driven algorithm design is a paradigm that uses statistical and machine learning techniques to select from a class of algorithms for a computational problem an algorithm that has the best expected performance with respect to some (unknown) distribution on the instances of the problem. We build upon recent work in this line of research by considering the setup where, instead of selecting a single algorithm that has the best performance, we allow the possibility of selecting an algorithm based on the instance to be solved, using neural networks. In particular, given a representative sample of instances, we learn a neural network that maps an instance of the problem to the most appropriate algorithm *for that instance*. We formalize this idea and derive rigorous sample complexity bounds for this learning problem, in the spirit of recent work in data-driven algorithm design. We then apply this approach to the problem of making good decisions in the branch-and-cut framework for mixed-integer optimization (e.g., which cut to add?). In other words, the neural network will take as input a mixed-integer optimization instance and output a decision that will result in a small branch-and-cut tree for that instance. Our computational results provide evidence that our particular way of using neural networks for cut selection can make a significant impact in reducing branch-and-cut tree sizes, compared to previous data-driven approaches.

Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut
Hongyu Cheng
Sammy Khalife
Dept. of Applied Mathematics & Statistics
Dept. of Applied Mathematics & Statistics Johns Hopkins University
Johns Hopkins University
Baltimore, MD 21218 hongyuchenggjun jhu. edu
Baltimore, MD 21218 khalife. samey@@amm@jjjj juu. edu
Barbara Fiedorowicz
Amitabh Basu
Dept. of Applied Mathematics & Statistics
Dept. Applied Mathematics Statistics
Johns Hopkins University
Johns Hopkins University
Baltimore, MD 21218 bfiedor1@jhu. edu
Baltimore, MD 21218 basu. ami tabh@jhuu edu
Abstract
Data-driven algorithm design is a paradigm that uses statistical and machine learn- ing techniques select from class of algorithms for computational problem an algorithm that has the best expected performance with respect to some (unknown) distribution on the instances of the problem. We build upon recent work in this line of research by considering the setup where, instead of selecting single algorithm that has the best performance. we allow the possibility of selecting an algorithm based on the instance to be solved, using neural networks. In particular, given a representative sample instances, we learn a neural network that maps an instance of the problem to the most appropriate algorithm for that instance. We formalize this idea and derive rigorous sample complexity bounds for this learning problem, in the spirit of recent work in data-driven algorithm design. We then apply this approach to the problem of making good decisions in the branch-and-cut frame- work for mixed-integer optimization (e.g.. which cut to add?). In other words, the neural network will take as input a mixed -ixxeer optimization instance and output a decision that will result in small pranch-and--o Our computational results provide evidence that our particular way of using neural networks for selection make significant impact in reducing branch-and-cur tree sizes, compared to previous data-driven approaches.
tree for that instance.
Background and motivation
Often there are several competing algorithms for a computational problem and no single algorithm dominates all the others. The choice of algorithm in such cases is often dictated by the "typical" instance one expects to see, which may differ from one application context to another. Data-driven algorithm design has emerged in recent years selection and draws upon statistical and machine learning techniques; see [alcan [2020] for a survey and references therein. More formally, suppose has a class I of instances of some computational problem with some unknown distribution, and a class of algorithms that can solve this problem parameterized by some "tunable parameters". Suppose that for each setting of the parameters, the corresponding algorithm can be evaluated by score function that tells us how
way to formalize this question of algorithm
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

well the algorithm does on different instances (e.g., rumning time, memory usage etc.). We wish to find the set of parameters that minimizes (or maximizes, depending on the nature of the score) the expected score on the instances (with respect to the unknown distribution), after getting access to an i..dd. sample of instances from the distribution, For example, could be a family of mixed-intess integer optimization problems and the class of algorithms are branch-and-cut methods with their different possible parameter settings, and the score function could be the size of the branch-and-cu tree.
In Balcan et al. 2021aa, al. the authors prove a central result on the sample complexity of this problem: if for any fixed instance in I, the score function has piecewise structure as a function of the parameters, where the number of pieces is upper bounded by constant R independent of the instance, the pieces come from family of functions of "low complexity". and the regions partitioning the parameter space into pieces have "low complexity" in terms of their shape. then the sample complexity is precise function of R and these two complexity numbers (formalized by the notion of pseudo-dimension see below). See Theorem 3.3 in |Balcan et al. (2021a) for details. The authors then proceed to apply this key result to diverse variety of algorithmic problems ranging from computational biology, computational economics to integer optimization.
Our work in this paper is motivated by the following consideration. In many of these applications, one would like to select not a single algorithm, i.e., a single setting of the parameters, but would like to decide on the parameters after receiving new instance of the problem. In other words, we would like to learn not the best parameter, but the best mapping from instances to parameters, We consider this version of the problem, where the mapping taken from a class of neural network functions. At a high level, switching the problem from finding the "best" parameter to finding the "best" mapping in a parameterized family of mappings gives the same problem: we now have new set of parameters the ones parameterizing the mappings (neural networks) and we have to select the best parameter. And indeed, the result from Balcan et al. [2021a] can be applied to this new setting, as long as one can prove good bounds psendo-dimensie in the space of these new parameters. The key point of our result is two fold:
1. Even if original space of parameters for the algorithms is amenable to the analysis of pseudo- dimension as done in [Bllcan et al. [202 it is not clear that this immediately translates to a similar analysis in the parameter space of the neural networks, because the "low complexity piecewise structure" from the original parameter space may not be preserved.
2. We suspect that our proof technique results in tighter sample complexity bounds, compared to what one would obtain if one could do the analysis from Balcan et al. [2021a] in the parameter space of the neural network directly. However, we do not have quantitative evidence of this yet because their analysis seems difficult to carry out directly in the neural parameter space.
One of the foundational works in the field of selecting algorithms based on specific instances is Rice (176), and recently, Gupta and Roughgarden 2016). Balcan al. [021c] have explored the sample complexity of learning mappings from instances to algorithms for particular problems. Our approach is also related to recent work on algorithm design with predictions; see Mitzenmacher and Vassilvitskii [2022] for short introduction and the references therein for more thorough surveys and recent work. However, our emphasis and the nature of our results are quite different from the focus of previous research. We establish sample complexity bounds for a general learning framework that employs neural networks to map instances to algorithms, which suitable for handling some highly complex score functions, such as the size of the branch-and-cud tree. The introduction of neural networks in our approach bring more intricate technical challenges than traditional settings like linear predictors or regression trees Gupta and Roughgarden (2016). On the application side, as long as we know some information about the algorithms (see Theorems 2.3 and 2.6). our results can be directly applied. This is demonstrated in this paper through applications to various cutting (3.6)/dd (37] Several references to fundamental applied work in data-driven algorithm selection can be found in the Balcan (020))
plane selection problems in granch-and-cut in Propositions [333 3.5) [3.5
Gupta and Roughgarden 2016 Balcan et al. 2021a
1.1 Applications in branch-and-cut methods for mixed-integer linear optimization
Mixed-integer linear optimization is a powerful tool that used in a diverse number of application domains. Branch-and-cutt is the solution methodology of choice for all ofate-of-the-art solvers for
2

---

mixed-intege optimization that is founded upon well-developed theory of convexification and systematic enumeration [Schrijver [986], Nemhauser and Wolsey| [9888]. Conforti et al. (2014). However, even after decades of theoretical and computational advances, several key aspects of branch-and-cut are not well understood. During the execution of the branch-and-cut algorithm on an instance, the algorithm has to repeatedly make certain decisions such as which node of the search tree to process next, whether one should branch or add cutting planes, which cutting planes to add, or which branching strategy to use. The choices that give small tree size for a particular instance may not be good choices for a different instance and result in a much larger tree. Thus, adapting these choices to the particular instance can be beneficial for overall efficiency. Of course, the strategies already in place in the best implementations of branch- wawcchh-nd-ce and-cut have to adapt to the instances. For example, certain cutting plane choices may not be possible for certain instances. But even beyond that, there are certain heuristics in place that adapt these choices to the instance. These heuristics have been arrived at by decades of computational experience from practitioners. The goal in recent years is to provide a data driven approach to making these choices. In a recent series of papers |Balcan et al.
[221a d b 2022 2018), , the authors apply the general sample complexity result from |Balcan et al. 2021a in the specific context of branch-and-cut methods for mixed-integer linear optimization to obtain several remarkable and first-of-therr-inne results. We summarize here those results that are most relevant to the cut selection problem since this is the focus of our work.
1. In Balcan et al. 2021d], the authors consider the problem of selecting the best Chvátal- Gomory (CG) cutting plane (or collection of cutting planes) to be added at the root node of the branch-and-cu tree. Thus, the "tunable parameters" are the possible multipliers to be used to generate the CG cut at the root node. The score function is the size of the resulting cranch-and-cut tree. The authors observe that for fixed instance of mixed-integer intteerr linear optimization problem, there are only finitely many CG cuts possible and the number can be bounded explicitly in terms of entries of the linear constraints of the problem. Via sophisticated piece of analysis, this gives the required piecewise structure on the space of multipliers apply the general result explained above. This gives concrete sample complexity bounds for choosing the multipliers with the best expected performance. See Theorem 3.3, 3.5 and 3.6 in Balcan et al. (2021d) for details. Note that this result is about selecting a single set of multiplierscutting planes that has the best expected performance across all instances. This contrasts with selecting a good strategy to select multipliers depending on the instance, that has good expected performance (see point 2. below).
2.
The authors in Balcan al.] [2021d] also consider the problem of learning good strategy that selects multipliers based on the instance. In particular, they consider various auxiliary score functions used in integer optimization practice, that map a pair of instance and a cutting plane for / that measures how well e will perform for processing I. The strategy will be a linear function of these auxiliary scores, i.e., a weighted average of these auxiliary scores, and the learning problem becomes the problem of finding the best linear coefficients for the different auxiliary scores. So now these linear coefficients become the "tunable parameters" for the general result from Balcan et al. [202 It is not hard to find the piecewise structure in the space of these new parameters, given the analysis in the space of CG cut multipliers from point 1. above. This then gives concrete sample complexity bounds for learning the best set of weights for these auxiliary score functions for cut selection. See Theorem 4.1 and Corollary 4.2 in Balcan et al. [22ld]] for details.
3. In all the previous results discussed above, the cutting planes considered were CG cuts, or it essentially assumed that there are only finite number of cutting planes available at any stage of the branch-and-cut algorithm. In the most recent paper [aaccan et al. (2022). the authors consider general cutting plane paradigms, and also consider the possibility of allowing more general strategies to select cutting planes beyond using weighted combina- tions of auxiliary score functions. They uncover the subtlety that allowing general mappings from instances to cutting planes can lead to infinite sample complexity and learning such mappings could be impossible, if the class of mappings is allowed to be too rich. See Theorem 5.1 in |Balcan et al. 22022. This point will be important when we discuss our approach below.
On the positive side, they show that the well-known class of Gomory- Mixerd-Miiid--mme Integer (GMI) cuts has a similar structure to CG cuts, and therefore, using similar techniques as discussed above, they derive sample complexity bounds for selecting GMI cuts at the root node. See Theorem 5.5 in Balcan et al. 2022). As far as understand, the analysis should extend to
3

---

the problem of learning weighted combinations of auxiliary score functions to select the GMI cuts as well using the same techniques as Balcan et al. (202Id), although the authors do not explicitly do this in Balcan et al. 2022)
Our approach and results. Our point of departure from the line of work discussed above that instead of using weighted combinations of auxiliary scores to select cutting planes, we wish to select these cutting planes using neural networks that map instances to cutting planes. In other words, the general framework described above, the "tunable parameters" are the weights of the neural network. The overall score function is the size of the branch-and-cut tree after cuts are added at the root. We highlight the two main differences caused by this change in perspective.
1. In the approach where weighted combinations of auxiliary score functions are used, after the weights are leart from the sample instances, for every new/unseen instance one has to compute the cut that maximizes the weighted score. This could be an expensive optimization problem in its own right. In contrast, with our neural approach, after training the net (i.e., learning the weights of the neural network), any new instance is just fed into the neural network and the output is the cutting plane(s) to be used for this instance. This is, in principle, a much simpler computational problem than optimizing the combined auxiliary score functions over the space of cuts.
2. Since we use the neural network to directly search for good cut, bypassing the weighted combinations of auxuliary scores, we actually are able to find better cuts that reduce the tree sizes by significant factor, compared to the approach of using weighted combinations auxiliary scores.
The above two points clearly evidenced by our computational investigations which present in Section AA] The theoretical sample complexity bounds for cut selection are presented in Section 3 As mentioned before, these are obtained using the main sample complexity result for using neural networks for data driven algorithm design that is presented in Section
Comparison with prior work cut selection using learning techniques. As already discussed above, our theoretical sample complexity work in cut selection is closest in spirit to the work in [Baccan al. (222 a b 2022 2018). However, there several other works in the literature that use machine
learning ideas to approach the problem of cut selection; see Deza and Khalil (2023) for a survey.
Tang et al. Tang et al. (2020) initiated the exploration of applying Reinforcement Learning (RL) to select CG cuts derived from the simplex tableau. Huang et al. Huang et al. [2022] apply supervised learning to rank a "bag of cuts" from a set of cuts to reduce the total runtime. More recently, the
authors in Turner et al. (2023) propose novel strategy that use RL and Graph Neural Networks (GNN) to select instance dependent weights for the combination of auxiliary score functions.
Our computational investigations, as detailed in Appendix A distinguishes itself from these prior computational explorations in several key aspects:
1. Previous methods were limited to a finite set of candidate cuts, requiring either an optimal simplex tableau or relying on a finite collection of combinatorial cuts. In contrast, our approach allows the possibility selecting from a possibly infinite family of cutting planes. Moreover, our method eliminates the need for computing a simplex tableau which can lead to a significant savings in computation (see Table I and the discussion in Section A.2
2. Many prior studies aimed at improving the objective value rather than directly reducing the branch-and-on runtime-wint the exception of Huang et al. Huang et al. [2022). who explored this through supervised learning. To the best of our knowledge, model is the first to directly target the reduction of the branch-and-cur tree size as its reward metric, which is strongly correlated with the overall running time.
RL-based
3. Prior deep learning approaches are not underpinned by theoretical guarantees, such as sample complexity bounds. Our empirical work takes the theoretical insights for the branch-and-cut problem presented in Theorem 2.3 and Proposition 3.3 as its basis.
The limitations of our approach are discussed in Section 4

---

2 Formal statement of results
We denote [d] as the set {1,2....,de .j for any positive integer d E+. For a set of vectors (x!...., x') S IR, we superseripts to denote vector indices, while subscripts specify the coordinates a vector; thus, xj refers to the j-th coordinate of x'. Additionally, the sign function, denoted as 8gn : IR - {0. 1). is defined such that for any I E R, sgn(2) 0 if x < 0, and otherwise. This function is applied to each entry individually when applied to vector. Lastly, the notation [.] is used to indicate the elementwise floor function, rounding down each component of vector the nearest integer.
2.1 Preliminaries
2.1.1 Background from learning theory
Definition 2.1 (Parameterized function classes). A gunaamtterized class is given by a function defined as
h h +
where I represents the input space, denotes the parameter space, and O denotes the output space. For any fixed parameter setting p E P, we define a function hi I - O as (!) = h(1, p) for all I E I. The set of all such functions defines the parameterized function class, a.k.a. the hypothesis class H. = {hp I + O p E P) defined by h.
Definition 2.2 (Pseudo-dimension). Let F a non-empty collection of functions from an input space I to R. For any positive integer t, say that set {4,,.... ..... I[} S I is pseudo-shattered by F there exist real numbers $1...., such that
2 [(sgn(f(L)) ..), sg...sgggnn))n))nnn.)......).).) st)) f E FH
The pseudo-dimenseo of F, denoted as (di E NU {+00}, is the size of the largest set that can be
by F.
The main goal of statistical learning theory is to solve a problem the following form, given a fixed parameterized function class defined by some h with output space O = R:
min Ei-D (h(I,
(1)
pEP
for an unknown distribution D, given access to i.i.d. samples II...., Ie from D. In other words, one tries to "learn" the best decision p for minimizing an expected "score" " with respect to an unknown distribution given only samples from the distribution. Such "best" decision can be thought of as a property of the unknown distribution and the problem is to "learn" this property of the unknown distribution, only given access to samples.
The following is fundamental result in empirical processes theory and is foundational for the above learning problem; see, e.g., Chapters 17, 18 and 19 in Anthony et al. [199]] especially Theorem 19.2.
Theorem 2.3. There exists universal constant C such that the following holds. Let H. be hypothesis class defined by some I x P + IR such that the range of h is in [0, B] for some B For any distribution D on X, 0, E (0, 1), and
C 2
B In 1 )
t
Pdim (H) In
we have
8 h(G.P) - ELLD [MT p)] Se for all p E P,
f. Σ
with probability - over i.i.d. samples II...., , I, E of size drawn from D.
Thus, if one solves the sample average problem minpep Σ. M(,,, p) with a large enough sample to within O(e) accuracy, the corresponding p would solve to within O(e) accuracy (with high probability over the sample). Thus, the pseudo-dimension Pdlm(() is key parameter that can be used to bound the size of sample that is sufficient to solve the learning problem.
5

---

2.1.2 Neural networks
We formalize the definition of neural networks for the purposes of stating our results. Given any function Rd
R - IR, we will use the notation (x) for x E IR to mean (x(x),, (
Definition 2.4 (Neural networks). Let R + R and let L be positive integer. A neural network WL, WL+1] z is paremterized function
with activation a and architecture class, parameterized by L + 1 affine transformations {Ti : " - R E [L + }]} with T1+1 linear, is defined as the function
[wo, w1..... .....
o.. -- Too0
I denotes the number of hidden layers in the network, while wi signifies the width of the i-th hidden layer for E [Z]. The input and output dimensions of the neural network denoted by we and WL+1, respectively. If T3 is represented by the matrix A' E R":xwi-1 and vector b E IR "R i.e., [x) A'x b' for E [L + 1]. then the weights of neuron j E [ux]] in the i-th hidden layer come from the entries of the j-th row of A' while the bias of the neuron is indicated by the j-th coordinate of b'. The size of the neural network is defined w1 +... + WL, denoted by U.
In the terminology of Definition 2.1 we define the neural network parameterized functions No Re x RW + 21, with IR tn denoting the input space and R W representing the parameter space. This parameter space is structured through the concatenation of all entries from the matrices A' and vectors b' for
[L + 1), into single vector of length W. The functions defined as No (x, w) = 1 ( .. T2(or (T) (a))))).))) ))) for any x E R and w E IR W where each T, represents the affine transformations associated with w RR.
In the context of this paper, we will focus on the following activation functions:
sgn: The Linear Threshold (LT) activation function sgn R -> {0,1), 1), which defined as sgn(x) = if x < and sgn(x) = 1 otherwise.
ReLU: The Rectified Linear Unit (ReLU) activation function ReLU : R + Rgo is defined as (e)U(()) max(0, xz.
CReLU: The Clipped Rectified Linear Unit (CReLU) activation function CReLU R
10, 1] is defined as CRcLU(z)) = min (aa((max(0, x>,1)
Sigmoid: The Sigmoid activation function Sigmoid : R (0,1) defined as
Sigmoid(x) I+--F
2.2 Our results
In this study, we extend the framework introduced by Balcan et al. Balcan et al. 2021a to explore the learnability of tunable algorithmic parameters through neural networks. Consider a computational problem given by family of instances I. Let us say we have a suite of algorithms for this problem, parameterized by parameters in P. We also have score function that evaluates how well a particular algorithm, given by specific settings of the parameters, performs on particular instance. In other words, the score function given by I x + [0, B). where B E R4 determines priori upper bound on the score. The main goal of data-driven algorithm design is to find a particular algorithm in our parameterized family of algorithms equivalently, find a parameter setting p E that minimizes the expected score on the family of instances with respect to unknown distribution on I, given access to a sample of i.i.d instances from the distribution. This then becomes a special case of the general learning problem [ where h = S and one can provide precise sample complexity bounds via Theorem 2.3] if one can bound the pseudo-dimension of the corresponding hypothesis class. A bound on this pseudo-dimension is precisely the central result in Balcan al. [202 see the discussion Section [
We assume the parameter space P is a Cartesian product of intervals [m. TI] x ... x [ne. Tel. where ni S T3 for each E [4]. The transformation from the instance space I to the parameter space P is structured through the following mappings:
An encoder function Enc I - Rd is defined to convert an instance E I into a vector x Enc(I) Rd, facilitating the instances to be suitably processed by neural network.

---

A simple example of such an encoder could be a compilation of all the instance's 's numerical data into single vector; but one can allow encodings that use some predetermined features of the instances.
2. A family of neural network mappings, denoted as N R x RW + R', is utilized. These mappings are characterized by an activation function Ø, and fixed architecture represented by [d, Wi..... WL, f] z For any given neural network parameters w RW, this network maps encoded instance E IR into y == Nº (x, w) E R'.
3. A squeezing activation activation,functiin o': R + [0, 1], is introduced to adjust the neural network's output the parameter space P. The parameter p P is computed by P. 7) + (Ti m,)o (y:) for = L......
The composite mapping from the instance space I to the parameter space P is denoted by Pw N" ,o' since the results of this study are applicable for any fixed and predetermined encoder function Enc.
The problem of learning the best neural mapping then becomes the learning problem [T with x R defined by h(I, w) := = (I, "0' (1)). We use
FR = (s No ())))(()))
()) - 10, B] W
to denote the corresponding hypothesis class (Definition 2.1
Our first result employs linear threshold neural networks for generating algorithm parameters, inspired by their analytically tractable structure and rich expressive capabilities, as supported by findings in Khalife et al. [2023]
Theorem 2.5. Consider set I of instances of computational problem with suite of algorithms
parameterized by P [m. 71] ... X [e. re), with score function S I x P - [0, B). Suppose that, for any given instance / I. there exist at most I polynomials on Ré, each of degree at most 7, such that within each region of where these polynomials have the same sign pattern, the function S(I, -) polynomial on Rf with degree at most X. For linear threshold neural networks N _d W + R' with a fixed architecture w [d, Wi..... W..., E 24+22 having size U and W parameters (Definition) 2.4, and using a Sigmoid squeezing function, we have
Pdim (F Nem Sigmoii) O (W (og(U>[(A+1]] 1)))
In addition to this, we investigate the sample complexity associated with the use of ReLU neural networks for parameter selection.
Theorem 2.6. Under the same conditions Theorem 2.5 with ReLU neural networks ReLU
Rd x RW +R R having the same fixed architecture and clipped ReLU squeezing function, we have
Pdim (FRROL (UROLU,CRaL.u) = O (LW log(U + + W log(>1(A + 1)))
Remark 2.7. Theorem 2.6 can be easily extended to the case where general piecewise polyno- mial activation functions are used instead of ReLU,, with each function having at most p 2 pieces and degree at most g 2 1. By applying the same proof techniques as in the theo- rem above and using Theorem 7 in Bartlett et al. [209]] the pseudo-dimension changes to O (LW log(p(U + E)) + L log(g) + W log(>1(A + I)J). While we present the ReLU case as the main theorem due to its common use in practical applications, from a theoretical perspective, ReLU activation functions are not fundamentally different from other piecewise polynomial activation functions in the context of this paper.
It is not hard to adapt the proofs of Theorem 2.5 and Theorem 2.6 to show that if any dimension of the parameter space is all of R rather than bounded interval, the pseudo-dimension bounds will only be smaller, under the same conditions. Additionally, if p {pi.... p, is a finite set, the problem can viewed as a multi-classificttion problem. That is, consider a neural network No R x R + IR,, where for any x E I2d and E R N w) outputs an r-dimensional vector, and we select the parameter corresponding the largest dimension. The pseudo-dimension of
this problem is given by the following:
Corollary 2.8. Under the same conditions as Theorem 2.5 and 2.6 but with P = =(p,,...,DD
Pdim S Ne Sigmoid) O (W log(Ur)) and Pdim F NRRLU N = O (LW log(U + +r))
7

---

3 Application to branch-and-cut
3.1 Preliminaries
Definition 3.1 (Integer linear programming (IIP)). Let n. E N+ be fixed natural numbers, and let A E Qmxn b Qm,, IR". The integer linear programming problem is formulated as
maxfc Ax < b, Z*)
The most successful algorithms and solvers for integer programming problems are based on methodology called branch-and-cee In branch-and-cu algorithm, one maintains two things in every iteration of the algorithm: 1) a current guess for the optimal solution, 2) a collection of polyhedra that are subsets of the original polyhedral relaxation of the ILP. In every iteration, one of these polyhedra are selected and the continuous linear programming (LP) solution for that selected polyhedron is computed. If the solution has objective value worse than the current guess, this polyhedron is discarded from the list and the algorithm moves to the next iteration. Otherwise, if the solution is integral, the guess is updated with this integral solution and this polyhedron is removed from further consideration. If the LP solution is not integral, one decides to either add some cutting planes or branch. In the former case, additional linear constraints added this polyhedron under consideration without climinating any feasible solutions. In the latter case, one selects a fractional variable x, in the LP solution and partitions the current polyhedron into two polyhedra by adding constraints X; S [ft] and x; 2 [fa] + 1, where fa is the value of this fractional variable. The current polyhedron is then replaced in the list by these be tracked by a branch-anaae and--cut tree whose nodes are precisely the different polyhedra processed by the algorithm. The algorithm terminates when there are no more polyhedra left in the active list and the current guess is reported as the optimal solution. As is often done in practice, an a priori bound B is set on the size of tree; if this bound is exceeded by the algorithm at any stage, the algorithm exist early and the current guess for the solution is returned. The wranch-and-cus tree size is very good indication of how long the algorithm takes solve the problem since the main time spent on solving the individual LPs in the iterations of the algorithm. We will thus use the tree size as the "score" function to decide how well branch-and-ee did on any instance.
new polyhedra. This entire process can
There are many different strategies to generate cutting planes in branch-and-oe Conforti et al. 2014). Nemhauser and Wolsey (1988), [Schrijver] [1986]. We will focus the so-called Chvátal Gomory (CG) cutting planes and Gomory Mixed-Integer (GMI) cuts Conforti et al.) (2014). There are usually several choices of such cutting planes to add (and some families are even infinite in size Conforti
jet al.] 2014)). We wish to apply the results of Section 2 to decide which cutting plane to select so that the branch-and-cut tree size is small.
3.2 Learnability of parameterized CG cut(s)
Let m, n be positive integers. We consider the ILP instance space I C ((A, b, c) A Qmxx, b E Q" e E R²), along with a fixed encoder function Enc I - Rd. A simple encoder might stack all elements of (A, b. c) E I into single vector of length d = mmn + + We also impose the conditions that Ene
AAgl S a and D [b: S b for any (A, b, c) T..
Following the discussion in Balcan et al. 2021d.. we define fcG u) as the size of the branch-an bound tree for given ILP instance / E with a CG cut parameterized by multiplier [0. 1) added at the root. We interpret fea as a score function elaborated in Section 2.2 The piecewise structure of feG in its parameters is characterized by:
Lemma 3.2 (Lemma 3.2 in Balcan et al. [2021d]). For any ILP instance I E I, there are at most
M : 2(a + b+r)) hyperplanes partitioning the parameter space [0, 11Th into regions where fea (I, u) remains constant for all u within each region.
Applying Theorem 2.5 and Theorem 2.6 to foG yields these pseudo-dimension bounds:
Proposition 3.3. Under the same conditions as Theorem 2.5 and 2.6 with the score function feg,
Pdim Fice
O (W (U)(
N Sigmoid
TScc Pdim NBCLU C
O (LW log(U + m) + W log M).
8

---

Extending this to adding &o CG cuts sequentially, we define fC (I, (uI..... uz)) as the branch-and- bound tree size after adding a sequence of k CG cuts parameterized by u...... ug the root for given IIP instance T E I. The piecewise structure of Jeg in its parameters is given by:
Lemma 3.4 (Lemma 3.4 in Balcan et al. (021d). For any ILP instance I E I, there O M) multivariate polynomials with mk + k(k 1)/2 variables and degree at most & partitioning the parameter space [o, I] 1] 12/2 into regions where [Ca (ur,...,u.) remains constant for all (uz...., Uz) within each region.
Accordingly, the pseudo-dimension bounds are Proposition 3.5. Under the conditions as Theorem 2.5 and 2.6 with the score function föo.
Pdim
Ffia Sigmosd) )
O (W log((UM) Wk),
Pdim (F NRRLU CRRLUU)
log(U mk) W log M Wk).
3.3
Learnability of cutting plane(s) from finite set
The selection of an optimal cut from an infinite pool of candidate cuts, as discussed in Proposition 3.3 and Proposition 3.5 is often difficult and inefficient practice. Consequently, a popular way is to select cuts based on information from the simplex tableau (such as GMI cuts), as well as some combinatorial cuts, which inherently limit the number of candidate cuts considered be finite.
Suppose we have a finite set of cuts C, and we define fnow (I, c) as the branch-and- bound tree size after adding cut E C at the root for given ILP instance I E I. Then Corollary [2.8 implies
Proposition 3.6. Under the same conditions as Theorem 2.5 and 2.6 with the score function fRow.
Pdim
[ fRow Sigmoid)
O (W Iog(U(C)) and Pdim [
, cRRELU) (LW +C)))
3.4 Learnability of cut selection policy
One of the leading open-source solvers, SCIP Gamrath et al. [020], uses cut selection method- ologies that rely on combining several auxiliary score functions. For finite set of cutting planes C, instead of directly using a neural network for selection, this model selects c*
arg max Ei=1 μ4 Score,(c, I) for each instance / E I. Here, Score, represents different heuristic scoring functions that assess various aspects of a cut, such as "Efficacy" Balas et al. "Parallelism" |ccherberg (2007), for a specific instance I, and the coefficients μ E |0. 1] tunable weights for these scoring models. Since C is considered to be finite, the above optimization problem solved through enumeration. The authors in Turner et al. [223) have experimentally implemented the idea of using a neural network to map instances to weights. We provide an upper bound on the pseudo-dimension in the following proposition of this learning problem.
1996) and
Proposition 3.7. Under the same conditions as Theorem 2.5 and 2 let fs µ1) denote the size of the branch-and- tree for after adding a cutting plane determined by the weighted scoring model parameterized by E
[0, 1j.. The pseudo-dimension bounds are given by:
Pdim (Fli
Sigmoiioo Sigmoid
= O (W log(U(C)))
Pdim (Ils
= O (LW log(U + + + W log((C))).
NRRLU CCRELU)
4 Discussions and open questions
In our study, we concentrated on adding CG cuts solely at the root of the branch-and-cut tree. However, devising a strategy that generates high quality cutting planes while being efficient across the entire branch-and-cut tree poses a significant and intriguing challenge for future research. Further, our theoretical findings are applicable to any encoder that maps instances into Euclidean spaces. Hence, utilizing fixed encoder capable of converting ILPs with different number of constraints into a same Fuclidean space can in principle enable the training unified neural network to generate cutting planes across the cranch-and-cut tree. Moreover, an effective encoder could improve the

---

neural network's 's performance beyond the one achieved with the basic stacking encoder used in our paper.
The neural network training problem (2 also requires further study. We used an RL approach (see Appendix (A] to update the neural network parameters and minimize the average tree size for ILP instances sampled from given distribution. However, this method does not guarantee convergence to optimal parameters, and relies heavily on the exploratory nature of the RL algorithm. For ILP distributions where random exploration of Chvátal multipliers is unlikely to yield smaller tree sizes, the RL algorithm may struggle identify an effective parameter setting. Developing more efficient and robust training methodology would greatly improve the practical value of our work.
Acknowledgments and Disclosure of Funding
All four authors gratefully acknowledge support from Air Force Office of Scientific Research (AFOSR) grant (A9550201034) Hongyu Cheng, Barara Fiedorowicz and Amitabh Basu also grate- fully acknowledge support from National Science Foundation (NSF) grant CCF2006587. Hongyu Cheng also acknowledges support from the Johns Hopkins University (JHU) Mathematical Institute for Data Science (MINDS) Fellowship, the Duncan Award 24-33, and the Rufus P. Isaacs Graduate Fellowship. Barbara Ficdorowicz also acknowledges support from the JHU Duncan Award 24-31.
References
Tobias Achterberg. Constraint integer programming. 2007.
Martin Anthony, Peter L Bartlett, Peter L Bartlett, al. Neural network learning: Theoretical foundations, volume 9. Cambridge: Cambridge University Press, 1999.
Egon Balas, Sebastián Ceria, and Gérard Cormuéjols. Mixed 0-1 programming by lift-and-project in branch-and-cut framework. Management Science, 1229):229-1246 1996.
Maria-Florina Balcan. Data-driven algirithm design. In Tim Roughgarden, editor, Beyond the Worst Case Analysis of Algorithms. Cambridge University Press, 2020.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning, pages 344-353. PMIR, 2018.
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient learn perffrrrfnnn algorithms? generalization guarantees for data-driven algorithm design. In Proceedings of the 53rd Anmual ACM SIGACT Symposium Theory of Computing, pages 919-932, 2021a.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Bllen Vitercik. Improved sample complexity bounds for branch-and-cut, arXiv preprint arXiv:2111.11207 2021b.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization in portfolio-bast algorithm selection. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 1222511233,, 2021c.
Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample com- plexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34:4015 4027, 2021d.
Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Structural anal- ysis of branch-and-cut and the learnability of gomory mixed integer cuts. Advances in Neural Information Processing Systems, 35:33890-33903, 2022.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11, 1998.
Peter I. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):225--231,, 2019,
10

---

Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:/308.3433: 2013.
Vasek Chvátal. Hard knapsack problems. Operations Research, 28(6): 1402-1411, 1980.
Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming, volume 271. Springer, 2014.
Arnaud Deza and Elias B Khalil. Machine learning for cutting planes in integer programming: A survey. XrXiv preprint arXlv:2302.09166 2023.
Herbert Edelsbrunner. Algorithms in combinatorial geometry, volume 10. Springer Science & Business Media, 1987.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference on machine learning, pages 1587-1596. PMLR, 2018.
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, et al. The scip optimization suite 7.0. 2020.
Rishi Gupta and Tim Roughgarden. A pac approach to applicaionnsppeiffee algorithm selection. In Proceedings of the 2016 ACM Conference Innovations in Theoretical Computer Science, pages 123-134, 2016.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https: /ww
gurobi. com
Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cuts for efficient mixed-integer programming. Pattern Recognition, 123:108353, 2022.
Hans Kellerer, UIrich Pferschy, David Pisinger, Hans Kellerer, Ulrich Pferschy, and David Pisinger. Multidimensional knapsack problems. Springer, 2004.
Sammy Khalife, Hongyu Cheng, and Amitabh Basu. Neural networks with linear threshold activations: structure and algorithms. Mathematical Programming, pages 1 1-24, 2023.
Jiri Matousek. Geometric discrepancy: An illustrated guide, volume 18. Springer Science & Business Media, 1999.
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM, (5(7))33-335 2022.
George L Nemhauser and Laurence Wolsey, Integer and combinatorial optimization, volume 18.
Wiley New York, 1988.
John R Rice. The algorithm selection problem. Advances in computers, volume 15, pages 65-118. Elsevier, 1976.
Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley and Sons, New York, 1986.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pages 387-395. Pmlr, 2014.
Eduardo D Sontag et al. Ve dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96. 1998.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. In International conference machine learning, pages 9367-9376. PMLR, 2020.

---

Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming. Open Journal of Mathematical Optimization, 4:1-28, 2023.
Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Under- standing ttraight estimator in training activation quantized neural nets. arXiv preprint arXiv:1903.05562, 2019.
12

---

A Numerical experiments
In this section, for given ILP instance space I conforming to the description in Section 3.2, and fixed distribution ' over it, we primarily attempt to employ ReLU neural networks for choosing a CG cut multiplier for each instance in the distribution, which translates into addressing the following neural network training (empirical risk minimization) problem:
1 foG (
AROLU (CR.LU(..)
min W WERW
(2)
where 11, I1....,4 I are iid. samples drawn from D, and recall that po C.oLU CReLU(N"(EnCC) (Eno(-), w)).
N
This problem, concerning the selection from an infinite pool of cuts, presents significant challenge. The target function fcG, in relation to its parameters, is an intricately complex, high-dimensional. and piecewise constant function with numerous pieces (recall Lemma 3.2). making direct application of classical gradient- -aadee methods seemingly impractical. As such, we use an RL approach, with our goal switched to identify relatively "good" neural network for this distribution. Then, based on Proposition 3.3 and Theorem 2.3
the average performance the chosen parameter setting on sampled instances closely approximates the expected performance on the distribution in high probability, given that the sample size t is sufficiently large.
A.1 Experimental setup
Data. We consider the multiple knapsack problems Kellerer et al. [2044] with 16 items and 2 knapsacks, using the distribution utilized in Balcan et al. [022b] that the authors refer to as the "Chvátal distribution" as it is inspired by Chvátal [9800]. Our synthetic dataset has a training set of 5,000 instances and a test set of 1,000 instances from the same distribution.
Training. Each instance I sampled from the distribution D is treated state in RL, with the outputs of the neural network considered as actions in the RL framework. The neural network thus functions the actor in an actor-critic scheme (Silver al. (2014), where the reward is defined the percentage reduction in the tree size after adding a cut, i.c., fca(1.0) fea((..) The Twin Delayed [co(1.0)
Deep Deterministic Policy Gradient (TD3) algorithm Fujimoto et al. 2018 is used here for the training of the neural network.
The experiments were conducted on Linux machine with a 12-core Intel 17-12700F CPU, 32GB of RAM, and an NVIDIA RTX 3070 GPU with 8GB of VRAM. We used Gurobi 11.0.1 Gurobi Optimization, LLC [023] to solve the ILPs, with default cuts. heuristics, and presolve settings turned off. The neural networks were implemented using Py MyTcoch 2.3.0. The details of the implementation are available https: / thub. com com/Hongyu comm/ooonyyCCCeng/eaaarroooooo
A.2 Empirical results
Better cuts. The experimental results indicate that even a suboptimal neural network parameteri- zation can outperform the cut selection methodologies used in leading solvers like SCIP. Figure I presents the average tree size comparison across 1 1,000 novel test instances, with three distinct strategies:
1. The blue solid line represents the tree size when the cut is selected based the highest convex combination score of cut efficacy and parallelism, adjusted by a parameter μ E [0, 1] (incremented in steps of 0.01). The candidate set of cuts includes all CG and GMI cuts generated from the appropriate rows of the optimal simplex tableau.
2. The green dash-dotted line demonstrates a notable reduction in tree size when using cuts generated through our RL approach;
3. The purple dash-dotted line follows the same approach as 2., but uses linear threshold neural networks to generate CG cut parameters. The training process uses the idea of Straigh--Througe Estimator (STE) [engio et al. (2013) Yin et al. 2019).
13

---

weighted auxiliary scores
ReLU neural network
Averaged treesize 1000 Instances
Linear threshold neural network
560
520
480
440
400
360
0.0
0.1
0.3
0.4
0.5
0.6
0.8
0.9
1.0
M
Figure 1: Comparison of granch-and-boumt tree sizes using different cut selection strategies.
Faster selection of cuts. The cut selection using neural networks only requires matrix multipli- cations and ReLU activations, and is notably rapid and lends itself to efficient parallelization on GPUs. In contrast, the procedure for selecting CG and GMI cuts from simplex tableau based on a weighted combination of cut efficacy and parallelism scores requires solving LPs to get the simplex tableaux, which is considerably slower, and compare potential cuts. Our empirical studies, conducted on a test set 1,000 instances repeated 100 times, highlight the significant disparity in computational speed, shown in Table T
without taking into account the time score
Table Comparison of the computational speeds between ReLU neural network inference and solving. This table presents the total time in seconds for 100 runs on a test set of 1,000 instances.
TASKS
TIME
Computing cuts via trained neural network on GPU
0.010
Computing via trained neural network CPU Solving required LPs using Gurobi
0.055
2.031
B
Auxiliary lemmas
Lemma B.I. For any æ1, Enz A..... An > O, the following inequalities hold:
+ log (
log x S
(3)
X1
d1 + Ap Ar
(4)
X + An
Lemma B.2 (Theorem 5.5 in Matousek 1999 Lemma 17 in Bartlett al. 2019], Lemma 3.3 Anthony et al. 1999), Theorem 1.3 Edelsbrunneri 1987 ). Let P C R and let f1....,
R I with / 2 L be functions that polynomials of degree when restricted to P. Then
pEP)]
0.
8+1
(ttpeffff(()....ss.....f P
m 1,
[+1
22em
:p P)] <
m 2 2.
l
14

---

Lemma B.3. Let h: I + R define parameterized function class with P S R', and let H. be the corresponding hypothesis class (Definition (.1). Let m N and R: + N be function with the following property: for any / E N and /1, ......7, E I, there exist R(() subsets Pi. PR(() of P such that p P P, and, for all i E [R(()] and j E [4] ( p) restricted to P; is polynomial function of degree most depending on at most E _ E the coordinates, In other words, the map
p (0(11,)).. p(,....((((Ipp))))
is a piecewise polynomial map from P to IR. with at most R(()) pieces. Then,
(2et(m+1) 1)
Pdim(H) S sup t 2213 12::2-11- S R(t)
8
Proof.
Given any 1 E N and (i), (T,, 8t) E x R, we first bound the size of {(sgn(h(41,)) p) - sgg)..,,,,n((
p) st)) E PJ.
Within each P,. p) 8y is a polynomial in for every j 1....,t ,.. given the hypothesis.
Applying Lemma B.2
(2et(m + +1) e
((sgg(((T1, ................................ sgg(h((. :
Summing over the different P., i E [R(t)], we obtain that
(2et(m + 1)
((sga(h(I1, p) "o)......snn(hhe p) st)) P S 2R(t)
e'
Thus, Pdim is bounded by the largest such that 2 < 2R(t)
2nt(m=+
F
Lemma B.4. Let ReLL IRd W R be neural network function with ReLU activation and architecture w = [d, Wi...... WL, E (Definition 2.4p. Then for every natural number >> LW, and
x² any x² xx E RRd, there exists subsets WI,..., We of T.W with Q S 24 2et ( (ion:) L.W
LW
whose union is all of R such that N(x), w) restricted to w E W. is a polynomial function of degree at most T. + 1 for all (1,5) [Q] x [t].
Proof. Follows from Section 2 in Bartlett et al.
1998 and Section 4 in Bartlett et al. 2019
Lemma B.5 (Anthony et al. 1999 Sontag et al. 1998 ). Let Negn : :o x TR W - TR be a neural network function with sgn activation and architecture
[Wo, W1,..., wL, f), where the final linear
transformation Ti+11 is taken to be the identity (Definition 2.4). Let W + + wr denote the size of the neural network. Then for every i N, and any x ,...,,'' I wh there exists subsets
WI,..., Wq of IR. with Q (etl) W' whose union is all of R where W = El_ (w;-1+1)
such that Negu (xd, w) restricted any W; is constant for all (i.j) [Q) x [1].
R tho Consider a neuron in the first hidden layer. The output of this neuron on the input x² is sgn (a, x²) + b), where a E R b E R are the weights associated with this neuron. As function of these weights. this is linear function, i.e., a polynomial function of #1
Proof. Fix a t E N and x .'..,"...,,
degree 1. Applying Lemma B.2 there are at most
regions in the space (a, b) " RR
such that within each region, the output of this neuron is constant. Applying the reasoning for the neurons the first layer, we obtain that the output of the first hidden layer (as a 0/1 vector in Re1) is
(wo (1)+)))
piecewise constant as function of the parameters of the first layer, with at most pieces. For a fixed output of the first hidden layer (which is vector in R ), we can apply the same
#0++T
(wi+1)us
reasoning and partition space of weights of the second layer into w1+1
regions where the
output of the second hidden layer is constant. Applying this argument iteratively across the hidden
15

---

layers, and using the inequality with at most
4
in Lemma B.
we deduce that decomposition exists for R
(wo (wo+1)er
(wi+1)ez
wel--+1)wx
et
et
et
W/ +
Wi +1
WT-1 +1
(w1+1)
( 1a--111/0
et
et (wo + 1) W1-1 +
et
100 +
w
ctw1
etwy
W
W
W
ctU
W
regions, such that within each such region the output of the last hidden layer of the neural network is constant, as a function of the neural network parameters, for all the vectors x , x".
C Proofs of main results
Proof of Theorem 2.5
Let h: Ix R.W. R
h(I, w = S(I, fo
N Sigmoid (I))
using the notation from Section 2.2 We wish apply Lemma B.3 on the parameterized function class given by h with P = R. for any natural number W, and any I1, II...., Lt. the function piecewise polynomial function on R w with at most R(t) pieces.
Accordingly, we need to find function R N - N such that (h(I,, ......... h(I,, w)) is
We consider the space of the neural parameters parameters of the neural network, except for the last linear transformation TL+1, and the space Rex= of matrices representing this final linear transformation. Thus, we identify one-to-one correspondence between W and W x &xxwL
Cartesian product of the space W" of all the
By Lemma B.5 there exist decomposition of W" into at most (ct)) regions, where W W - Ewr, is the number of parameters determining the space W such that within each region, the output of the final hidden layer the neural network is constant (as function of the parameters in the region) for each input Enc(L,), j [t].
We fix the parameters w E WV to be in one of these regions and let z be the (constant) output corresponding input Enc(1;) for any parameter settings in this region. Let us consider the behaviour of Sigmood((A (A++12²), which is the result of sigmoid activation applied the final output of the neural network, as a function of the final set of parameters encoded by the matrix A 4 E Rx We follow the approach used in the proof of Theorem 8.11 in Anthony et al. 1999 For each & E [e]
WL
(Sigmoid(A 4+1 2 + exp( (A (1 2())
F (e
W2
(e 1-
A y
Let 02: e A for i E [WL], we have
I Ozi
(igmmid(A44H)) 4
T Ozs (II. 1h 01+2?
Note that the right hand side above is a ratio polynomials Oss with degrees at most 2
Next, as per the hypothesis of Theorem 2.5 let wi...., of be the polynomials on RR, each of degree a polynomial with degree at most À within each of the regions where the signs of vif,... ... ot constant. Moreover, let 7 [0, 1] P be the affine linear map T(u) 7/k (Tx Ti Uk. We observe then that for all T such that the functions
at most 7. such that the function S
No (Siigmoidd( 4+1 (+ttzz))),,...
(T( (+11))))
16

---

have the same signs, then h(1,, (w, (wt) - S(1,, P Sigmoid (I₃)) is poly- w.At++1 nomial of degree at most A. By the observations made above, the functions vi (Siggmoid(AA ()))) ................................ off (Sigmoiid( z2)))
rational functions, i.e., ratios of polynomials, in the transformed parameters 8k, and the numerators and denominators these
rational functions have degrees bounded by 2w Since sgn (5) = sgn (gQ( for any multivariate
polynomials P. Q (whenever the denominator is nonzero), we can bound the total number of sign patterns for (T(igiiio (44=22)))) .... of (T(Sigmoid((A+)))
using Lemma B.2 where polynomials defining the regions have degree at most 3 on the transformed parameters 0zi- We have to consider all the functions v (I (A )).),, (Sigmoid for j [t]. giving total of tf rational functions. Thus, application of Lemma B.2 gives decomposition of Rexws into at most
2e IT' 3ywE
EUz
GetyT
ELL
regions such that h( (w, A)+)) is a polynomial of degree at most within each region. Combined
with the bound ( (wrr W on the number of regions for w E W', we obtain a decomposition of the
full parameter space W x Re g into at most
etU W
W
6EtyI
bug
R(t)= =
2
regions, such that within each region h(4z, (w, A )), as function of (w, AW, is a polynomial of degree at most X, for every j E [t]. Moreover, note that within each such region, ho( (w, (w,A4+1) A
depends only on AL+1, Applying Lemma B.3 Pdim (FS NNeE (iign,i is bounded by the largest
t N such that
EtU W
W GetyT Evor (2ct(A+1) 2
(
2'-1
Ew,,
Taking logarithms on both sides, we want the largest such that
1 5 (t 2)
etU
(GetyI"' + fwr log
(2et(A +1)
w' log
+ twr log
W
Eurr.
As we only need to derive an upper bound for the pseudo-dimension. we can loosen the inequality above using the inequality in Lemma B.T
1 (1 2) Sw"
etU/W" BeU
6etyT/e
+ log(8U) + EuFr.
48e7Twr +log(487[wr.)
2
2et(A+ + ()/(L + log(16(A +1)
+ tW1
16e(A + 1)
1 + W log(SU) + 8
two log(487TWi) + -t Lwi log(16(A + 1))
3
48yTwL 16(A + 1)
t + W log(8U') + tuz log
8
8U
3
W log(SU) + lwn log(96-T(2 UU)
then it's not hard to that
Pdim NeNTgmaaii = O (W log U + twr log (>I(A + 1))) = O (Wlog(U>T(A + 1)))
Proof of Theorem 2.6
Let h I R W
+ as
RoLU _CReLU (I)),
h(1, w) S(1, v
17

---

using the notation from Section 2.2 We wish apply Lemma B.3 on the parameterized function class given by h with RW. Accordingly, we need to find function R : - N such that for any natural number i >> IW, and any / /,..... I, the function w + (N(T, w)... TT,,, w)) is piecewise polynomial function on R# with at most R(t) pieces.
Note that BBLL and architecture [d, wi,.... WL, 26, E]. where the final linear function is the fixed function Tu) (Th Th UR. This is because (x)) = (e) ReLU(x 1) can be simulated using two ReLU neurons. Applying Lemma B.4 this implies that given t N and II....,
(R) @BeLL,,CRLUU (I) can be seen as the output of a neural network with ReLU activations
.......II I I, there are
2et Σ ( (L (L+ 1)W
(L+1)W
2eet(U + 28) 2
(L+1)W
Q S 24+1
W
regions Wi...., We whose union is all of IR" ssuch that sp Not.U (CRELU (I,) restricted E W; a polynomial function of degree at most L + for all (i. E [Q] x [t].
Next, as per the hypothesis of Theorem 2.5 let vi...., off be the polynomials on R', each of degree at most 7 such that the function S(4 :) a polynomial with degree at most À within each of the regions where the signs of vi. vi...., .,, e are constant. Thus, for all E RW such that
(1 (((eR))EcRRoL)(())))
www.y//w..W......o Rol,U, (Iz))
have the same signs, then h(1,, w) S(1j, P ReLU,CReLU (1)) is a polynomial of degree at most X(L + 2). The functions vf (y.ReLt, (1,)). .,. (ww.wl M...L.,,CRe..UUA. are polynomials of de-
(
gree at most r(L + 2). Considering all these polynomials for E [t]. by Lemma B.2 each W; S R
from the decomposition above can be further decomposed into most 2 (2el+x(L+2)
regions such that for all in such region, h[[J, w) is polynomial function of of degree at most X(L + 2).
To summarize the arguments above, we have a decomposition of W into at most
R(t) = 24+1 (201U + 28) (L-1)W
2 2 ( (2 2)) W
W
W
regions such that within each region, h(lj, w) is polynomial function of w of degree at most
X(L + 2). Applying Lemma B.3 Pdim F c.rLuu is bounded by the largest E N such that
2'1 22-1 (2ct(U
+ 28)
(L+1)W
+
(2et(At ()( + +2) W
2
W
W
W
which is bounded by the largest such that
2et(U + 20)
2etl'n(LL + 2)
5 11 5L21))++++(00 1)W log
+ W log
W
W
2el(A + 1)(L +
+ W log
W
1 - + (L+ + 1)W log(16(U + 20)) + 5tt + W log(161 + 2))
<L + 2+ +
1 + W (o6(( +)
3 t (L+ 1)W (o6( + 26)) + W Wog(>T((A+ + 1)) - 2W log(16(L 2)),
< + 2 +
where the inequality
in Lemma B.I is applied in the second line. Then it's not hard to see that
Pdim F
(ERLL,CRRaU)) R CRRLU)
O (LW (LWloggU + E) + W Woog(>I(A + 1)))
18

---

Proof of Corollary 2.8 We introduce an auxiliary function f: + {pI..... pr} given by f(x)
Parg mg)) and let S' I R
R be
(I, S(I, f(x)..
There exists decomposition of the R" space obtained by at most rir-1) hyperplanes
2
{x E RR' x = v(i,)) [r) +.
Within each decomposed region, the largest coordinate of is unchanged. Therefore, for any fixed E I, the new score function (), remains constant each of these regions. Then a direct application of Theorem 2.5 and Theorem 2.6 S" yields the desired result.
Proof of Proposition 3.7 The proof of Proposition 3.7 is analogous to the proof of Theorem 4.1 in Balcan al. 2021d]. For any fixed instance I, let the set of candidate cutting planes be (1..... Cc J. Comparing the overall scores for all cuts introduces the following hyperplanes:
m4 Score; 1)
Σ ny Score; 1), Vj, [[CI),5 #
There are at most C[([[-11) hyperplanes decomposing the μ space [0, 1] Within each region defined
2
by these hyperplanes, the selected cut remains the same, the branch-and-cut tree size is constant. This proves that fs([, μ)) is a piecewise constant function on μ., for any fixed then apply Theorem 2.5land and Theorem 2.6 to derive the pseudo-dimension bounds.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction indeed clearly state the main contributions and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our work are adequately discussed in the final section of the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
20

---

Answer: [Yes]
Justification:
All assumptions are clearly stated, and all proofs are provided in Appendices
and[C]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The details of the implementation are available at
com/
Hongyu- Chwngn/Leaeannnnsnngggl The details explained in the README file.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
21

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The details of the implementation are available at Hongyu- hheee/uuhhhhn/aaaaanCSSnnsiig The details are explained in the README file.
com/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
btiaps..c/puulic/guuu
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This paper primarily focuses on theoretical aspects. However, the de- tails of the implementation available at https://github. com Hhtp//oonnuucggg/////e LearnCGusingUNi
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: This paper primarily focuses theoretical aspects. The computational experiments in the Appendix A are only to provide some crisp insights and to verify the theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
22

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: These are clearly stated in the Appendix A. and in the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
in
Answer:
[Yes]
Justification:
The research conducted in this paper conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This paper has no societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
23

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not release any data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The assets used in this paper have been properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
24

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not introduce any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "NPyiPDG7hw", "reviewer": "Reviewer_vkrW", "summary": "The authors study the problem of algorithm selection for specific instances of a problem. In particular they provide theoretical results for the learnability of a mapping from problem instances to algorithm parameters with application to branch-and-cut. They establish sample complexity bounds for learning a few different neural network architectures for this task. The appendix includes some synthetic experiments where they apply this method.", "questions": "- Theorems 2.5 and 2.6 assume that the parameter space can be decomposed into regions where the function remains polynomial with bounded degree. Is this realistic? \n- Besides tree size, have you evaluated other measures of performance for branch and cut or other problems?\n- What is the practical interpretation of the established bounds for algorithm selection on this problem? How does it inform network design / historical instance curation ?", "limitations": "The authors discuss the limitations appropriately in the conclusion.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is theoretically rigorous and studies a significant problem (algorithm selection for problem instances). The use of a data-driven / ML approach is interesting and appears novel. It appears to this reader to make a signficant theoretical contribution.", "weaknesses": "- although sample complexity bounds are valuable, their practical interpretation for large scale problems is unclear. relating the established bounds to the state of practice for branch and cut, for example, might help shed some light on the importance to practitioners.\n\n- the actual neural network training is done via reinforcement learning, suggesting sample complexity is only one of many challenges to be addressed in generating high-utility NNs to solve this mapping problem. \n\n- the paper focuses on branch-and-cut methods for mixed-integer optimization, and generalization to other algorithmic problems is not thoroughly explored.\n\n- the work is centrally focused on theory, so naturally the empirical contribution is minimal, essentially left to the appendix.\n\nMiscellaneous:\n\n- the algorithm exist early -> exits early", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review.\n\n**Weaknesses:**\n\n- 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.\n\n- 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.\n\n- 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. \n\n- 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. \n\n**Questions:**\n\n- 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.\n\n- 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.\n\n- 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.", "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": "", "extra_scores": {}}, {"review_id": "IgadmbMciJ", "reviewer": "Reviewer_vvGd", "summary": "This paper studies data-driven algorithm design, which learns a class of algorithms to optimize the expected performance scores given i.i.d. samples of instances.\nIn particular, the paper studies the sample complexity of learning (the weights of) neural networks computing the size of certain branch-and-cut trees for mixed-integer programming.\n\nBased on the results of Balcan et al. to bound pseudo-dimension, this paper studies learning neural network weights to compute the size of certain branch-and-cut trees, avoiding the need to optimize for weighted combinations of auxiliary score functions for each new instance, and getting smaller tree sizes.", "questions": "For the original question—solving mixed-integer programming but not only to minimize branch-and-cut tree sizes—what does the results of the paper imply?", "limitations": "This is a theoretical paper that do not have broader societal impacts.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well written, including the context of research (to motivate data-driven algorithms and mixed-integer programming), overview, and technical aspects (neural networks, the technical definition of pseudo-dimensions).\n2. The idea to study data-driven algorithm designs using neural networks to solve mixed-integer programming is new (unlike previous works studying weighted combinations of auxiliary score functions), and the result applies to a general class of neural networks.\n3. The technical argument (to bound pseudo-dimension of neural networks) is intuitive, given the existing works to study data-driven algorithm design with pseudo-dimension.\n4. The theoretical improvement is experimentally verified on a synthetic dataset with thousands of instances.", "weaknesses": "1. The application to the size of branch-and-cut tree for integer linear programming with Chvátal-Gomory cuts (parameterized by multipliers at *root*), or with Gomory Mixed-Integer cuts (at *root*), are somewhat limiting (as pointed out in the Discussion section). This reader thinks that the applications are chosen so that the geometric analysis argument can go through to bound the pseudo-dimension (hence to apply Theorems 2.5 and 2.6, Corollary 2.7), and unlikely to generalize to effective bounds in more general settings, where the geometric picture will be more complicated, which needs to account for both the neural netorks and (the nodes inside) the branch-and-cut trees.\n2. The theoretical bounds are asymptotic which are unlikely to have effective/small constants.\n\nNitpick:\n* In some places, the paper uses branch-and-*bound* tree, while in most places (including the title) the paper uses branch-and-*cut*. It may help to use a consistent name.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review.\n\n**Weaknesses:**\n\n- 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.\n\n- 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$.\n\n**Questions:** \n\nWe 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.\n\nBranch-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.", "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": "", "extra_scores": {}}, {"review_id": "lNiOdFC039", "reviewer": "Reviewer_FoeV", "summary": "The paper introduces an approach to data-driven algorithm design by leveraging neural networks to select the most appropriate algorithm for a given instance of a computational problem. The motivation is clear. This paper decision to extend the paradigm from selecting a single best algorithm to a context-specific selection. The introduction of neural networks as the parameterized family of mappings is a novel approach that could potentially offer significant benefits in terms of adaptability and performance. Overall, the paper presents an interesting approach to algorithm selection and parameter tuning using neural networks. The theoretical grounding and practical motivation are commendable.", "questions": "(1) Can the author elaborate on the role of theoretical guarantees such as the bounds on pseudo-dimension and sample complexity? How do these theoretical results translate into practical performance, and what are the limitations of the theoretical framework?\n\n(2) For neural networks with different activation functions, this paper gives different bounds. What results will be produced when there are different activation functions in the neural network?\n\n(3) Neural networks are often considered black boxes, making it difficult to understand why a particular parameter set was chosen for a given instance. How does the sample complexity of theoretical analysis guide the learning of specific algorithms?", "limitations": "While the paper mentions deriving rigorous sample complexity bounds, the tightness of these bounds and their practical implications need to be carefully evaluated. The theoretical guarantees may not always translate directly to strong empirical performance.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The methodology of using neural networks to map problem instances to the most suitable algorithm is well-articulated. The derivation of rigorous sample complexity bounds is a strong theoretical contribution, providing a solid foundation for the practical applications discussed later. The integration of these theoretical insights with practical computational experiments is a strength of the paper.", "weaknesses": "(1) Training Overhead: Training neural networks can be computationally intensive, especially when dealing with large and complex datasets. The time and resources required for training may limit the scalability of the approach.\n\n(2) Inference Time: While the method aims to optimize performance on a per-instance basis, the inference time for selecting the optimal parameters using a neural network could be longer than traditional static parameter selection methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful review.\n\n**Weaknesses:**\n\n1. 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.\n\n2. 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.\n\n**Questions:**\n\n1. 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.\n\n    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. \n\n2. 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:\n\n    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 \n    $\\mathcal{O}(LW \\log(p(U+\\ell)) + L^2W \\log(d) + W \\log(\\gamma \\Gamma(\\lambda + 1))).$\n\n    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.\n\n3. 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.\n\n**Limitations:** \n\nIndeed proving complementary lower bounds on the sample complexity would be good.\n\nWe 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.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper contributes to the development of the data-driven algorithm design area by providing theoretical results (sample complexity bounds ) for the learnability (via neural networks) of a mapping from problem instances to branch-and-cut algorithm parameters.
Notwithstanding issues about the real efficiency that can be obtained by exploiting the bounds, mainly linked to the training process of the neural network, the proposed results are timely and significant. 
Rebuttal contributed to clarify several of the related issues raised by reviewers, leading some of them to raise their scores. Moreover, in the AC/reviewers discussion the most negative reviewer (borderline accept) was in agreement with the proposal to accept the paper.
Decision: Accept (poster)