📚TheoryAdvanced

VC Dimension

Key Points

•
VC dimension measures how many distinct labelings a hypothesis class can realize on any set of points of a given size.
•
A set is shattered if every possible $\frac{0}{1}$ labeling of that set is achievable by some hypothesis in the class.
•
Classic examples: intervals on the real line have VC dimension 2; linear separators in $ $R^{d}$ $ have VC dimension $d+1$; any finite class has VC dimension at most $ $⌊$ $lo g_{2}$ $∣ H ∣$ $⌋$ $.
•
The VC inequality bounds the generalization gap uniformly over the class in terms of its VC dimension.
•
PAC sample complexity scales like $O((d + $lo g$ (1/ $δ$ ))/ $ε^{2}$ )$ in the agnostic setting, and like $O((d $lo g$ (1/ $ε$ ) + $lo g$ (1/ $δ$ ))/ $ε$ )$ in the realizable setting.
•
High VC dimension increases the potential to overfit; low VC dimension may underfit if the target is complex.
•
Infinite VC dimension does not automatically prevent learning (e.g., nearest neighbor can generalize under distributional assumptions).
•
VC dimension guides model selection, regularization, and sample size planning by quantifying capacity.

Prerequisites

→Basic set theory and functions — To understand hypothesis classes, subsets, and labelings.
→Concentration inequalities (Hoeffding/Chernoff) — VC bounds rely on uniform convergence derived via concentration and union bounds.
→Combinatorics and binomial coefficients — Sauer–Shelah lemma and counting labelings use combinatorial arguments.
→Linear algebra and geometry of hyperplanes — Examples involving linear separators in $\mathbb{R}^d$ require geometric intuition.
→Perceptron algorithm — Used to test linear separability in small experiments and understand margins.
→PAC learning framework — VC dimension is central to PAC sample complexity and generalization guarantees.
→Asymptotic notation (Big-O) — To interpret sample complexity and runtime bounds.
→i.i.d. sampling assumption — VC generalization bounds typically require independent, identically distributed data.

Detailed Explanation

Tap terms for definitions

01Overview

Hook → If you give me n data points and a model family, how many ways can that family paint the points red/blue? If it can paint them in every possible way (all 2^n patterns), we say it shatters the set.
Concept → The Vapnik–Chervonenkis (VC) dimension is the largest n for which such total flexibility is possible, over some placement of n points. It is a property of a hypothesis class (e.g., all linear classifiers in R^d), not of a single trained model. VC dimension captures capacity: the larger it is, the more complex patterns the class can fit.
Example → Intervals on the real line can realize any labeling on any two points by choosing an interval that includes exactly the positives, so VC = 2. But with three points, labeling + - + cannot be captured by a single interval, so it fails to shatter 3 points.
Why it matters → VC dimension powers generalization theory. The VC inequality gives a high-probability bound that the empirical error and true error are close uniformly over the class, with a dependence on VC dimension d and sample size n. This leads to PAC sample complexity bounds telling us how many samples suffice to learn with accuracy ε and confidence 1−δ. Practically, VC dimension explains overfitting: if your dataset is too small relative to model capacity, the class can fit noise; if it’s large enough, uniform convergence kicks in and training error becomes a reliable guide to test error.

02Intuition & Analogies

Hook → Think of hypotheses as cookie cutters and your dataset as sugar sprinkles on a tray. Each cutter shape carves the tray into “inside” (label +1) and “outside” (label −1).
Concept → A class with high VC dimension is like owning many flexible cookie cutters; no matter how you color the sprinkles, you can always find a cutter that includes exactly the red ones and excludes the blue ones—at least up to some number n of sprinkles. That n is the VC dimension.
Analogy 1: Light projector. Imagine you have a projector (hypothesis class) and a small set of points on a wall. For each on/off pattern of those points (labeling), if you can adjust the projector’s mask (parameters) to illuminate exactly the “on” points and not the “off” ones, the projector shatters that set. The largest set size for which you can always do this is the VC dimension.
Analogy 2: Switchboard. With n switches there are 2^n configurations. A class shatters a set of n points if it has enough wiring to realize every configuration on that set. The VC dimension measures how many switches you can fully control before you run out of wiring constraints.
Example → Two points on a line: any up/down coloring can be captured by an interval that wraps the “ups.” Three points: the pattern up–down–up forces two disjoint intervals, which a single interval cannot do—hence failure to shatter 3.
Takeaway → VC dimension is not about the average case; it’s a worst-case capacity. It tells you the largest number of points you could be forced to fit in all possible ways. That worst-case perspective is what makes the generalization guarantees so strong.

