Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming
Authors: Hongyu Cheng
Amitabh Basu
Venue: NeurIPS 2025 poster ()
Keywords: Integer programming
branch-and-cut
cutting planes
branch-and-bound
sample complexity
learning theory
Primary area: optimization

Abstract: Mixed-integer programming (MIP) provides a powerful framework for optimization problems, with Branch-and-Cut (B&C) being the predominant algorithm in state-of-the-art solvers. The efficiency of B&C critically depends on heuristic policies for making sequential decisions, including node selection, cut selection, and branching variable selection. While traditional solvers often employ heuristics with manually tuned parameters, recent approaches increasingly leverage machine learning, especially neural networks, to learn these policies directly from data. A key challenge is to understand the theoretical underpinnings of these learned policies, particularly their generalization performance from finite data. This paper establishes rigorous sample complexity bounds for learning B&C policies where the scoring functions guiding each decision step (node, cut, branch) have a certain piecewise polynomial structure. This structure generalizes the linear models that form the most commonly deployed policies in practice and investigated recently in a foundational series of theoretical works by Balcan et al. Such piecewise polynomial policies also cover the neural network architectures (e.g., using ReLU activations) that have been the focal point of contemporary practical studies. Consequently, our theoretical framework closely reflects the models utilized by practitioners investigating machine learning within B&C, offering a unifying perspective relevant to both established theory and modern empirical research in this area. Furthermore, our theory applies to quite general sequential decision making problems beyond B&C.

Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming
Hongyu Cheng
Amitabh Basu
Dept. of Applied Mathematics & Statistics
Dept. of Applied Mathematics & Statistics Johns Hopkins University
Johns Hopkins University
Baltimore, MD 21218 hongyucheng@jin edu
Baltimore, MD 21218 basu. ami aaiiaabh@hii edu
Abstract
Mixed-integer programming (MIP) provides powerful framework for optimiza- tion problems, with Branch-and- (B&C) being the predominant algorithm state-of-the-art solvers. The efficiency of B&C critically depends on heuristic policies for making sequential decisions, including node selection, cut selection, and branching variable selection. While traditional solvers often employ heuristics with manually tuned parameters, recent approaches increasingly leverage machine learning, especially neural networks, learn these policies directly from data. A key challenge is to understand the theoretical underpinnings of these learned policies. particularly their generalization performance from finite data. This paper establishes rigorous sample complexity bounds for learning B&C policies where the scoring functions guiding each decision step (node, cut, branch) have certain piecewise polynomial structure. This structure generalizes the linear models that form the most commonly deployed policies in practice and investigated recently a foundational series of theoretical works by Balcan et al. Such piecewise polynomial policies also cover the neural network architectures (e.g., using ReLU activations) that have been the focal point of contemporary practical studies. Consequently, theoretical framework closely reflects the models utilized by practitioners investi- gating machine learning within B&C, offering unifying perspective relevant both established theory and modern empirical research in this area. Furthermore, theory applies to quite general sequential decision making problems beyond B&C.
Introduction
Mixed-Intee LixeedInteger Programming (MIP) provides a powerful optimization tool for problems arising in diverse fields such finance [Cornuejols et al. 2018), vehicle routing (Toth and Vigo 2014]. telecommunication. network design Kerivin and Mahjoub| 2005), production planning [Pochet and Wolsey| 2006). name few, where decisions involve both discrete choices and continuous adjustments. We focus on problems formulated as min {cTx x Ax < b, E Th R }. where E (mx((xtt
computational and systems biology [
E QTT, and с E * The predominant methodology for solving such MIPs is the Branch-and-Cun (B&C) algorithm [Jünger ct al. 2009 Conforti et al. 2014) (see Algorithm below for standard outline). B&C operates by exploring search tree where each node represents linear programming (LP) relaxation of a subproblem derived from the original MIP. The process involves solving these LP relaxations, adding valid inequalities (cutting planes) to tighten the relaxations without excluding feasible integer solutions, and partitioning the solution space (branching) by imposing constraints on variables, typically integer-constre condtrieed variables [nx]) that take fractional values in an LP solution. The practical performance of the B&C algorithm is critically influenced by the sequence of strategic
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

decisions made during this dynamic process, including how nodes are selected for exploration, which cutting planes are added, and which variables are chosen for branching [Achterberg et al. 2005].
Algorithm 1 The Branch-and-Cun Algorithm
Require: Initial MIP instance I, maximum rounds M, error tolerance Égap. 1: Initialize open node list L < [No). UB + oo, LB + -0, x* - null, i +-
2: while C + and UB LB Egap and i M do
3: Node Selection: Choose N E via node selection policy; C + L) {N*}.
4: Solve LP at N"; let solution be x and value be z[p-
5:
Let aiP denote the LP value associated with any node E C.
6:
if L.P infeasible or =[P 2 UB then goto Line 18
7:
end if
8:
if' x'x is integer feasible then UB + = x < No Prune (remove) N E L with zMp 2 UB.
9:
goto Line 18
10:
end if
Decide whether to add cutting planes (goto Line 12b or branch (goto Line 15
12:
Cut Selection: Generate candidate cuts C; Select C C via cut selection policy.
Add C* N formulation. Keep N* unchanged if C
14:
Update L t L u ]," ). LB + minNe (z[p). and goto Line 18
15:
Branching: Select fractional variable index j [m1] from x via branching policy.
16:
Create Nr, N from N by adding constraints xj S (x[p), and xj 2 (xxF),
17:
Update L L U (Nz, Na), LB minNec(=
18:
+ +
19:
end while
Ensure: Best found incumbent solution x* and final bounds LB, UB.
Hcuristic procedures within B&C often rely on scoring rules to guide decisions. A prominent example arises in the crucial task of cut selection within state-of-the-an art solvers like SCIP (Achterberg] 2009 Gamrath et al. 2020]. At a given state s of the search (characterized, for instance, by the current problem (A, b, c), current LP solution x(p. and potentially the best known integer feasible solution x, often called the incumbent solution), a set AA" of candidate cuts is available. A cut selection policy must then choose beneficial subset from AA..
Many widely-used, human-designed heuristics implement this selection by scoring each candidate cut a E AA, represented by a x & B. These policies employ various feature extractors, functions that map the pair (s, a) to vealev quality measure. Key feature extractors used SCIP include Accherberg 2007 Wesselmann and Stuhl 2012
Gamrath et al. 2020):
Efficacy (der):: (e a) == (a x T - 0)/|||//l2. This measures the Fuclidean distance by which the current LP solution xip violates the cut.
Objective Parallelism (dot)): (s, a) == aa /eTc//(laa c[[[[[]/]2lll)))))) This measures the similarity between the cut normal a and the objective vector c.
Directed Cutoff Distance (shaca): This feature quantifies efficacy specifically in the direction from x towards the incumbent X, when is available and distinct from x[p. is computed as dasa (8, a) = (a X - B)/ T (x - x[p)1/1| x(pll2).
(j inn] a, + 0H/H( E [n] a; * 0}}, where n = T. + n2 is the total number of decision variables. This calculates the fraction of integer-constrained variables (j [mx)) among all variables involved in the cut.
Integral Support (dm)): Prm (s, a)
These feature extractors produce a vector Φ(s, a) = (def(ss a), (sj a), daa(s, a), Pm a))T R4. Policies like SCIP's s default Hybrid selector define the score using a linear function determined by a parameter vector
(W1, W2, Wa, w.) E R4. The score is computed
f(s, a, w) = w T o(s a) = wider(s, a) + W2 (s, a) Wadded a) + Wadma a). Crucially, the choice of the weight vector w defines specific eut selection policy within this linear scoring framework; different weights lead to different prioritizations of cuts. The weights w

---

typically vre-tuned based on extensive computational experiments, SCIP's more advanced Ensemble selector also employs weighted-sum score f(s, a. w') (w') o' a), but utilizes an extended feature vector d' (s, a) E' (where l may be larger than 4) that includes additional, often normalized. metrics like density, dynamism, pseudo-cost scores, and variable lock information [Achterberg 2007 The selection policy then chooses the cut a" that yields the highest score.
This practice of using parameterized, score-basee rules is widespread in B&C. For instance, beyond the linear scoring approach exemplified by SCIP's Hybrid cut selector, other critical decisions also rely on similar mechanisms. Branching variable selection frequently employs heuristic scores derived from informative features, such as pseudo-costs which estimate the impact of branching on candidate variables (Achterberg] 2007] Achherberg et al. 2005]. Node selection strategies also commonly utilize scoring based various node attributes [He et al.] 2014, Yilmaz and Yorke-Smith [02T]. The prevalence of such score-guided heuristics across multiple B&C components motivates our study of such policies within the following general framework.
Let S be the state space, Each state & E S contains the information available at a given step of the branch-and-cut algorithm (Algorithm D including the tuple (C,x*, i, N*). Let AA be the space of possible actions for a specific decision type is (e.g., k = 1 for node selection, & = 2 for cut selection, S. let A C AA denote the set of available actions of
k for branching). For given state type & for state (e.g., A$ = A in the example above contains candidate cuts). The goal is to learn a parameterized scoring function f& : S x A& x W/ + R.,, parameterized by w* E WR. where Wa is the parameter space (e.g., the weight vector in the SCIP Hybrid example belongs to W2). This function evaluates potential actions E AG. A fixed feature extractor function d2 : S x A + R4 maps the state-action pair (x, a) to a feature vector (e.g., Φ(s, a) E IR for = 2 in the example above). The scoring function often takes the form fu a, w a/x (oh (s, a), w*). where thx could be an ML model like a Multi-Layer Perceptron (MLP, Definition 3.6) or, as exemplified by SCIP's Hybrid selector, a linear function Uxx (óx((ss, a), w*) (w*)² ( (s,a), a). The chosen action a" is typically one that maximizes the score, selected according to a* arg aa fu a, w*)
(with a consistent tie-breaking rule). Training the parameters w often relies on supervisory signals from an expert function or oracle, which provides high-quality action evaluations (e.g., Strong Branching scores [Alvarez et al. 2017). exact bound improvements from cuts [Paulus et al. 2022 or assesses the overall impact on the search (e.g.. reduction in runtime or tree size [Huang et al.) 2022)
Supervised learning methods then use these expert-derived values as targets or labels to optimize w".
2 Prior work and our contributions
We first discuss prior computational and theoretical work using ML techniques to make B&C decisions, and then describe our contributions in that context. We will use the language of the general framework described above to discuss everything in unified way.
2.1 Related empirical work
Learning to select node. (Action type k = 1) Selecting which node to explore next from the queue L of active nodes (i.e., the set of potential actions Af = L) is a critical B&C decision. He et al. 2014) learn a linear scoring function where fi a, w = (w2) di (s, a), to score each candidate node E Ai. For each candidate node its features Φi (s, a). categorized as node, branching, and tree features, are obtained using information typically recorded by solvers. The node with the highest score is selected, with the policy trained to imitate an oracle that exclusively explores nodes leading to an optimal integer solution. Differing in scope. Yilmaz and Yorke-Smith (2021) learn a policy for child selection. Their scoring function uses MLP classifier 1/1 This MLP takes input features comprising 29 base metrics (listed in their Table 1). These include features of the branched variable (e.g., its simplex basis status), features of the newly created child nodes (e.g., their bounds), and tree features (e.g., global bounds and current depth). The MLP computes scores fi (s, a, w') for three distinct actions following branch-exploring the left child node, the right child node, or both children, and selects the action with the highest score. Their expert policy is derived from paths to the top-k known solutions.
Learning to cut. (Action type k 22) In state 8, an action a E Ai corresponds to selecting candidate cuts at node N Huang et al. [2022) use fixed features dz a) E 1d (detailed in their
3

---

Table 1) as input to an MLP l/2. This MLP outputs a score f2(s, a, w²) = (s, a), w²) for each cut, and cuts with the highest scores are selected. Their expert oracle assesses the quality of sets (bags) of cuts based on overall runtime reduction. Pauuuus et al. [2022] also utilize a fixed initial feature representation (as detailed in their Table 5, based on Gasse et al. 2019 ), encoding the LP relaxation and candidate cuts A as a tripartite graph. Their scoring function is complex model comprising a Graph Convolutional Neural Network (GCNN), an attention mechanism, and a final MLP (the entire set of parameters for this composite model is learned from data). This function produces a score for each cut, and cuts with the highest scores are then selected. Their expert signal is the exact LP bound improvement (Lookahead score) from individual cuts.
Learning to branch. (Action type & = 3) In state s, an action a E Ağ represents choosing a fractional variable a E [ng] to branch on within node N Strong Branching (SB) often serves as the expert oracle for this task. Khalil et al. [2016] proposed a linear scoring function fa(s, a, w²) (w²)T (5 a). Their fixed feature extractor Φ3(8, a) computes features (based on 72 atomic features as detailed in their Table 1) describing candidate variable
the context of the current node. The variable a with the highest score fs w²) is selected for branching. Similarly, Alvarez et al. [2017] used an Extremely Randomized Trees model [Geurts et al. (006) to directly predict SB scores Ja(s, a, w"); here, the parameters w define the learned structure of the tree ensemble. Their fixed feature extractor (s(s, a) calculates features for variable a based on static problem data, dynamic information from the current LP solution, and optimization history. The variable a E [ma] yielding the highest predicted SB score chosen.
These learning-basse -ased strategies empirically demonstrate the potential to automate the design of high-performance policies for various decisions within B&C solvers, including node selection, cut selection, and branching, by leveraging data and expert knowledge in a structured manner. Consequently, establishing a rigorous theoretical foundation for these learned policies, particularly regarding their sample complexity and generalization guarantees, becomes essential.
2.2 Related theoretical work
In statistical learning theory, the goal is to find a parameter w E W that minimizes the expected cost E,-D[V (I, w)]. where V I x W + [0, H] is cost function bounded above by some H >> 0, and D is an unknown distribution over the instance space I. In the context of branch-and-cut, (T, w) represents measure of the overall performance (e.g., final tree size, solution time) when applying a policy (for node, cut, and branching variable selections) parameterized by w to solve the initial problem instance I. Since D is unknown, usually rely on an empirical estimate derived from finite sample (/,,... } C I drawn independently and identically distributed (i.i.d.) from D, by selecting the parameter that minimizes the empirical average 1/ E V(4, w). A fundamental question concerns the sample complexity of uniform convergence: how fast does the empirical average converge to the true expectation, uniformly for all parameters E W, as the sample size N increases?
Standard results relate this uniform convergence rate to measures of the complexity of the function class = (V(, w) ++ [0, H w E W). One such measure the pseudo-dimensio Pdim(V)).
and classical results (see, e.g.. Pollard 1984 give bounds of the form: with probability at least 1 - 8,
Σ -) EL-o = = ( H N
Pdim(V) log(1/5)
sup WEW
(1)
N
significant line of research establishing rigorous sample complexity bounds for data-driven al- gorithm configuration was initiated by Gupta and Roughgarden [2016). This PAC-style approach inspired investigations into the learnability of parameters for vanoos algorithms by analyzing the structure of algorithm performance with respect to its parameters. Recent applications include configuring components within B&C (such as variable selection (Balcan et al., 2024b) and cut generation/selection [Balcan et al.) 2021c| 20226 2021a Cheng et al. 22]4202 Cheng and Basu 2024)). ). learning heuristic functions for graph search algorithms Sakauu and Okil 2022], tuning parameters for iterative methods like gradient descent Jiao et al. 2025). configuring data-driven projections for linear programming [Sakaue and Oki 2024], J, analyzing combinatorial partitioning problems [Balcan]
et al. 2017]. mechanism design for revenue maximization [Balcan et al. 2025b), tuning ElasticNet

