Minimax Analysis of Active Learning

1. Introduction

• Active learning selects unlabeled examples for annotation, addressing the annotation burden of supervised learning; this paper studies the label requests needed to reach a target error.The pool-based protocol permits sequential selection from an abundant pool of unlabeled points.Source: §1 · pp. 1–2

1.1 The Prior Literature on the Theory of Active Learning

• Prior noisy-learning upper bounds lacked complementary minimax lower bounds capable of confirming when active learning could not outperform passive learning.The paper identifies this gap as persisting despite existing lower bounds for Tsybakov noise being below passive minimax sample complexity.Source: §1.1 · p. 3
• In low-noise Tsybakov regimes, the star number characterizes minimax label complexity, and almost all prior active-learning complexity measures equal it in worst-case value.The paper also proves that doubling dimension is bounded if and only if the star number is finite.Source: §1.1 · p. 4, §1.2 · p. 4

1.2 Our Contributions

• The work establishes near-matching distribution-free minimax bounds across several noise models, often improving prior upper bounds, and proposes a strategy that uses hypothesis-class structure and estimated label variances.Its algorithmic innovation modifies repeated querying to account for changing label variances.Source: §1.2 · pp. 4–5
• For nonextremal Tsybakov noise, active learning improves on passive learning; in high-noise regimes, finite-VC classes have essentially the same label complexity up to logarithmic factors.The paper contrasts this high-noise result with the differing class complexities known in the realizable case.Source: §1.2 · p. 4
• The paper separates minimax label complexity under Tsybakov noise from the Bernstein class condition, unlike passive learning, where the two are equivalent up to logarithmic factors.For most studied noise models, examples show that the gaps between upper and lower bounds cannot generally be reduced beyond logarithmic factors without additional complexity measures.Source: §1.2 · p. 5

1.3 Outline

• The article proceeds from formal settings and noise models to the star number, minimax bounds, passive-learning comparisons, prior complexity measures, and proofs.It also relates the star number to doubling dimension.Source: §1.3 · pp. 5–6

2. Definitions

• The target distribution defines the Bayes classifier and each classifier’s error rate, while the hypothesis class is an arbitrary set of measurable classifiers.The paper focuses on classes containing at least three classifiers and uses d for their VC dimension.Source: §2 · pp. 6–7
• In the pool-based protocol, the learner can inspect an unlabeled sequence and sequentially request at most its label budget before outputting a classifier.The analysis assumes an inexhaustible supply of unlabeled examples; the number needed for the stated label complexity is left open.Source: §2 · p. 6
• The minimax label complexity is the smallest label budget for which an active algorithm achieves the desired guarantee uniformly over the specified distribution family.The definition is parameterized by error and confidence levels.Source: §2 · p. 7
• The analysis assumes relevant random variables and events are measurable, and introduces conventions for logarithms, asymptotic inequalities, and limits.The paper notes that some claims technically require measurability qualifications.Source: §2 · p. 7

3. Noise Models

• The analysis considers realizable, bounded-noise, Tsybakov-noise, Bernstein-class, benign-noise, and agnostic-noise conditions.The conditions specify different restrictions on the joint distribution or the best classifier in the hypothesis class.Source: §3 · p. 8
• The realizable, bounded-noise, and Tsybakov families are related by the inclusions RE ⊆ BN(β) ⊆ BC(1/(1 − 2β), 1) and RE ⊆ TN(a, α) ⊆ BC(a, α).The stated Tsybakov condition is equivalent to requiring the Bernstein-class conditions for all classifiers, rather than only those in C.Source: §3 · p. 8
• For passive learning, minimax sample complexities under Tsybakov noise and the Bernstein class condition are equivalent up to a logarithmic factor, but the paper’s results imply this does not hold for active learning.The paper notes that much prior label-complexity literature uses the weaker Bernstein-class assumption.Source: §3 · p. 8

4. A Combinatorial Complexity Measure