03Formal Definition

Hoo k \to W e

want a crisp way to capture “can realize all labelings.”

C o n ce pt \to L e t

X

\) be the input space and \(

H

\subseteq

\{h:

X

\to

\{0,1\}\}\) a hypothesis class. For a finite set \(S = \{

x_{1}

\dots

x_{n}

\subset

X

\), define the set of labelings induced by \(

H

\) on S as \(

\mathcal{H}|_S = \{ (h(x_1),\dots,h(x_n)) : h \in \mathcal{H} \} \). We say S is shattered by \(\mathcal{H}\) if \(|\mathcal{H}|_S|

= 2^n\), i.e., every binary labeling of S is realized by some h in \(

H

\). Definition (VC

d im e n s i o n) \to T h e

VC dimension \(

d_{V C}

(

H

)\) is the maximum n such that there exists an S of size n shattered by \(

H

\). If sets of arbitrarily large size can be shattered, the VC dimension is infinite. Growth function → \(m_{

H

}(n) =

max_{∣ S ∣ = n}

∣ H ∣

|\) counts how many distinct labelings the class can realize on n points in the worst case. Sauer–Shelah’s lemma shows that when \(d_{VC}(\mathcal{H}) = d < \infty\), \(m_{\mathcal{H}}(n)\) grows polynomially in n (at most \(\sum_{i=0}^{d} \binom{n}{i}\)), not exponentially. Uniform convergence → With i.i.d. samples, the VC inequality bounds \(\sup_{h\in\mathcal{H}} |

R(h)-

R

(h)|\) with high probability using \(m_{

H

}(n)\), leading to PAC sample complexity depending mainly on \(

d_{V C}

(

H

)\), \(

ε

\), and \(

δ

\).

04When to Use

Hook → When should you reach for VC dimension instead of, say, parameter count or training loss?
Concept → Use VC dimension to reason about model capacity and generalization without distribution-specific assumptions, to compare hypothesis classes, and to estimate how many samples you need for PAC learning.
Use cases:

Choosing between models: linear separators (VC = d+1) vs. polynomial separators (higher VC). Prefer lower VC if data is scarce to reduce overfitting risk.
Feature engineering: adding features increases VC; be mindful of sample size.
Sample size planning: apply PAC bounds (n = O((d+\log(1/\delta))/\varepsilon^2)) to budget data collection for desired accuracy/confidence.
Explaining behavior: a high-capacity neural net fitting random labels hints at very high VC; regularization (norm constraints, margins, early stopping) effectively lowers capacity.
Sanity checks: finite classes obey (d \le \lfloor \log_2 |\mathcal{H}| \rfloor). If someone claims tiny finite (|\mathcal{H}|) but massive VC, that’s inconsistent.
Example → In 2D, any three non-collinear points can be labeled in all 8 ways by some line (VC = 3); for four points, some labelings (like XOR on the corners of a square) are impossible for a single linear separator, so the class cannot shatter 4.

⚠️Common Mistakes

Hook → Many pitfalls come from over-interpreting what VC dimension does and doesn’t say.
Mistakes and fixes:

Equating VC dimension with parameter count. A model with many parameters can have low VC if constrained (e.g., linear separators with norm bound and margin). Conversely, simple-looking rules can have infinite VC (nearest neighbor). Always analyze the class, not the raw parameter count.
Thinking infinite VC means “cannot learn.” VC theory gives distribution-free uniform convergence; failing that doesn’t imply no generalization under additional structure (margins, smoothness, stability). Don’t overgeneralize.
Ignoring realizable vs. agnostic settings. Bounds differ: realizable case yields (\varepsilon^{-1}) dependence (up to logs), agnostic yields (\varepsilon^{-2}). Use the right formula.
Confusing “shatters a set” with “classifies this dataset perfectly.” Shattering demands realizability of all labelings of the same set, not just the current labeling.
Miscomputing shattering by testing too few labelings. To prove shattering, you must realize all 2^n labelings; to disprove, a single counter-labeling suffices.
Treating VC bounds as tight predictions. They are often loose but directionally informative. Use them for guarantees and planning, not as precise performance forecasts.
Forgetting distributional assumptions (i.i.d.). VC bounds typically assume i.i.d. sampling; adversarial or dependent data may violate guarantees.

Key Formulas

VC Dimension

d_{V C} (H) = sup {n \in N : \exists S \subset X, ∣ S ∣ = n, ∣ H ∣_{S} ∣ = 2^{n}}

Explanation: The VC dimension is the largest n for which some n-point set can be labeled in all possible ways by hypotheses in the class. If such sets exist for arbitrarily large n, the VC dimension is infinite.

Growth Function

m_{H} (n) = ∣ S ∣ = n max ∣ H ∣_{S} ∣

Explanation: This counts, in the worst case over all n-point sets, how many distinct labelings the class can realize. It governs the generalization bound via the union bound.

Sauer–Shelah Lemma

m_{H} (n) \leq i = 0 \sum d (i n) for d = d_{V C} (H)

Explanation: If the VC dimension is finite (d), then the number of achievable labelings grows at most polynomially in n. This prevents the exponential blow-up that would ruin uniform convergence.

VC Inequality (General Form)

P (h \in H sup ∣ R (h) - R (h) ∣ > ε) \leq 4 m_{H} (2 n) exp (- \frac{n ε ^{2}}{8})

Explanation: With n i.i.d. samples, the probability that empirical and true risks differ by more than ε for some h is bounded by a term depending on the growth function and an exponential decay in n.

VC Inequality (Using Sauer–Shelah)

P (h \in H sup ∣ R (h) - R (h) ∣ > ε) \leq 4 (\frac{2 e n}{d})^{d} exp (- \frac{n ε ^{2}}{8})

Explanation: Substituting the Sauer–Shelah bound for the growth function yields a bound in terms of the VC dimension d only. It provides a clean capacity–sample tradeoff.

Agnostic PAC Sample Complexity

n = O (\frac{d + lo g ( 1/ δ )}{ε ^{2}})

Explanation: To get true risk within ε of the best in the class with probability at least 1− $δ,$ it suffices to have number of samples on this order. The 1/ $ε^{2}$ dependence arises from concentration with noise.

Realizable PAC Sample Complexity

n = O (\frac{d lo g ( 1/ ε ) + lo g ( 1/ δ )}{ε})

Explanation: If the target labeling is realizable by the class, fewer samples are needed—scaling like 1/ε up to logarithmic factors—because empirical risk minimization achieves zero training error.

Example VC Dimension: Intervals

d_{V C} (intervals on R) = 2

Explanation: Two points can be labeled arbitrarily by selecting an interval; three points cannot realize the +−+ pattern with one interval, so the VC dimension is exactly 2.

Example VC Dimension: Linear Separators

d_{V C} (halfspaces in R^{d}) = d + 1

Explanation: Any set of d+1 points in general position can be shattered by a hyperplane; sets of size d+2 cannot all be shattered. This characterizes the capacity of linear classifiers.

Finite Class Bound

d_{V C} (H) \leq ⌊ lo g_{2} ∣ H ∣ ⌋ for finite H

Explanation: A finite class cannot realize more than |H| distinct labelings; since 2^d labelings are needed to shatter d points, the VC dimension is bounded by the base-2 logarithm of the class size.

Perceptron Convergence (Separable Case)

T \leq (\frac{R}{γ})^{2}

Explanation: For linearly separable data with margin γ and input norms bounded by R, the perceptron makes at most (R/ $γ)^{2}$ mistakes/updates. This provides a runtime proxy when testing separability in small examples.

Complexity Analysis

We provide three C++ programs illustrating shattering and sample complexity. 1) Intervals on the line: For a fixed set of n 1D points, we enumerate all 2^n labelings and check if each is realizable by a single interval. The realizability test is O(n): after sorting once, a labeling is realizable iff the positive labels form one contiguous block (or are empty/all). Thus the total time is O(n·2^n) and space is O(n). This exponential enumeration is inevitable for exact shattering verification on arbitrary classes and is acceptable for small n in demos. 2) Linear separators in

