The Internal Growth Function: A More General PAC Framework for Scenario Decision Making
Authors: Guillaume O Berger
Raphael Jungers
Venue: Accepted by TMLR ()

Abstract: This paper introduces a new PAC framework for scenario decision-making problems.
Scenario decision making consists in making a decision that satisfies a probabilistic constraint (also called a chance constraint) from finitely many sampled realizations (called scenarios) of the constraint.
PAC bounds are sufficient conditions on the number of samples to guarantee with high confidence that the sample-based decision satisfies the true constraint with a prescribed probability.
Existing PAC bounds rely on intrinsic properties of the problem, such as convexity (Calafiore and Campi, 2005), finite VC dimension (Alamo et al., 2009) or existence of a compression scheme (Margellos et al., 2014).
While powerful in some applications, these PAC bounds can be vacuous (or infinite) when the properties are not satisfied.
In this paper, we propose a new PAC framework, leading to PAC bounds that are not vacuous for a strictly larger class of scenario decision-making problems.
This bound is based on the novel notion of ``internal growth'', which adapts the notion of ``growth function'' from classical machine learning (Vapnik and Chervonenkis, 1968) to scenario decision making.
We also relate this notion to other novel properties of the system, such as the $k$-VC dimension.
Furthermore, we show a partial converse result: namely, that for the family of stable monotone scenario decision algorithms, the algorithm is PAC if \emph{and only if} it satisfies our criterion.
Finally, we demonstrate the usefulness of our framework, and compare with existing approaches, on practical problems.

Published in Transactions on Machine Learning Research (02/2026)
The Internal Growth Function: A More General PAC Frame- work for Scenario Decision Making
Guillaume O. Berger
pullaameebereer@uucoooon..
Deportment of Applied Mathematics ICTEAM Institute
UCLouvain
Raphaël M. Jungers
Department Applied Mathematics, ICTEAM Institute UCLowain
Reviewed on OpenReview: https: // openreview. net/ forun? id- HdHHAPKSS
Abstract
This paper introduces a new PAC framework for scenario docision-making problems. Sce- nario decision making consists making a decision that satisfies a probabilistic constraint (also called a chance constraint) from finitely many sampled realizations (called scenarios) of the constraint. PAC bounds are sufficient conditions on the number of samples guar- antee with high confidence that the sample-based decision satisfies the true constraint with prescribed probability. Exxistnng PAC bounds rely on intrinsic properties of the problem, such as convexity (Calafiore and Campi, 2005), finite VC dimension (Alamo et al., 2009) or existence of a compression scheme (Margellos et. al., 2014). While powerful in some applications, these PAC bounds can be vacuous (or infinite) when the properties are not satisfiod. In this paper, we propose a new PAC framework, lcading to PAC bounds that are not vacuous for a strietly larger class of scenario decision-making problems. This bound is based on the novel notion of "internal growth", which adapts the notion of "growth func- tion" from classical machine learning (Vapnik and Chervonenkis, 1968) to scenario decision making. We also relate this notion to other novel propertics of the system, such as the k-VC dimension. Furthermore, we show a partial converse result: namely, that for the family of stable monotone scenario decision algorithms, the algorithm is PAC and only if satisfies our criterion. Finally, we demonstrate the usefulness of our framework, and compare with existing approaches, on practical problems.
1 Introduction
Many problems in engineering involve making decision in the face of random constraints: e.g,, controlling a robot in an environment with randomly moving obstacles (Campi & Garatti, 2008), planning energy produc- tion under uncertain demand (Antoniadou-Plyye tolerance (Pagnoncelli et al., 2012), smart building management with safety and comfort requirements (Pari- sio et al., 2014), machine learning (Campi & Garatti, 2023), ctc. The probability that a decision violates given random constraint is called its risk. Making a decision that has low risk is challenging for two reasons: (i) the constraint landscape is often intractable, as it typically consists in infinitely many possible realizations of the constraint with the non-convex requirement that the decision satisfies "high-probability" subset. of these realizations (Blackmore et al., 2010; Mammarella et al., 2022); (ii) the distribution of the chance constraint is often unknown in practical applications, which makes a mosel-based design impossible.
et al., 2022), portfolio management with prescribed risk
The approach of scenario decision making (Campi & Garatti, 2008; Alamo et al., 2009; Campi & Garatti, 2011: Margellos al., 2014; Esfahani et al., 2015; Campi & Garatti, 2018; Campi et al., 2018; Garatti & Campi, 2022; Campi & Garatti, 2023; Rocchetta et al., 2024) provides simple and effective way to address

---