• When maximized over distributions or data sets, several active-learning complexity measures—including disagreement coefficient and splitting index—equal the star number.The listed measures also include extended teaching dimension growth and version space compression set size.Source: §4 · p. 9
• The star number s is the largest number of points for which each point can be isolated as the sole disagreement between a shared classifier and one corresponding witness.The star number is infinite if no largest such number exists.Source: §4 · p. 9
• The star number is at least the VC dimension, but its gap over VC dimension can be infinite.The section relates VC dimension to maximum hypercube degree in the data-induced one-inclusion graph, while star number corresponds to maximum degree.Source: §4 · pp. 9–10
• Threshold classifiers on R have star number 2, whereas interval classifiers on R, linear separators in R^k for k ≥ 2, and axis-aligned rectangles in R^k for k ≥ 1 have infinite star number.These examples illustrate finite and infinite values across hypothesis classes.Source: §4 · p. 10
• For intervals of width at least w on [0, 1], the star number lies between ⌊2/w⌋ and ⌊2/w⌋ + 2.The lower bound follows from a constructed star set; the upper-bound argument handles both possible labelings by the center classifier.Source: §4 · pp. 10–11

5. Main Results

• Except for Theorems 6 and 8, the results refine prior best-known bounds; the Tsybakov- and benign-noise refinements are the most significant, with Theorem 5 the primary contribution..Source: §5 · p. 12
• For 0<α<1, Theorem 5’s Tsybakov-noise active bounds improve asymptotically on passive learning: ˜O(ε2α−2) for s<∞ and ˜O(ε2α−2 ∨ (1/ε)) for s=∞.The corresponding improvement factors are ˜Θ(ε−α) for s<∞ and ˜Θ(ε−min{α,1−α}) for s=∞.Source: §5 · p. 13
• When 0<α≤1/2, all finite-VC classes have ˜O(ε2α−2) Tsybakov-noise label complexity, so their active complexities essentially converge up to logarithmic factors.This regime gives strong improvements over passive learning across the finite-VC classes considered.Source: §5 · p. 13
• As α rises above 1/2, the easy–hard complexity spread re-emerges: easy classes gain more over passive learning as α approaches 1, while the hard-class gap shrinks.For easy classes, the limiting bounded-noise case has a near-exponential improvement over passive learning.Source: §5 · p. 13
• For benign noise with ν≥√ε, Theorem 7’s bounds give all finite-VC classes roughly a 1/ν label-complexity reduction over passive learning, with little easy–hard distinction.The passage characterizes this as the strongest improvement previously known only for easy classes.Source: §5 · p. 13
• Examples span the upper–lower-bound gaps for Theorems 3, 4, 5, and 7, while the authors conjecture refinements to some d- and s-dependences remain open.They also note that the bounded-noise example limits how much its upper bound can generally be reduced.Source: §5 · pp. 14–15
• For a class containing the specified s+1 classifiers, the paper separates Tsybakov and bounded noise: under bounded noise the lower bound exceeds Theorem 5’s Tsybakov upper bound.The authors note that passive-learning sample complexities under these models are equivalent up to an unresolved logarithmic factor.Source: §5 · pp. 14–15

5.1 The Strategy behind Theorems 5 and 7

• The strategy partitions X into cells, infers Bayes-optimal labels from queried labels within cells, and filters increasingly noisy cells before applying realizable-case learning.For finite star number, it uses a CAL-style disagreement strategy on inferred labels to obtain the stated s-dependence.Source: §5.1 · pp. 16–17

Realizable and bounded noise

• For realizable and bounded noise, finite star number yields polylogarithmic active complexity in the passive complexity, while infinite star number gives asymptotically comparable complexity.In the bounded-noise case, the sufficient condition for gains in constants is s ≪ (1−2β)d/ε, which is more restrictive than in the realizable case.Source: §6 · pp. 17–18

Tsybakov noise

• Under Tsybakov noise, active minimax label complexity is o(passive minimax sample complexity) for every α ∈ (0, 1).The comparison also reports an upper-bound improvement over the passive lower bound by roughly a factor of 1/(aε^α), aside from logarithmic factors.Source: §6 · p. 18

Bernstein class condition

• For the Bernstein class condition, finite s suffices for active gains, but when s = ∞ the bounds leave the necessary and sufficient conditions unclear.An example with s = ∞ gives ΛBC ≳ MBC/Log(1/ε), so improvements there may be limited to constants and logarithmic factors; active Bernstein and Tsybakov complexities can differ even when their passive complexities are equivalent up to such factors.Source: §6 · p. 18

Benign noise

• With benign noise and fixed ν, active learning has no asymptotic improvement in ε; when ν varies with ε, the bounds describe different behavior.For νε such that ε ≤ νε = o(1), the passage gives separate bounds for finite and infinite s.Source: §6 · p. 18