R^{2}

: For k points, we enumerate 2^k labelings and test linear separability with the perceptron. Each perceptron run over k points in

d = 2

dimensions takes O(T·k·d) where T is the number of updates until convergence (when separable). By the perceptron convergence theorem, T ≤ (R/

γ)^{2},

depending on data scale R and margin

γ .

Therefore, total time is O(2^k · k · d · T), which is practical only for small k (e.g.,

k \leq 12

). Space is O(k·d) for storing points and weights. Note: if a labeling is not separable, we detect non-convergence by a maximum-iterations cap; for small synthetic datasets this is reliable, but it is not a proof method. 3) VC sample complexity calculator: We need the smallest n satisfying 4(2 e n/d)^d exp(−n

ε^{2} /8)

≤

δ .

We compute this via monotone search: exponentially increase n (doubling) until the inequality holds, then binary search the interval. Each evaluation is O(1); the overall time is O(log n*) where n* is the minimal solution. Space is O(1). Across all programs, the bottleneck is the exponential number of labelings; this is intrinsic to brute-force shattering checks and highlights why theory uses combinatorial bounds instead of enumeration for large n.

Code Examples

Check if a 1D point set is shattered by intervals (VC = 2 demonstration)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Return true if a given labeling on sorted points is realizable by a single interval [L, R]
5 // A single interval realizes a labeling iff the positives form one contiguous block (possibly empty or all).
6 bool interval_realizable(const vector<int>& labels) {
7     int n = (int)labels.size();
8     int firstPos = -1, lastPos = -1;
9     for (int i = 0; i < n; ++i) if (labels[i] == 1) { firstPos = i; break; }
10     for (int i = n-1; i >= 0; --i) if (labels[i] == 1) { lastPos = i; break; }
11     if (firstPos == -1) return true; // no positives -> choose empty interval
12     // Check that all indices between firstPos and lastPos are positive
13     for (int i = firstPos; i <= lastPos; ++i) if (labels[i] != 1) return false;
14     return true;
15 }
16 
17 // Brute-force shattering test: are all 2^n labelings realizable by a single interval?
18 bool is_shattered_by_intervals(vector<double> x) {
19     sort(x.begin(), x.end()); // only order matters
20     int n = (int)x.size();
21     int total = 1 << n;
22     vector<int> labels(n);
23     for (int mask = 0; mask < total; ++mask) {
24         for (int i = 0; i < n; ++i) labels[i] = (mask >> i) & 1;
25         if (!interval_realizable(labels)) return false; // a single counterexample breaks shattering
26     }
27     return true;
28 }
29 
30 int main() {
31     // Example 1: n=2 (should be shattered)
32     vector<double> a = {0.0, 1.0};
33     cout << "Two points shattered by intervals? " << (is_shattered_by_intervals(a) ? "YES" : "NO") << "\n";
34 
35     // Example 2: n=3 (should NOT be shattered; the + - + labeling fails)
36     vector<double> b = {-1.0, 0.0, 2.0};
37     cout << "Three points shattered by intervals? " << (is_shattered_by_intervals(b) ? "YES" : "NO") << "\n";
38 
39     return 0;
40 }
41