Published in Transactions on Machine Learning Research (02/2026)
these challenges by leveraging the principle of sample-based methods. The approach consists in drawing sampled realizations (called scenarios) of the random constraint, and making a decision that satisfies all, or a predefined fraction, of the sampled constraints. The decision made from the scenarios is called the scenario decision, and the function mapping the m scenarios to their associated scenario dccision is called the scenario decision algorilhm. A key aspect of this approach is that under some assumptions on the problem or algorithm, one can provide guarantees on the risk of the scenario decision, called PAC (Probably Approzimately Correct) guarantees (Shalev-Shwartz & Ben-David, 2014; Mohri et al., 2018): that is, upper bounds on the probability (with respect to the sampling of the m scenarios) that the risk of the scenario decision exceeds some prescribed tolerance These bounds are referred to as confidence bounds. Existing PAC guarantees for scenario decision algorithms are complexity-based (De Farias & Van Roy, 2004; Alamo et al., 2009; Lauer, 2024), or compression-based (Campi & Garalti, 2008; Calafiore, 2010; Campi & Garalli, 2023; Margellos et al., 2015), following the classification in the recent survey by Rocchetta et al. (2024). Complexity-
guarantocs rely on the identification of decisions as binary classificrs of the constraints (between those that are satisfied by the decision, and those that are violated), and leverage classical results in the theory of binary classification learning, such as the VC dimension (Vapnik & Chervonenkis, 1971), which provide necessary and sufficient conditions for set of classifiers to be PAC-learnable (Shalev-Shwartz & Ben-David, 2014; Mohri et al., 2018). Compression- scenario optimization problems (Campi & Garatti, 2008; Margellos et al., 2014), rely on the property that any set of scenarios can be compressed to a subset of bounded size (called the compression size) and give the same decision as the original set of scenarios. However, some scenario decision algorithms do not satisfy any of these properties (Berger & Jungers, 2025), motivating the need for new PAC guarantees for scenario decision a algorithms.
guarantees, which apply among others to convex
In this paper, propose a new type of PAC guarantees that is strictly more general than the PAC guar- antees mentioned above. These PAC guarantees rely on novel notion called the internal growth function of the scenario decision algorithm, and is inspired from the notion of growth function in binary classification learning (Shalev-Shwartz & Ben-David, 2014; Mohri et al., 2018) (Section 3). We show that an internal growth function that is sub-exponential (called slow internal growth) translates to PAC guarantees for the scenario decision algorithm (Section 4). Furthermore, we relate the slow internal growth property to the criteria mentioned above, showing that it generalizes them, and to another novel quantity, called the k- VC dimension, which refines the notion of VC dimension for scenario decision algorithus (Section 5). Addi- tionally, we present partial converse results: we show that for the class of stable monotone scenario decision algorithrs (studied, e.g., in the context of one-class classification learning; Eppstein & Erickson, 1994; Chan &
2021), the slow internal growth property is sufficient and necessory to obtain PAC guarantees (Section 6). Finally, we demonstrate the usefulness of the new PAC guarantees on concrete examples of sce- nario optimization problems, where the existing approaches fail show the PAC property, but our approach succeeds (Section 7).
Related works
The recent survey by Rocchetta et al. (2024) classifies PAC bounds into three categories: (i) complerity- based PAC hounds (De Farias & Van Roy, 2004; Alamo et al., 2009; Lauer, 2024), based namely on the notions of VC dimension or Rademacher complexity; (ii) compression--ussed PAC bounds (Littlestone & Warmuth, 1986; Floyd& & Warmuth, 1995; Margellos et al., 2015), based on the notion of compression; and (iii) scenario-based PAC bounds (Campi & Garalti, 2008; Calafiore, 2010; Campi & Garatti, 2023), that are tailored to convex sccnario optimization problems (and sometimes exploit additional assumptions, like "non-degeneracy" or "non-concentratedd mass" to obtain better bounds; Campi & Garatti, 2023). A close connection between compression based and scenario- beenario-based PAC bounds was established in Margellos et al. (2015), showing among others that scenario-based PAC bounds imply the existence of a compression scheme for the scenario decision algorithm, and thereby can be also analyzed in this way.
In a recent paper (Berger & Jungers, 2025), we show that complexity- bounds are incomparable in scenario decision making (contrarily to the classical classification problem; Moran & Ychudayoff, 2016), in the sense that one can be vacuous for some scenario decision algorithms, while the other remains informative, and vice-versa. As a corollary, it follows that the underlying properties (i.e.,
and compression- PAC
2

---

Published in Transactions on Machine Learning Research (02/2026)
finite VC dimension existence of compression scheme) are not necessary to obtain PAC guarantees for scenario decision algorithms. The criterion based on the internal growth proposed in this paper is more general in that it is satisfied whenever any of the aforementioned properties is satisfied, and is also shown to be satisfied for some scenario decision algorithms, even when none the other properties are. Furthermore, for monotone algorithms, it is shown to be satisfied if and only if the algorithm has PAC guarantees. The question of whether this reverse direction holds for all scenario decision algorithms remains open.
The abstract view on scenario decision algorithms considered in this work (Section 2.2) draws connec- tion with the problem of one-class classification where one tries to learn the support of distribution (see, e.g., Perera et al., 2021 for a survey). However, rescarch in this area mainly focuses on analyzing specific algorithrms (e.g., SVM-based or deep one-class classifiers) and applications (e.g., outlier or anomaly detec- tiou), so that the results are less relevant for the purpose of this paper, which aims to provide a general and widely applicable framework for scenario decision making.
Notation N {0, .. denotes the set of nonnegative integers. Given m E N, we let [m]] = {I,..., m... Given a set 5, 2 (called the power set of S) denotes the set of all subsets of S, and |S] denotes its cardinality. Given a probability measure μ and m E N, pM denotes its m-fold product, i.e., nx" = p 6 ... 6 y (m times). Given a set S, we let S = - STh be the set of all finite tuples with elements in S.
2 Problem statement
2.1 Risk-aware decision making and scenario decision making
Consider set E of decisions (for instance, in Example 1, each E represents path in configuration space; in Example 2, each & E E represents an SVM classifier in a feature space). We consider constraints our decisions (for instance, in Example the path & must avoid the obstacles; in Example 2, the classifier & must classify the points correctly). Each constraint is represented by the set of decisions that satisfy it; hence, it is a subset of E. We consider a set X C 2 of constraints on E. For each x E and & E E we say that & satisfies the constraint x if E z; otherwise & violates x.
The goal of risk-aware decision making is find a decision & that satisfies the constraints in X with a high probability. For that, we assume probability mcasure μ on X.!
Problem 1 (Risk-aware decision making). For E, X and μ as above, and given risk tolerance E (0, 1], find E E such that PSAT, = pl(x E X : E x}) 2 1 e.
Solving Problem is challenging in general because the set X can be very large or infinite, so that computing ,.AT,((E) for a given can already be challenging (Blackmore et al., 2010), let alone finding one that satisfies the risk tolerance. Furthermore, in many applications, the probability measure on X is unknown. Indeed, it arises from complex phenomena- such as random noise, stochastic demand, random events, etc.-that are hard to capture or model accurately. In this context, sample- based methods such as scenario decision making provide a powerful and principled way to address these challenges. It consists in sampling m constraints Ti...., Tm from X (independently with probability μ) and making a decision based on these samples. Hence, scenario decision algorithm maps tuples of constraints in X to decisions in E:
Definition 1. Let E be decision space and X constraint space as above. A scenario decision algorithm is a function A : X + E, satisfying that for all m E N, (II)...,,Im)) E x and i E [m], A(zI...., E It.
Remark 1. The assumption made in Definition 1, called the consistency assumption, requires that the decision outputted by the algorithm satisfies the input samples. This property is satisfied by large class of scenario
1 All subsets of X or X considered throughout the paper are supposed to be measurable with respect to the underlying distribution μ.. This includes the sets far E X g E a) for all & & (used in Problem 1) and the sets f#r E X PPSAT, > c) for all > 0 (used in equation 1). This is common underlying assumption in secuario optimization (sec, e.g., Caratti & Campi, 2021, footnote 6).
We note that we do not assume the existence a decision satisfying all x X. However, if scenario decision algorithm exists for the problem, then any finste set (21,-..,5ml C X, there is decision & satisfying all 2t's for [m].
3

---

Published in Transactions on Machine Learning Research (02/2026)
decision algorithms in the literature (e.g., Campi & Garatti, 2008; Alamo et al., 2009; Margellos et al., 2014; Esfahani et al., 2015; Campi & Garatti, 2018; Campi et al., 2018; Garatti & Campi, 2022; Campi & Garatti, 2023; Rocchetta et al., 2024).
We illustrate the concept of scenario decision algorithm with two examples:
Example 1 (Path planning). Consider the problem of finding the shortest path between a source location S and & target location T while avoiding a randomly positioned obstacle, as depicted in Figure la. The path must belong to set 3 of "admissible" paths (for instance, all paths that are smooth and have bounded curvature, or all paths that can be represented using H via-points; Jankowski et al., 2023). Fach possible position of the obstacle induces the constraint that the path must avoid the obstacle in that position. Since the position is random, this leads to the constraint that the path must avoid the obstacle with high probability.
More formally, let & be a path and e be the position of the center of the obstacle. Hence, the associated constraint on &, denoted by T(c), is & ((c) if and only if n Bao 2) = 0, where (c, is the 1,2-ball centered at with radius We let X f=(c) : E R²), and v be a probability measure on the center of the obstacle. This induces naturally probability mcasure on X, given by p(S) offc E IR? : 3(c) E S)) (i.e., / tt).
When the probability measure v is not known to the planner, the scenario approach can be used to circumvent this issue by requiring only sampled positions Cm of the center of the obstacle. For instance, a scenario decision algorithm can be defined by:
A(r Tm) = arg min E(S) s.t. E x4 Vi E [m).
mig
EEE
where x; = z(cs) for each i [m] and E(E) is the length of 5.3 A tie breaking rule can be used if the minimizer is not unique. It is straightforward to see that A satisfics Definition 1.
Example 2 (SVM classifier). Consider a feature space 2 C Rd, and a probability measure v on 2 (-1, +1). We seek an SVM classifier of the form Z + sign( (a, 2) + B), where a and B are parameters to determine, such that with high probability on (z, A) E Z x +1,, x = sigu( (a, z) + B); see Figure 1b for an illustration.
For that, we let E be the set of decisions of the form _ = (a,33,1). where a R2, ||]| 1, B E R and n E R. Furthermore, for each (z, A) E Z x +1,, we define the constraint 7(2, X) by (a, n) 5(2, if and only if X((a,z) =) + 3) 2 n.. The scenario decision algorithm is then defined as follows: given samples we compute
(2i, At),...... (Zms Xm) from Z x
A(r Im) = arg max " s.t. gE Vie [m). {=(a.8.n)E=
where x; = -(22, Xr) for each i E [m]. A tie-breaking rule can be used if the maximizer is not unique. It is straightforward to see that A satisfies Definition 1.
4
This paper studies the correctness of scenario decision algorithms, in the sense that their output satisfies Problem 1 with high probability on the sampling of the input constraints. More precisely, we consider PAC (Probably Approximately Correct) guarantees, introduced by Valiant (1984) and standard in machine learning, capturing the fact that if sufficiently many i.i.d. samples of the constraints are used, then with high probability (with respect to the sampling of the constraints), the decision output by the algorithm has a risk below e (i.c., satisfics Problem 1):
Definition 2. A scenario decision algorithm A: X* - 3 is PAC (Probably Approzimately Correct) if for every 8 E (0, 1) and E E (0, 1), there is N N such that for all m N oo) and all probability measure a X, it holds with probability at least 1 5 that if independent samples æ1,..., Zm are drawn from J., then A(z Im) satisfies Problem 1, i.e.,
(fx E X PSAT (A(z))
(1)
We assume that, given (#1 Fm)) ) there always exists path satisfying C x; for all [m]. This can be guarantoed for instance we assume that the sampled positions of the obstacle never block completely the way from S to T, or by having "fallback" solution En. which by definition satisfies all constraints E X, but has sufficiently large cost not be preferred when there is feasible path.
4

---

Published in Transactions on Machine Learning Research (02/2020)
La
CH
(a) Path-planning problem (Example 1).
(b) SVM classifier problem (Example 2).
Figure 1: (a) The path parameterized by H via-points (gray dots). The path must avoid the obstacles (red regions) with high probability, while having minimal length. (b) SVM classifier g in the form of separating hyperplane & + (a, 2) + 3, where z is point in the feature space. The positive instances are represented in red, and the negative instances in blue.
where x a shorthand for Tm)
This leads main problem considered in this paper:
Problem (PAC assessment). Given a scenario decision algorithm A A + E, decide if is PAC, and is, give sufficient values of N a function of 8 and 6.
2.2 Abstract scenario decision making
We introduce abstract scenario decision algorithms. The abstraction removes the explicit output decision "parametrization" and directly tracks which constraints are satisfied by the output. This simplifies the analysis of these algorithms.
To introduce the abstraction, let start with closer look at the definition of PAC algorithm (Definition 2). Given & E E, let SET(E) fx E X & æ} be the set of constraints satisfied by &. The definition of PSAT in Problem implies that PSAT (E) = (S)A Hence, PSAT, , (A(æ)) in equation 1 can be replaced by p(A'(w)), where A'(x) (AT(A())). The algorithm A' = SAT A is called the abstraction of A.
Proposition 1. Consider a scenario decision algorithm A X' + E. The abstraction A' = SAT of A salisfies (i) A' X* + 2 (ii) for all m N and ( 3mm E X (.i,..., S , and (iii) for all X* and any probability measure μ on X, PSAT, , (A(z)) (x)((
(ii) from the consistency of A. This leads to the general definition of an abstract scenario decision algorithm:
Proof. (1) and (iii) are straightforward.
Definition 3. Let X be a constraint space. An abstract scenario decision algorithm is a function A X* 2x, satisfying that for all m and (II,...,, E Xm, {ZI....,Im] C A(,
Definition (PAC) translates directly abstract scenario decision algorithmss
Definition 4. An abstract scenario decision algorithm A X* 2 is PAC (Probably Approzimately Correct) if for every 8 E (0, 1) and 10, there is N E N such that for all m N n [N, and all probability measure on X, it holds with probability at least 1 - 8 that if m independent samples 21. 21...., I' are drawn from μ,, then A(r1,.... xm) satisfics Problem 1, i.c.,
p (Tx X *(A(z)) 2 ct) 2 2-88.
(2)
where x is shorthand for Zm))
In view of Proposition 1, it is sufficient to prove PAC results for abstract scenario decision algorithms, those will transfer directly to concrete scenario decision algorithms. Therefore, in the rest this paper, we focus on abstract scenario decision algorithms, and call them simply "scenario decision algorithms".
5

---

Published in Transactions on Machine Learning Research (02/2020)
Erample 3 (Generated ideal). Let X = N. Consider the (abstract) scenario decision algorithm A X 2* defined by A(z1,... ,m,. = (.1,..., Rm) = (k +... + km ki,..., km E 2 0 N. It is easy to see that A satisfies Definition 3. Indeed, for any (Z1,..., Im) E X and i E [m], it holds that E (xI,..., zm) since 2, = 0z1 +... Oz + 1x; + Or,+1 +... + Oz Modulo a straightforward identification between integers a and their set of divisors d(x: = {v E N: : y (where y x o a E yN), the algorithm can be obtained as the abstraction of a concrete algorithm A, with decision space E = N and constraint set X = {d(x) x e N}, defined by Ac(d(zi),.... d(zm)) - max (N= d(x:)), i.e, Az(d(2)) ............)....... ..... d(rm)) is the greatest common divisor (ged) of (.1, ...,, Fm ). It is known (see, e.g., Jacobson, 2009, p. 104) that is the ged of (.1,..., Zmm] if and only if gN = (. Tm), showing that (AT().((( ...., d(xm))) {d(z) E (z1...., [m))
Im)
2.3 Stability and monotonicity
Before ending this section, we introduce two additional assumptions, called stability and monotonicity, scenario decision algorithmss, which will be used later in this paper when we discuss converse results.
The notion of stability is common in the scenario decision making (Campi & Garatti, 2008; Calafiore, 2010; Campi & Garatti, 2018; Garatti & Campi, 2022; 2021; Campi & Garatti, 2023; Rocchetta et al., 2024). It captures the property that if the returned decision satisfies some unsampled constraints, then adding these constraints to the tuple of sampled constraints does not change the output:
Definition 5. A scenario decision algorithm A: X + +2X is stable if for all x X and y A(x), it holds that A(x, u) = A(æ).
The notion of monotonicity captures the property that the larger the set of sampled constraints, the larger the set of satisfied constraints:
Definition 6. A scenario decision algorithm A X + 2x is monolone if for all (m, n) E N2, (I1, 3m) E X and (y1,...,Bn) X", [m E ,.1....,,h. .n. implies A( S A(yI....,
Erample 4. The scenario decision algorithm A in Example 3 is stable and monotone. Indeed: 1) For the stability: if (f1,...,, then y = >m lez; for l E Z, i E [mn] so that (II,.... Tm, y) = (x1, .m) 2) For the monotonicity: it is clear that (xI...., Im S (,1...., yn implies (Z1,..., S (yI...., Bn) 4
Exomple 5. The scenario decision algorithms searching for the smallest enclosing rectangle or polytope (as in, e.g., Eppstein & Frickson, 1994; Chan Har-Peled, 2021 with no outliers) are stable and monotone.
3 The internal growth
In this section, we present the main concept introduced this paper: the internal growth. This concept will be leveraged in the next section to derive a PAC sufficient condition for scenario decision algorithms.
The notion of internal growth is based the notion of internal projected hypothesis class, which we introduce first. Both notions are extensions of the notions of growth function and projected hypothesis class in binary- classification learning (see, e.g., Shalev-Shwarte & Ben-David, 2014; Mohri et al., 2018) to scenario decision algorithms; see also Remark 2 below.
Definition 7. Let A be a scenario decision algorithm and C X. The internal projected hypothesis class of S with respect A the set
o(5 A) = (A(x)) n a S*).
The internal projected hypothesis size of S with respect to A is defined by p(S; =s{(S;
Remark 2. The notion of internal projected hypothesis class contrasts with the classical notion of projected hypothesis class in binary-clasiffcation learning, which corresponds to the set (A(z) ns a E X*); ;; see also Definition 10, later in the paper.
Example 6, Let X and A be in Example 3. Let S (2.5,6). Then, one can check that
A(E) ns = 0, A(2) n = (2,6).
A(5) ns= {5).
A(2,5)
A(5,6) n = S, n A(2,5,6) n n S
A(6) ns= [6).
6

---

Published in Transactions on Machine Learning Research (02/2026)
where is the empty tuple. Since A is monotone, input tuples with the same set of elements give the same output (e.g., A(2, 5, = A(5, 2)). Henee, aS; A) (0, (5), (6), (), and p(S; A) 5. Note that in this example, the internal projected hypothesis class coincides with the projected hypothesis class. 4
Finally, the internal growth function gives the maximal value of the internal projected hypothesis size for all sets of given cardinality:
Definition 8. Let A X* 2x be a scenario decision algorithm. The internal growth function r(:;A) N N of A is defined by
r(m; A) = max (p(S: S S X, [S| S m))
Clearly, 7(m; A) S 2 We say that has slow internal growth grows a sub-cxponential rate:
Definition 9. Let X 2x be scenario decision algorithm. We say that A has slow internal growth if for all r >>>>>> 1, it holds that r(m; A) E O(r")), i.e. there is C 2 0 such that for all m N, T(m; A) S Crm
In the following, we drop the reference to A in 0, P and when A is clear from the context.
Example 7. Let X and A be as in Example 3. It holds that r(m) = 2m Indoed, let m E N and P be the set containing the first m prime numbers. Consider the set 5 = (P/4 g P} where P = IIpp P. is not difficult to show that for any r E N and (II, E S A(z ((.)....2,))) = I,,] Hence, a(S) = 2 and p(S) = 2| = 2mm which implics that A has not slow internal growth.
4 Slow internal growth implies PAC
In this section, we present the main result of the paper, stating that the slow internal growth property implics that the algorithm PAC, and we derive sufficient bounds on N (ef. Problem 2) based on the internal growth function of A:
Theorem 1. Let A X 22x be scenario decision algorithm. If A has slow internal growth, then A is PAC. Furthermore, N in Desinition 2 con be any N such that (i) eN 2 8, and (ti) for all m E N (N, oc), 2e -mm/ < 8. We note that N E N satisfying (i) and (ti) always exists since, by Definition 9, for all <> 0, there erists C 2 0 such that for all m E N, 7(2m)= S Ceemis
Proof of Theorem 1
We will prove the theorem in several steps. The proof is inspired from the proof of the frequency of e-nets by Haussler & Welzl (1987), but adapts to include internal projected hypothesis classes.
Fix E (0, 1) and let m E be such that em 2 8. Fix a probability measure μ on X and consider the following three sets:
B (III, , Im) E XT' ((A(z),........ xm)) < -e},
B (II I2m) E 2mm, :(A(z)...... (nn) < 1 e, H Izmb \
cm
2 5
B2 (2)))., E 2 3T E
.I......, o(fi,,... }), "m, C CT, Hammly..., 32m]
\T|
Lemma Let be as in Theorem 1, and B, and Bg be as above. It holds that B S B2.
Proof. Straightforward since T can be chosen equal to A(z the definition of B2.
The following lemma instrumental, and inspired by Haussler Welzl (1987, Lemma 3.4):
Lemma 2. Let A be as in Theorem 1, and B and Bi be as above. It holds that nT'H (B) S 2p (Bi).
gNI where g is the god of (.....,,e)), which satisfies g PP/( ..-g)) q,) where 91.............................. 4s P distiuct and such that (#1....,,))
Indeedd, A(r
(P/g....,PP/o
If S. [rr),, then y P/q for some
[Q...... ........))) 9,),
that g C q which implics that y gN. To give an example, take = 3, that P (2,335), 5), P 30, and (15, 6). For (15, 10), we get A(x:) = 5N so that A(x) x (10, 6), we get A(xr 2N so that A(z) {10,6) etc.
[15, 10); for (15, 6), we get A(x) 3N so that A(x) S (15,6):

---

Published in Transactions on Machine Learning Research (02/2026)
Proof. To simplify notation, we denote æ1 = (æ1...., Fm) and 22 = (2m.....m..mm) Note that 2m2 (B,) Eyy Ezg (1), 02) E Bı]. Since (0), E B1 implies 01 E B, it follows that
1 (B)) Em, (1 E B) Emg [(211 22) E Bil).
Now, fix 21 E and let p= m(A(x1)) > It holds that
sm
m p* (1 mm
Egg 1[ 02)) & B1}
Σ 0=
cm since it is the probability that at most 2
elements of æ2 belong to X A(xx)) where the elements are pm
sampled ii.d and the marginal probability of any element to belong to X A(x1) is p. Since and by Chebyshev's inequality, we obtain that
em
<
2
2
En (((1) & B1] s mp(1 p)
4
(pm/2)2 I s
pm 2'
where the last inequality follows from the assumption that em 2 8. Hence, B (2)1, E Bi] 2 and
2m B1) 2 Em, 1 E B} - (d'(B) (B),
concluding the proof.
Lemma 3. It holds that 2m (B2) S (1 722m).
Proof. Let a= 2 We let I be the uniform distribution on the subsets of elements from the set [2m]. Note that
2m B2) E (a
max (E
(11l Fm) [T] 1l[[mm1...... [2m) | \TI > al)
E -
Fam (1f(a) Fm C T) 1[K 22m) \T| > al)
-m Bi Sm I
max Tea((zim..22m))
(1 TT] 11| T2mb \ 77 a))
(since one can replace (II,..., Im by
E E Fim
E Ba tng
Σ
(Ill,))..,, ST) 10]_11((,,, ...
Teo
(because the sum larger than or equal to the max)
E =
Σ al.,
.... |T| a) E (n . - CT)
Σ
(11 (111(1)...,, | \T| > al 2m
(since the probability of choosing m elements in f 32m3 that are in T is most (1 - c/2m)", mh, where [xI,..,, T > a)
E (p((za,...,.2 x2ml) (1
a
< (1- (1 m ((2m).
2m
This concludes the proof.
Hencee the number elements 22 that belong to X A(x1) follows Binomial distribution with parameters of trials) and p (probability of success of each trial). Its mean given by f = mp and variance by a² mp(1 p)-
m (number

---

Published in Transactions on Machine Learning Research (02/2026)
Proof of Theorem 1. Fix e (0, 1) and ò E (0, 1). Let E N be such that 2 (1 - =)("T(2m) ő and cm 8.
By Lemmas 1, 2 and 3, we have that.
n (B) S 2p 2m (B)) S am
2p (B2) S 20- 100-em/44/1 (2m/4((2m) 5.
Hence,
LHS of equation = (X B) 11mh 2 1 6. To conclude the proof, note that 2e 2e-em/A (2m) I implics 2 (1 - f) th 7(2m) S since + + e".
5 Connections with other PAC criteria
In this section, we discuss the connection of the slow internal growth property with other PAC sufficient conditions available in the literature, namely the finite VC dimension criterion (Alamo et al., 2009) and the existence of compression scheme (Margellos et al., 2015). 6 We show that both criteria imply that the internal growth function is polynomial, thereby implying the slow internal growth property. This shows that the latter is at least as general as the union of both existing criteria. The examples in Section 7 will show that it is in fact striclly more general (in particular, the scenario decision algorithm in Example 9 features super- poterroooyoomia,,, yet sub-exponential, internal growth). Next to this, we also introduce a novel quantity, called the k- VCVC dimension, which refines the notion of VC dimension, and we show that finiteness this quantity for all l is necessary and sufficient for the slow internal growth property.
5.1 Finite VC dimension and V-VC dimension
We first present the PAC sufficient condition from Alamo et al. (2009), based on the finiteness of the VC dimension, and show that our sufficient condition is more general. To present this condition, need to first recall the notions of projected hypothesis class, growth function and VC dimension, introduced by Vapnik & Chervonenkis (1971) in the context of binary classification, and adapted to scenario decision algorithms by Alamo et al. (2009):
Definition 10. Let A: X + 2 be a scenario decision algorithm and let S X. The projected hypothesis class of S with respect to A is the set
= (A
The projected hypothesis size of S with respect to A is defined by p((S; A) (o The growth function Al): N N of A is defined by
('m;; A) = max (e' (S: |S| S <m}.7
The VC dimension of A is the supremum of all m E N such that r'(m; A) = =
It is shown by Alamo et al. (2009) that if A has finite VC dimension, then A is PAC. In fact, if A has finite VC dimension, it also holds that A has slow internal growth, thereby showing that the slow internal growth property is more general than the finite VC dimension property:
Proposition 2. Let A X 2 be a scenario decision algorithm. If A has finite VC dimension, then A has slow internal growth. In particular, it holds that ((m) S .max/ {24, (em) }}.
Proof. It is straightforward to see that for all S X, (S) C OSS). Hence, P(S) S P(() and 7(m) I r'mm). Let d < oc be the VC dimension of A. By Sauer Shelah's lemma (see, e,g., Shwartz & BaviDavid, 2014, Lemma 6.10), holds that for all m E (d, oo), r'm)) & (smI)" Also, when m E Nn d), holds that 7'mm) < 2d, concluding the proof.
6See also Rocchetta (2024) for survey. Cleerryy r'(m; A) g 2m.
9

---

Published in Transactions on Machine Learning Research (02/2026)
Next, we introduce novel quantity inspired from the VC dimension, which we call the V-VC dimension and is always smaller than the VC dimension. We then show an equivalence result. with the slow internal growth property. The purpose of this equivalent criterion is to ease the verification of the slow growth property. The V- dimension is defined as follows:
Definition 11. Let A x + 2 be a scenario decision algorithm and & E N. The k- VC dimension of A is the supremum of all m E N for which there are sets S X and R S X such that |S| m, [R] S km and {A(x) ns: x E }-} 2
We show that the k-VC dimension of a scenario decision algorithm is finite for all k E N if and only if the algorithm has slow internal growth:
Theorem 2. Let A - 2* be a scenario decision algorithm. The following propositions are equivalent: (i) A has finite k- VC dimension for all le E N; (ii) A has slow internal growth.
Proof. 1) Proof of (ii) + (i): For a proof by contraposition, let & E N and assumee that A has infinite K-VC dimension. We will show that for infinitely many m E N, r(m) 2 2m/(k+1), which will conclude the proof.
For that, fix N E N. Let m E NN [N x)) such that there are S and R as in Definition 11. Let U = SU R. It holds that |0] S (k+ + 1)m, and that 2 Co(U). Hence, 7((k + 1)m) > 2mh concluding the proof.
2) Proof of (i) = (ii): Fix r > 1. Let k E N such that (ek) I rh. Let d E N be the V-VC dimension of A. We show that for all m E Nn [kd, oo), r(m) I r", which will conclude the proof of 2).
For that, fix m E N n [kd, oc). Fix S S X with [S] S m. Let U S S be such that (A(z) x E S = 2 It holds that |0] S m/k: indcod, if [U] > m/k, then [S] S k/U), and since the V-VC dimension of A is d, it follows that [U] I d, contradietion. Since U was arbitrary, it follows that the largest cardinality c of a set U C S such that {A(x) : x E 5*}= 2 is at most m/ m/k. Hence, from the Sauer-Shelald lemma (see, e.g., Shalev-Shwartz & Ben-David, 2014, Lemma 6.10), it holds that
p(S) =
em
S (ek)ma/k S rm
where the last inequality follows from the definition of k.
5.2 Compression scheme
Finally, present the PAC sufficient condition from Margellos et al. (2015), which is based on the notion of compression, first introduced by Littletonee & Warmuth (1986) in the context of binary classification. We then show that our PAC sufficient condition is more general.
Definition 12. Let X + 2 be a scenario docision algorithm and d E N. A compression scheme of + X
X and A, : X + 2x satisfy that for all m E N and (Ii,...,,Tm)) E X", Ac( Fm)) E [I1,..., 1d and A(z Tm) = A, (A
size d for A is a pair of functions AA), wherein
X
It is shown by Margellos et al. (2015) that if A admits a compression scheme, then A is PAC. In fact, we can show that if A admits a compression scheme, then A has slow internal growth, thereby showing that the slow internal growth property is more general than the compression property:
Proposition 3. Let A X* + 2 be a scenario decision algorillm. If A admils a compression scheme, then A has slow internal growth. In particular, it holds that T(m) S md.
Proof. Let Ar) be a compression scheme of size d for A. Let m E N, and let SC X such that |S| S m. For each x E S*, holds that Ax(x) C Sd. Hence, (S) S (g) y S that (mm) S md, concluding the proof.
Thus, p(S) S ma This shows
Remark 3. Propositions 2 and 3 show that when the scenario decision algorithm has finite VC dimension admits compression scheme, then its internal growth function is polynomial. In Section 7.2, we study a sccnario decision algorithm whose internal growth function is super-polynomial. However, since it is still sub-exponential, we can prove that the algorithm is PAC by using the slow internal growth property.
8 Ag is called the compression map and A, the reconstruction map.
10

---

Published in Transactions on Machine Learning Research (02/2020)
6 When is the sufficient condition necessary?
In this last theoretical section, we investigate the question of "when is the slow internal growth property not only sufficient, but also necessary to be PAC"? We show a converse result for the case stable monotone algorithms (ef. Section 2.3):
Theorem 3. Let A: X + 2x be stable monotone scenario decision algorithm. If A has not slow internal growth, then A is not PAC.
The proof relies on the following result from Berger & Jungers (2025, Section 4):
Lemma 4 (Berger & Jungers, 2025, Theorem 4). Let ; all d E N, there is m E N n [d, oo) such that 7(m) = 2mh then A is not PAC.
X + 2x be a scenario decision algoritlmm. If for
Remark 4. In Berger Jungers (2025, Soction 4), the largest m N such that r(m) = 2n is called the dVC dimension of A. Note that in Lemma 4, we do not require that A is stable monotone.
The proof of Theorem 3 is concluded by showing that the dVC dimension of A (cf. Remark 4) is infinite if A has not slow internal growth:
Lemma 5.
Let A: X - 2 be a slable monolone scenario decision algorithm. If A has not slow internal growth, then for all d E N, there m N [d, oo) such that T(m) = mm
Proof. Let d E N. Assume that A has not slow internal growth. By Proposition 2, it follows that A has infinite VC dimension. Hence, there exist. m N n [d, oo) and S S X such that | = m and d'()) 25. Using the assumptions of stability and monotonicity, we will show that (S) = 25, so that p(S) 2 and r(m) = 2m Therefore, let N and T = (nn C S. We will show that , s definition of S implies that there is holds that A(x,T1,.... Z......,,,..). f = A(x). From the monotonicity, it follows that A(rI,...,Z,,) n,) C T. From the consisteney, it holds that T C A( ;,)) Hence, A( Fn) ns = T. Since n E N and T C S were arbitrary, this implies that (S) = 25, concluding the proof.
The
X such that A(x) ns = T. Fix such æ. From the stability, it
Proof of Theorem 3. Combine Lemmas 4 and 5.
7 Illustrative examples
We present three examples illustrating our results. We first present a simple example, showing elementarily that the slow internal growth property is strictly more general than the finite VC dimension condition and the existence of compression scheme (cf. Section 5). Then, we present more involved example, showing that the slow internal growth property can analyze non-trivial scenario optimization problems, which are also not tractable with the other criteria. Finally, revisit. Example 1 and show that the slow internal growth property provides PAC guarantees for the associated path-planning algorithm.
7.1 Simple example
This example shows elementarily that the slow internal growth property is strictly more general than the finite VC dimension condition and the existence of a compression scheme. The example relies on the existence of scenario decision algorithms satisfying the finite VC dimension condition, but not the existence of a compression scheme, and vice-versa, as shown by Berger Jungers (2025). It goes as follows:
Exomple 8 (Union of scenario decision algorithms). Let X, be a constraint set and Ai Xi + 2X1 be a scenario decision algorithm that has finite VC dimension, but does not admit compression scheme (for instance, take the algorithm in Berger & Jungers, 2025, Section III.B). Similarly, let X, be a constraint set and A₂ : Xÿ + 2Xx be a scenario decision algorithm that admits a compression scheme, but has infinite VC dimension (for instance, take the algorithm in Berger & Jungers, 2025, Section III.A). Without loss of generality, assume that X1 X2 =
Let X X1 U22 and define A X* 2X by A(E (si D... C X1, "imm.- C X2, < in and j1 <... < jm-n- In other words, the input
Im) A AI( Ft, Ug( I Jn))) where
11

---

Published in Transactions on Machine Learning Research (02/2026)
tuple of sampled constraints F1,...,2m Zm is divided into two tuples Th....,, and ..1...., 2 depending whether the sampled constraint belongs to X1 or X2, and then passed respectively to A and A2. Once this is done, the set returned by A is combined with the one by A2 to give the final output of A.
Proposition 4. The scenario decision algorithm A in Example 8 has infinite VC dimension and does not admit a compression scheme.
Proof. Straightforward from the assumptions A1 and A2, and since for each {1,2] and all X; A(x) = (z.).
We show that A has slow internal growth. This comes from a more general fact that the union of finitely many scenario decision algorithms preserves the slow internal growth property:
Proposition 5. Let p E Nyo- For each [p], let X, be constraint set and A, X2 - 2X, be scenario
decision algorithem. Define X = X and A x + 2x by A(x) A -U== As(ws), where for each E [p), is the subtuple of a containing the elements of æ that are in X, and only those ones." 9 It holds that for all m E N, T(m; A) < II T(m; A.). Hence, if for each s E [p], A, has slow internal growth, then A has slow internal growth.
Proof. To prove the bound on the internal growth function, let S S X. For each E [p], let S, = S It holds that (S) = (A, (x,) x, S Vs [p]}. Hence, p(S; A) I IIp=1 p(S,: A,). Thus, for all m E N, rmm; A) S II= ((m; A.), concluding the proof of the bound on the internal growth function. The proof of the preservation of the slow internal growth property is straightforward.
Corollary 1. The scenario decision algorithm A in Ezample has slow internal growth.
Proof. Straightforward from Proposition 5 and the fact that A and A2 have slow internal growth (conse- quence of Propositions and 3, respectively).
7
This concludes the first example, showing elementarily that the slow internal growth property is strictly more general than the other criteria discussed in Section 5.
7.2 Scenario optimization problem
In this section, we present more involved, and concrete, example of scenario decision algorithm, that cannot be proved PAC using the criteria discussed in Section 5, but can be proved so using the slow internal growth crilerion. Furthermore, this example exhibits a clear distinction with the algorithmss that can be studied with the criteria in Section 5 (or a combination of them using Proposition 5) since its internal growth function is super-por polynomial (it grows in 2V"). The example can be seen as a two-stage optimization problem, where one first optimizes an objective with respect to a variable u, and then optimizes second objective with respect to second variable v, with constraints given by the optimizer u" of the first stage. It. goes as follows:
Example 9 (Two-stage scenario optimization). Let un u2 be decision variables with values in N, and oo Ul,... be decision variables with values in {0, Denote u = (w1, U2) and v = (Vo. e)...... Let E = N22 x {0, 1] be the set of values of (u, v). Let. X1 be a set of constraints of the form X; = (c) : c E N2), where Zi(c) {(u, v) E : u + c). Let X₂ be a set of constraints of the form X₂ = {Zz(d) : d e N), where
(2(d) ((,,v) E va = 1}. Denote X XX2 2
Let E (0, 4). Given (0, and probability measure μ X, consider the following chance-constrained optimization problem:
8
d such that {
va va=1 NdeNn (nj + u2, 00), mffz x: (u E x)) 2 1-c.
U1 + U2 +
(3)
== (M))
(1...
d=0
More formally, if
then x. = (Zig...., for some in <... < by such that (Fig...,, din S X. and for
all j [m]] (f1...., (n), 2, X,.
12

---

Published in Transactions on Machine Learning Research (02/2026)
Boxplot of value of the risk
10
10a
10-1
(HA(())
10-2
10
4
10
10
32
100
316
1000
3162
10000
Figure 2: Numerical experiments for the scenario decision algorithm in Example 9, using the probability distribution described in the paragraph below Example 9 with p = 0.25. Box plots of the value of the risk 1- ((((x))), as a ~ nM ii.d. for different values of m and doing M = 50 experiments for cach value of m. We see that the risk decreases monotonically (in average and in maximum value) as m increases. The purple line represents the theoretical upper bound (obtained from Theorem and Proposition 6) on the 0.95-th quantile of the value of the risk 1 p(A(x)). We see that it is indeed above the empirical values.
Solving equation 3 can be approached using scenario optimization. Concretely, given m samples Z1,..., Tm from X, consider the scenario optimization problem:
va =1 Vd NN (u + u2, 20); {
min (MT M2) 0= Po.........))
U1 + U2
d+1 va such that
(u,v) E Vie [m].
d=0
Given m E N and (ZI...., Im E _ let (u*, (Z) be the optimal solution of equation 1. Define the scenario decision algorithm A X* + 2x by A(x) = {x X (u", (u",e")(() (xx E x
We ran numerical experiments on the scenario optimization problem Example (equation 4). For that, we let be the gcometric distribution on N with success rate E (0, 1).11 Then, we let f be the proba- bility measure on X defined by for all (cr, 02) N2, (ct, pl (())) = (v(dd))
{v((ci))(((e2)) and for all N,
For different samples sizes m E N (see horizontal axis in Figure 2), we aimed to estimate the value of u(A(z)) when x E x is sampled i.i.d. according to For that, we computed M = 50 experiments for each value of m. The results are reported on Figure 2. We see that the risk decreases monotonically (in average and maximum value over the M experiments) as m increases. This suggests that the scenario decision algorithm in Example is PAC.
We now prove formally that the scenario decision algorithm in Example 9 is PAC by using the slow internal growth property. For that, show that its internal growth function is upper bounded by O(2v"H). Addition- ally, we show that it is lower bounded by 9(2vm). Hence, the internal growth function is super-polynomial, but sub-exponential. By Remark 3, the former will imply that the algorithm does not satisfy the sufficient conditions Section
Proposition 6. The scenario decision algorithm A in Ezample 9 satisfies 7(m) E 29(Vm), nomely,
In of ties, take the optimal solution (u, v) with smallest lexicographic order. 11That is, for all & N, v((k)) (1 p p.
13

---

Published in Transactions on Machine Learning Research (02/2026)
1) for all m E N, 7(m) S 2
ii for all E N, there is m E N 0o) such that r(m) 2 2vm-1
Proof. 1) Proof of i): We show that for any finite set S S X, it holds that p(S) - 23 where m = [S]. which will conclude the proof.
(S]. Let C = (ceN:: : :.(c) E S} and D= -didNN 52(d) S). For that, fix a finite set S S X, and let m = m= Let k be the smallest integer such that f(c, 02) E Nº :1 + k C. It holds that for all x S*,
(x) + (a)) S k. Hence, for all æ E 5" and d E Nn [k, x)), it holds that rz(()) = 1, so that (2(d) E A(x).
This implies that (A(() N : x E S < 2 Furthermore, it holds that (u*(x) x E H - C S m.
This implies that {{(x)) n N2 x E {* S m. Hence, pSS) S m2vk Finally, note that h2 /2 < C S m. This shows that p(S) I m2v2m. The latter is smaller than 22v2m.
2) Proof of ii): Fix
Nso and let m kkk + 1)/2 + k. Let C ((0),02) E E : :1 + - 1] and 13. Let S (c): c C} and S = (d2(d) e D}. Define S = S U S2. It holds that |S|= = m. We show that for any set T2 S S2, it holds that S UT2 E (S)) This will conclude the proof since
D = {0,, (O,...,.. k- -
it implies that T [kk(k + 1)/2 + k) 2 2*, hence r(m) 2 2Vm-I.
To prove the claim, fix T2 S S2 and let T = Si U2- Let be a tuple containing all elements of T and only those ones. We show that A(x) n = T. Indeed, it holds that uxx) + (zxx) = k. Thus, for each x E X2. x E A(x) if and only if x E T2. Hence, A(x) n S = S1 U2, concluding the proof.
Corollary 2. The scenario decision algorillem A in Example 9 is PAC.
Proof. Combine i) in Proposition 6 and Theorem 1.
A quantitative upper bound the 0.95-th quantile of the value of the risk 1 - =a((a))), when ~ i..d., obtained from Theorem 1 and i) in Proposition 6 is represented in Figure 2 for different values of m. We see that this upper bound is indeed above the empirical values obtained from the nunerical experiments.
n
Corollary 3. The scenario decision algorithm A in Example 9 has infinite VC dimension and does not admit a compression scheme.
Proof. Combine ii) in Proposition 6 and Remark 3.
Remark 5. The slow internal growth property of the scenario decision algorithm A in Example 9 could have been proved using the k-VC dimension criterion (Theorem 2) too. Nevertheless, this would have not provided the quantitative upper and lower bounds on 7 as in Proposition 6.
Remark 6. Corollary 3 could have been proved without using the lower bound on the internal growth function provided in ii) in Proposition 6. We find this lower bound informative, as it demonstrates the existence of scenario decision algorithms for which the internal growth function is super-polynomial but sub-cxponential. Nevertheless, below is a sketch of alternative proof of Corollary 3.
Sketch of alternative proof of Covollary 3. 1) Infinite VC dimension: This comes from the fact that set of
constraints S = +(02d)): d E N n [0, m - 1]} is shattered by E, i.e., d'(S) = 2 (with of as in Definition 10). Indeed, for any T C S, take u = (0, m) and v = (vo, .1....) defined by
0d {
1
if (d) E T or d2 m, otherwise,
AAE
It is clear that uu, = (u",") (x) for some x E X*; indeed, take x whose elements consist of those of T (c1(c) : c = (2),02) E Nº, Ci + 02 S m m-11, 1). 1}. Since T is arbitrary, this shows that o'(S) = 25, so that 7'(m) = 2m. Since m is arbitrary, this implies that the VC dimension of A is infinite (Definition 10).
2) No compression scheme: This comes from the fact that the set of constraints S (c) : c = (cI, 02) e
N², ci + c2 < m - 1} cannot be compressed with size smaller than |S| mm + 1). Since m is arbitrary, no compression scheme exists for A.
The upper hound obtained as the smallest value e such that -m (2m) S 0.05.
14