---

[alccan et al., 2022a hyperparameter tuning in neural networks Balcan et al. [2025a], and learning decision trees [Balcan and Sharma 2024]. Building on the techniques used across these diverse applications, Balcan et al. formalized and generalized the approach, particularly emphasizing the role of the piecewise structure of algorithm performance in establishing sample complexity guarantees |Baccan et al., 2024a c Related theoretical foundations, surveys, and analyses are also available in Balcan 2020 Balcan et al. 2021b].
The first application of this PAC learning paradigm specifically to the B&C setting was presented by Balcan el. [2024b] (first appearing in ICML 2018), who analyzed learning linear variable selection policies. They showed that the B&C tree size is piecewise constant function of the linear weights, enabling pseudo-dimension bounds. Subsequently, [Balcan et al. (2021c) extended this line of research significantly. They considered learning parameters for generating Chvátal-Gonee Gomory (CG) cuts and policies selecting cuts based on weighted combinations of standard scoring rules. They showed that sequential CG cuts induce a piecewise structure defined by multivariate polynomials, and that weighted scoring rules lead to piecewise constant behavior with respect to the weights. Importantly, Balcan et al. [2021c) also introduced and analyzed general model of tree search, providing sample complexity bounds for simultaneously tuning multiple components (like node, variable, and cut selection) when guided by linear scoring functions. Further refinements came from Balcan et al. [021a]. who exploited the path-wise nature of many common B&C scoring rules within their general tree search model to derive exponentially sharper bounds, dependent on tree depth rather than total nodes, for policies using such rules. Addressing the challenge of infinite cut families, Baacaan et al. (022b analyzed the learnability of Gomory Mixed-Intes (GMI) cut parameters, establishing piecewise structure defined by degree- 10 polynomial hypersurfaces.
More recently, theoretical work has begun to incorporate nonlinear models used in practice. Cheng (ct al. 2024] studied the sample complexity of using neural networks to map instances directly to algorithm parameters (specifically for cut selection), analyzing the complexity in terms of the neural network weights. Expanding on the types of cuts considered, Cheng and Basu [2024) investigated learning parameters for general Cut Generating Functions (CGFs). CGI's provide broad theoretical framework for deriving cutting planes, generalizing classical families like CG and GMI cuts (see [Basu et al. [2015) for a survey), and thus represent a promising avenue for enhancing B&C performance. Cheng and Basu 2024) derived sample complexity bounds for learning parameters within specific CGF families and also explored learning instance-dependent CGF parameters using neural networks.
2.3 Our contribution
The present paper contributes to this theoretical foundation by establishing rigorous sample complexity bounds for learning B&C policies where the scoring functions fx a) guiding each decision step (node/cut/branching variable selection) belong to the class of piecewise polynomial functions
with respect to the parameters w. This class, formalized in Definition 3.1, provides unifying lens. It naturally includes the linear models studied previously [Balcan et al. 2024b 2021c) and, as shown below in Proposition 3.4. our results improve upon the existing bounds for this
Balcan et al.] 2021c| Theorem 5.2]. Crucially, this framework also encompasses the neural network architectures (e.g., MLPs with ReLU activations) prevalent in recent work described above in Section 2.1 Lemma 3.7 below, building on Anthony and Bartlett [1999] and [Brtleett et al. (2019). confirms that such networks yield scoring functions with the required piecewise polynomial structure.
By establishing that piccewise polynomial scoring functions induce a related piecewise structure in the overall cost metric V(L,-) (Theorem 3.3 our work bridges the gap between prior theory (largely focused on linear scoring rules [Balcan et al. 2021c a 2024b) and current practice involving neural networks. We derive pseudo-dimension bounds (Propositions and 3.8) applicable to both linear and neural network-based policies, leading to distribution distribbtion-indeeenddnnn sample complexity guarantees via (I) The identified structure also opens the door to potentially tighter, detendepnndent guarantees via empirical Rademacher complexity Prroposition3.9)
Our techniques apply to more general sequential decision making problems beyond branch-and- cut. We develop this more general theory first in Section and then derive the consequences for branch-and-cut in Section[4]
5

---

3 General Framework and Sample Complexity Bounds
We consider general setting involving an iterative procedure operating state from state space S. The procedure starts from an initial state so E S, which is typically derived from an initial problem instance I I. The procedure may consist of multiple rounds (e.g., corresponding to processing nodes in a B&C tree), where each round involves executing d distinct types of actions sequentially. For any state transition function determines the next state s' if action E A is selected in state s. The selection of an action a" E Ai is guided by parameterized scoring function f6 As = Usee sES Ag. The function f& takes the current state candidate action a, and parameter vector w Wi C RR
S, there exists a set Ai, of available actions of action type k E [d].
A& x W₁ + R_, where
imput and returns score. Fixing the parameters wt.... ..... w determines a decision policy, and the goal is to select good policy, i.e., a good set of parameters, as determined by penalty functions Pk S A X N + R for each action type k. The value (s i) represents the penalty obtained when taking action a in state s and round i. Algorithm ooutlines this general process, including penalty accumulation, employing greedy action selection strategy based on the scoring functions at each step.
Algorithm A Sequential Decision Process that Generalizes B&C
Require: Initial state E S, terminal states S C S. policy parameters w E WR. scoring functions Sk : x A x We -> IR, penalty functions Pk S A x N -> for lt E [d], max rounds M.
1: Initialize 8 <- 8g, i 4- 0, V +- O.
2: while s & S and < MM do
3: for k == 1 to d do
4: Determine available actions A for state 8.
5: if Aí then continue
6: end
7:
Select action a" arg max, far (s, a, w²). Break ties by lexicographic order. Accumulate penalty - + Pi((s, a", .1).
8:
9:
Compute the state s' that results from applying action a" in state Update state 8 + s'.
10:
11:
if s E S then break end end for
12:
13:
14:
i+i+1. 1.
15:
end while
Ensure: and V.
3.1
Worst-case sample complexity bounds
Let (I, w) denote the total penalty (overall cost) obtained when Algorithm 2 executed starting from initial state derived from instance I E I. using policy parameterized by w (w² ...., w where each component - E Wi C R T provides the parameters for the k-th action type's scoring function. The overall policy parameter space is W Ih Wi S R.W with W - W being the total number of parameters. This overall cost V w) serves as a measure of the policy's effectiveness (e.g., runtime), and the goal find that minimizes E (I, w)] (see Section 2). To analyze the sample complexity of learning w via i.i.d samples from D, we aim to bound the complexity of the function class V (V(:w) dimension Pdlim(V) Our theoretical analysis relies on specific structural properties of the scoring functions f employed each step of Algorithm 2 To formalize this, let us first define a general structural property that has piecewise behavior.
- [0, H w E W), typically via its pseudo-
Definition 3.1. Let G be a class real-valued functions defined on a domain X C R' for some l N. We say G has (T" 7/, (B)-structure if for any finite collection of N functions ....... 9N G with 2 7, the domain A' can be partitioned into at most NTT disjoint regions such that within each region, every function 9j X R (j 1,..., NN is fixed polynomial of degree at most B.
Let (Ja We- R (s,a) a) S A denote the class of functions, indexed by state-action pairs (s, a), derived from the scoring functions for action type k E [d]. We assume that

---

F exhibits such (T,, Te -x))stuccture over the parameter space Wy for all & E [d]. Furthermore, we assume the number of available actions for any state s and action type ls is uniformly bounded: [ S Pk: for constants Pk 2 2.
The focus scoring functions arising from classes Fx possessing this (Tk, Tk, ( -strucure is well-founded for two main reasons:
1. This structure naturally includes linear policies (f) a, w) = (w")"Txxss a) using fixed feature extractors Φx). For any fixed state-action pair (s, the function f/ a, is a single polynomial (in w) of degree B = over the entire parameter space W. Thus, the corresponding class (Ft)* has (1, -sttruccee Such linear scoring models were investigated in [Balcan et al. 2021c| (which generalizes [Balcan et al. (024b)).
2. This structural assumption allows us to analyze modern deep learning practices. If scoring functions are implemented as MLPs with piecewise polynomial activations, the resulting function class (Fx possesses (Tx, 7k, 3e ) Lemma 3.7 formally establishes this, detailing the specific parameters Tk; 7k, Sx based the MIP's characteristics like depth, width, degree of activation etc. This confirms our theoretical framework's ss applica- bility to these widely used modern models, aligning with empirical research discussed in Section 2.1
The following lemma connects the pseudo-dimension of the function class H. th(- w) I
R w E W} to the structural properties of its dual class H2 = (h(I,-) W + +RI I I]. where h: I x W + a general function mapping instance instance-parameter pairs to outputs. Specifically, bounds Pdim(H) based on the (I, -struucue of H!".
Lemma 3.2. Let / I x W + I,, where W C RW for some W E N4. If H" has a (T, structure with 3,3) N_ N x N, then the pseudo-dimension of H satisfies:
Pdim(H) s 4 (? log(22 + 1) + W log(4eB + 1) + log log(2l)).
Theorem 3.3. Consider the sequential decision process defined in Algorithm 2 Assume each scoring
function class F% has (T j. Yk. ) struucure with (Tx, Tk. 5&) E N N N4. and |Agi S Pk- Let 7 = Dx k= The p = II Pk. I = I L'k, and recall that W = Eh=n Wa. Then, V has
(T", 7',, strruccue with r' 24 24 GG+WWM-T (e (e BL
W
and Y = W.
Theorem 3.3 establishes the crucial property that if the scoring function classes Fi possess (T&, 7h,, )struucce,e,,, then the resulting cost function dual class V* exhibits a -/truuuuccc ie., a piecewise constant structure. This result, when combined with Lemma 3.2 yields bounds on the pseudo-dimension Pdim(VV. These bounds, in turn, enable the derivation of sample complexity guarantees through standard uniform convergence results, such as I See a more detailed discussion of the uniform convergence results in Appendix C.2
As specific application, consider the case of linear scoring functions:
Proposition 3.4. Let yL be the cost function class obtained when using linear scoring functions fa a, w²) = (w") T fxxxx (s, a) for all k E [d]. Then, Pdim (v*)) = O (WM)) Ed= log ps)
Remark 3.5. Proposition 3.4 improves upon the bound established in Theorem 5.2 by Balcan + W log W This
al. [221cc for linear scoring functions: (dim(V')) o (W
improvement stems from our analysis technique, which leverages the particular structure inherent in our problem setting, rather than relying on the theorems presented in Balcan et al. 2024a]] (see a
related discussion in Appendix F, Bartlett et al. (2022).
Turning to nonlinear models, particularly neural networks, we first establish in Lemma 3.7 that scoring functions implemented via MLPs (with suitable activations) satisfy the required structural property. This allows us to apply our general framework (Theorem 3.3 and Lemma (.2) to derive pseudo-dimension bounds, and thus sample complexity results, for policies modeled by MLPs.
Definition 3.6. A Multi Layer Perceptron (MLP) computes MLP(x, w) Rd x WVW - T via the composition MLP(x, w) (TI, o (t) o Ti-1w ... o o Ti (x). Here T.w denote affine transformations parameterized by w IgW and o-)) denotes the element wesse application of
7

---

the activation function σ R - R. The network has L 2 1 layers, U total neurons, and W total parameters. We assume the activation piecewise polynomial: its domain R can be partitioned into at most p disjoint intervals such that, within each interval, a is defined by univariate polynomial of degree most a.
Lemma 3.7. Consider an MLP as defined in Definition 3.6 characterized by W, U.U.P.PP a. Then, the class (MLP(x,) :) RW R E RR4) has a2 L (2epU/W)) LW LWW, La*) -structure.
Proposition 3.8. Let DMPPP be the cost function class obtained when using MLP scoring functions [u(8, a, w+ M wx) for all & E [d]. Then,
Pdim (D"Ie)
((2 L.Ws) (As {
lo
log E puVs)) log Σ
Σ
W. logas
A-1
Specifically, for ReLU MLPs, we have ag and ph = 2 for all is E [d], leading the bound:
d
ΣVR Uk ))
Pdim (DROLU)= =0 W&
M
log pk + log
3.2 Data-dependent sample complexity bounds
Alternatively, uniform convergence result similar to can be obtained using the empirical Rademacher complexity. Let Sy = -., .N)) be the sample drawn i.i.d. from D. The empir- ical Rademacher complexity is RR,(V) = Eo-1-1 1111 wsupwew Ei V.V, w)]. Standard results (e.g., see Theorem 26.5 in "Shalev-Shwart and Ben-Davidd (014) and Theorem 3.3 in [Mohri al. 2018) provide the following uniform convergence guarantee: with probability at least 1 6,
N Σ v(L, w) EE,D w)] = =0 =0(Rs, (RSx HV
log(1/5) N
sup we W
N
Since Rsw, (V) is computed directly on the sample Sv, this bound is inherently data-dependent and can sometimes provide tighter estimates than worst-case guarantees like (T). which rely solely on the distribution-indeeendett pseudo-dimension Pdim()) Importantly, bounding R. (V) relies fundamentally on the structural properties of the dual class V", just like the case of pseudo- dimensioo..
Let Qas (I) denote the total number of distinct state-action pairs (s, a) of type &o E [d] encountered when Algorithm 2 executed an initial state derived from instance within its first M rounds. The proof of Theorem 3.3 usses a worst-case estimate for M, (),, namely P&P (Lemma
However, the presence of terminal states in Algorithm 2 often results in the actual number of encountered state-action pairs, (Z). being substantially smaller than this worst-case bound. The empirical Rademacher complexity bound presented below directly incorporates the sum of these (M,&(I.) values from the sample {L,,... J. A more detailed discussion and comparison of the bounds derived from pseudo-dimension and empirical Rademacher complexity can be found in Appendix C.2
Proposition 3.9. Under the same hypothesis as Theorem N W, we have
3.3 for any SN (TI...,, IN} with
d ΣΣ (l),)(L))
e EE Be
R&N (V) <
d+
Σ log F& (7 W)log log
+ W log
4 Application to Branch-and-Cut
Our general sequential decision process (Algorithm 2) can model the B&C algorithm (Algorithm T as discussed in Section and Section 2 Starting from an initial state su derived from an MIP instance I = (A, b, c). B&C iteratively makes decisions for node selection (k: = 1), cut selection (k: = 2), and branching
3), corresponding to the d action types in our framework. The
parameters w (w1, 2 w3) governing these scoring functions can be trained via methods like
imitation learning [He al. 2014 Paulus al. 2022 Yilmaz and Yorke-Smith 202T Alvarez et
2017 reinforcement learning [Tang et al. 2020 tune the respective policies (see Section 2.1
8

---

Furthermore, the accumulated penalty V in Algorithm 2 can directly measure B&C performance. For instance, setting immediate penalties Pi (s. a. i)
P2 a. 1, and (s a, i) = 2 for all (s, a, i) E S x A X N makes the cost V I x W + [0, 3M] equal to the size of the B&C tree. Consequently, minimizing V minimizing the total number of explored nodes, which is a common measure of B&C algorithmic efficiency, although the total runtime is also affected by other factors such as node processing time [Linderoth and Savelsbergh 1999].
Modern solvers often prioritize aggressive cut generation at the root node of the B&C tree [Contardo et al. 2023]. This strategy leverages the global validity of root cuts and their potential for significant early impact [Contardo et al. 2023). Theoretical work also suggests that restricting cuts to the root can be optimal under certain conditions [Kazachkov et al.) [024]. J. Motivated by these considerations. we unalyze learning cut selection policy (k = 2) via a ReLU neural network parameterized by w². We assume cuts are added only at the root node for rounds before branching begins, where is typically small. In each round i E [R]. the policy uses scores f2 0, w²) from the ReLU network to select at most e cuts from a pool of candidates. We assume a uniform upper bound r on the number of available candidate cuts (lypically, r = Omm + KR),, where is the number of constraints). We use fixed, deterministic rules for node and branching variable selection (e.g., depth- Septh-fisst search and a product scoring rule, respectively). Proposition 3.8 then implies the following.
Proposition 4.1. Let 7 7 (I, w²) denote the resulting B&C tree size for instance under the setup as discussed above. Then,
Pdim ((TRel. (.. w²) : I + R w² E W2)) = (L2 (sRlogr + log U2))
Our analysis also extends to simultaneously learning policies for all three core B&C decisions (k = 1, 2),, each governed by separate ReLU network with parameters w E We. We assume the standard bounds on the action space sizes: P1 S MM available nodes for selection, P2 = O(m + M) candidate cuts, and Ps
candidate branching variables. Plugging into Proposition 3.8 we obtain:
Proposition 4.2. Let (I, w) denote the tree size when using B&C policies based on ReLU networks with parameters w (w', 2 w²). ). For the corresponding class Di we have:
Pdim (y = O ((L, W1 + L2W22 + LaWa (M (log(m + M) + log + log (U, +2
5 Empirical Validation
To complement our theoretical analysis, we conduct an experiment to test for consistency with the convergence rate suggested by our theoretical upper bounds (Equations T and (
Setup. We trained a cut-selection policy] implemented as an MLP, to imitate an expert oracle based on normalized LP objective-value improvement, yielding a fixed parameter vector w. The network uses two inputs (cut efficacy and objective parallelism), has two hidden layers with ten ReLUU neurons each, and single output with a clipped ReLU activation to produce score in [0, 1). We evaluated this fixed policy on two sets of packing instances from (Tang et al. (020) with m constraints and variables, using the configurations (m 10, 20) and (m = 15, n 30). The performance metric, V (1, ). is the B&C tree size obtained when our MLP, parameterized by w, selects the 10 cuts with the highest scores at the root node.
Methodology. Given training and test instances ( V Ji=1 and {1 1ý=1- drawn i.i.d. from a distribution D, we measure the empirical generalization gap using the quantity
N
N
1
Σ f(N) = N
V( train W)
Σ
V(
w)
N
The motivation for this is grounded in the uniform convergence bounds (Fquations T and 2 bounds establish that the deviation of any N-sample average from the true expectation is bounded by some EN = OLIVVN). Because this guarantee applies to the averages over both the training and test sets, it follows from the triangle inequality that their difference, f(N), is bounded by 2 Thus, f(N) serves as direct, empirically measurable proxy for the convergence rate. To ensure statistical stability, we report the average f (N) over 30 independent trials for each N [1, 100].
). These
'Our code is available at hthttss: : //gi thub. com Hongyu- Secenngyu-Chhnnee Cheng/ BCC The experiments were performed desktop computer with Intel 17-0FF CPU (12 cores, 20 threads) and 32GB of RAM.

---

Results. To test whether the empirical data follows the ((1/VN) convergence rate suggested by
theoretical upper bound, we fit the empirical data to the curve g(N; a. 6) a/ a/vN + b. Figure | presents the results for both instance sets. The fitted curve closely tracks the empirical data, achieving high coefficients of determination (R²2 0.951 and R² = 0.959). This provides strong evidence that the generalization error converges in a manner consistent with our theoretical bound. Moreover, the result suggests that the constants in the generalization bounds of practical magnitude for this distribution integer programs, bridging the gap between our theory and its application.
140
350
Frreltiol
53% Fitled glte 21 =0.531
eris cI
120
Pittet 9306 (M999
010 (nodeN))
000
Trep 100--2200-0 pap (nodees)
220
230-
Samole
10, 20 instances.
(b) 15, 72 30 instances.
Figure 1: Empirical generalization gap ((N) versus sample size N. The blue dots represent the average gap over 30 trials, the shaded region is the 95% confidence interval, and the red line is the fitted curve g( a, b) a/vN +
6 Conclusions and Future Work
This paper establishes theoretical framework for analyzing the generalization guarantees of learn- ing policies within B&C and, more generally, within sequential decision-making processes. We demonstrate that if the scoring functions that guide the decisions exhibit a piecewise polynomial structure with respect to their learnable parameters, then the overall performance metric (e.g., . tree size for B&C) is a piecewise constant function of these parameters. This structural insight enables us to derive pseudo-dimensee parameterized not only by traditional linear models but also, significantly, by neural networks with piecewise polynomial activations such as ReLU, Our results thereby help bridge the gap between theoretical analyses, which have predominantly focused linear policy classes, and the increasingly prevalent use of nonlinear, data-driven heuristics in contemporary algorithm configuration, offering unified perspective for understanding their generalization performance.
bounds and corresponding sample complexity guarantees for policies
Future investigations could build upon this work in several promising directions. One key thcoretical challenge is to explore the expressive power and limitations of such parameterized policies. In particular, we aim to characterize their ability to approximate optimal strategies for these decision making problems, and analyze the associated bias-variance trade-offs inherent in the learning phase. related issue the critical role of the expert function or oracle that provides training signals; we need a deeper theoretical understanding of how the choice and quality of this expert influences the performance of the learned policy, ideally culminating in provable guarantees regarding its proximity true optimality. The scope of current framework could also be expanded. For instance, adapting the analysis to accommodate structured infinite action spaces, such as those involved in generating cuts using CGFs [Basu et al. 2015), would enhance its practical utility for integer programming. Moreover, enriching the underlying sequential decision model to formally include stochasticity in state transitions would allow our sample complexity results address wider of dynamic and less predictable algorithmic environments.
Acknowledgments and Disclosure of Funding
Both authors gratefully acknowledge support from Air Force Office of Scientific Research (AFOSR) grant FA95500-5-1-0038. The first author also acknowledges support from the Johns Hopkins University Mathematical Institute for Data Science (MINDS) Fellowship and the Duncan Award.
10

---

References
Tobias Achterberg. Constraint integer programming. 2007.
Tobias Achterberg. Scip: solving constraint integer programs. Mathematical Programming Computa- tion, 1:1-41. 2009.
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33(1):22-54 2005.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning-basse based approximation of strong branching. INFORMS Journal on Computing, 29(1):185-195, 2017.
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations, volume 9. Cambridge University Press, 1999.
Maria-Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond the Worst Case Analysis of Algorithmss Cambridge University Press, 2020.
Maria-Florina Balcan and Dravyansh Sharma. Learning accurate and interpretable decision trees. arXiv preprini arXiv:2405. 1591 2024.
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Leamning-theoretie theoretic foundations of algorithm configuration for combinatorial partitioning problems. In Conference Learning Theory, pages 213-274. PMLR, 2017.
Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved sample complexity bounds for branch-and-cut. arXiv preprint arXiv:2111.11207, 2021a.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization in portfolio-based algorithm selection. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 2225-12232, 2021b.
Maria-Floree Florina Balcan, Dan Deblasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn nigh-performing algorithms? J. ACM, 71(5), October 2024a. ISSN 0004-5411,
doi: 10. 145/3676278. URL /tttps:///oiii /ttp://///.aoorr//..10011////// 1145/3676278
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch: Generalization guarantees and limits of data-independent discretization. J. ACM. 71(2), April 2024b. ISSN 0004-5411. doi: 10. 10.1145/3637840. URL https::/toi...ooo org.0.....g/.... 1145 0333/40
Maria-Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. Algorithm configuration for structured pfaffian settings. arXiv preprint arXiv:2409.04367, 2024c.
Maria-Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. Sample complexity of data-driven tuning of model hyperparameters neural networks with structured parameter-dependent dual function. arXiv preprini arXiv:2501. 13734, 2025a.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization guarantees for multi- item profit maximization: Pricing, auctions, and randomized mechanisms. Operations Research, 73(2):648-663, 2025b.
Maria-Floriin 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, 14:4015-4027. 2021c
Maria-Florina F Balean, Misha Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the ElasticNet across instances. Advances in Neural Information Processing Systems, 35:27769- 27782, 2022a.
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, 2022b.

---

Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Conference on Learning Theory, pages
PMLR, 2022.
Peter L 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):2285-230) 20121, 2019.
Amitabh Basu, Michele Conforti, and Marco Di Summa. A geometric approach to cut-generating functions. Mathematical Programming, 151:153-189, 2015.
Hongyu Cheng and Amitabh Basu. Learning cut generating functions for integer programming. 2024.
Advances in Neural Information Processing Systems,
Hongyu Cheng. Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut. Advances in Neural Information Processing Systems, 17722036-22060) 2024.
Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming, volume 271.
Springer, 2014.
Claudio Contardo, Andrea Lodi, and Andrea Tramontani. Cutting planes from the branch-and-bound tree: Challenges and opportunities. INFORMS Journal on Computing, 35(1):2-4, 2023.
Gerard Cormuejols, Javier Peña, and Reha Tütüneü. Optimization methods in finance. Cambridge University Press, 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.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Pierre Geurts, Damien Emstt and Louis Wehenkel. Extremely randomized trees. Machine learning. 63:3-42, 2006.
Rishi Gupta and Tim Roughgarden. A pac approach to application-specifii algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 123-134, 2016.
Dan Gusfield. Integer linear programming in computational and systems biology: an entry-level text and course. Cambridge University Press, 2019.
He He. Hal Daumé, and Jason Eisner. Learning to search in branch and bound algo- rithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q Weinberger, ed- itors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, neurips. httpc//pee..lleeppppeeeeeeeee/ee
Inc., 2014. URL 0331000ra222222200c0000000222223 .pdf
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.
Xianqi Jiao, Jia Liu, and Zhiping Chen. Learning complexity of gradient descent and conjugate gradient algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 17671-1767 2025.
Michael Jünger, Thomas M Liebling, Denis Naddef, George Nemhauser, William R Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A Wolsey. 50 Years of integer programming 1958-2008: From the early years to the state-of-the-art Springer Science & Business Media, 2009.
Aleksandr Kazachkov, Pierre Le Bodic, and Sriram Sankaranarayanan. abstract model for branch and cut. Mathematical Programming, 206(1):175-202. 2024.
12

---

Hervé Kerivin and A Ridha Mahjoub. Design of survivable networks: A survey, Networks: An International Journal, 46(1):1-21, 2005.
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI conference artificial intelligence, volume 30, 2016.
Jeff T Linderoth and Martin WP Savelsbergh. computational study of search strategies for mixed integer programming. INFORMS Journal Computing, (127:173-187, 1999.
Mchryar Mohri. Afshin Rostamizadch, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2018. URL https::/mitppes:t ublish cwm/cbook foundations- of wof-maciin---e learning------- -tteeeeeereeeee70////eee Cover Second Edition.
Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pages 17584-17600. PMLR, 2022.
Yves Pochet and Laurence A Wolsey. Production planning by mixed integer programming, volume 149. Springer, 2006.
David Pollard. Convergence of Stochastic Processes. Springer, 1984.
Shinsaku Sakaue and Taihei Oki. Sample complexity of learning heuristic functions for greedy- best-first and A search. Advances in Neural Information Processing Systems, 35:2889-2901, 2022.
Shinsaku Sakaue and Taihei Oki. Generalization bound and learning methods for data-driven projections in linear programming. Advances in Neural Information Processing Systems, 37: 12825-12846, 2024.
Shai Shalov-Shwarzz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. In International conference on machine learning, pages 9367-9376. PMLR, 2020.
Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014.
Franz Wesselmann and Uwe Stuh.. Implementing cutting plane management and selection techniques. In Technical Report. University of Paderborn, 2012.
Kaan Yilmaz and Neil forke-Smith. study of learning search approximation in mixed integer branch and bound: Node selection in scip. Ai, 2(2): 2021.
13

---

A Auxiliary Lemmas
Lemma A.1. Let d be a positive integer, and let 01,.... Od, .i...., ba > O. The following inequali- ties hold:
a
/ (mm
(1) log S
+
log
b1
Σi-1
>
anbr
bk d
1=
bk
b=
601
601
(3)
if 2 b2 bi
b1
b2
Proof. (1) This follows from the observation that log(a1/b1) S 01
(2) Since f(x)
log æ is concave on (0, +o0), Jensen's incquality gives
d
be
bk j=1 bj
log
[I ak
log
Σ
ak
log as =
bj
ΣØ bj
k=1
j
which implies that
d
d
Ek= anbe
(
Σ Ei aRbs xk=1 bK
Ede
log
II
k
by
log
log
Σk=1 by
The inequality then holds because log is increasing (0, +00).
(3) suffices to prove that g(z) = æ (log(ea)) - log is increasing on (0, ail. Note that its derivative is g (ar) (log(ea1) log x) + xx-1/x) log(ai) log(z), which is positive for x (0, a.). The result follows since gxx) log((ea)/<r)) and log(-) (-) is increasing.
Lemma A.2 (Theorem 8.3 in |Atthony and Bartlett 1999]). Let EI...., R 7 R be N multivariate polynomials of degree most with N W and N. Then
2eNB w W
sgg(...ss((n)n)))) w RWW }| 2
if 1,
(gn.:))))..,s((((((((() W R RRR 1,
where e is the base of the natural logarithm.
Definition A.3 (Pseudo-dimension). Let H = (K(,, w) I - R w E W} be class of real-valued functions defined on an input space I, parameterized by w E W. The pseulo-dimension of H, denoted Pdim( (H), is the largest integer N for which there exist instances {I,..... IN} I and real threshold values y/1 Vi...... ....... UN E R such that the function class H. realizes all 2 possible sign patterns on these instances relative to the thresholds:
(sgn(h((4, w)
(hg.....gg((((N........ w) (N)) w W]|=
no such finite largest exists, then Pdim = +00.
Proof of Lemma 3.2 Consider any set of N instance-witness pairs (71, ......... (IN. .N) E x R, where N E N. and N 2 7. By the lemma's hypothesis, the parameter space W be partitioned into K < NYT disjoint regions Qı, Qx- Within each region Q; (i E [K]), for every instance I (j E [N].. the function h(4z.-) coincides with a fixed polynomial n):(w) of degree at most & for all w E Q; Let II(N) be the total number of distinct sign patterns over W:
II(N) (sgn((((4, ht). w) UN)) w E W)].
14

---

We can bound (I) by summing the number of patterns within each region:
K
[I(N
((sgn(h(4) w) "...yy.....,glll........ sgu(hs(s w) UN)) w Q:H
K
Σ
((sgn(n:(()) ..),...,,...................... (ttp://w(w)))o...sssssssvvv - yN)) w E Q:)l-
(3)
We consider two cases based on the degree 8:
Case 1: B O. In this each T75s is constant. Therefore, the sum in is bounded by
K & N By Definition A.3 the pseudo-dimensing Pdim (H) is the largest integer N such that
2 [I),), and upper bounded by the largest N such that 2 I N*T. Taking logarithms yields:
N log(2) S log(NTT) 7 (og((N) log(T))
N
+ log e(x+1)) + log(T)
S 7
E(7 +
$ N + 7og((7 + 1) + log
where the second inequality follows from the first incquality in Lemma A.I Rearranging gives (log(2) - 2) N 7 + 1) + log(T'. Since (Iog(2) 1/e) this implies
Pdim(()) v 4( log(7 + 1) + log l).
Case 2 1. We consider any 2 W. Within each region Q,, the functions Tys 7y:(w) yy are polynomials of degree at most B. Applying Lemma A.2 to bound the number of sign patterns for the N polynomials within each region Qi gives:
2eNN w
H(sgn(n:(w)) - y.)......gnn.......... Sgg.....gn((NNWW))) UN)) w Q+I 2
Substituting this into the sum in and using N we get:
2eN SNT.. .2
2eN
(TN) < K
W
W
Similarly, the pseudo-dimension Pdim(H) bounded by the largest N such that
2eN B W
w
2 < 2NTT
Taking logarithms:
2eN
N 12g(2) < log(2) + 7 log(N) + log((') + W log
W
N
267 +
2eN
462
< log(2) +
+ log
+ log r + W
+ log
2ey +
4c2
<oo((2) +
N 7 log + 1)
N W log(4e3) + logI
2E
2e
1 + 7 (2 + + W log(4e;)) + log(2l).
Rearranging gives (log(2) 1 N < log + 1) W log(4e,)) + log(21'). This implies
Pdim(H) < 4 (> log + + W log(4e3) + log(2l)).
Combining both cases yields the claimed bound:
Pdim(H) < 4 (? log (2y + 1) W log + 1) + log (21)).
15

---

B Proofs of the results from Section 3.1
Lemma B.I. Assuming Pj 2 for all j E [d]. then for all M 2 1 and all & E [d], we have
QM, & PLPM
where p 1T Pj.
Proof of Lemma B. Recall that QM. (7) is the total number of distinct state-action pairs (8, a) of type & E [d] encountered when Algorithm i executed starting from an initial state derived from
within its first M rounds. In the first round, it is easy verify that there are at most IT k- Pj states
that are about to take type-k action for all k E [d]. Therefore, Q1,x(I) S Ph 1-=1 Pj 11 Pj.
Thus,
QM,((T) S QM-1x(() +
Il
Pj
DM-
k
M-1
Pj
Σ
p
j=1
1=0
k
MM
Pj
p
j=1
k
II
(PaPh-11)
Pj
S pkp
where the second last inequality holds since we assume 2 2 for all j. This establishes the claim for round M N4 and all & E [d].
Lemma B.2. Consider an arbitrary collection of N instances SN = {....... IN}, where N
E (7k + Wa). Let ỘM, Σ (I) denote the total number of distinct state-action pairs of type k E [d] encountered across all instances in SN within the first M rounds of Algorithm 2
Recall r I l'.. Then, the number of distinct output vectors satisfies:
<E Di @MAPKBR W
r(Sw) ([, w), ... V(IN,w)) w /ww/w W)l $ 2
II
W
Proof of Lemma
B. The set of instances Sy = (11.... IN) define at most N distinct initial states
for Algorithm Our objective is to prove that the parameter space W T Wg can be partitioned into at most r(Sx) disjoint regions, such that within any given region, the execution sequence of Algorithm (specifically, the sequence of states visited and actions taken) remains identical for all instances J,...., In when parameterized by any w from that region. Consequently. the final accumulated penalty Vl,, w) will constant for each E [N] within such a region.
Let us fix an action type E [d]. The total number of distinct type-k state-action pairs encountered across all N instances is bounded by the sum N (M. @M.-. The assumption that the function class F = [f ...) We - RR, (s) E Ax } has a (I'R, Tke 8& (t)-stuuctrre allows to apply Definition 3.1 to the collection of functions (ff a, corresponding all distinct state- action pairs encountered across the N instances (whose total number is most QM. 2 N 2 7 by assumption). This application partitions the parameter space Wi into a collection of at most T*M Ta disjoint regions. Within each such region resulting from this initial partition, every function fa (s, a, is a fixed polynomial in w E W3 of degree at most 3x.
16

---

2e Re(QMapp//23B. Now, consider any one fixed region obtained from this initial partition of W,. For the action selection a" +- arg aE.4 (s, a, w") to yield consistent result for all w within this fixed region and for all relevant states 8, the set of maximizers must be invariant. This invariance is ensured the signs of the polynomial differences Čε,ú (w*) := fa(s, a', w*) -f((s, a² w*) are constant for all distinct pairs a', a² E A and all relevant states s E Ag. Here, A denotes the set of all states, across the instances, that are encountered during the M rounds of executing Algorithm 2 and at which type-k action is about to be taken. Since [s, a', and fi (s, a² are fixed polynomials of degree at most 5% in the current region, their difference εa (s,j)("") is also polynomial of degree at most 8k- Consider the collection of all distinct polynomial differences ())) arising from all such states 8 and all distinct pairs a', a² E Af.. For each state 8, there are ((22)) distinct pairs {at, a²). Since [Agl < Pk. we have (142.1) S | px/22. Thus, the total number of polynomial differences in the collection is bounded by
A 2
QMAAPK S
Σ SEAR
IA
2
2
SEAR
The signs of these polynomial differences induce a refinement of the current fixed region into finite number of subregions. According to Lemma A.2 the number of such subregions is at most
2e 2e(QMMPk 32 WR
2
WR
Within any single subregion generated by this refinement, the sign every relevant polynomial difference (w") is constant for all w in that subregion. This constancy of signs implies that for any relevant state the outcome of the comparison between (s, wx) and fi((s a,, w*) (i.e., greater than, less than, or equal to) is fixed for all w in the subregion. Consequently, the set of actions achieving the maximum score, arg max fis(s, a, w"), invariant throughout the subregion.
By applying this sign-based refinement to every region from the initial partition of Wa. we obtain a final partition of Wy. The total number of regions rx(SN) in this final partition is bounded by the product of the number of initial regions and the maximum number of subregions per initial region:
(c@MAPa WR
(n(Sx)= S The -2
QM. Pr
We
The overall parameter space W = -II W/ is then partitioned by the Cartesian product of these final partitions for each W4. The total number of resulting regions r(Sx) ) in W satisfies
<Q@MAPPBR
Wi
r(SN) S II (S() < 2d
II
Ts
M.N.
II
WR
(4)
1=1
1=1
k=1
k=1
Applying the second inequality from Lemma
A.1
we bound the product term:
Wi @AAAPARR
Ei=i W.
k= WR (eQMMAPBaa/Wa
πI
WR
Σi
c Ed
@MAPPERR
k=
W
where W -dd We. Substituting this back gives the final bound on the total number of regions in W:
(e
@MAPEEBa
W
r(Sx) S TMe
2d Tx
T
(5)
W
1=1
k=1
Within each of these r r(Sx) disjoint regions of W, the set arg max Lu [a w²) is invariant for all relevant decision steps. Assuming consistent bie-breaking rule (c.g., lexicographical based on
17

---

action representation), the specific action a" chosen at each step is fixed throughout the region. Since this holds for all decision steps encountered during the execution of Algorithm| 2 for any instance I (i E [N], the entire sequence of states visited and actions taken is invariant for all w within the region, As the accumulated penalty V( w) is solely determined by this fixed sequence, ( w) must be constant function of w in the region. This invariance holds for all E [M]. This completes the proof.
Proof of Theorem 3.3 In the worst case, by Lemma B.1 we have the following holds for all & E [d].
N
Σ (M) Npxp"
where p = II Pk. Plug this into the inequality (5) from Lemma B.2
we obtain that for N 2
D (7k + Wx):
(I w)... ...... V(IN, w)) w we WH
W
cNNp
Eh=
PR.3K
N )M
T
W
k=1
k=1
(
e
P2.32
=N PM (MMMM 135 2d
T NW MAW.
W
k=
eeDd 32.3 W
w
SNT+W ((M+1)66- (14H1166-)..4f 2
where 7 = Ei Tk. r
II Kx. and W Ei= WR.
By Definition 3.1 this establishes that the function class V" (V(T,-) W - R T I} has
7(",,',))sste Struuuuee where 7 W E W*), which is larger than N assumed in Lemma B.2 and
m'= 2dd 20
<E PLBB
E
W
Proof of Proposition 3.4
Direct verification confirms that the linear scoring function class (Ft)) has
a (1,0, 1) structure. this case, the parameters from Theorem 3.3 specialize to 7 2 7k T = TT= k= T& 1, and Be = for all k, which implies Σ 1= PL.3 Et_ p.. Thus, the
associated class (12)* possesses ( with 7 W and
w
I' = W(M+(1
e
P
W
18

---

Applying the bound from Lemma 3.2 yields:
Pdim (VL) <4 (W log(2W (2 1) log(2("))
W log(2W + 1) + (d (02) W (M++) +1)
log2
log Ph + W log
E
Σ
Pk
W log W
2W +
)
-4
W log
(d+1) (M + 1)
log Ph + W log
Pk
W
Rm
km
4
W 1og(3e)
22 log
II
Pk
log (M 1)
log Pk
WM
log Pk
1=11
Proof of Lemma 3.7 Let W; locally denote the number of parameters in the first layers of the MLP, and let Ug denote the number of neurons in the i-th layer, for E [L]. Following the proof technique of Theorem in [Bartlett et al., 2019], for any N inputs X1..... XN with N Z LW, the parameter space W can be partitioned into at most
Els W;
NcNp EL (1+ 11-111a--a1 1)a²
24
El= W.
El-, W.
2eNp DI U
524
El W1
2eNNULa El W.
-24
E W;,
(2eNpUTa LW LW
<24
(2epU
LW
=NLW L
W
disjoint regions, where the last inequality due the third inequality in Lemma A. and the fact that N > LW. Within each region, the function MLP(x,,)) W - R is a fixed polynomial in w of degree at most La f. for every j E [N].
This decomposition shows that the function class (MLP(x,)) :): W R x E Rdd) has a (T, 7)B
LW
structure, where I' = 2'W 2cpt
7 LW, and B Lat.
Proof of Proposition 3.8
According to Lemma 3.7
we have that
L.W,
F3 = 24x a
Li
7/ = La We. and
Bx LBa
Ws
19

---

Let A Ex= Lr -= -
k=1
Ls.
The parameters in Theorem 3.3 are 7 Ex= 7h = A
PR = Ei=ı PL and
W.
[eepuUk
LuWe
r
2
0
W
k=1
2
Li
W/
2eppuUk Wi
Lx
0kk
k=1
k=1
Ens L.
22
Wiwk O'
LE
-k=l BeLa WeLaWePhUR/Wa
S
Enn LAWA
A=1
2
II
d
L.WA
Ei RepiIkua A
O
A==
where the inequality follows from the second inequality in Lemma 7+ W = A + W and
Then, we have that 7'
log(TV) < log
2d (DDttMM+HDD
r2w, II
Ox
b==1
LepaLaUe
k= k= 3z
A
W
=(d + L) log + (A + W) + 1) log p+
L log an + Aloo
Σ
2epx Uk
A=1
Aog + W log
Laa La /W
Therefore, apply Lemma 3.2
obtain:
Pdim (DMLP)
<4((A + W log
(A A W) + 1) + 1og((11))
2(A W) + Wlo
2(A
W) +1
<4 Aoo
+ (d + Σ. +1) log
W
d
d Σ k=
+ (A + (M + 1) log +
L log az + A log
2epn. LepxLaUh Un
+ 2W 2W (cpi)
+ log
Σat at!
<4
A Alog 5 + W log(3 +2) + (d + L + 1) log2 2- - 2A(M + 1) log Alog
Σ 2epxLalia
+2W log (Ep) + 22 (og))( W
Σ
ak
In
+
W log on
k=1
d
-0
A + W log I + AM p + Alog Σ
PALLUR
+
W log p + W log
Σ
ak
+
L Wi log as
k=1
k=
-
AM Aogg Alog
Σ
PnUR
+ W log
Σ akk
Ls
Σ WR Wv log on:
d
d
d L log on
We
M
log Pk + log
Σ PEU
+ W log
Okk
k=
For ReLU MLPs, have Og and pk = 2 for all A E [d]. Thus, we can simplify the last term
obtain:
(5/
)))
Pdim (DMIP) =0
[ La We
M Σ
log Pk log Σ UK
1=1
k=1
20

---

C Data-dependent sample complexity
C.1 Proof of Proposition 3.9
Lemma C.1 (Massart's Lemma), Let X = fx'...., x²} S
RN
be a finite set of vectors. Then we
have
N (a, xexx)
V2logr logr
B--11
max jeIr] N
max sElr|
x
X
N
We aim bound the empirical Rademacher complexity Rsw (V) for sample SN - (1,.... IN II with N 2 Ek=n (7h + W&):
Proof of Proposition 3.9
Rs, (V) BB-(-1113N
1 WEW N 1=1
Vo. w)
sup
W} be the set of possible output vectors over the sample Sy. Lemma B.2 implies that the parameter space W can be partitioned into at most r(Sx) regions, such that within each region, the vector (V(1,, w)...., V(IN. w)) is constant. Therefore, the set X is finite, containing most r(Sx) distinct vectors, say X = ....,,'((xx)) The supremum over w E W can thus be replaced by a maximum over the finite set X:
Let X = ((V(I, w)...., V(IN. w))
1 N (a, x²)
RAN (V) = BoN(-111N
max jEir(SX)
Applying Massart's Lemma (Lemma C.I
we get
(Sx)
v 2 log (r(Sx))
(V)
max [Sxr
x
x"
T(SN)
N
2 log (r(Sx))
< HVN
N
We
2 N
@ WR
< H
log
2T
Q
II
k=1
H
2
d dlog? 2 log i+
Yh log QM. +
Wn log
N
H
2
d logg log [+
Σ (Th Wx) log QM. +
Σ
Wx log
(epxi3
N
Wk
k=1
< H
2
do 2 log r+ Σ (Th Wx) Σ Qmak
+ Wloog
(e === PR:Bee
e
N
(e PrrBi W
2 N
log Ti (7+ W) log ΣΣ QmalTT) + Wlog
< H
d
1=1
The second inequality follows because V(I, w) [0. H) implies that each coordinate of x and 1 >x= xf lies [o, H.. Thus, each coordinate difference vector x² + x in absolute value by H. Since this vector is N-dimensional, its La norm is therefore upper bounded by H HVN. The third inequality is due to
bounded
21

---

C.2 Uniform convergence bounds from pseudo-dimension and Rademacher complexity
As discussed Section 3.2 both pseudo-dimension and empirical Rademacher complexity yield uniform convergence guarantees, as stated in ( and (2) respectively. The pseudo-dimension provides data-independent measure function class complexity. Its calculation (as in Theorem 3.3 leading to Propositions and ultimately incorporates worst-case estimates for the number of distinct state-action pairs, related to P&PP per instance (derived from Lemma B. contrast, the empirical Rademacher complexity bound (Proposition 3.9 directly uses the empirically observed sum 2k=1 Qr,,(()) for any instance I D. Since this sum can be substantially smaller than the worst-case estimate (i.e., Pk ) in many settings, Rademacher-basee bounds can be much tighter in practice. To facilitate concrete comparison of the uniform convergence guarantees obtained by these two measures, we now consider the specific case where ReLU MLPs, characterized by Li, Wk. Ux iid ~
for k [d]. serve the scoring functions. Given SN (I..... Iv] pseudo-dimension bound for ReLU MLP policies from Proposition 3.8 into
DV, substituting the we have:
N V(I, w) Er-n(V(I, w)]
sup WEW
N
2=1
Pdim(() (V) + log(1/6)
1
N
EA=1 L&Wa)
d (M Ek= log Pk + log
EE Us/
log (1/8
H
H
N
To derive the empirical Rademacher complexity bound for policies employing ReLU MLP scoring functions, apply the results of Lemma 3.7by taking a₁ 1 and py: 2 (characteristic of ReLU). Let Σx= L,Wa and L Ek=1 Lg. and for this MLP case 7 A based on Lemma 3.7 Substituting these ReLUUspecific structural parameters (Tx, Tk. 3k) into the general empirical Rademacher complexity bound from Proposition 3.9 yields:
Rsw (V)
2
Ek=1 LoUik
N ΣΣ Qma(l))
(e Pklck W
<H
d L Alog
(A+ W) log
W W'oog
N
<H.
2
d 7 + (A Wog
Σ L Qmalti)
+ W Woo
e
Pk
N
=0
H.
1
Alog ΣΣ (M)(
W log
Σ Pk
N
Therefore, substituting this into
2 we obtain the following bound with probability at least - 5:
N V(h, w) EE w)l
sup weW
log(1/8)
Rox (V) + Hy
N
Ed kmml
log
Ed Ri IN (M..(T))) + Wlog Ed Pk:
log(1/8)
-0
H1
+ 11
(6)
22

---

The preceding uniform convergence bounds for ReLU MLP policies highlight the key distinc- tion when comparing their dominant terms. The pseudo-dimension based bound ( via Proposi- tion 3.8 is influenced by factors scaling with M Ek=1 log Pt- This term reflects a dependency on the maximum rounds M and the maximum action space sizes, characteristic of worst-case, data- independent analysis. In contrast, the Rademacher based bound (6) has the corresponding leading term log E (rra(Tii) This shows a dependency on the logarithm of the empirically observed total number of distinct state-action pairs. As this empirical sum can be substantially smaller than the quantities implied by the worst-case parameters M and p in many practical scenarios, the Rademacher-baset bound may offer tighter guarantee.
As an example, consider set of binary integer programming problems, each with variables x, {0, 1} for j [n). Assume that for these problems, the feasible regions of their respective LP relaxations all have an empty intersection with the boundary of the [0. 1]" hypercube. Suppose that n),, while other decisions are
only the variable branching policy is learned (i.e., d = 1, with deterministic. In such a scenario, any variable branching operation can lead the termination of Algorithm in the context of B&C by proving infeasibility for the resulting subproblems. Then, the total number of distinct branching decision contexts (state-action pairs) for an instance I; on the order of (n). However, the pseudo-dimension based bound would still have the term M log This term could be much larger than a term like log(Nn), which would be the leading term the bound derived from empirical Rademacher complexity in this case (since Ex QM, = O(N))). Consequently, the empirical Rademacher complexity's direct dependence Σ I would yield a tighter sample complexity guarantee.
In similar vein, if tighter universal bound on (M) for all instances I can be setablished-basee on specific properties or structural characteristics of problems drawn from the distribution under study-that that is better the worst possible PKp estimate (which was used in Lemma B. then the bounds in Theorem can can be improved. Consequently. this would also lead to more refined pseudo- dimension bounds in Propositions 3.4 and and 3.8 A simple bound is |8], the total number of states in the state space S. In certain settings, [S] may be much smaller than PkP because the latter counts different paths taken in the decision process which can be exponentially larger than the total number of states. Another situation is when the termination states/conditions in the decision process imply a smaller value for Q M. (7) for all I, compared to pMp or (S].
While bounds based on the empirical Rademacher complexity, R.w. (V), are valuable as they adapt to the specific set of instances SN (e.g., via terms involving pestance-specife quantities Q (T.) for I, E 5x), this instance-specfffcity means their values would hard to estimate for a different set of instances S'y ~ D (e.g.. when considering new test set). To obtain bound that is characteristic of the distribution D (for a given sample size N), we use the expected Rademacher complexity,
Rx (V) Es RR..,. (V)]. This quantity reflects the average-case complexity over all possible samples, depending distribution-dependes quantities like J.M.A E,-D M, (T)], rather than instance-specific values from particular sample. Formally, this derivation proceeds as follows:
R (V) ESNNDN
RSw [P)
ESynDN
H.
2
d d+I+ (A W)log
Σ
(mall))
W log
Σ Pk
k=
d N
2
log ΣΣ Qmaa(T))
H
d I. (AA W)E WNDDN
+ W Wlog
Pk
N
A=
d
$ H
2
d+ T.+ (A+ W)
ESN-DN ΣΣ QMa((T)
+ W
Pk
N
k=1
Pk: ))
H
2
d+ T. (A + Wolog
N
park
W log
<>p, k=1
N
1=1
23

---

where the second and third inequalities utilized Jensen's 's inequality. Then, standard uniform conver- gence results (e.g.. [Mohri al. 2018 Theorem 3.3]) imply that with probability at least 6:
N
sup WEW
(l ()) EIn w)l
N
==1
1og(1/6) N (V) H
Lkmi
d
Wr: log N
Ne 2kml m.nk) + W
(Et Pk)
log(1/6)
H
+ H V
N
N
24

---

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]
The abstract and introduction accurately state the paper's contributions, which focus on establishing sample complexity bounds for learning Branch-and-Crn policies guided by piecewise polynomial scoring functions, and its intended scope.
Justification:
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 the work performed by the authors?
Answer: [Yes]
Justification: This is theoretical paper. Limitations are stated in the assumptions of theorems, lemmas, and propositions. The future work section (Section 6) also discusses current limitations and future extensions.
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 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 (e.g.. independence assumptions, noiseless settings, model well-specification, 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 is low or images are taken in low lighting. Or speech-to-text system might not be used reliably 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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
25

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are clearly stated within the theorems, lemmas, and propo- sitions. Complete proofs are provided the appendix (Appendices to C). with all
dependencies clearly referenced.
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 in 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 to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: 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)?
Answer: [Yes]
Justification: All details required reproduce our experiment are provided in Section S including the source code, model architecture, data distribution, and evaluation procedure.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not 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 make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed 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 are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS 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 reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
26

---

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
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code reproduce experimental results is available at https:// gi github. hww.://oooogggguoooogg//SSSSSSSO
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cot
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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 NeurIPS code and data submission guidelines (https
guidddss/ggide////eeeeeoessssses CodeSubmiee ssi onPolicy) 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 are 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
The experimental setting and all relevant details are described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a 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, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The plots in Figure report 95% confidence intervals for the empirical generalization gap, calculated over 30 independent trials for each sample size.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, 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 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 of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments were performed on standard personal computer and did not require significant computational resources. The entire process for the reported results completed within a few minutes.
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 or failed experiments that didn't make into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research does not involve aspects that would conflict with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations 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 presents theoretical results the sample complexity of learning algorithmic policies. does not directly lead societal impacts, so detailed discussion not applicable here.
28

---

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.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 conrectly, 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 to 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 models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is purely theoretical and does not involve the release of data or models that would pose a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual 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: [NA]
Justification: This paper is purely theoretical and does not use any external code, data, or models as assets.
Guidelines:
The answer NA means that the paper does not 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.
29

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssippsiiiie thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pa se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset'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 is purely theoretical and does not introduce or release any new assets such as datasets or code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of 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 is 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: The research presented in this paper is purely theoretical and does not involve crowdsourcing 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 to the NeurIPS Code 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
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper is purely theoretical and does not involve research with human subjects, IRB approval is not applicable.
Guidelines:
30

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on 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 expect authors adhere 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: This is theoretical paper, and LLMs are not an important, original, or non-standard component of the core methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy hbtpps///aaarrrreeccc/////ffeeea for what should or should not be described.
31


Reviews:
[{"review_id": "mPT2aGecIS", "reviewer": "Reviewer_SAVB", "summary": "This paper provides a theoretical analysis of the sample complexity for learning heuristic policies within the Branch-and-Cut (B&C) framework for mixed-integer programming. The authors introduce a general model for sequential decision-making that abstracts the B&C process. Their central contribution is to show that if the scoring functions guiding decisions (e.g., node, cut, and variable selection) have a \"piecewise polynomial\" structure with respect to their learnable parameters, then the overall performance metric (e.g., B&C tree size) is a \"piecewise constant\" function of those same parameters. This structural insight allows them to derive novel generalization bounds, via pseudo-dimension and Rademacher complexity, for policies parameterized not only by traditional linear models but also, significantly, by modern neural networks with ReLU activations.", "questions": "Please see the above sections.\n\nQ1: How robust is the “piecewise-constant” nature of the overall cost function $V(I,w)$ to the choice of the penalty functions $P_k$? Specifically, if $P_k$ was not constant but a complex function modeling the time of an action (e.g., the time to solve an LP), would the core theoretical result (Theorem 3.3) still hold?\n\nQ2 : In Proposition 3.8 you deliberately use the weakened upper bound on $\\Gamma$ from Lemma 3.7, even though the proof of Lemma 3.7 yields a strictly tighter bound. Why not employ the tighter bound to obtain a sharper estimate of the Pdim in Proposition 3.8?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Though I checked the proofs, I am not an expert in statistical learning theory and may have overlooked some concepts\n\n# Strengths\n1. The primary strength of this paper is extending the formal analysis of learnable algorithm policies to the non-linear domain, specifically ReLU-based MLPs. This is highly relevant, as much of the recent empirical success in this area has come from such models. This work provides a much-needed theoretical foundation for these practices.\n\n2. The introduction of the $(\\Gamma,\\gamma,\\beta)$-structure is an elegant and powerful abstraction.\n\n3. The paper is mathematically rigorous. All major claims are stated formally as theorems, propositions, or lemmas, and are accompanied by detailed proofs in the appendix.\n\n# Weaknesses:\n\n1. The primary weakness is that the derived worst-case bounds (Propositions 3.8, 4.1, 4.2) depend on parameters that can be astronomically large, such as the maximum number of algorithm rounds \\(M\\) and the total number of network parameters \\(W\\). The dependency on \\(M\\) is particularly concerning, as it can lead to exponentially large terms in the complexity bounds. This raises questions about the practical utility of the bounds, as they may be too loose to provide meaningful sample size estimates for real-world applications.\n\n2. The analysis for neural networks is contingent on the activation functions being piecewise-polynomial. This is a strong restriction that excludes many popular and high-performing non-linearities (e.g.,  Sigmoid) and advanced architectures (e.g., GNNs, attention mechanisms). This limits the direct applicability of the results to a specific, albeit common, class of neural network architectures.\n\n3. No experiments are presented to gauge how the theoretical bounds correlate with actual B&C policy learning e.g., how many instances are needed in practice, or whether data-dependent Rademacher estimates are indeed small. This leaves a gap between theory and solver practice.\n\n## Minor\n4. The title, \"Generalization Guarantees for Learning Branch-and-Cut Policies,\" implies broad applicability. However, the concrete results for neural networks apply to a very specific class of models. This creates a potential mismatch between the perceived scope of the paper and the actual scope of the theoretical guarantees provided. While all theoretical work relies on assumptions, the restrictiveness here is significant enough that the title may be seen as over-promising.", "was_revised": true, "final_justification": "I recommend accepting this paper. The authors have addressed most of my concerns: they clarified how their bounds act as practical “scaling laws,” added a clear data-dependent Rademacher analysis, showed how to extend their work beyond ReLU activations, and provided experiments that support their theory. These improvements strengthen both the theoretical and practical impact of the paper and outweigh the few remaining minor issues.", "rebuttal": "Thank you very much for reading our paper and providing detailed feedback.\n\n**Weaknesses:**\n\n1. We thank the reviewer for this insightful comment and for raising an important point about the nature of worst-case theoretical bounds. We would like to begin by clarifying the primary message of our bounds for practitioners. The main takeaway is not to estimate a precise sample size from the worst-case formula, but rather to provide a \"scaling law\" for neural network design in this setting. The key insight from our analysis is that the sample complexity scales linearly with the number of network parameters ($W$) and layers ($L$), as shown in Propositions 3.8, 3.9, 4.1 and 4.2. This provides direct, actionable guidance: if a practitioner has a trained model that already achieves a satisfactory performance, but wishes to increase its expressive power with a larger architecture to further reduce the inductive bias, our results indicate that maintaining a similar generalization guarantee requires that the number of training instances increase by a commensurate factor. This theoretical principle, derived from our specific analysis of the sequential decision process, establishes a clear and practical trade off between model complexity and data requirements in this domain.\n\n    Having said that, we agree that the pseudo-dimension bounds, by design, provide a distribution-independent guarantee for any problem fitting our general framework, and can thus appear loose due to the dependency on worst-case parameters like $M$. We address this in the paper in two ways and Appendix C.2 is dedicated to this.\n    * Our work also provides a path to tighter, data-dependent guarantees via the empirical Rademacher complexity (Proposition 3.9), and we refer the reviewer to Appendix C.2 for a detailed discussion illustrating the advantages of this approach. To make this concrete, this discussion includes an example analyzing a class of integer programs with $n$ variables where branching actions can lead to rapid termination of the search tree. In this setting, the number of states encountered for an instance is merely $O(n)$. The pseudo-dimension bound, however, must account for the worst case and thus scales with a term like $\\sqrt{\\frac{M\\log n}{N}}$, where $N$ is the training sample size and $M$ could be as large as $\\Omega(2^n)$. In contrast, our Rademacher bound adapts to the problem's benign structure and scales with a much smaller term, $\\sqrt{\\frac{\\log(Nn)}{N}}$, offering a much tighter and more meaningful guarantee.\n    * Even for the worst case pseudo-dimension based bounds, we discuss in Appendix C.2 how the the structure of the specific decision making process could imply a pseudo-dimension bound that is much better than something that scales with $M$. In particular, the factor $M$ really comes from having to count all possible paths that the decision process could take, which could be exponential in $M$. In contrast, the pseudo-dimension can alternatively be bounded by other parameters; for example, the total number of states which could be an exponential factor smaller than the total number of paths (something that is exploited by dynamic programming for solving such decision making problems). See the discussion in lines 692-700 in Appendix C.2.\n\n    We did not include this discussion in the main text so as to not distract from the main message, which is to show that bounds for general decision making processes can be obtained with immediate consequences for B&C. We thought the fine-tuned bounds were better left in an appendix for an interested reader. We aim to produce a journal version of this paper that will be more detailed and nuanced in its discussions.\n\n2. This is an excellent point, and we thank the reviewer for highlighting the scope of our current analysis. We chose to focus on piecewise polynomial scoring functions in this work for several reasons: they form a natural and non-trivial generalization of the linear models studied in prior work, and this class is already rich enough to provide the first generalization guarantees for widely-used architectures like Multi-Layer Perceptrons (MLPs) and Graph Neural Networks (GNNs) (with a fixed number of message passing rounds) with piecewise polynomial activations.\n\n    However, the reviewer is correct that this excludes other important non-linearities. Nevertheless, our proof technique is more general and can be extended to accommodate neural networks with exponential-based activations (e.g., Sigmoid, Tanh, Swish) and, crucially, advanced architectures involving attention and Softmax mechanisms.\n\n    This extension requires introducing the theory of Pfaffian functions [1, 2], as modern architectures—such as the composite GNN, attention, and MLP model in [3]—result in scoring functions that exhibit a \"piecewise Pfaffian\" structure. A recent, concurrent work [4] has also laid groundwork for PAC learning with this specific structure. The analytical path for this extension involves replacing the sign pattern counting argument from our Lemma A.2. Doing this for Pfaffian structures is founded on a powerful result by Khovanskiĭ [1], analogous to Bézout's theorem for polynomials, that provides an explicit bound on the number of non-degenerate solutions to a system of Pfaffian equations. This allows us to bound the number of connected components for any intersection of the decision boundaries defined by Pfaffian structures. Following Lemma 7.9 of Anthony \\& Bartlett [5], this bound on intersections can be used to derive an upper bound on the number of sign patterns generated by the decision boundaries.\n\n    Following this path, the central structural result of our paper would still hold: if the scoring functions are piecewise Pfaffian, the final cost function $V(I,\\mathbf{w})$ is still a piecewise constant function of $\\mathbf{w}$ for any fixed $I$, with boundaries defined by Pfaffian structures, and corresponding pseudo-dimension and Rademacher complexity bounds can be derived. This would handle nonlinear activations like Sigmoid, as well as models like GNNs composed with attention mechanisms. We will add a dedicated section in the final version of the paper outlining this extension and its implications.\n\n3. We did not include experiments in the original submission as our primary motivation was to provide the theoretical foundations for the successful empirical works surveyed in Section 2.1. However, we agree with the reviewers that a computational study strengthens the paper. We have thus conducted a new proof-of-concept experiment to provide an empirical view of our theoretical bounds. The results verify the predicted $\\mathcal{O}(1/\\sqrt{N})$ convergence rate ($R^2=0.944$) and show that practical generalization errors are substantially smaller than the worst-case bounds. For the full details of this experiment, we respectfully refer the reviewer to our response to Reviewer U6oB.\n\n**Title.** Indeed, the title refers to the broad applicability of our theoretical framework, which extends beyond the specific models we instantiate. While our concrete results focus on the class of MLPs with piecewise polynomial activations, the framework itself is more general. As detailed in our response to Weakness 2, our analysis can be extended to the broader class of piecewise Pfaffian functions, providing guarantees for modern architectures with Sigmoid and attention. To improve clarity, we will revise the abstract to specify that our main results are instantiated for piecewise polynomial models, and keep the title to reflect the framework's full potential.\n\n**Questions:**\n1. Yes, our core theoretical result (Theorem 3.3, which states no requirements for $P_k$) holds for any choice of penalty functions $P_k$, including complex, non-constant ones like local computation time. The reason is that our analysis partitions the parameter space $\\mathcal{W}$ into regions within which the entire execution trace—the full sequence of states visited and actions taken—is invariant. This partition is determined exclusively by the scoring functions. Since the execution trace is fixed within each region, the accumulated cost, $V(I,\\mathbf{w})=\\sum P_k(s,a^*,i)$, is a sum over a fixed sequence of penalty values and is therefore constant, regardless of the functional form of $P_k$. The only assumption needed is that an identical action in an identical state incurs an identical cost. \n2. This is a sharp observation, and we thank the reviewer for their careful reading. Our decision to use the simplified bound was a deliberate choice to prioritize the clarity and interpretability of the final pseudo-dimension bound in Proposition 3.8. The simplified form allows a reader to immediately see the asymptotic dependencies on high-level network parameters ($L,W,U$), rather than being obscured by more complex summation terms. While this simplification loses some precision in the constants, it does not alter the core conclusion of our analysis. Per the reviewer's valuable suggestion, we will add a remark in the final version to acknowledge the tighter intermediate bound and explicitly discuss this trade-off between algebraic simplicity and tightness.\n---\n[1] Khovanskiĭ, A.G., 1991. Fewnomials (Vol. 88). American Mathematical Soc..\n\n[2] Karpinski, M. and Macintyre, A., 1997. Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. Journal of Computer and System Sciences, 54(1), pp.169-176.\n\n[3] Paulus, M.B., Zarpellon, G., Krause, A., Charlin, L. and Maddison, C., 2022, June. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning (pp. 17584-17600). PMLR.\n\n[4] Balcan, M.F., Nguyen, A.T. and Sharma, D., Algorithm Configuration for Structured Pfaffian Settings. Transactions on Machine Learning Research.\n\n[5] Anthony, M. and Bartlett, P.L., 2009. Neural network learning: Theoretical foundations. Cambridge University Press."}, {"review_id": "8FrfPZBf7c", "reviewer": "Reviewer_U6oB", "summary": "This paper develops a theoretical framework for analyzing the generalization guarantees of learned policies for Branch and Cut (B&C) when solving mixed-integer programs (MIPs). B&C is one of the most widely used techniques for solving MIPs. Existing solvers primarily rely on heuristics for node selection, cut selection, and branching variable selection. Recently, there has been growing interest in learning B&C policies. This paper contributes to this line of work by providing sample complexity bounds for learning such policies. \n\n \n\nThe authors view B&C as a sequential decision-making process involving three types of actions at each step: node selection, cut selection, and branching variable selection. The goal is to learn a parametric scoring function that guides these actions. To analyze the difficulty of learning such policies, the authors derive sample complexity upper bounds for both linear and multilayer perceptron (MLP) scoring functions. \n\nThe framework presented in Section 3 provides a general analysis of imitation learning, with learning B&C policies treated as a specific application of imitation learning. Finally Section 4 provides bound for B&C from the bounds developed in Section 3.", "questions": "- In the context of Branch-and-Cut, what exactly does the penalty function measure? Could you clarify its practical motivation—for example, how it reflects solver performance or computational cost? \n\n- How does the complexity analysis compare to the analysis provided in Theorem 5.1 of Cheng, Basu (NeurIPS 2024)?  \n\n- How might your theoretical findings impact  or strengthen existing learning-based B&C methods such as those proposed by Tang et al. (ICML,2024), Khalil el al (AAAI, 2016), Cheng, Basu (NeurIPS 2024)?", "limitations": "YES", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "I am not entirely familiar with the research topic. I am aware of some recent works which aim to learn policies for solving MIP problems. This paper, on the other hand, makes a strong theoretical contribution and provides a generic framework for sample complexity bounds for learning B&C policies\n\nWhile the theoretical framework is well-developed, the paper could benefit from a computational study or empirical experiments.", "was_revised": true, "final_justification": "I recommend accepting this paper. Prior to the rebuttal, I was already inclined to accept. During the rebuttal, the authors provided thorough responses to all of my questions. They also conducted and reported an additional computational study, which further strengthens the contribution. Hence, I will be maintaining my rating in favor of acceptance.", "rebuttal": "Thank you very much for the thoughtful review. \n\n\n**Experiments:**\n\nWe did not include experiments in the original submission as our primary motivation was to provide the theoretical foundations for the successful empirical works surveyed in Section 2.1. However, we agree with the reviewers that a computational study strengthens the paper. We have thus conducted a new experiment to empirically investigate the convergence behavior of the generalization error.\n\nWe first trained a fixed cut-selection policy. This policy is implemented as a Multi-Layer Perceptron (MLP) with two input neurons (for cut efficacy and parallelism), two hidden layers with five neurons each using ReLU activations, and a single output neuron with a clipped ReLU activation to produce a score in $[0,1]$. The network, parameterized by $\\mathbf{w}$, was trained to imitate an expert signal based on the Linear Programming (LP) gap closed by a cut. We then evaluated this fixed policy on the packing distribution from [3], with 15 constraints and 30 variables. For each instance $I$, the performance metric $V(I, \\mathbf{w})$ is the Branch-and-Cut (B&C) tree size resulting from a procedure where our policy adds 3 cuts per round for 5 consecutive rounds at the root node.\n\nThe quantity we measured is $f(N) = \\left|\\frac{1}{N}\\sum_{i \\in S^{\\text{train}}\\_{N}} V(I_i, \\mathbf{w}) - \\frac{1}{N}\\sum_{j \\in S^{\\\\text{test}}\\_{N}} V(I_j, \\mathbf{w})\\right|.$ For each sample size $N$ (from 1 to 50), the sets $S^{\\text{train}}\\_{N}$ and $S^{\\text{test}}_{N}$ consist of $N$ instances drawn independently and uniformly at random from their respective larger pools of training and unseen test instances. To ensure statistical stability, we repeated this sampling process $10$ times and report the average $f(N)$. The motivation for using this quantity is theoretically grounded. Our theory (e.g., Eq. (1)) bounds the deviation of both the training and test (of size $N$) averages from the true expectation, $\\mathbb{E}[V(I, \\mathbf{w})]$, by a term that scales as $\\mathcal{O}(1/\\sqrt{N})$. It then follows from the triangle inequality that their difference, $f(N)$, is also bounded by a term of the same order. This makes $f(N)$ a direct empirical quantity for investigating the predicted convergence rate.\n\nIt is important to clarify that the goal of this experiment is a proof-of-concept for the rate of convergence, not to numerically verify the specific constants in the theoretical upper bound. To this end, we fitted the empirical data to a curve with the theoretically-motivated functional form $g(N) = a \\sqrt{1/N}$, yielding the parameter $a=346.86$. The results indicate a strong correspondence between our theory and this empirical observation, as the fitted curve achieved a high coefficient of determination of $R^2 = 0.944$. Due to formatting limitations, we cannot include the plot, but the table below presents a comparison for several representative sample sizes, showing the general close match between the empirical error $f(N)$ and the fitted curve $g(N)$.\n\n| $N$ | $f(N)$ (avg) | $g(N)$ (fitted) | Relative Error |\n|---:|---:|---:|---:|\n| 1 | 337.90 | 346.86 | 2.65% |\n| 2 | 289.75 | 245.27 | 15.35% |\n| 3 | 176.77 | 200.26 | 13.29% |\n| 4 | 152.00 | 173.43 | 14.10% |\n| 5 | 126.18 | 155.12 | 22.94% |\n| 10 | 100.09 | 109.69 | 9.59% |\n| 20 | 81.19 | 77.56 | 4.47% |\n| 30 | 65.17 | 63.33 | 2.82% |\n| 40 | 56.09 | 54.84 | 2.21% |\n| 50 | 38.26 | 49.05 | 28.20% |\n\nThis experiment provides strong empirical evidence that the generalization error of a learned B&C policy for this distribution converges at the rate predicted by our theoretical analysis. We believe this result strengthens the connection between our theory and solver practice, and we will include and extend this empirical study in the final version of the paper.\n\n\n**Questions:**\n\n1. The penalty function $P_k(s, a, i)$ in our framework is a general mechanism designed to quantify the immediate local cost associated with taking action $a$ (of type $k$) in state $s$ at round $i$. Its practical motivation is to allow for the modeling of various concrete measures of solver performance or computational cost. In the specific application to B&C presented in Section 4, we instantiate the penalty function to measure the size of the B&C tree, a standard measure of solver efficiency. For example, by setting the penalty to 1 for a cut action and 2 for a branch action, the total accumulated penalty $V(I, \\mathbf{w})$ directly corresponds to the total number of nodes explored.\n    \n    However, a key strength of our framework is that our core theoretical results (e.g., Theorem 3.3) impose no restrictions on the functional form of $P_k$. As long as it is a deterministic function mapping the $(s,a,i)$ triplet to a real-valued cost, our analysis holds. This allows one to define $P_k$ to model other important computational costs, such as the CPU time for solving an LP relaxation or for performing cut separation, under the standard assumption that an identical action in an identical state incurs an identical cost.\n2. There are several key differences between the learning paradigm considered in our paper and that of Cheng and Basu [1]:\n    * Our work analyzes the paradigm of learning a *scoring function*, which assigns a score to each available action, with the highest-scoring action being selected. This aligns with the prevalent practice in modern solvers and much of the empirical literature. In contrast, [1] considers learning a neural network that directly maps a problem instance to a specific action (e.g., a cutting plane parameter).\n    \n    * The analysis in [1] is focused on the important special case of adding cutting planes only at the root node of the B&C tree. Our framework is more general, providing guarantees for a sequential process where decisions (node selection, cut selection, and branching) are made dynamically throughout the entire B&C tree, not just at the root.\n    \n    * Cheng and Basu [1] analyzes a setting with a continuous, infinite action space, as they consider an infinite family of cutting planes. Our paper, in line with common solver implementations like SCIP and most empirical studies, assumes that the set of available actions at any given state is finite.\n\n3. This work aims to provide the rigorous theoretical foundations that underpin the empirical success of many learning-based B&C methods, such as those surveyed in Section 2.1 of the paper. For foundational empirical studies like [2], our framework provides what we believe to be the first formal generalization guarantees for learning the types of score-based policies they investigate. While we are uncertain of the specific Tang et al. (ICML, 2024) paper being referred to, we believe our general framework is a valuable tool for analyzing the generalization guarantees of a wide range of such data-driven policies.\n\n    Another insight from our analysis that we think could be valuable for practitioners is the following. Our work provides a \"scaling law\" for neural network design in this setting: the sample complexity scales linearly with the number of network parameters ($W$) and layers ($L$), as shown in Propositions 3.8, 3.9, 4.1 and 4.2. This provides direct, actionable guidance: if a practitioner has a trained model that already achieves a satisfactory performance, but wishes to increase its expressive power with a larger architecture to further reduce the inductive bias, our results indicate that maintaining a similar generalization guarantee requires that the number of training instances increase by a commensurate factor. This theoretical principle, derived from our specific analysis of the sequential decision process, establishes a clear and practical trade off between model complexity and data requirements in this domain.\n\n---\n\n[1] Cheng, H. and Basu, A., 2024. Learning cut generating functions for integer programming. Advances in Neural Information Processing Systems, 37, pp.61455-61480.\n\n[2] Khalil, E., Le Bodic, P., Song, L., Nemhauser, G. and Dilkina, B., 2016, February. Learning to branch in mixed integer programming. In Proceedings of the AAAI conference on artificial intelligence (Vol. 30, No. 1).\n\n[3] Tang, Y., Agrawal, S. and Faenza, Y., 2020, November. Reinforcement learning for integer programming: Learning to cut. In International conference on machine learning (pp. 9367-9376). PMLR."}, {"review_id": "0IxdpaJT9u", "reviewer": "Reviewer_u1pW", "summary": "This paper presents a rigorous theoretical framework to analyze the generalization performance of learned heuristic policies for Branch-and-Cut (B&C) algorithms in Mixed Integer Programming (MIP). It introduces sample complexity bounds for policies guided by piecewise polynomial scoring functions, a class that includes linear models and neural networks (e.g., MLPs with ReLU).", "questions": "(1) How sensitive are your generalization guarantees to the expert quality (e.g., strong branching vs. suboptimal heuristic)?\n(2) How do the theoretical bounds scale in practice with real-world ReLU network sizes used in B&C solvers?", "limitations": "(1) Role of oracle quality in training (e.g., strong branching) could influence generalization.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The strength of this paper:\n\n1. extends previous PAC-style algorithm configuration theory, yielding new pseudo-dimension and Rademacher complexity bounds for both worst-case and data-dependent settings. It bridges the gap between empirical methods and theoretical guarantees.\n\nThe weakness of this paper:\n\n1. Lacks guidance on how to translate theory into practice (e.g., how to bound pseudo-dimension for specific networks in practice). Providing case studies may facilitate the reader's better understanding of the claims in this paper.", "was_revised": true, "final_justification": "The author provided detailed explanations to my questions, and I will maintain my score for this paper.", "rebuttal": "Thank you very much for the thoughtful review. \n\n**Weakness:**\n\nWe would like to clarify that for the class of Multi-Layer Perceptron (MLP) policies with piecewise polynomial activations (e.g., ReLU), our paper already provides a direct translation of this nature. Specifically, Proposition 3.8 and 4.2 offer explicit pseudo-dimension bounds directly in terms of a network's architectural characteristics (number of parameters $W$, layers $L$, neurons $U$, etc.). More fine-tuned bounds can be given in terms of the specific sizes of the different layers, which we left out for space and clarity of the stated bounds. Our intent with these results was to provide precisely the kind of guidance the reviewer is asking for: a clear mapping from practical model design choices to their theoretical sample complexity implications.\n\nWe fully agree with the reviewer that extending this to a broader range of architectures is an excellent point that would further strengthen the paper. As mentioned in our response to Reviewer SAVB, our framework can be generalized to cover models with \"piecewise Pfaffian\" structure. When we add the promised discussion section on this Pfaffian extension to the final version, we will be sure to include concrete case studies, outlining how to derive bounds for specific, empirically-used models involving Graph Neural Networks (GNNs) and/or attention mechanisms.\n\n**Questions:**\n\n1. This question points to the important distinction between generalization error and approximation error. Our generalization guarantees provide an upper bound on the *uniform convergence error* for the entire function class parametrized by $\\mathcal{W}:$ $\\sup_{\\mathbf{w} \\in \\mathcal{W}}\\left|\\frac{1}{N} \\sum_{i=1}^N V\\left(I_i, \\mathbf{w}\\right)-\\mathbb{E}_{I \\sim \\mathcal{D}}[V(I, \\mathbf{w})]\\right|.$ \n\n    This bound is determined by the complexity of the function class $\\mathcal{V}$ as defined on lines 155-156 of the paper, which can be measured in a distribution-independent manner by its pseudo-dimension or in a distribution-dependent manner by its Rademacher complexity. Crucially, both measures of complexity depend on the policy architecture but are independent of the expert that generates the training labels. Our guarantee thus ensures that for any policy $\\mathbf{w} \\in \\mathcal{W}$ (whether trained using an expert or some other means), its empirical performance on the sample is a reliable estimate of its true expected performance.\n    \n    The expert's quality, however, is critical for a different aspect: the empirical performance on the sample $S$ of the specific policy $\\widehat{\\mathbf{w}}\\_S$ selected  after the training process. Our theoretical guarantee works as follows:\n\n    * A high-quality expert will guide the learner to a policy $\\widehat{\\mathbf{w}}_S$ with low empirical cost. Our guarantee ensures that this empirically effective policy will also have a low true expected cost, i.e., generalize well to unseen instances.\n\n    * Conversely, a suboptimal expert will lead to a policy with high empirical cost. Our guarantee still holds, but simply confirms that this empirically poor policy will also perform poorly in expectation on new instances.\n\n    Thus, our framework provides guarantees for the *relative* quality of the final learned policy (on unseen instances) with respect to its empirical performance on the sample, while the *overall* performance of the final learned policy is naturally bounded by the quality of the expert being imitated.\n\n2. The primary message of our theoretical bounds is to provide a \"scaling law\" that governs the relationship between sample complexity and network size for learning B\\&C policies. As established in Propositions 3.8, 3.9, 4.1 and 4.2, the dominant term in our pseudo-dimension bound scales linearly with the number of network parameters ($W$) and layers ($L$). \n\n    This provides direct, actionable guidance: if a practitioner has a trained model that already achieves a satisfactory performance, but wishes to increase its expressive power with a larger architecture to further reduce the inductive bias, our results indicate that maintaining a similar generalization guarantee requires that the number of training instances increase by a commensurate factor. This theoretical principle, derived from our specific analysis of the sequential decision process, establishes a clear and practical trade off between model complexity and data requirements in this domain.\n\n    We also conducted a new proof-of-concept experiment to provide an empirical view of our theoretical bounds. The results verify the predicted $\\mathcal{O}(1/\\sqrt{N})$ convergence rate ($R^2=0.944$) and show that practical generalization errors are substantially smaller than the worst-case bounds. For the full details of this experiment, we respectfully refer the reviewer to our response to Reviewer U6oB.\n\n\n**Limitations:** This relates directly to our previous response concerning the distinction between generalization and approximation error. As detailed there, our guarantees are independent of the expert's quality, as they give bounds on the *relative* quality of the learned policy (on unseen instances) with respect to its empirical performance on the sample."}, {"review_id": "XmE4s9tbfK", "reviewer": "Reviewer_twK1", "summary": "This paper contributes to a recent line of work on provable sample-complexity guarantees for learning to tune branch-and-cut. Prior work by Balcan et al. has focused on learning linear weights to combine predetermined heuristic scores such as efficacy, parallelism, etc. in order to choose between branch-and-cut actions (such as what cuts to add, what variable to branch on, what node to explore next, and so on). The present work builds and extends upon that line of work by learning scores that are piecewise polynomial functions of the parameter weights. This is better reflective of current practice that has used neural networks to map instances (the state of a branch-and-cut solve of an integer program) to desired actions (the next cut to add, etc.) directly. The bounds are obtained by analyzing the pseudodimension of the class of induced cost functions, and the authors do this for a general abstraction of a sequential decision process that generalizes branch-and-cut.", "questions": "In [1] the authors also consider a general abstraction of tree search that generalizes branch-and-cut, and their main sample complexity results are for that general model of tree search. How does that model compare to the model of a sequential decision process that you consider in the present paper? (I see that the authors in [1] also only consider linear weightings of scores, but a comparison of the two models would nonetheless be useful.) Also, how does the model compare to the formal model of dynamic programming?\n\nDefinition 3.1 to me seems like a special case of the general notion of piecewise decomposability in [2]. Is that correct? If so there should probably be some mention of this.\n\nVery minor nitpick on notation: I think using k = 1, 2, 3 to denote node selection, cuts, and branching is awkward and you should just write something like A^s_{node}, A^s_{cut}, A^s_{branch} or something like that.\n\n\n[1] Balcan, Prasad, Sandholm, Vitercik. Improved sample complexity bounds for branch-and-cut. CP 2022.\n\n[2] Balcan, Deblasio, Dick, Kingsford, Sandholm, Vitercik. How Much Data Is Sufficient to Learn High-Performing Algorithms? Journal of the ACM.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This is a nice theory paper that contributes a missing piece to the recent generalization theory for learning cut selection policies. It provides a theoretical backing for various experimental papers. The proofs mostly seem to rely on by-now standard techniques, but that is ok. Some experiments showing the impact of parameter tuning and/or empirically testing the sample complexity would be nice, but not required for a theory paper.\n\nOne weakness is that the work could be seen as largely incremental to prior work, with no fundamentally new techniques introduced. But I also think that is OK.\n\nSee the question section for a few specific comments.", "was_revised": true, "final_justification": "The authors provided a detailed rebuttal. I am in favor of accepting the paper.", "rebuttal": "Thank you very much for the thoughtful and encouraging review. \n\n> Some experiments showing the impact of parameter tuning and/or empirically testing the sample complexity would be nice, but not required for a theory paper.\n\nWe did not include experiments in the original submission as our primary motivation was to provide the theoretical foundations for the successful empirical works surveyed in Section 2.1. However, we agree with the reviewers that a computational study strengthens the paper. We have thus conducted a new proof-of-concept experiment to provide an empirical view of our theoretical bounds. The results verify the predicted $\\mathcal{O}(1/\\sqrt{N})$ convergence rate ($R^2=0.944$) and show that practical generalization errors are substantially smaller than the worst-case bounds. For the full details of this experiment, we respectfully refer the reviewer to our response to Reviewer U6oB.\n\n>In [1] the authors also consider a general abstraction of tree search that generalizes Branch-and-Cut (B&C), and their main sample complexity results are for that general model of tree search. How does that model compare to the model of a sequential decision process that you consider in the present paper? (I see that the authors in [1] also only consider linear weightings of scores, but a comparison of the two models would nonetheless be useful.)\n\nThe framework in [1] and our sequential decision process differ in two fundamental aspects:\n* The model in [1] analyzes policies derived from a convex combination of two pre-defined scores, parameterized by a single scalar. Our framework provides guarantees for a much broader class of policies where the scoring function itself is a general piecewise polynomial function of a high-dimensional parameter vector $\\mathbf{w}$—a framework that, as we detail in our response to Reviewer SAVB, can be further extended to the even more general class of piecewise Pfaffian functions.\n\n* The analysis in [1] crucially relies on the scoring functions and action sets to have a certain \"path-wise\" property to achieve its strong, depth-dependent bounds. Our framework is more general as it is state-based and does not require this structural assumption. This is a critical distinction, as many sophisticated heuristics used in empirical work are not strictly path-wise; for example, scoring rules may incorporate global tree features (e.g., the current primal-dual gap or the total number of open nodes), which our state-based model can naturally accommodate.\n\n> Also, how does the model compare to the formal model of dynamic programming?\n\n\nOur model is exactly the same as the formal model of decision making studied within (deterministic) dynamic programming (DP). Of course, for something like B&C, one would not want to use DP to decide on the optimal set of actions at every decision point as this would be prohibitively expensive from a computational standpoint. Instead we use the framework as a formal language to analyze data-driven learning paradigms used to make these decisions within B&C. Naturally, our general framework allows applications to data-driven (as opposed to DP based) approaches for sequential decision making beyond B&C.\n\nWe thank the reviewer for these valuable suggestions. In the final version, we will add a detailed discussion situating our framework with respect to both the tree search model in [1] and the broader literature on Markov Decision Process (MDP) formulations for B&C, as well as dynamic programming.\n\n> Definition 3.1 to me seems like a special case of the general notion of piecewise decomposability in [2]. Is that correct? If so there should probably be some mention of this. \n\nThis is an insightful question, and indeed there is a conceptual connection between our Definition 3.1 and the notion of \"piecewise decomposability\" in [2]. The $(\\mathcal{F}, \\mathcal{G}, k)$-structure from [2] is more general as it allows $\\mathcal{F}$ to be any class with a finite dual pseudo-dimension, whereas our work focuses on piecewise polynomial function classes. However, this specialization is well-motivated, as many applications of the framework in [2] and subsequent works ultimately consider much simpler settings, such as piecewise constant or linear functions (e.g., [1, 2, 3]). \n\nThe primary advantage of our $(\\Gamma, \\gamma, \\beta)$-structure, compared to the one in [2], lies in how it characterizes the partition of the parameter space, which could be a more direct and natural setting for certain function classes.\n\n* First, describing the partition via $k$ functions drawn from a single boundary class $\\mathcal{G}$ (as done in [2]) is not always ideal. For a ReLU Multi-Layer Perceptron (MLP), the parameter space is partitioned by an arrangement of polynomials with varying degrees (from $1$ to $L$, the depth of the MLP). A direct, layered analysis like in [4] can establish sharper bounds on the number of regions, compared to a potentially lossy analysis that fits a single boundary class $\\mathcal{G}$ to describe this complex arrangement. Doing so could lose information by forcing all boundary polynomials to have the highest degree.\n\n* Second, for function classes such as piecewise polynomials and MLPs, applying the framework of [2] can result in another source of loss in the tightness of the bounds on pseudo-dimension. The framework in [2] takes as given the VC dimension of the boundary functions defining the pieces, and applies Sauer's Lemma to derive a bound on the number of expressible sign patterns (i.e., pieces or regions). If a tighter, direct bound on the number of pieces is available (as in our Lemma 3.7), using it usually gives a strictly better upper bound on the overall pseudo-dimension. This potential loss in tightness has been noted in several recent works, including our own Remark 3.5 where a concrete example is discussed, and in the discussions in [6, 7, 8, 9].\n\nIn summary, while conceptually related to [2], our definition is tailored for settings with piecewise polynomials, leading to a more efficient characterization and tighter bounds for this important class of problems. We will add a discussion of this relationship in the final version.\n\n\n> Very minor nitpick on notation: I think using k = 1, 2, 3 to denote node selection, cuts, and branching is awkward and you should just write something like $A^s_{node}, A^s_{cut}, A^s_{branch}$ or something like that.\n\nThis is a great suggestion for improving clarity. We agree that the proposed notation is much more intuitive, and we will adopt it in the final version of the paper.\n\n---\n\n[1] Balcan, M.F., Prasad, S., Sandholm, T. and Vitercik, E., 2022, July. Improved Sample Complexity Bounds for Branch-And-Cut. In 28th International Conference on Principles and Practice of Constraint Programming.\n\n[2] Balcan, M.F., Deblasio, D., Dick, T., Kingsford, C., Sandholm, T. and Vitercik, E., 2024. How much data is sufficient to learn high-performing algorithms?. Journal of the ACM, 71(5), pp.1-58. \n\n[3] Balcan, M.F.F., Prasad, S., Sandholm, T. and Vitercik, E., 2022. Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts. Advances in Neural Information Processing Systems, 35, pp.33890-33903.\n\n[4] Bartlett, P.L., Harvey, N., Liaw, C. and Mehrabian, A., 2019. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63), pp.1-17.\n\n[5] Anthony, M. and Bartlett, P.L., 2009. Neural network learning: Theoretical foundations. cambridge university press.\n\n[6] Bartlett, P., Indyk, P. and Wagner, T., 2022, June. Generalization bounds for data-driven numerical linear algebra. In Conference on Learning Theory (pp. 2013-2040). PMLR.\n\n[7] Balcan, M.F., Nguyen, A.T. and Sharma, D., Algorithm Configuration for Structured Pfaffian Settings. Transactions on Machine Learning Research.\n\n[8] Cheng, H. and Basu, A., 2024. Learning cut generating functions for integer programming. Advances in Neural Information Processing Systems, 37, pp.61455-61480.\n\n[9] Cheng, H., Khalife, S., Fiedorowicz, B. and Basu, A., 2024. Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut. Advances in Neural Information Processing Systems, 37, pp.25036-25060."}]

Author rebuttal:

Meta-review: This paper studies the learning of score-based policies for branch-and-cut methods in MIP solving. The authors show a uniform convergence result for score functions across different models (say, the space of NN parameters for a fixed architecture), by bounding standard learning-theoretic quantities (e.g. pseudo-dimensions for data-independent bounds, and Rademacher complexity for data-dependent bounds).

Reviewers and I generally liked the result: it provides a solid theoretical foundation for a relevant and important component in MIP solving, and is a step towards bridging theory and empirical methods.

Here are two concrete suggestions from the reviewer discussion:
- Please consider adding the phrase "score-based" somewhere in the title. The current title is overclaiming a bit.
- Please include the experimental results requested by Reviewer U6oB, ideally in the main body using the extra page.
Decision: Accept (poster)