An interval [L, R] on the real line labels points inside as positive and outside as negative. Such a classifier can realize a labeling iff the positive labels appear consecutively after sorting the points. We enumerate all 2^n labelings for small n and check this contiguity condition. The program confirms that any 2-point set is shattered, whereas 3-point sets are not.

Time: O(n · 2^n) for n points (labeling enumeration dominates)Space: O(n)

Test shattering by linear separators in R^2 via perceptron (VC = 3 demonstration)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct Perceptron {
5     vector<double> w; // weights including bias as last coordinate
6     double lr;
7     int max_iter;
8     Perceptron(int d, double lr_=1.0, int max_iter_=100000): w(d+1, 0.0), lr(lr_), max_iter(max_iter_) {}
9 
10     // Predict sign(w·x + b). Here x is augmented with 1 for bias.
11     int predict(const vector<double>& x_aug) const {
12         double s = 0.0;
13         for (int i = 0; i < (int)w.size(); ++i) s += w[i] * x_aug[i];
14         return s >= 0 ? +1 : -1;
15     }
16 
17     // Train on a separable dataset. Returns true if perfect classification achieved within max_iter.
18     bool train(const vector<vector<double>>& X, const vector<int>& y) {
19         // X must be augmented with 1 as last coordinate for bias.
20         int n = (int)X.size();
21         for (int it = 0; it < max_iter; ++it) {
22             bool any_mistake = false;
23             for (int i = 0; i < n; ++i) {
24                 int pred = predict(X[i]);
25                 if (pred != y[i]) {
26                     any_mistake = true;
27                     for (int j = 0; j < (int)w.size(); ++j) w[j] += lr * y[i] * X[i][j];
28                 }
29             }
30             if (!any_mistake) return true; // perfectly classified
31         }
32         return false; // likely not separable (or margin tiny)
33     }
34 };
35 
36 // Check if a given labeling of points is linearly separable via perceptron (in 2D).
37 bool labeling_separable_by_line(const vector<pair<double,double>>& pts, const vector<int>& labels01) {
38     int n = (int)pts.size();
39     vector<vector<double>> X(n, vector<double>(3)); // [x, y, 1]
40     vector<int> y(n);
41     for (int i = 0; i < n; ++i) {
42         X[i][0] = pts[i].first;
43         X[i][1] = pts[i].second;
44         X[i][2] = 1.0; // bias
45         y[i] = labels01[i] ? +1 : -1;
46     }
47     Perceptron p(2, 1.0, 100000);
48     return p.train(X, y);
49 }
50 
51 // Brute-force shattering test in 2D for lines.
52 bool is_shattered_by_lines(const vector<pair<double,double>>& pts) {
53     int n = (int)pts.size();
54     int total = 1 << n;
55     vector<int> labels(n);
56     for (int mask = 0; mask < total; ++mask) {
57         for (int i = 0; i < n; ++i) labels[i] = (mask >> i) & 1;
58         if (!labeling_separable_by_line(pts, labels)) return false;
59     }
60     return true;
61 }
62 
63 int main() {
64     // Three non-collinear points (should be shattered by lines in R^2)
65     vector<pair<double,double>> A = {{0,0}, {1,0}, {0,1}};
66     cout << "3 non-collinear points shattered by lines? " << (is_shattered_by_lines(A) ? "YES" : "NO") << "\n";
67 
68     // Four corners of a square (not all labelings are separable, e.g., XOR)
69     vector<pair<double,double>> B = {{-1,-1}, {-1,1}, {1,-1}, {1,1}};
70     cout << "4 square-corner points shattered by lines? " << (is_shattered_by_lines(B) ? "YES" : "NO") << "\n";
71 
72     return 0;
73 }
74