---

Published in Transactions on Machine Learning Research (02/2026)
7.3 Example 1 revisited
Consider the following modification of Example 1:
Example 10 (Path planning revisited). Consider a path-planning problem in a discrete "two-dimensional" environment Env (O.....MT MM², where M > 1. The goal is to find path from S = (0. 0) that goes as close as possible to T = (M, M). See Figure 3 for an illustration. Let X = Env \ (S). The path can only move horizontally and vertically, i.e., each path 5 is described by a sequence of points (Go....,G;) G.) E Env"+1 such that çu and for all j E [r]. G--lla I 1, where the n'-mmrm is defined by l1(uz, U2) || |ur] + |uz]-- A random obstacle is present in the environment, where its random position is denoted by x E X (we assume
that the obstacle is not positioned at 5). Given x E X and path ç 5 (Go.-... G-) E Env"+] we say that & collides with the obstacle in position if there is j E [r] such that [j f==z. z.
We consider the following algorithm for finding a path with low collision probability from sampled positions of the obstacle. Assume given m E N sampled positions of the obstacle, denoted (xi,..., Fm) E X Define w E N as the largest integer such that at least w sampled positions are outside [0, w 1j3 ie., such that Hi [m]] : I, & [0, w - 1]33| 2 w². Then, find a path confined in [0, w --w-a 1|2 that goes as close as possible to T and avoids all sampled positions of the obstacle. 13 Denote the algorithm that returns the path given the sampled positions by Ac, and denote the associated abstract scenario decision algorithm by A X 2* defined by A(x)= (x E X Aa(a:) does not collide with the obstacle in position æ).
We show that the scenario decision algorithm in Example 10 is PAC by using the slow internal growth property.
Proposition 7. The scenario decision algorithm A in Example 10 satisfies r(m) S 22m
Proof. The proof is similar to the proof of i) in Proposition 6, so we give only the main ideas. If S C X has size m, then the size w in the definition of Ae in Example 10 is at most [m Since the path is confined in [ w- - 1)2, it holds that (5) C {X T T C [0, w - 1]3). Hence, p(S) S 2n < 2V
]
Corollary 4. The scenario decision algorithm A in Ezample 10 is PAC.
Proof. Combine Proposition 7 and Theorem 1.
Remark 7. The path-planning algorithm in Example 10 can be seen as the "quick start" of a longer-horizon path-planning algorithum Indeed, can lead quickly and safely to a location in [0, - 1|2 nearer to T, then a more defensiveecooseevaatie sample-based path-planning algorithm (e.g., Brudermüller et al., 2024; Cherukuri et al., 2025) can be used for the rest of the path. See Figure 3 for illustration.
8 Conclusion
This work addresses limitations of existing PAC sufficient conditions for scenario decision algorithms, first highlighted by Berger & Jungers (2025). In particular, we propose a new framework, based on the novel notions of internal projected hypothesis classes and internal growth function, to obtain PAC sufficient condi- tions that are applicable (i.e., non non-vacuous) to a broader class of scenario decision problems. The usefulness of our framework is demonstrated on a challenging numerical example.
For future work, we plan to address the question of how to check the slow internal growth property effi- ciently. In the numerical experiments of this work, the verification of the slow internal growth property was addressed in ad-hoc manner, but no systematic approach was provided (note that the lack of systematic verification approach is also present with other PAC sufficient conditions studied in this work! Leveraging the equivalent criterion in Theorem 2 and combination properties such as the one in Proposition 5, we plan to provide mathematical and algorithmic tools for the systematic verification of the slow internal growth property. We also plan to address the question of the necessity of the property. We resolved this question
If there is more than optimal path, take the shortest oue, and then the one with smallest lexicographic order. We note the exception of convex scenario programs, for which the compression size equal the dimension of the decision variable (Calafiore, 2010); or the classification problems using simple shapes (e.g., rectangles, spheres, hyperplanes) for which the VC dimension well known (Shalev-Shwartz & Ben-David, 2014).
15

---

Published in Transactions on Machine Learning Research (02/2026)
W
W
Figure 3: Path-planning problem revisited (Example 10). The sampled positions of the obstacle are in rod (note that a same position may be sampled multiple times). The path (light blue) avoids all sampled positions of the obstacle. The value of and the path from S to (w- 1, w 1) (black dot) computed as explained in pattiiiuee-ooenniillly more
Example 10. From (w - 1, w 1) to T, any other sample-based path-planning defensive/consse conservaiveeee (here, padding of two units of distance from the path to any sampled position in Env [0, w 1)2 is required)-oog can be used.
for the family of stable and monotone scenario decision algorithms, but we plan to address it for the general case in future work.
Acknowledgments
G. Berger is a FNRS Postdoctoral Researcher. R. Jungers is a FNRS honorary Research Associale. This project has received funding from the European Research Council (ERC) under the European Union's Hori- zon 2020 rescarch and innovation program under grant agreement No. 864017 (project name: L2C), from the Horizon Europe program under grant agreement No. 101177842 (project name: UniMaaS), and from the ARC (French Community of Belgium) (project name: SIDDARTA). We thank the anonymous reviewers for their insightful comments on the first version of this manuscript.
References
Teodoro Alamo, Roberto Tempo, and Eduardo F Camacho. Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems. IEEE Transactions Automatic Control, 54(11): 2545-2559, 2009. doi: 221109/TAC.2000.200
Kyriaki Antomiadou-Plytariin David Steen, Ola Carlson, Baraa Mohandes, Mohammad Ali Fotouhi Ghazvini, ct al. crenario-based stochastic optimization for energy and ficxibility dispatch of a microgrid. IEEE Transactions on Smart Grid, 13(5):3328 3341, 2022. doi: 201109/TSS.2022.31777
Guillaume O Berger and Raphaäl M Jungers. PAC learnability of scenario decision-makee making algorithms: necessary conditions and sufficient conditions. IEFE Control Systems Letters, 9:186-191, 2025. doi: 10.1109/LCSYS. 200000//LLSYYY222235567777
Lars Blackmore, Masahiro Ono, Askar Bektassov, and Brian C Williams. A probabilistic particle-control approximation of chance-constrained stochastic predictive control. IEEE Transactions on Robotics, 26(3): 502,517, 2010. doi: 10.1109/TRO.2001 21T.O.2000.2444948
Lara Brudermiller, Guillaume Berger, Julius Jankowski, Raunak Bhattacharyya, Raphaäl Jungers, and Nick Hawes. CC-VPSTO: efficient online robot motion planning, 2024. arXiv preprint arX.v:2402.01370.
Via-Point- based Stochastic Trajectory Optimisation for safe and
16

---

Published in Transactions on Machine Learning Research (02/2026)
Giuseppe Carlo Calafiore. Random convex programs. SIAM Journal on Optimization, 20(6):3427-3444, 2010. doi:
Marco C Campi and Simone Garatti. The exact feasibility of randomized solutions of uncertain convex programs. STAM Journal Optimization, 19(3):1211-1230, 2008. doi: 10.1137 /0133700006921X
Marco C Campi and Simone Garatti. A samplinggann--licarrdnn approach to chance-constraineed optimiza- tiom: feasibility and optimality, Journal of Optimization Theory and Applications, 148(2):257722)) 280, 2011.
doi: 101007//00057-000097746.
Marco C Campi and Simone Garatti. Wait-and-judge scenario optimization. Mathematical Programming, 67(1):155 189, 2018. doi: 10.1007/110107-01--10555
Marco C Campi and Simone Garatti. Compression, generalization and learning. Journal of Machine Learning Research, 24(339):1 14, 2023.
Marco Campi, Simone Garalti, and Federico A Ramponi. A general scenario theory for nonconvex optimization and decision making. IEEE Transactions on Automatic Control, 63(12): 4078, 2018. doi: 10.1 AA8.TA012221888444440
Timothy M Chan and Sariel Har-Peled. Smallest k-cnclosing rectangle revisited. Discrete & Computational Geometry, 66(2):769 791, 2021. doi: 10.1007/:0044440000-0000 0023990---0000...00000
Ashish Cherukuri, Anushri Dixit, and Astghik Hakobyan. Distributionally robust and risk-averse model predictive control for motion planning and control: reformulations and computational issues. In Emanuele Garone, Nya. Kolmanovsky, and Tam W Nguyen (eds.), Nonlinear and Constrained Control: Applications, Synergies, Challenges and Opportunities, volume 496 of Lecture Notes in Control and Information Sciences, pp. 151-179. Springer, 2025.
Danicla Pucci De Farias and Benjamin Van Roy. On constraint sampling in the lincar programming approach to approximate dynamic programming. Malhemalics of Operalions Research, 29(3):42 478, 2004. doi:
David Eppstein and Jeff Frickson. Tterated nearest neighbors and finding minimal polytopes. Discrele & Computational Geometry, 11(3):321-350, 1994. doi: 10.1007/BF0257001.
Peyman Mohajerin Esfahani, Tobias Sutter, and John Lygeros. Performance bounds for the scenario approach and an extension to class of non-convex programs. IEEE Transactions Automatic Control, 60(1): 46-58, 2013. doi: 10.1109 TTC.T....2214233772222
Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the Vapmik-Chhervoenkiis dimen- sion. Machine learning, 21:269 21:269-304, 1995. doi: 10.1023/A: A: 1:226660316600
Simone Garatti and Marco C Campi. The risk of making decisions from data through the lens of the scenario approach. IFAC-Papert PapersOnLine,, 54(7):607- -020007766666666 2021. doi: 10. 11016/j.ifacol.2000 2et..222...... .08.427.
Simone Garatti and Marco C Campi. Risk and complexity in scenario optimization. Mathematical Program- ming, 191:243-2788 2022. doi: 10.
David Haussler and Emo Welzl. c-nets and simplex range queries. Discrete & Computational Geometry, 127 151, 1987. doi: 10.1007/BF02156
Nathan Jacobson. Basic algebra I. Dover Publications, Mincola, NY, 2nd odition, 2009.
Julius Jankowski, Lara Brudermüller, Nick Hawes, and Sylvain Calinon. VP-STO: Vin-Point-based Stochastic Trajectory Optimization for reactive robot behavior. In 2023 IEEE International Conference Robotics and Automation (ICRA), pp. 10125-10131. IEEE, 2023. doi:
Fabien Lauer. Margin-based scenario approach to robust optimization in high dimension. JEEE Transactions on Automatic Control, (901))7118) 22-7189, 2024. doi: 2A1109/TAC.2004.3330
17

