Pith. sign in

REVIEW 3 major objections 6 minor 22 references

How hard is learning to cut? Trade-offs and sample complexity

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Learning to select cutting planes has sample complexity at least as high as generic regression over the same model class, for both standard score functions.

desk verdict Timely question and a clever transfer construction, but the central lower bound relies on an invalid reduction from score minimization to zero-label square loss, so the main theorem isn't proven as stated. read the letter →

arxiv 2506.00252 v1 pith:WV7LPTVN submitted 2025-05-30 math.OC cs.LG

Sammy Khalife , Andrea Lodi This is my paper
classification math.OCcs.LG MSC 90C1090C5768Q32
keywords learningtocutsamplecomplexitycuttingplaneselectionbranch-and-cuttreesizegapclosedfat-shatteringdimensionVCChvátal-Gomorycuts
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes the first sample-complexity lower bounds for learning-to-cut in integer programming. It shows that for any cut-generating model class satisfying two mild closure conditions, minimizing either the branch-and-cut tree size or the gap-closed score over an unknown instance distribution needs at least $\Omega(\mathrm{VCdim}(\mathcal{F}[n])/\epsilon)$ samples, the same order as learning an arbitrary real-valued target from the same class by square loss. Because the bound is worst-case over distributions and holds for every learning algorithm, the difficulty is intrinsic to the cut-selection problem rather than an artifact of a particular training method. The paper also proves the same lower bound when cuts are restricted to those read from the Simplex tableau, and it shows the bounds are nearly tight against known upper bounds for ReLU neural networks. On set-cover and facility-location instances, a graph neural network trained with the cheaper gap-closed score performs almost as well as one trained directly on tree size.

What carries the argument