We enumerate all labelings of a small 2D point set and use the perceptron to test linear separability. For three non-collinear points, all 2^3 labelings are realizable by a line (shattered). For the four corners of a square, some labelings (e.g., XOR) are not separable, so shattering fails. The perceptron converges on separable labelings and typically fails to converge (within a cap) otherwise, which suffices for small educational examples.

Time: O(2^n · n · d · T) where d=2 and T is perceptron updates until convergenceSpace: O(n · d)

Compute minimal sample size from the VC generalization bound

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Evaluate the RHS of the VC inequality upper bound using Sauer–Shelah:
5 // P(sup |R - R_hat| > eps) <= 4 * ( (2 e n)/d )^d * exp( - n eps^2 / 8 )
6 // We return log of the RHS for numerical stability.
7 double log_vc_bound(int d, double eps, int n) {
8     if (d <= 0) {
9         // For d=0, m_H(2n)=1, so bound reduces to 4 * exp(- n eps^2 / 8)
10         return log(4.0) - (n * eps * eps) / 8.0;
11     }
12     const double e = std::exp(1.0);
13     double term1 = log(4.0);
14     double term2 = d * log((2.0 * e * n) / d);
15     double term3 = - (n * eps * eps) / 8.0;
16     return term1 + term2 + term3;
17 }
18 
19 // Find minimal n such that bound <= delta using doubling + binary search
20 int minimal_n_vc(int d, double eps, double delta) {
21     if (eps <= 0 || delta <= 0 || delta >= 1) throw runtime_error("Invalid eps/delta");
22     int n_low = 1, n_high = 1;
23     auto ok = [&](int n){ return log_vc_bound(d, eps, n) <= log(delta); };
24     // Increase n_high until the inequality holds
25     while (!ok(n_high)) {
26         n_low = n_high;
27         n_high *= 2;
28         if (n_high > 100000000) break; // safety cap
29     }
30     // Binary search between n_low+1 and n_high
31     while (n_low + 1 < n_high) {
32         int mid = n_low + (n_high - n_low) / 2;
33         if (ok(mid)) n_high = mid; else n_low = mid;
34     }
35     return n_high;
36 }
37 
38 int main() {
39     int d = 10;           // VC dimension
40     double eps = 0.05;    // desired accuracy
41     double delta = 0.05;  // confidence 1 - delta
42     int n = minimal_n_vc(d, eps, delta);
43     cout << "Minimal n satisfying VC bound: " << n << " (d=" << d << ", eps=" << eps << ", delta=" << delta << ")\n";
44     return 0;
45 }
46