---

Published in Transactions on Machine Learning Research (02/2026)
Nick Littlestone and Manfred Warmuth. Relating data compression and learnability, 1986. Unpublished manuscript.
Martina Mammarella, Victor Mirasierra, Matthias Lorenzen, Teodoro Alamo, and Fabrizio Dabbene. Chance-constrained sets approximation: probabilistic scaling approach. Automation, 137(110108), 2022. 202.1tt1c...2..10100....
doi:
Kostas Margellos, Paul Goulart, and John Lygeros. On the road between robust optimization and the scenario approach for chance constrained optimization problems. IEEE Transactions on Automatic Control, 59(8): 2258 2263, 2014. doi: 10.1109/TAC.22142233002
Kostas Margellos, Maria Prandini, and John Lygeros. On the connection between compression learning and scenario based single-stage and cascading optimization problems. IEEE Transactions on Automatic Control, (0110)22716221 2721, 2015. doi: 10.109/TAAC.2055224477
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwakkar Foundations of machine learning. MIT, Cambridge, MA, 2nd edition, 2018.
Shay Moran and Amir Ychudayoff. Sample compression schemes for VC classes. Journal of the ACM, 63(3): 1 1-10, 2016. doi: 2,.114/2899440.
Bernardo K Pagnoncelli, Daniel Reich, and Marco C Campi. Risk-return trade-off with the scenario approach in practice: case study in portfolio selection. Journal of Optimization Theory and Applications, 155: 707-722, 2012.
doi: 10.1007/510957-12-0077
Alessandra Parisio, Luca Fabietti, Marco Molinari, Damiano Varagnolo, and Karl Johansson. Control of HVAC systems via seenaiio-bssed explicit MPC. In 53rd IEEE conference on decision and control, pp. 5201-5207. IEEE, 2014. doi: 10.1109/ DC00///CCDD201.74000000
Pramuditha Perera, Poojan Oza, and Vishal M Patel. One-class classification: a survey, 2021. arXiv preprint arXiv:2101.00661.
Roberto Rocchetta, Alexander Mey, and Frans A Oliehock. A survey scenario theory, complexity, and compression-based learning and generalization. TEEF Transactions on Neural Networks and Learning Systems, 35(12):16985 16999, 2024. doi: Tttp:/NNNNSS.....3...0.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: from theory to algorithms. Cambridge University Press, Cambridge, UK, 2014. doi: 10.1077/C0097811729000
Leslie Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134 1142 1984. doi: 10.1145/1968.1972
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applicalions, 16(2):264 280, 1971. doi: 10.1137 10.1137/1116000 1116025.
18