Agnostic noise

• For agnostic noise, the upper and lower bounds leave the improvements unclear when s > 1, and whether benign-noise-strength gains generally hold remains open.For s < 1, the upper bound improves over the passive lower bound by roughly a factor of 1/(ν+ε)^s, aside from logarithmic factors.Source: §6 · p. 18

7. Connections to the Prior Literature on Active Learning

• Worst-case complexity measures let the authors compare distribution-dependent prior bounds with their minimax label-complexity results.The section first characterizes these measures’ worst-case values, then combines them with known bounds and compares the resulting rates.Source: §7 · pp. 19–20
• Almost all prior active-learning complexity measures equal the star number when maximized over distributions or data sets.The paper says this equivalence also helps establish its main results by allowing it to build on diverse prior techniques.Source: §7 · pp. 19–20
• Worst-case doubling dimension is bounded if and only if the star number is finite.The doubling dimension can be upper- and lower-bounded in terms of the star number when maximized over distributions.Source: §7 · p. 20

7.1 The Disagreement Coefficient

• The disagreement coefficient is introduced as a particularly well-studied active-learning complexity measure.The section then gives its definition for a classifier, hypothesis class, input distribution, and radius parameter.Source: §7.1 · p. 20

P (DIS (BP (h, r)))

• At ε=0, the worst-case disagreement coefficient equals the star number.This connection is used to compare prior disagreement-based bounds with the paper’s results.Source: P (DIS (BP (h, r))) · p. 21
• The paper’s bounds refine prior disagreement-based bounds for realizable and bounded-noise learning.The refinements apply to the bounds on ΛRE and ΛBN, with sometimes-smaller factors.Source: P (DIS (BP (h, r))) · pp. 21–22
• For Tsybakov noise with α ≤ 1/2, Theorem 5 removes the disagreement-coefficient factor; other cases also yield refinements.For α > 1/2, the stated bound is sometimes smaller; the BE bound is also improved, sometimes significantly when ε ≪ ν ≪ 1 and d is large. Bounds for BC and AG are equivalent to the prior ones.Source: P (DIS (BP (h, r))) · p. 22

7.2 The Splitting Index

• As ε → 0, the worst-case splitting-index quantity is essentially equal to the star number, and Theorem 3 reduces a bound’s first min term from sd to s.The splitting-index analysis also notes that smaller τ corresponds to more unlabeled data and a larger splitting index, though the bound’s logarithmic factors depend inversely on τ.Source: §7.2 · pp. 23–24

7.3 The Teaching Dimension

• The extended teaching dimension growth function equals the star number as m → ∞, and every minimal specifying set is a star set.The paper also establishes XTD(C, m) ≤ s, yielding XTD(C, m) = TD(C, m).Source: §7.3 · p. 26
• The paper’s bounds refine the teaching-dimension-based realizable and BE bounds, while its AG bound is equivalent up to logarithmic factors.For the BE case, the refinement can be significantly smaller when ε ≪ ν ≪ 1 and d is large.Source: §7.3 · p. 26

7.3.1 THE VERSION SPACE COMPRESSION SET SIZE

• When h ∈ C, the minimal version space compression set size equals the empirical teaching dimension.The compression set size is the smallest subsequence preserving the version space.Source: §7.3.1 · p. 27
• In the realizable case, CAL’s label-complexity upper bound matches the minimax label-complexity upper bound up to logarithmic factors.For h in the class, version-space compression sets are equivalent to specifying sets, yielding equality between their sizes.Source: §7.3.1 · pp. 27–28

7.4 The Doubling Dimension

• The worst-case doubling dimension is bounded if and only if the star number is finite, with upper and lower bounds expressed in terms of the star number.The bounds can generally differ by roughly a factor of d.Source: §7.4 · p. 28
• Examples show the doubling-dimension bounds can be tight: the lower bound to a universal constant factor in one class, and the upper bound aside from a small logarithmic-factor difference in another.Source: §7.4 · p. 29
• An inequality relating doubling dimension and disagreement coefficient enables comparisons between bounds; in the realizable case, Bshouty, Li, and Long (2009) give a passive sample-complexity bound no larger than Gine9 and Koltchinskii (2006), aside from constants.Source: §7.4 · p. 29

8. Conclusions