This program inverts the VC inequality bound (with the Sauer–Shelah substitution) to find the smallest sample size n ensuring the generalization gap exceeds ε with probability at most δ. It uses logarithms to avoid numerical underflow and performs a doubling search followed by binary search to locate the minimal n efficiently.

Time: O(log n*) bound evaluations, each O(1)Space: O(1)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Return true if a given labeling on sorted points is realizable by a single interval [L, R]
5	// A single interval realizes a labeling iff the positives form one contiguous block (possibly empty or all).
6	bool interval_realizable(const vector<int>& labels) {
7	int n = (int)labels.size();
8	int firstPos = -1, lastPos = -1;
9	for (int i = 0; i < n; ++i) if (labels[i] == 1) { firstPos = i; break; }
10	for (int i = n-1; i >= 0; --i) if (labels[i] == 1) { lastPos = i; break; }
11	if (firstPos == -1) return true; // no positives -> choose empty interval
12	// Check that all indices between firstPos and lastPos are positive
13	for (int i = firstPos; i <= lastPos; ++i) if (labels[i] != 1) return false;
14	return true;
15	}
16
17	// Brute-force shattering test: are all 2^n labelings realizable by a single interval?
18	bool is_shattered_by_intervals(vector<double> x) {
19	sort(x.begin(), x.end()); // only order matters
20	int n = (int)x.size();
21	int total = 1 << n;
22	vector<int> labels(n);
23	for (int mask = 0; mask < total; ++mask) {
24	for (int i = 0; i < n; ++i) labels[i] = (mask >> i) & 1;
25	if (!interval_realizable(labels)) return false; // a single counterexample breaks shattering
26	}
27	return true;
28	}
29
30	int main() {
31	// Example 1: n=2 (should be shattered)
32	vector<double> a = {0.0, 1.0};
33	cout << "Two points shattered by intervals? " << (is_shattered_by_intervals(a) ? "YES" : "NO") << "\n";
34
35	// Example 2: n=3 (should NOT be shattered; the + - + labeling fails)
36	vector<double> b = {-1.0, 0.0, 2.0};
37	cout << "Three points shattered by intervals? " << (is_shattered_by_intervals(b) ? "YES" : "NO") << "\n";
38
39	return 0;
40	}
41

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct Perceptron {
5	vector<double> w; // weights including bias as last coordinate
6	double lr;
7	int max_iter;
8	Perceptron(int d, double lr_=1.0, int max_iter_=100000): w(d+1, 0.0), lr(lr_), max_iter(max_iter_) {}
9
10	// Predict sign(w·x + b). Here x is augmented with 1 for bias.
11	int predict(const vector<double>& x_aug) const {
12	double s = 0.0;
13	for (int i = 0; i < (int)w.size(); ++i) s += w[i] * x_aug[i];
14	return s >= 0 ? +1 : -1;
15	}
16
17	// Train on a separable dataset. Returns true if perfect classification achieved within max_iter.
18	bool train(const vector<vector<double>>& X, const vector<int>& y) {
19	// X must be augmented with 1 as last coordinate for bias.
20	int n = (int)X.size();
21	for (int it = 0; it < max_iter; ++it) {
22	bool any_mistake = false;
23	for (int i = 0; i < n; ++i) {
24	int pred = predict(X[i]);
25	if (pred != y[i]) {
26	any_mistake = true;
27	for (int j = 0; j < (int)w.size(); ++j) w[j] += lr * y[i] * X[i][j];
28	}
29	}
30	if (!any_mistake) return true; // perfectly classified
31	}
32	return false; // likely not separable (or margin tiny)
33	}
34	};
35
36	// Check if a given labeling of points is linearly separable via perceptron (in 2D).
37	bool labeling_separable_by_line(const vector<pair<double,double>>& pts, const vector<int>& labels01) {
38	int n = (int)pts.size();
39	vector<vector<double>> X(n, vector<double>(3)); // [x, y, 1]
40	vector<int> y(n);
41	for (int i = 0; i < n; ++i) {
42	X[i][0] = pts[i].first;
43	X[i][1] = pts[i].second;
44	X[i][2] = 1.0; // bias
45	y[i] = labels01[i] ? +1 : -1;
46	}
47	Perceptron p(2, 1.0, 100000);
48	return p.train(X, y);
49	}
50
51	// Brute-force shattering test in 2D for lines.
52	bool is_shattered_by_lines(const vector<pair<double,double>>& pts) {
53	int n = (int)pts.size();
54	int total = 1 << n;
55	vector<int> labels(n);
56	for (int mask = 0; mask < total; ++mask) {
57	for (int i = 0; i < n; ++i) labels[i] = (mask >> i) & 1;
58	if (!labeling_separable_by_line(pts, labels)) return false;
59	}
60	return true;
61	}
62
63	int main() {
64	// Three non-collinear points (should be shattered by lines in R^2)
65	vector<pair<double,double>> A = {{0,0}, {1,0}, {0,1}};
66	cout << "3 non-collinear points shattered by lines? " << (is_shattered_by_lines(A) ? "YES" : "NO") << "\n";
67
68	// Four corners of a square (not all labelings are separable, e.g., XOR)
69	vector<pair<double,double>> B = {{-1,-1}, {-1,1}, {1,-1}, {1,1}};
70	cout << "4 square-corner points shattered by lines? " << (is_shattered_by_lines(B) ? "YES" : "NO") << "\n";
71
72	return 0;
73	}
74

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Evaluate the RHS of the VC inequality upper bound using Sauer–Shelah:
5	// P(sup \|R - R_hat\| > eps) <= 4 * ( (2 e n)/d )^d * exp( - n eps^2 / 8 )
6	// We return log of the RHS for numerical stability.
7	double log_vc_bound(int d, double eps, int n) {
8	if (d <= 0) {
9	// For d=0, m_H(2n)=1, so bound reduces to 4 * exp(- n eps^2 / 8)
10	return log(4.0) - (n * eps * eps) / 8.0;
11	}
12	const double e = std::exp(1.0);
13	double term1 = log(4.0);
14	double term2 = d * log((2.0 * e * n) / d);
15	double term3 = - (n * eps * eps) / 8.0;
16	return term1 + term2 + term3;
17	}
18
19	// Find minimal n such that bound <= delta using doubling + binary search
20	int minimal_n_vc(int d, double eps, double delta) {
21	if (eps <= 0 \|\| delta <= 0 \|\| delta >= 1) throw runtime_error("Invalid eps/delta");
22	int n_low = 1, n_high = 1;
23	auto ok = [&](int n){ return log_vc_bound(d, eps, n) <= log(delta); };
24	// Increase n_high until the inequality holds
25	while (!ok(n_high)) {
26	n_low = n_high;
27	n_high *= 2;
28	if (n_high > 100000000) break; // safety cap
29	}
30	// Binary search between n_low+1 and n_high
31	while (n_low + 1 < n_high) {
32	int mid = n_low + (n_high - n_low) / 2;
33	if (ok(mid)) n_high = mid; else n_low = mid;
34	}
35	return n_high;
36	}
37
38	int main() {
39	int d = 10; // VC dimension
40	double eps = 0.05; // desired accuracy
41	double delta = 0.05; // confidence 1 - delta
42	int n = minimal_n_vc(d, eps, delta);
43	cout << "Minimal n satisfying VC bound: " << n << " (d=" << d << ", eps=" << eps << ", delta=" << delta << ")\n";
44	return 0;
45	}
46