The load-bearing object is the transfer lemma (Lemma A.1), which lower-bounds the fat-shattering dimension of the scored concept class $\mathcal{F}_{s,\sigma'}$ by $\mathrm{VCdim}(\mathcal{F}[n])$. Its construction uses two-variable integer programs whose two candidate Chvátal–Gomory cuts produce scores separated by a constant or by $\Omega(\gamma)$: one cut gives the integral optimum directly, while the other is redundant and leaves the branch-and-cut tree larger. By shattering the instances' first constraint with the generator class and using the squeezing function $\sigma'$ to convert output signs into cut weights, any labeling can be realized, so the composed class inherits the VC dimension of the generator. The general fat-shattering lower bound of the paper's Theorem 2.4 then converts that dimension into a sample-complexity lower bound.

What would settle it

Find any distribution over instances and two functions $f,g$ in a class satisfying Assumptions 1 and 2 for which $\mathbb{E}[h(I,f(I))]<\mathbb{E}[h(I,g(I))]$ but $\mathbb{E}[h(I,f(I))^2]>\mathbb{E}[h(I,g(I))^2]$ for one of the two score functions $h$ taking values in $[0,1]$; this would falsify the Remark 2.5 equivalence that carries the lower bound, since the two objectives would no longer share a minimizer.

Watch

Extended reading notes

Core claim

The central result is Theorem 3.2: under Assumptions 1 and 2, the sample complexity of learning to score cuts obeys $m_{\mathcal{L}}(\epsilon,\delta)=\Omega(\mathrm{VCdim}(\mathcal{F}[n])/\epsilon)$ for both the gap-closed and branch-and-cut-tree-size scores. The proof works through a transfer lemma: the fat-shattering dimension of the scored class $\mathcal{F}_{s,\sigma'}$ is at least the VC dimension of the underlying cut-generating class, so a generic fat-shattering lower bound on learning applies. The same argument carries over when candidate cuts are restricted to those produced by the Simplex tableau, giving Theorem 3.6. For ReLU neural networks with $L$ layers and $W$ weights, the bound becomes $\Omega(\tfrac{W L}{\epsilon}\log(W/L))$, which matches the best known upper bounds up to logarithmic factors and the standard $1/\epsilon$ versus $1/\epsilon^2$ gap.

Load-bearing premise

The lower bounds depend on treating 'minimize the expected score' as identical to 'minimize the expected squared score with all labels set to zero'; if those two objectives ever pick different functions, the proof targets a different problem than the one stated.

Editorial extensions

If this is right

  • To reach an $\epsilon$-optimal expected score with high probability, any learner needs on the order of $\mathrm{VCdim}(\mathcal{F}[n])/\epsilon$ solved instances, so dataset sizes must grow linearly in the model class's VC dimension.
  • The same lower bound applies whether the training signal is the expensive branch-and-cut tree size or the cheaper gap-closed score, so switching to the proxy does not reduce the worst-case amount of data needed.
  • Restricting the cut pool to Simplex-tableau cuts leaves the complexity unchanged: the lower bound still scales with the VC dimension of the model that scores the tableau cuts.
  • For ReLU neural networks, the lower bound $\Omega(\tfrac{W L}{\epsilon}\log(W/L))$ nearly meets known upper bounds, leaving only logarithmic factors and the standard $1/\epsilon$ gap.
  • In the reported experiments, graph-neural-network cut selection reduces average tree size relative to random selection on set cover and facility location, and the gap-closed-trained model is within a few percent of the tree-size-trained model, supporting the proxy in practice.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof's reduction to square loss is asserted rather than derived; if a score function and class existed for which the minimizer of the expected score and the minimizer of the expected squared score differ, the lower bound would apply to a different objective than the one the paper states.
  • Because the bounds are worst-case over instance distributions, structured real-world distributions could be learnable with far fewer samples; the experimental results on two ILP families are consistent with that possibility.
  • The lower-bound construction only needs two specially built two-variable ILPs per shattered point, so the same approach should transfer to other cut-quality scores that are constant on those two constructed cuts, such as dual-bound improvement.
  • The residual $1/\epsilon$ gap between lower and upper bounds mirrors general learning theory, suggesting that closing it for learning-to-cut would require distributional assumptions rather than a sharper worst-case analysis.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies the sample complexity of learning-to-cut for integer programming: given an unknown distribution over ILP instances, one must choose a function f from a class F that maps instances to CG-cut weights so as to minimize either the branch-and-cut tree size score or the gap-closed score. The main theoretical claim is that, under two closure assumptions on F, the sample complexity is Ω(VCdim(F[n])/ε) for both scores, with a similar result for tableau cuts, and that for ReLU networks this yields Ω(WL log(W/L)/ε). The proof route is to reduce the score-minimization objective to square-loss regression with all labels set to zero, then apply a fat-shattering lower bound. The paper also reports experiments with a GNN trained with each of the two scores on set covering and facility location instances.

Significance. If the main lower bounds were valid, they would constitute the first quantitative sample-complexity lower bounds for the learning-to-cut framework and would show that score minimization is essentially as hard as generic supervised learning over the same concept class. The empirical comparison between gap-closed and branch-and-cut tree size as training signals is also a useful starting point for a largely empirical literature. However, the central reduction on which all theoretical results rest is invalid, so the theoretical significance is not currently established. The paper does not provide code or machine-checked proofs; the proofs are standard mathematical arguments.

major comments (3)
  1. [Section 2.2, Eq. (2) and Remark 2.5] The claimed equivalence between minimizing E[h(I,f(I))] and minimizing E[h(I,f(I))^2] with all labels set to zero is asserted without proof and is false in general. For nonnegative bounded scores, pointwise monotonicity of the square does not imply equality of the minimizers of the expectations: for example, over a distribution with P(X=x1)=0.9 and P(X=x2)=0.1, two candidate functions with scores (0,1) and (0.1,0.1) have E[s]=0.1 for both, but E[s^2]=0.1 for the first and 0.01 for the second. Thus the square-loss objective can select a different function than the original score objective. Moreover, if F_{s,σ'} contains a function whose score is identically zero, the sample complexity of (2) is zero, while fat_{F_{s,σ'}}(γ) can be large; Assumptions 1 and 2 do not exclude this situation. Consequently, Theorem 3.2 and Corollary 3.3 are not established for the objective stated in the abstract.
  2. [Appendix A, proof of Theorem 3.2] The proof invokes AB09 Theorem 19.5 as a lower bound on the sample complexity of the class F_{s,σ'}. That theorem is a supervised-learning lower bound for regression with labels generated by an unknown target function; setting all labels to zero removes the target and changes the problem to unconditional second-moment minimization, which is not the object that Theorem 19.5 addresses. Even if the reduction in Remark 2.5 were correct, the cited theorem would not lower-bound the sample complexity of the unsupervised objective (2). This is a load-bearing gap in every theoretical result of the paper, including Propositions 3.4 and 3.7.
  3. [Remark 2.5 and Section 2.1] The reduction in Remark 2.5 also requires the score function to take values only in [0,1], but the branch-and-cut tree size score is a relative variation of the tree size and can be negative when a cut increases the tree; the paper's own example at the end of Section 2.1 describes a cut that leads to a larger branch-and-cut tree. Therefore the stated hypotheses for the zero-label square-loss trick are not met for one of the two scores that the theorems claim to cover.
minor comments (6)
  1. [Appendix A, proof of Theorem 3.2] The proof drops the factor 16 in the denominator when passing from Theorem 2.4 to the displayed inequality mL ≥ (fat_{F_{s,σ'}}(ε/α)-1)/ε; the quoted theorem has 16α in the denominator. This does not affect the Ω order, but the displayed inequality is inaccurate.
  2. [Appendix A, Lemma A.1, final paragraph] The sentence describing the two label cases says 'when yi = −1 ... generates the CG-cut u1, and when yi = −1 ... generating the CG-cut u2'; the second condition should presumably be yi = 1, and the labeling convention should be checked against Definition 2.3, where yi = -1 corresponds to high values.
  3. [Section 3.2 and Appendix A] The numbering is inconsistent: the statement in Section 3.2 is Theorem 3.6, but the appendix proves 'Theorem 3.7', and the proof of Proposition 3.7 refers to 'Theorem 3.7' instead of Theorem 3.6.
  4. [Table 1] The lower and upper bounds in Table 1 omit the factors 1/ε and 1/ε^2 that appear in the text; as printed, the table suggests the sample complexity is independent of ε, which is misleading.
  5. [Abstract and Section 4.2] The abstract says the gap-closed score is empirically an effective proxy, but Table 2 shows that the GNN trained with gap closed is worse than the GNN trained with tree size on both problem families and worse than the Parallelism heuristic on set cover; the empirical support for the proxy claim is therefore weaker than stated.
  6. [Assumption 2 and Definition 2.1] The notation Fi[n](c) used in Assumption 2 is not clearly defined: Definition 2.1 defines F[i](c) with a different index convention, and the dimension of the restriction vector c is not specified consistently with the domain Rn×m+m+n of F.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower-bound derivation is self-contained; the flagged Remark 2.5 reduction is an unproved equivalence (a correctness risk) rather than a circular step.

full rationale

The central derivation chain is Theorem 3.2 -> Lemma A.1 -> Theorem 2.4 (AB09). Lemma A.1 explicitly constructs ILP instances and CG cuts to fat-shatter F_{s,sigma'}, proving fat_{F_{s,sigma'}}(gamma) >= VCdim(F[n]) using Assumptions 1-2 and explicit score computations; it does not fit any constant from data and does not assume the lower bound it proves. Theorem 3.2 then applies the external AB09 lower bound. The only load-bearing step that is asserted without proof is Remark 2.5's equivalence between minimizing E[h(I,f(I))] and minimizing E[h(I,f(I))^2] with all labels set to zero; this is a missing justification and potentially invalid reduction to a different objective, but it is not circular because the lower bound is not defined in terms of itself. The comparison upper bounds cite the authors' own [CKFB24], but that citation is used only to contextualize tightness and is not needed to derive the lower bounds. No fitted-input-called-prediction, self-definitional, or author-imported uniqueness pattern is present.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The theoretical lower bound rests on standard learning theory results and two explicit assumptions on the concept class. The most fragile ingredient is the asserted equivalence between the score minimization and the zero-label square loss problem, which is not proven. The score functions themselves are not formally defined, which adds an unstated normalization assumption. No new physical or mathematical entities are introduced.

assumptions (5)
  • standard math Theorem 2.4 from Anthony and Bartlett (2009): any learning algorithm for a [0,1]-valued function class has sample complexity at least (fat_F(epsilon/alpha)-1)/(16 alpha).
    Used as the starting point of the lower bound in Theorem 3.2.
  • domain assumption Assumption 1: the concept class F is closed under input translation and per-coordinate output scaling.
    This closure is used in Lemma A.1 to translate shattered instances and rescale CG weights without leaving the class. It holds for ReLU and GNNs but is a restriction of the result.
  • domain assumption Assumption 2: the VC dimension of each coordinate-restricted class F_i[n](c) is constant in c.
    Used to transfer shattering from one coordinate to the whole vector output; stated as true for (graph) neural networks with a non-identically-zero activation.
  • ad hoc to paper Equivalence of minimizing the raw score E[h(I,f(I))] and minimizing the square loss E[h(I,f(I))^2] with all labels set to 0.
    Remark 2.5 asserts this equivalence without proof; the equivalence is not generally true for deterministic bounded scores because the minimizer of the second moment can differ from the minimizer of the first moment.
  • domain assumption The score functions for gap closed and branch-and-cut tree size can be normalized to [0,1] and the construction of Lemma A.1 yields score differences of order gamma (gap closed) and 1 (tree size).
    The proof computes scores for the two constructed cuts but the paper never formally defines these scores nor their normalization, so this is an unstated assumption about the practical scoring rules.

how reviews work

0 comments
Cite this review

Pith. "Pith review of How hard is learning to cut? Trade-offs and sample complexity." pith.science (2026). https://pith.science/paper/WV7LPTVN

@misc{pith2026250600252,
  author       = {Pith},
  title        = {Pith review of: How hard is learning to cut? Trade-offs and sample complexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WV7LPTVN}},
  note         = {Machine review of arXiv:2506.00252}
}
abstract

In the recent years, branch-and-cut algorithms have been the target of data-driven approaches designed to enhance the decision making in different phases of the algorithm such as branching, or the choice of cutting planes (cuts). In particular, for cutting plane selection two score functions have been proposed in the literature to evaluate the quality of a cut: branch-and-cut tree size and gap closed. In this paper, we present new sample complexity lower bounds, valid for both scores. We show that for a wide family of classes $\mathcal{F}$ that maps an instance to a cut, learning over an unknown distribution of the instances to minimize those scores requires at least (up to multiplicative constants) as many samples as learning from the same class function $\mathcal{F}$ any generic target function (using square loss). Our results also extend to the case of learning from a restricted set of cuts, namely those from the Simplex tableau. To the best of our knowledge, these constitute the first lower bounds for the learning-to-cut framework. We compare our bounds to known upper bounds in the case of neural networks and show they are nearly tight. We illustrate our results with a graph neural network selection evaluated on set covering and facility location integer programming models and we empirically show that the gap closed score is an effective proxy to minimize the branch-and-cut tree size. Although the gap closed score has been extensively used in the integer programming literature, this is the first principled analysis discussing both scores at the same time both theoretically and computationally.

Figures

Figures reproduced from arXiv: 2506.00252 by the authors.

Figure 1
Figure 1. Example of 2D instance used to construct the lower-bound and prove Lemma A.3. Both cuts CG1 and CG2 are possible cuts from the Optimal Tableau. The cut derived from CG1 gives directly the optimum (0, 5), whereas the cut CG2 gives a suboptimal fractional solution. Both cuts are then mapped via the redundant constraint of the collection of instances, to γ-shatter the instances according to the score considered. 14 [P… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

22 extracted references · 20 canonical work pages

  1. [1]

    Neural network learning: Theoretical foundations

    Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations . cambridge university press, 2009

    work page 2009

  2. [2]

    Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks

    Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research , 20(63):1--17, 2019

    work page 2019

  3. [3]

    Sample complexity of tree search configuration: Cutting planes and beyond

    Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems , 34:4015--4027, 2021

    work page 2021

  4. [4]

    Integer programming , volume 271

    Michele Conforti, G \'e rard Cornu \'e jols, and Giacomo Zambelli. Integer programming , volume 271. Springer, 2014

    work page 2014

  5. [5]

    Chv\'atal

    V. Chv\'atal. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics , 4:335--337, 1973

    work page 1973

  6. [6]

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

    Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Data-driven algorithm design using neural networks with applications to branch-and-cut. arXiv preprint arXiv:2402.02328 , 2024

    work page Pith review arXiv 2024

  7. [7]

    Rethinking the capacity of graph neural networks for branching strategy

    Ziang Chen, Jialin Liu, Xiaohan Chen, Wang Wang, and Wotao Yin. Rethinking the capacity of graph neural networks for branching strategy. Advances in Neural Information Processing Systems , 37:123991--124024, 2024

    work page 2024

  8. [8]

    Machine learning for cutting planes in integer programming: A survey

    Arnaud Deza and Elias B Khalil. Machine learning for cutting planes in integer programming: A survey. arXiv preprint arXiv:2302.09166 , 2023

    arXiv 2023

Show all 22 references
  1. [9]

    Generalization of erm in stochastic convex optimization: The dimension strikes back

    Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. Advances in Neural Information Processing Systems , 29, 2016

    2016

  2. [10]

    R.E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society , 64:275--278, 1958

    1958

  3. [11]

    A pac approach to application-specific algorithm selection

    Rishi Gupta and Tim Roughgarden. A pac approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages 123--134, 2016

    2016

  4. [12]

    Gurobi Optimization, LLC

  5. [13]

    Learning to select cuts for efficient mixed-integer programming

    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

    2022

  6. [14]

    Mixed integer programming computation

    Andrea Lodi. Mixed integer programming computation. In 50 years of integer programming 1958-2008: From the early years to the state-of-the-art , pages 619--645. Springer Berlin Heidelberg Berlin, Heidelberg, 2009

    1958

  7. [15]

    Learning to stop cut generation for efficient mixed-integer linear programming

    Haotian Ling, Zhihai Wang, and Jie Wang. Learning to stop cut generation for efficient mixed-integer linear programming. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 38, pages 20759--20767, 2024

    2024

  8. [16]

    Algorithms with predictions

    Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM , 65(7):33--35, 2022

    2022

  9. [17]

    Integer and combinatorial optimization , volume 18

    George L Nemhauser and Laurence A Wolsey. Integer and combinatorial optimization , volume 18. Wiley New York, 1988

    1988

  10. [18]

    Learning to cut by looking ahead: Cutting plane selection via imitation learning

    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

    2022

  11. [19]

    The algorithm selection problem

    John R Rice. The algorithm selection problem. In Advances in computers , volume 15, pages 65--118. Elsevier, 1976

    1976

  12. [20]

    Theory of Linear and Integer Programming

    Alexander Schrijver. Theory of Linear and Integer Programming . John Wiley and Sons, New York, 1986

    1986

  13. [21]

    Stochastic convex optimization

    Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT , volume 2, page 5, 2009

    2009

  14. [22]

    Reinforcement learning for integer programming: Learning to cut

    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

    2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.