• Under Tsybakov noise, minimax active-learning label complexity for VC classes is always smaller than passive learning’s.The paper expresses its bounds using the star number and finds that many prior distribution- and sample-dependent complexity measures equal it in the worst case.Source: §8 · p. 29
• The bounds are distribution-free worst-case guarantees; minimax complexity with a fixed marginal distribution remains an important open problem.This issue is particularly important when the star number is infinite.Source: §8 · p. 29
• The authors propose distribution-dependent bounds whose worst-case values are never worse than the distribution-free bounds established here.Source: §8 · pp. 29–30

Appendix A. Preliminary Lemmas

• The appendix begins by introducing preliminary lemmas for use in the main proofs.Source: Appendix A · p. 30

A.1 ε-nets and ε-covers

• The disagreement-set collection {DIS({h, g}) : h, g ∈ C} has VC dimension at most 10d, supporting the sampling guarantees.Source: §A.1 · p. 32
• With probability at least 1 − δ, the sampled classifier set is an ε-cover of C and the sample is an ε-net for disagreement sets.The cover uses the P(DIS({·, ·})) pseudometric.Source: §A.1 · p. 32
• Lemma 22 gives a high-probability ε-net construction by selecting from an independent sequence of P-distributed samples.Source: §A.1 · pp. 32–33
• Lemma 24 extends the ε-net guarantee to sets generated by a function of n sample points and labels in a sample-compression setting.Source: §A.1 · p. 34

A.2 Lower Bound Constructions for Noisy Settings

• The lower-bound construction uses k classifiers on k support points of mass ζ, with label noise β there and a residual point labeled without noise.The family is indexed by t ∈ {1, …, k}; Lemma 26 states an implication for general X and C using the construction's classifiers and points.Source: §A.2 · p. 36
• For any active learner A(n), some P_k,ζ,t in RR(k, ζ, β) gives probability strictly below 1−δ of excess risk at most ζ/2(1−2β).Source: §A.2 · p. 37

A.3 Finite Approximation of VC Classes

• Because the Adams–Nobel partition depends strongly on P, relaxing exact constancy to near-constancy enables a data-dependent partition construction.Source: §A.3 · pp. 37–38
• With probability at least 1−δ, a sample-defined cover induces disjoint cells on which every classifier in the cover is constant.Source: §A.3 · p. 38

• Appendix B provides proofs of the article’s main results.Source: Appendix B · p. 39

B.1 The Realizable Case

• The proof gives a lower bound proportional to s ∧ 1; combined lower bounds also include terms proportional to d and Log, with ΛRE(ε, δ) ≥ d stated regardless of d.Source: §B.1 · pp. 39–40
• The s log upper-bound proof adapts disagreement-based analysis with an ε-net, refining logarithmic factors and eliminating label-complexity dependence on δ.This part builds on the technique of Wiener, Hanneke, and El-Yaniv (2014), itself refining El-Yaniv and Wiener (2010, 2012).Source: §B.1 · p. 40
• An ε-net paired with membership-query halving yields a classifier agreeing with the target on the net and error at most ε with probability at least 1 − δ.The halving method treats the net as its instance space; under realizability it recovers the target on that set, while the ε-net property controls error outside it.Source: §B.1 · pp. 41–42
• Across at most ⌈log2(1/ε)⌉ rounds, the algorithm reduces disagreement mass until it is at most ε with high probability under realizability.Each successful round halves the disagreement mass; the target remains in the surviving version space.Source: §B.1 · p. 45
• For every P_XY ∈ R_E, Λ_RE(ε, δ) ≤ 9c̃′s log(1/ε) ≲ s log(1/ε) when n ≥ 9c̃′s log(1/ε), with success probability at least 1−δ.Source: §B.1 · p. 45

B.2 The Noisy Cases