Reviews:
[{"review_id": "OvVPKRpJ0E", "reviewer": "Reviewer_ofkR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new PAC framework for scenario decision-making based on the notion of internal growth, an adaptation of classical growth functions to the scenario setting. It shows that sub-exponential internal growth is sufficient to guarantee PAC learnability and provides explicit sample-complexity bounds. The framework generalizes existing PAC results based on VC dimension and compression schemes, and introduces the k-VC dimension as an equivalent characterization of slow internal growth. The theory is demonstrated on examples, including a two-stage scenario optimization problem.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The main claims are supported by rigorous theoretical analysis. The authors provide formal definitions of internal growth, prove that slow internal growth implies PAC guarantees with explicit sample-complexity bounds, and establish connections to existing VC-dimension and compression-based criteria. The illustrative examples, including the two-stage scenario optimization problem, demonstrate cases where proposed method applies, providing concrete validation of analysis usefulness.", "audience_yn": "Yes", "audience_explanation": "The paper addresses a fundamental question in scenario optimization and learning theory: when sample-based decision algorithms admit PAC guarantees. By introducing a more general framework that extends beyond classical VC-dimension and compression-based analyses, the work is directly relevant to researchers in statistical learning theory. The new internal growth notion, as well as the demonstrated applicability to non-standard scenario optimization problems, are appreciated.", "requested_changes": "* While slow internal growth is the core sufficient condition of the paper, the manuscript does not discuss a practical way to verify it for a given scenario decision algorithm. Practical guidelines for checking this property for new algorithms are missing, which limits the applicability of the framework. Providing clearer check would be valuable.\n\n* The necessity result is restricted to stable monotone algorithms. More discussion of whether this condition might extend beyond this subclass would be appreciated.\n\n* While the synthetic two-stage example effectively demonstrates the advantages of the proposed approach, adding more realistic or varied application examples (e.g., from control or robotics) would further support the practical significance of the framework.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1CneMvrJfb", "reviewer": "Reviewer_HGTy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Summary\n\nIn classic classification, we learn a hypothesis $h$ from sampled data so that it generalizes - i.e., it has low misclassification risk; in scenario decision making (SDM), a “scenario” is a realized random constraint (modeled here as the set of decisions that satisfy it), and the goal is to compute from sampled scenarios $S$ a decision $x=A(S)$ whose population violation risk is small with high confidence. This paper studies PAC guarantees for such scenario decision algorithms. They note that while extending VC/Rademacher and compression can yield guarantees, these routes are sufficient but not necessary PAC in SDM. \n\nTo go beyond them, the paper introduces a strictly (supported by examples in Sec 7) more general complexity notion - the Internal Growth Function (IGF) in Sec. 3, extending the classic growth function to the SDM setting. They further prove slow (sub-exponential) IGF implies PAC in Sec 4; prove existing VC/compression conditions imply slow IGF in Sec 5; and prove IGF corresponds exactly to k-VC dimension (finite k-VC $\\Leftrightarrow$ slow IGF) in Sec 5. Moreover, it is shown in Sec 6 that for stable monotone algorithms, slow IGF is also necessary, while the necessity direction for general SDM remains open. \n\n### Strengths\n\nThe paper addresses key limitations of existing PAC guarantees for SDAs, clarifying what is sufficient versus necessary and closing some gaps in our understanding of PAC conditions for scenario decision making. I appreciate that several examples are provided to help ground the abstract concepts and guide the reader through the messages.\n\n### Weaknesses (mostly presentation/clarity)\n\nDespite the examples, the presentation remains dense and contains multiple abstraction layers. The work would benefit from more bridging sentences to smooth the transitions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Mostly yes, but several arguments would benefit from brief supporting explanations, e.g., in Examples 3, 4, and 5, even if they are relatively straightforward.", "audience_yn": "Yes", "audience_explanation": "PAC guarantee is an important way to understand the fundamental learnability of a problem. While PAC theory has been extensively studied for classic supervised learning, it is far less developed for SDM, where key gaps remain. This paper is interesting because it directly targets those gaps. It introduces an idea (the Internal Growth Function) that extends the classic “growth function” to SDM, links it to known tools (like VC and compression), and shows when it gives guarantees even where existing methods don’t. Hence, it grounds PAC guarantees for SDM in a framework that is pretty well-aligned with classical learning theory.", "requested_changes": "1) **Add brief explanations to Examples 3–5.**  \n   Even if the steps are simple, including 1–2 sentences of brief explanations can be helpful for the readers.\n\n2) **Brief introduction to $X\\subseteq 2^\\Xi$ (Sec. 2.1).**  \n   This can look a bit abrupt at first glance. It could be helpful to motivate by something like “A realized constraint can be represented as the set of decisions that satisfy it. ...” Then give the formal definition.\n\n3) **Motivate the abstraction (Sec. 2.2).**  \n   It could be helpful to start with why it is useful. E.g., abstraction removes the explicit decision parameterization and directly tracks which constraints the output satisfies.\n\n4) **Clarify the intuition in Example 9.**  \n   This example somehow does not look immediately natural to me. Please add further intuition for why this problem cannot be proved PAC using the criteria in Section 5, but can be proved PAC using the slow internal growth criterion.\n\n\n### Minor\n1. Typo: in the proof of Lemma 2, there's a bracket of indicator function, you should change from } to ].", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "v3DsFVUf1P", "reviewer": "Reviewer_fNKv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission is a short note on how to generalize and unify two criteria for PAC learnability of scenario decisions: finite VC dimension and existence of a compression scheme. Each of these two criteria is sufficient for PAC learnability but none is implied by the other. The newly introduced criterion, called slow internal growth, (strictly) generalizes these two criteria (it is implied by each of them but is shown to be more general), is a sufficient condition for PAC learnability, and in addition, is also a necessary condition for a large class of natural scenario decision algorithms (stable and monotone ones). \n\nThe short note is written in a concise, neat, and elegant way, while being pedagogical enough (which I can tell because I wasn't familiar with scenario decisions and after investing some time to get familiar with the objects, I could follow perfectly the text and even enjoyed reading it).", "claims_and_evidence_yn": "Yes", "claims_explanation": "I carefully read the proofs (except for the ones of Section 7, which I only scanned) and spotted no issue other than occasional clarifications for laymen like me.", "audience_yn": "Yes", "audience_explanation": "Researchers interested in PAC learnability of scenario decisions would be interested in the findings (given the submission offers [almost] a necessary and sufficient condition for that). These researchers belong to several communities but definitely are represented in the machine-learning community, as the bibliography shows (e.g., the 2023 JMLR article by Campi and Garatti).", "requested_changes": "I have no strong such suggestions, the submission is already in excellent shape. I merely have a list of small comments (many due to my prior ignorance of the field, I guess), which I provide below.", "broader_impact_concerns": "N/A", "additional_comments": "I'm listing my questions and comments in the order of the text.\n\nPage 2, Problem 1 is stated in great generality and it is even unclear that a solution $\\xi$ exists. Later, the submission is clear (cf. Problem 2) that Problem 1 may be unfeasible. But at this stage, I was wondering whether I was missing something. Similarly, in Definition 1, I marked to myself that in particular, $A(x_1,\\ldots,x_m)$ must belong to $\\cap_{i=1}^m x_i$ and I was worried that the latter intersection could be void. \n\nPage 3, Example 1: Is $\\overline{x}^{-1}$ a (Borel) measurable map? You would need it for $\\mu$ to be well defined. Also, in the definition of $A$ as some argmin: it could well be that no such $\\xi$ exists, e.g., if the $m$ obstacles block completely a 'column'. Shouldn't there be some feasability assumptions?\n\nPage 5, Definition 6: I would have expected $m \\geq n$ (but $m \\leq n$ is considered)\n\nPage 6, Remark 2: Is it $\\boldsymbol{x} \\subseteq X^\\star$ or $\\boldsymbol{x} \\in X^\\star$? Compare to Definition 7, where it is $\\boldsymbol{x} \\in S^\\star$. Also, a pointer to Definition 10 would be useful here.\n\nThe proofs of pages 7-8 are elementary and enjoyable to read because 'everything' is in the definitions of Section 3. Some occasional details may be useful, like, adding one or two equations in the middle of page 7 when Chernoff's bound is applied. Also, Footnote 1 could rather be converted in 2 lines of real text, saying that $e^{-\\epsilon m /4} \\tau(2m)$ can be bounded by something of order $\\gamma^m$ with $\\gamma = e^{-\\epsilon/4} r < 1$ for a well-chosen $r > 1$, thus converges to 0, which entails the existence of $m$. \n\nPage 8, proof of Theorem 1: You do not seem to substitute the bound of Lemma 3 but a smaller bound; indeed, $1-\\epsilon/4$ is larger than $e^{-\\epsilon/2}$, I believe, but $e^{-\\epsilon/4}$ would be fine.\n\nPage 8, Definition 10: Same comment as for Page 6, Remark 2 \n\nSection 6: Just a note, the key argument for necessity is thus Berger and Jungers (2025, Theorem 4) but the present short note cleverly relies on it. \n\nPage 13, proof of Corollary 3: When reading it, one may regret that Section 5 did not state in dedicated and formal remarks that for both cases studied therein, the internal growth function was polynomial, and that, combined with the very definition (Definition 9), this only leaves the super-polynomial / sub-exponential case. I find this an interesting insight, that somehow is buried into the proof of Corollary 3. The beginning of Section 5 could also be more specific about this and explain how it will be proved that the new condition is strictly more general.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)