• The method partitions the space using X1, then uses X2 to simulate the Cohn, Atlas, and Ladner (1994) algorithm, estimating each query by majority votes from X3 points in the same cell.This replaces direct labels of query points with repeated labels from their partition cell.Source: §B.2 · p. 46
• Rejecting points when no clear majority emerges within a decreasing query limit shifts the effective marginal distribution toward less-noisy regions.The rejection tends to occur more often in cells with higher noise rates.Source: §B.2 · p. 46
• When γ_Jm > ε/128, the cell’s majority label has greater probability mass than its opposite label on the event in Lemma 32.The comparison is between PXY(Jm × {yJm}) and PXY(Jm × {−yJm}).Source: §B.2 · p. 48
• With probability at least 1 − δ/32, the subroutine’s returns across the stated k, m, and n ranges are restricted to abstention or f*’s label.Lemma 35 gives this guarantee on the intersection of the specified events.Source: §B.2 · p. 52
• With an infinite budget, f* remains in every version space V_m for all k and m ≤ m̃_k on the event specified by Lemma 37.This is the algorithm’s guarantee for the infinite-budget case, which proceeds until m = m̃.Source: §B.2 · p. 55
• A finite budget meeting Lemma 41’s stated threshold suffices to match the infinite-budget classifier and achieve excess error at most ε with probability at least 1−δ.The infinite-budget guarantee is transferred to the finite-budget run by ensuring it reaches the same stopping point.Source: §B.2 · pp. 63, 67, 68
• Algorithm 1 is not adaptive to the noise parameters; removing that dependence via model selection is left for future work.The passage mentions Balcan and Hanneke (2012) and Hanneke (2011) in connection with model-selection discussions.Source: §B.2 · pp. 67–68
• The upper bounds for Theorems 6 and 8 use known results for other algorithms, while the lower bound for Theorem 6 is new.Source: §B.2 · p. 68
• For Theorem 4 under bounded noise, the proof sets γhatε=max{1/2−β, ε/2} and takes the smaller of the active-learning and passive ERM upper bounds.The choice of bound depends on ε, δ, β, d, and s.Source: §B.2 · pp. 68–69
• For TN(a, α), the proof establishes an Algorithm 1 upper bound and constructs RR(k, ζ, β) ⊆ TN(a, α) to obtain a lower bound via Lemma 26.The construction verifies the Tsybakov condition for every distribution in RR(k, ζ, β).Source: §B.2 · pp. 70, 73
• Theorem 5’s upper bound can be improved by logarithmic factors: use (45) directly, with another reduction when α is bounded away from 1/2.In the latter case, the proof notes that the relevant summations are geometric; for very large a, the BE(1/2) bounds may be more informative.Source: §B.2 · p. 74
• Theorem 6’s BC(a, α) upper bound re-expresses existing results using the star number, while its lower bound is inherited from Theorem 5.The proof says its upper-bound technique provides no new algorithm-design insights for BC(a, α).Source: §B.2 · pp. 74–75
• For BE(ν), the upper bound takes the minimum of two derived expressions, and the lower-bound proof yields a stronger term when ε > ν.The proof also notes that terms d and ν can be added to the stated lower bound, increasing it when ε > ν.Source: §B.2 · pp. 77–78
• Theorem 8’s AG(ν) upper bound combines a result for a modified A2 algorithm with Theorem 10, and its lower bound follows from Theorem 7’s BE(ν) bound.The cited algorithm result is attributed to Hanneke (2014), building on Hanneke (2007b), Dasgupta, Hsu, and Monteleoni (2007), and Koltchinskii (2010).Source: §B.2 · pp. 78–79

Appendix C. Proofs for Results in Section 7

• Appendix C provides proofs of the complexity-measure equivalences stated in Section 7.Source: Appendix C · p. 79

C.1 The Disagreement Coefficient

• For finite s, Lemma 42 equates the full supremum with the supremum over finitely supported distributions.This reduction lets the proof establish the upper bound by induction on support size.Source: §C.1 · pp. 79, 82
• For positive ε, the proof bounds the disagreement coefficient by s for every classifier and finitely supported distribution.The inductive argument handles supports of increasing size by reducing them to smaller supports.Source: §C.1 · pp. 80, 82
• At ε = 0, the worst-case disagreement coefficient equals the star number s.The proof obtains this as a limiting case from the positive-ε bound.Source: §C.1 · p. 82

C.2 The Splitting Index

• The proof states that the floors of the reciprocals of the two splitting quantities agree.This lets the argument work with the simpler quantity defined from finite supports.Source: §C.2 · p. 83
• For finite-support distributions, the limit as the tolerance parameter tends to zero equals the corresponding limiting splitting quantity.The proof uses the smallest positive point mass to relate the limiting definition to finite-support behavior.Source: §C.2 · pp. 84–85
• For every finite support size, the proof establishes a splitting threshold of at least 1/s, yielding the corresponding lower bound for the limiting quantity.The induction uses the star-set property to control the largest split among points in the support.Source: §C.2 · pp. 85–87

C.3 The Teaching Dimension

• A specifying set whose every single-point deletion ceases to specify is a star set, so minimal specifying sets inherit that structure.Lemma 14 follows because deleting any point from a minimal specifying set leaves too few points to specify the classifier.Source: §C.3 · p. 88
• The extended teaching-dimension growth function equals min{s, m}, where s is the star number and m is the sequence length.The proof supplies a lower-bound construction using star-set points and an upper bound through minimal specifying sets.Source: §C.3 · pp. 88, 90

C.4 The Doubling Dimension

• The doubling-dimension proof bounds covering numbers of disagreement balls using packings and the VC-Sauer lemma.It relates the packing size to the disagreement coefficient before applying the VC-Sauer bound.Source: §C.4 · pp. 91–92

Appendix D. Examples Spanning the Gaps

• For fixed d and s, two constructed classes have VC dimension d and star number s, establishing tightness of several theorem bounds up to stated factors.The passage distinguishes upper-bound tightness up to universal constant and logarithmic factors from lower-bound tightness up to logarithmic factors.Source: Appendix D · p. 92

General lower-bound construction

• A general lemma combines lower bounds for component classes into a lower bound for a constructed class whose component VC dimension is 1 and star number is ⌊s/d⌋.For d ≲ 1, the lower bounds in the cited theorems already match their respective upper bounds up to constants and logarithmic factors.Source: §D.1 · pp. 93, 96

The realizable case

• The realizable-case upper bound is sometimes tight within a factor proportional to Log(1/ε).The construction uses a class whose component classes have star number ⌊s/d⌋.Source: §D.1 · p. 97

Bounded noise

• For bounded noise with β bounded away from 0, the upper bound is sometimes tight to within logarithmic factors.The result also extends to β near 0 through the realizable-case result and RE ⊆ BN(β).Source: §D.1 · p. 98

Tsybakov noise

• For Tsybakov noise with α ∈ (1/2, 1), the upper bound is sometimes tight to within logarithmic factors for sufficiently small ε.For α ≤ 1/2, tightness is already established by the lower bound in Theorem 5.Source: §D.1 · pp. 98–99

Benign noise

• The benign-noise upper bound is sometimes tight to within logarithmic factors, by reduction from the preceding noise-model results.The reduction uses the inclusion RE ⊆ BE(ν).Source: §D.1 · p. 99

The realizable case

• In the realizable case, the lower bound in Theorem 3 is sometimes tight up to universal constant factors.The passage establishes this for the constructed hypothesis-class example.Source: §D.2 · p. 103

Bounded noise

• For bounded noise, Theorem 4’s lower bound is sometimes tight within logarithmic factors when β is bounded away from 0; near 0, the inherited Theorem 3 bound is also sometimes tight.The inherited bound applies because the realizable distributions are included among the bounded-noise distributions.Source: §D.2 · p. 104

Tsybakov noise

• Theorem 5’s lower bounds are sometimes tight within logarithmic factors: always for 0 < α ≤ 1/2, and also for 1/2 < α < 1 under stated conditions.For the latter regime, the passage specifies a ≥ 4, ε ∈ (0, 1/(24a^(1/α))), and δ ∈ (0, 1/24].Source: §D.2 · p. 105

Benign noise

• For benign noise, the ν = 0 lower bound is tight up to constant factors; the passage begins an analogous argument for ν > 0 without stating its conclusion.The ν = 0 case uses the realizable-case result, with the Theorem 3 lower bound included to strengthen the Theorem 7 bound.Source: §D.2 · pp. 103, 105

D.2 The Lower Bounds are Sometimes Tight

• For ν not near 0, the lower bound in Theorem 7 is tight within logarithmic factors when ε < ν.This holds for ε ∈ (0, (1 − 2ν)/24) and δ ∈ (0, 1/24].Source: §D.2 · p. 107
• For ν near 0, the inherited lower bound on Λ_BE(ν)(ε, δ) is tight within logarithmic factors when ε ≥ ν.Since RE ⊆ BE(ν), the bound applies to Λ_BE(ν)(ε, δ); this holds for ε ∈ (0, 1/9) and δ ∈ (0, 1/3).Source: §D.2 · p. 107