📚TheoryAdvanced

Rademacher Complexity

Key Points

•
Rademacher complexity is a data-dependent measure of how well a function class can fit random noise on a given sample.
•
Empirical Rademacher complexity uses random ±1 signs on the training inputs and asks how large the average signed output can be when optimized over the class.
•
It yields tight, practical generalization bounds: true risk is at most empirical risk plus a term proportional to the complexity and a concentration term.
•
For linear predictors with bounded weights and bounded inputs, the complexity scales like B X / sqrt(n), shrinking with more data.
•
For deep networks with 1-Lipschitz activations, it is controlled by the product of spectral norms (and certain Frobenius terms) of the weight matrices.
•
Compared to VC dimension, Rademacher complexity is often much tighter in practice because it depends on the actual data distribution and sample.
•
You must compute the complexity of the loss-composed class when bounding generalization error, typically via a Lipschitz contraction.
•
Monte Carlo with Rademacher signs gives practical estimators of empirical complexity for many classes, and is easy to implement.

Prerequisites

→Probability basics — Understanding expectations, independence, and concentration is necessary for interpreting Rademacher averages.
→Norms and vector geometry — Bounds for linear models and neural networks rely on L2 norms, spectral norms, and Frobenius norms.
→Statistical learning theory basics — Concepts like empirical risk, true risk, and uniform convergence underpin generalization bounds.
→Convex Lipschitz losses — Using contraction to move from function classes to loss-composed classes requires Lipschitz properties.
→Linear algebra (SVD, eigenvectors) — Spectral and Frobenius norms and power iteration appear in neural-network bounds.

Detailed Explanation

Tap terms for definitions

01Overview

Rademacher complexity is a modern tool in learning theory that quantifies how expressive a hypothesis (function) class is on a specific dataset. Instead of asking for a worst-case, distribution-free capacity (as VC dimension does), it measures how well the class can correlate with pure noise placed on the observed inputs. It does so using Rademacher variables—independent random signs in {−1, +1}. If a class can reliably match many different random sign patterns, it is considered rich and thus prone to overfitting; if it cannot, it has limited capacity and generalizes better. Two related notions exist: empirical Rademacher complexity, computed on a fixed sample, and expected Rademacher complexity, averaging over the data distribution. Both lead to clean generalization bounds that add a data-dependent complexity term to the empirical risk. The quantity scales down like 1/√n with more data, and depends on geometric properties of the class, such as norms of parameters and inputs for linear models or layer norms for neural networks. These properties make Rademacher complexity especially valuable for understanding modern models where VC dimension is either infinite or overly pessimistic.

02Intuition & Analogies

Imagine handing your model a dataset where the inputs are real but the labels are replaced by coin flips. If your model can still fit those random labels very well, it is probably very flexible—perhaps too flexible—because it can chase noise. Rademacher complexity captures exactly this idea by flipping random signs for each training input and asking: how large can the model’s average signed output be, if we choose the best model in the class after seeing the signs? If the answer is often large, your class can mimic many random sign patterns; if it is small, the class is stiff and can’t easily align with noise. Think of it like a radio tuner: a very sensitive tuner (high complexity) picks up lots of stations—including static—so it’s easy to hear something that seems like a song even when it’s just noise. A less sensitive tuner (low complexity) only locks onto strong, real stations. With more data points, the noise tends to cancel out, so even a flexible class has a harder time aligning with the random signs; that’s why Rademacher complexity typically shrinks like 1/√n. For linear models, this alignment boils down to how big your weight vector can be and how large the inputs are: bounded weights and inputs limit how much correlation with random signs is possible. For deep networks, each layer can amplify signals; the product of layer gains (spectral norms) controls how much noise alignment can grow as it propagates through the network.

03Formal Definition

Let S = (

x_{1}

\dots

x_{n}

) be a sample of size n from an input space

X

, and let

F

be a class of real-valued functions on

X

. Let

σ_{1}

\dots

σ_{n}

be i.i.d. Rademacher variables taking values in \{ -1, +1 \} uniformly. The empirical Rademacher complexity of

F

on S is \[

\hat{R}_{S}

(

F

) =

E_{σ}

\left

[

sup_{f \in F}

\frac{1}{n}

\sum_{i = 1}^{n}

σ_{i}

x_{i}

)

\right

]. \] The (distribution-dependent) expected Rademacher complexity is \[

R_{n}

(

F

) =

\mathbb{E}_{S \sim \mathcal{D}^{n}}\left

[

\hat{R}_{S}

(

F

)

\right

], \] where

D

is the data distribution. For a loss function

ℓ

R

\times

Y

\to

R

(often bounded and L-Lipschitz in its first argument), generalization bounds typically involve the complexity of the loss-composed class

ℓ

\circ

F

= \{ x

\mapsto

ℓ

(f(x), y) : f

\in

F

\}. A standard bound (for bounded losses and using symmetrization and concentration) states that with probability at least 1 -

δ

over the draw of S, for all f

\in

F

, \[ R(f)

\leq

\hat{R}

(f) + 2\,

R_{n}

(

ℓ

\circ

F

) +

\frac{l o g ( 1/ δ )}{2 n}

, \] where R(f) is the true (population) risk and

\hat{R}

(f) is the empirical risk.

04When to Use

Use Rademacher complexity when you want a data-dependent and often tighter generalization analysis than VC dimension. It is particularly helpful when: (1) the hypothesis class has infinite or impractically large VC dimension (e.g., many neural networks), (2) you can bound model norms (e.g., weights) and input norms, allowing sharp capacity control, (3) you care about how the observed sample geometry affects learnability (e.g., clustered vs. diverse inputs), and (4) you want practical, computable surrogates via Monte Carlo for model selection or early stopping. Concrete applications include: deriving risk bounds for linear predictors with norm constraints; comparing different regularization strengths (smaller norms yield smaller complexity); analyzing margin-based methods (via Lipschitz losses like hinge or logistic); estimating capacity of ensembles or finite hypothesis sets (using Massart’s lemma); and bounding deep network capacity using products of spectral norms per layer, potentially guiding architecture or regularization choices.

⚠️Common Mistakes

Common pitfalls include: (1) Forgetting to analyze the loss-composed class: generalization bounds typically require \mathfrak{R}(\ell \circ \mathcal{F}), not \mathfrak{R}(\mathcal{F}) directly. Use the contraction lemma for L-Lipschitz losses. (2) Ignoring boundedness assumptions: many proofs require outputs or losses bounded in [0,1] or [-1,1]; rescale if needed. (3) Mixing empirical and expected complexities: \hat{\mathfrak{R}}{S} is sample-specific, whereas \mathfrak{R}{n} averages over S; using the wrong one in a bound changes constants and interpretation. (4) Mis-scaling by n: the definition includes the 1/n factor; omitting it leads to incorrect rates. (5) Using a single draw of Rademacher signs: Monte Carlo estimators need multiple trials to reduce variance; otherwise estimates can be noisy. (6) Overlooking data geometry: for linear classes the bound depends on |x_{i}|, not just dimension; large outliers can inflate complexity. (7) Applying deep-network bounds blindly: spectral-norm-based bounds are upper bounds and can be loose; computing spectral norms must be done carefully (e.g., via power iteration), and activations should be 1-Lipschitz to apply standard results. (8) Double-dipping by tuning models on the same sample used to claim a bound without accounting for selection: bounds are uniform over the class, but if you iterate data-dependent choices of the class itself, care is needed.

Key Formulas

Empirical Rademacher Complexity

\hat{R}_{S} (F) = E_{σ} [f \in F sup \frac{1}{n} i = 1 \sum n σ_{i} f (x_{i})]

Explanation: Takes a fixed sample and measures how well the class can align with random ±1 signs on those inputs. Higher values mean the class can fit noise more easily.

Expected Rademacher Complexity

R_{n} (F) = E_{S \sim D^{n}} [\hat{R}_{S} (F)]

Explanation: Averages the empirical complexity over the random draw of the dataset. Used in distribution-dependent bounds.

Generalization Bound (bounded loss)

R (f) \leq \hat{R} (f) + 2 R_{n} (ℓ \circ F) + \frac{lo g ( 1/ δ )}{2 n}

Explanation: With probability at least 1− $δ,$ the true risk of any f is at most its empirical risk plus twice the complexity of the loss-composed class and a concentration term shrinking like 1/ $n$ .

Contraction Lemma

\hat{R}_{S} (ϕ \circ F) \leq L \hat{R}_{S} (F)

Explanation: If φ is L-Lipschitz (and typically $φ (0) = 0),$ composing the class with φ scales the complexity by at most L. This lets you move from functions to their losses.

Linear Class Bound

\hat{R}_{S} (F_{lin}) = \frac{B}{n} E_{σ} i = 1 \sum n σ_{i} x_{i}_{2} \leq \frac{B}{n} i = 1 \sum n ∥ x_{i} ∥_{2}^{2} \leq \frac{BX}{n}

Explanation: For linear predictors with \ $∣ w ∥$ _2 $\leq$ B and inputs bounded by \ $∣ x_{i} ∥$ _2 $\leq$ X, the empirical complexity is at most B X / √n. More data or smaller norms reduce capacity.

Massart's Lemma (finite classes, bounded outputs)

\hat{R}_{S} (F) \leq \frac{2 lo g ∣ F ∣}{n}

Explanation: If each function outputs values in [−1,1] on the sample and the class is finite, the complexity depends only on the log of its size and decreases with 1/√n.

Relation to VC Dimension

R_{n} (F) \leq C \frac{VC ( F )}{n}

Explanation: For binary classes with finite VC dimension, Rademacher complexity is upper-bounded by a constant times √ $\frac{V C}{n}$ , linking classical and modern capacity measures.

Deep Network Bound (1-Lipschitz activations)

R_{n} (F_{NN}) ≲ \frac{c X}{n} (ℓ = 1 \prod L ∥ W_{ℓ} ∥_{2}) (ℓ = 1 \sum L \frac{∥ W _{ℓ} ∥ _{F}^{2}}{∥ W _{ℓ} ∥ _{2}^{2}})^{1/2}

Explanation: For networks with 1-Lipschitz activations (e.g., ReLU) and inputs of norm at most X, complexity grows with the product of spectral norms and a Frobenius-term factor, and decays as 1/√n.

Finite Class Supremum

E_{σ} j \in [M] max \frac{1}{n} i = 1 \sum n σ_{i} f_{j} (x_{i})

Explanation: For a finite set of functions { $f_{j}$ }, the supremum reduces to a maximum over j. This is convenient for direct computation or Monte Carlo estimation.

Complexity Analysis

Estimating empirical Rademacher complexity via Monte Carlo requires repeatedly sampling Rademacher sign vectors and computing the supremum over the class. For linear classes with an L2-norm constraint \

∣ w ∥

\leq

B, the supremum against a fixed sign vector has a closed form:

\frac{B}{n}

\,\

∣ \sum_{i} σ_{i} x_{i} ∥

_2. Computing this vector sum costs O(n d) where d is the input dimension; taking its Euclidean norm is O(d). Repeating over T Monte Carlo trials yields O(T n d) time and O(d) memory, dominated by accumulating the d-dimensional sum. For finite hypothesis classes of size M with precomputed predictions on the sample, computing the supremum reduces to taking a maximum over M inner sums per trial. Each inner sum over n points is O(n), so a naive approach is O(T M n) time with O(M) memory for the per-function accumulators (or O(1) extra memory if recomputed on the fly). If predictions are stored in an M×n matrix, random-access improves constants but not asymptotics. For deep networks, practical computation of spectral norms for weight matrices of sizes p×q via power iteration costs O(K p q) per matrix for K iterations; across L layers, this is O(L K p q) time, and memory is O(p q) for each matrix. The resulting bound is an upper bound, not a Monte Carlo estimate. In all cases, the Monte Carlo variance decreases like 1/T, so doubling trials reduces standard error by about 1/√2. The overall sample-size dependence of the theoretical bounds is typically O(1/

n

), reflecting that capacity shrinks as data grows.

Code Examples

Monte Carlo estimate of empirical Rademacher complexity for an L2-bounded linear class

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute Monte Carlo estimate of empirical Rademacher complexity for
5 // F = { x -> w^T x : ||w||_2 <= B }. Closed-form supremum for a fixed sigma:
6 //   sup_{||w||<=B} (1/n) sum_i sigma_i w^T x_i = (B/n) || sum_i sigma_i x_i ||_2.
7 
8 static mt19937_64 rng(1234567);
9 
10 vector<vector<double>> make_synthetic_data(size_t n, size_t d, double Xmax) {
11     uniform_real_distribution<double> dist(-Xmax, Xmax);
12     vector<vector<double>> X(n, vector<double>(d));
13     for (size_t i = 0; i < n; ++i) {
14         for (size_t j = 0; j < d; ++j) X[i][j] = dist(rng);
15     }
16     return X;
17 }
18 
19 // One Monte Carlo trial: draw sigma in {−1,+1}^n, compute (B/n)||sum sigma_i x_i||.
20 double one_trial_linear_RC(const vector<vector<double>>& X, double B) {
21     size_t n = X.size();
22     size_t d = X[0].size();
23     bernoulli_distribution coin(0.5);
24     vector<double> acc(d, 0.0);
25     for (size_t i = 0; i < n; ++i) {
26         double si = coin(rng) ? 1.0 : -1.0; // Rademacher sign
27         for (size_t j = 0; j < d; ++j) acc[j] += si * X[i][j];
28     }
29     double norm2 = 0.0;
30     for (size_t j = 0; j < d; ++j) norm2 += acc[j] * acc[j];
31     double acc_norm = sqrt(norm2);
32     return (B / static_cast<double>(n)) * acc_norm;
33 }
34 
35 // Estimate empirical RC by averaging T trials.
36 double estimate_linear_RC(const vector<vector<double>>& X, double B, int T) {
37     double sum = 0.0;
38     for (int t = 0; t < T; ++t) sum += one_trial_linear_RC(X, B);
39     return sum / static_cast<double>(T);
40 }
41 
42 int main() {
43     ios::sync_with_stdio(false);
44     cin.tie(nullptr);
45 
46     size_t n = 1000;   // samples
47     size_t d = 50;     // dimension
48     double B = 5.0;    // weight L2 bound
49     double Xmax = 1.0; // each coordinate in [-Xmax, Xmax]
50     int T = 200;       // Monte Carlo trials
51 
52     auto X = make_synthetic_data(n, d, Xmax);
53     double rc_hat = estimate_linear_RC(X, B, T);
54 
55     // Theoretical upper bound using max norm per sample: BX / sqrt(n),
56     // where X is an upper bound on ||x_i||_2. We estimate X by observed max.
57     double Xbound = 0.0;
58     for (const auto& xi : X) {
59         double n2 = 0.0; for (double v : xi) n2 += v*v;
60         Xbound = max(Xbound, sqrt(n2));
61     }
62     double theory = B * Xbound / sqrt(static_cast<double>(n));
63 
64     cout << fixed << setprecision(6);
65     cout << "Estimated empirical RC (linear class): " << rc_hat << "\n";
66     cout << "Simple theoretical bound B*X/sqrt(n): " << theory << "\n";
67     return 0;
68 }
69

Uses the closed-form supremum for L2-bounded linear predictors to estimate empirical Rademacher complexity via Monte Carlo. It also prints a simple upper bound B X / sqrt(n) based on the maximum observed input norm.

Time: O(T n d) for T trials on n samples in d dimensionsSpace: O(d) additional memory besides the dataset

Empirical Rademacher complexity for a finite hypothesis class (precomputed predictions)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // We have M hypotheses f_j, j=1..M, each producing a prediction vector on the sample:
5 // P[j][i] = f_j(x_i) with values in [-1, 1]. For each Rademacher draw sigma, the supremum
6 // over the finite class is max_j (1/n) sum_i sigma_i * P[j][i]. We average over T trials.
7 
8 static mt19937_64 rng2(42);
9 
10 // Create a synthetic predictions matrix with mild correlation.
11 vector<vector<double>> make_predictions(size_t M, size_t n) {
12     normal_distribution<double> base(0.0, 0.5);
13     vector<vector<double>> P(M, vector<double>(n));
14     for (size_t j = 0; j < M; ++j) {
15         double bias = tanh((static_cast<double>(j) - (double)M/2) / (0.2*M));
16         for (size_t i = 0; i < n; ++i) {
17             double v = bias + base(rng2);
18             // clamp to [-1,1]
19             P[j][i] = max(-1.0, min(1.0, v));
20         }
21     }
22     return P;
23 }
24 
25 double estimate_finite_RC(const vector<vector<double>>& P, int T) {
26     size_t M = P.size();
27     size_t n = P[0].size();
28     bernoulli_distribution coin(0.5);
29     double total = 0.0;
30     vector<double> s(n);
31     for (int t = 0; t < T; ++t) {
32         for (size_t i = 0; i < n; ++i) s[i] = coin(rng2) ? 1.0 : -1.0;
33         double best = -1e100;
34         for (size_t j = 0; j < M; ++j) {
35             double sum = 0.0;
36             for (size_t i = 0; i < n; ++i) sum += s[i] * P[j][i];
37             best = max(best, sum / static_cast<double>(n));
38         }
39         total += best;
40     }
41     return total / static_cast<double>(T);
42 }
43 
44 int main() {
45     ios::sync_with_stdio(false);
46     cin.tie(nullptr);
47 
48     size_t n = 500;  // samples
49     size_t M = 100;  // number of hypotheses
50     int T = 300;     // Monte Carlo trials
51     auto P = make_predictions(M, n);
52 
53     double rc_hat = estimate_finite_RC(P, T);
54 
55     // Massart's lemma bound (outputs in [-1,1]): sqrt(2 log M / n)
56     double massart = sqrt(2.0 * log((double)M) / (double)n);
57 
58     cout << fixed << setprecision(6);
59     cout << "Estimated empirical RC (finite class): " << rc_hat << "\n";
60     cout << "Massart's lemma upper bound:            " << massart << "\n";
61 
62     // Example: If empirical 0-1 risk is R_hat, a typical bound is
63     // R <= R_hat + 2 * RC_loss + sqrt(log(1/delta)/(2n)). For demonstration, set R_hat=0.1, delta=0.05.
64     double R_hat = 0.10;
65     double delta = 0.05;
66     // Using RC of the function class as proxy; for bounded 1-Lipschitz surrogate losses, use contraction.
67     double gen_bound = R_hat + 2.0 * rc_hat + sqrt(log(1.0/delta) / (2.0 * n));
68     cout << "Illustrative generalization bound (proxy): " << gen_bound << "\n";
69 
70     return 0;
71 }
72

Treats a finite hypothesis class by precomputing predictions on the sample. For each random sign vector, the supremum is a maximum over M functions. It reports the Monte Carlo estimate and compares it with Massart’s bound √(2 log M / n). It also shows a plug-in generalization bound for illustration.

Time: O(T M n) for T trials, M hypotheses, n samplesSpace: O(M n) to store predictions (or O(1) extra if streamed)

Computing a deep-network Rademacher complexity upper bound via spectral norms

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // This program demonstrates computing an upper bound of the form
5 //   RC <= (c * X / sqrt(n)) * (prod_l ||W_l||_2) * sqrt( sum_l ||W_l||_F^2 / ||W_l||_2^2 )
6 // for networks with 1-Lipschitz activations (e.g., ReLU), following Bartlett et al.-style bounds.
7 // We implement power iteration to estimate spectral norms, and compute Frobenius norms exactly.
8 
9 static mt19937_64 rng3(7);
10 
11 double spectral_norm_power_iteration(const vector<vector<double>>& W, int iters = 50) {
12     size_t r = W.size();
13     size_t c = W[0].size();
14     vector<double> v(c), u(r);
15     normal_distribution<double> nd(0.0, 1.0);
16     for (size_t j = 0; j < c; ++j) v[j] = nd(rng3);
17     auto normalize = [](vector<double>& a){ double s=0; for(double x:a) s+=x*x; s=sqrt(s); if(s>0) for(double& x:a) x/=s; };
18     normalize(v);
19     for (int t = 0; t < iters; ++t) {
20         // u = W v
21         fill(u.begin(), u.end(), 0.0);
22         for (size_t i = 0; i < r; ++i)
23             for (size_t j = 0; j < c; ++j)
24                 u[i] += W[i][j] * v[j];
25         normalize(u);
26         // v = W^T u
27         fill(v.begin(), v.end(), 0.0);
28         for (size_t j = 0; j < c; ++j)
29             for (size_t i = 0; i < r; ++i)
30                 v[j] += W[i][j] * u[i];
31         normalize(v);
32     }
33     // Rayleigh quotient approximation: ||W v||_2
34     vector<double> Wv(r, 0.0);
35     for (size_t i = 0; i < r; ++i)
36         for (size_t j = 0; j < c; ++j)
37             Wv[i] += W[i][j] * v[j];
38     double norm = 0.0; for (double x : Wv) norm += x*x; return sqrt(norm);
39 }
40 
41 double frobenius_norm(const vector<vector<double>>& W) {
42     double s = 0.0; for (auto& row : W) for (double w : row) s += w*w; return sqrt(s);
43 }
44 
45 int main(){
46     ios::sync_with_stdio(false);
47     cin.tie(nullptr);
48 
49     // Create a simple 3-layer MLP weight set: dimensions 20->50->30->10
50     auto makeW = [](size_t r, size_t c){
51         normal_distribution<double> nd(0.0, 0.1);
52         vector<vector<double>> W(r, vector<double>(c));
53         for(size_t i=0;i<r;++i) for(size_t j=0;j<c;++j) W[i][j]=nd(rng3);
54         return W;
55     };
56     vector<vector<vector<double>>> weights;
57     weights.push_back(makeW(50, 20));
58     weights.push_back(makeW(30, 50));
59     weights.push_back(makeW(10, 30));
60 
61     // Suppose inputs satisfy ||x||_2 <= X.
62     double X = 1.0; // radius bound on inputs
63     size_t n = 1000; // sample size
64 
65     double prod_spec = 1.0;
66     double sum_ratio = 0.0;
67     cout << fixed << setprecision(6);
68     for (size_t l = 0; l < weights.size(); ++l) {
69         double s = spectral_norm_power_iteration(weights[l], 80);
70         double F = frobenius_norm(weights[l]);
71         prod_spec *= s;
72         sum_ratio += (F*F) / (s*s + 1e-12);
73         cout << "Layer " << l+1 << ": spectral= " << s << ", Frobenius= " << F << "\n";
74     }
75 
76     double c = 2.0; // a loose constant for illustration
77     double rc_bound = (c * X / sqrt((double)n)) * prod_spec * sqrt(max(0.0, sum_ratio));
78     cout << "RC upper bound (illustrative): " << rc_bound << "\n";
79     return 0;
80 }
81

Estimates spectral norms via power iteration and computes an illustrative deep-network Rademacher complexity upper bound for 1-Lipschitz activations. This is a theoretical upper bound, not an empirical estimate, and constants are simplified for clarity.

Time: O(L K r c) to estimate spectral norms with K iterations for each L layer of size r×cSpace: O(rc) per layer to store the weight matrix

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute Monte Carlo estimate of empirical Rademacher complexity for
5	// F = { x -> w^T x : \|\|w\|\|_2 <= B }. Closed-form supremum for a fixed sigma:
6	// sup_{\|\|w\|\|<=B} (1/n) sum_i sigma_i w^T x_i = (B/n) \|\| sum_i sigma_i x_i \|\|_2.
7
8	static mt19937_64 rng(1234567);
9
10	vector<vector<double>> make_synthetic_data(size_t n, size_t d, double Xmax) {
11	uniform_real_distribution<double> dist(-Xmax, Xmax);
12	vector<vector<double>> X(n, vector<double>(d));
13	for (size_t i = 0; i < n; ++i) {
14	for (size_t j = 0; j < d; ++j) X[i][j] = dist(rng);
15	}
16	return X;
17	}
18
19	// One Monte Carlo trial: draw sigma in {−1,+1}^n, compute (B/n)\|\|sum sigma_i x_i\|\|.
20	double one_trial_linear_RC(const vector<vector<double>>& X, double B) {
21	size_t n = X.size();
22	size_t d = X[0].size();
23	bernoulli_distribution coin(0.5);
24	vector<double> acc(d, 0.0);
25	for (size_t i = 0; i < n; ++i) {
26	double si = coin(rng) ? 1.0 : -1.0; // Rademacher sign
27	for (size_t j = 0; j < d; ++j) acc[j] += si * X[i][j];
28	}
29	double norm2 = 0.0;
30	for (size_t j = 0; j < d; ++j) norm2 += acc[j] * acc[j];
31	double acc_norm = sqrt(norm2);
32	return (B / static_cast<double>(n)) * acc_norm;
33	}
34
35	// Estimate empirical RC by averaging T trials.
36	double estimate_linear_RC(const vector<vector<double>>& X, double B, int T) {
37	double sum = 0.0;
38	for (int t = 0; t < T; ++t) sum += one_trial_linear_RC(X, B);
39	return sum / static_cast<double>(T);
40	}
41
42	int main() {
43	ios::sync_with_stdio(false);
44	cin.tie(nullptr);
45
46	size_t n = 1000; // samples
47	size_t d = 50; // dimension
48	double B = 5.0; // weight L2 bound
49	double Xmax = 1.0; // each coordinate in [-Xmax, Xmax]
50	int T = 200; // Monte Carlo trials
51
52	auto X = make_synthetic_data(n, d, Xmax);
53	double rc_hat = estimate_linear_RC(X, B, T);
54
55	// Theoretical upper bound using max norm per sample: BX / sqrt(n),
56	// where X is an upper bound on \|\|x_i\|\|_2. We estimate X by observed max.
57	double Xbound = 0.0;
58	for (const auto& xi : X) {
59	double n2 = 0.0; for (double v : xi) n2 += v*v;
60	Xbound = max(Xbound, sqrt(n2));
61	}
62	double theory = B * Xbound / sqrt(static_cast<double>(n));
63
64	cout << fixed << setprecision(6);
65	cout << "Estimated empirical RC (linear class): " << rc_hat << "\n";
66	cout << "Simple theoretical bound B*X/sqrt(n): " << theory << "\n";
67	return 0;
68	}
69

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// We have M hypotheses f_j, j=1..M, each producing a prediction vector on the sample:
5	// P[j][i] = f_j(x_i) with values in [-1, 1]. For each Rademacher draw sigma, the supremum
6	// over the finite class is max_j (1/n) sum_i sigma_i * P[j][i]. We average over T trials.
7
8	static mt19937_64 rng2(42);
9
10	// Create a synthetic predictions matrix with mild correlation.
11	vector<vector<double>> make_predictions(size_t M, size_t n) {
12	normal_distribution<double> base(0.0, 0.5);
13	vector<vector<double>> P(M, vector<double>(n));
14	for (size_t j = 0; j < M; ++j) {
15	double bias = tanh((static_cast<double>(j) - (double)M/2) / (0.2*M));
16	for (size_t i = 0; i < n; ++i) {
17	double v = bias + base(rng2);
18	// clamp to [-1,1]
19	P[j][i] = max(-1.0, min(1.0, v));
20	}
21	}
22	return P;
23	}
24
25	double estimate_finite_RC(const vector<vector<double>>& P, int T) {
26	size_t M = P.size();
27	size_t n = P[0].size();
28	bernoulli_distribution coin(0.5);
29	double total = 0.0;
30	vector<double> s(n);
31	for (int t = 0; t < T; ++t) {
32	for (size_t i = 0; i < n; ++i) s[i] = coin(rng2) ? 1.0 : -1.0;
33	double best = -1e100;
34	for (size_t j = 0; j < M; ++j) {
35	double sum = 0.0;
36	for (size_t i = 0; i < n; ++i) sum += s[i] * P[j][i];
37	best = max(best, sum / static_cast<double>(n));
38	}
39	total += best;
40	}
41	return total / static_cast<double>(T);
42	}
43
44	int main() {
45	ios::sync_with_stdio(false);
46	cin.tie(nullptr);
47
48	size_t n = 500; // samples
49	size_t M = 100; // number of hypotheses
50	int T = 300; // Monte Carlo trials
51	auto P = make_predictions(M, n);
52
53	double rc_hat = estimate_finite_RC(P, T);
54
55	// Massart's lemma bound (outputs in [-1,1]): sqrt(2 log M / n)
56	double massart = sqrt(2.0 * log((double)M) / (double)n);
57
58	cout << fixed << setprecision(6);
59	cout << "Estimated empirical RC (finite class): " << rc_hat << "\n";
60	cout << "Massart's lemma upper bound: " << massart << "\n";
61
62	// Example: If empirical 0-1 risk is R_hat, a typical bound is
63	// R <= R_hat + 2 * RC_loss + sqrt(log(1/delta)/(2n)). For demonstration, set R_hat=0.1, delta=0.05.
64	double R_hat = 0.10;
65	double delta = 0.05;
66	// Using RC of the function class as proxy; for bounded 1-Lipschitz surrogate losses, use contraction.
67	double gen_bound = R_hat + 2.0 * rc_hat + sqrt(log(1.0/delta) / (2.0 * n));
68	cout << "Illustrative generalization bound (proxy): " << gen_bound << "\n";
69
70	return 0;
71	}
72

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// This program demonstrates computing an upper bound of the form
5	// RC <= (c * X / sqrt(n)) * (prod_l \|\|W_l\|\|_2) * sqrt( sum_l \|\|W_l\|\|_F^2 / \|\|W_l\|\|_2^2 )
6	// for networks with 1-Lipschitz activations (e.g., ReLU), following Bartlett et al.-style bounds.
7	// We implement power iteration to estimate spectral norms, and compute Frobenius norms exactly.
8
9	static mt19937_64 rng3(7);
10
11	double spectral_norm_power_iteration(const vector<vector<double>>& W, int iters = 50) {
12	size_t r = W.size();
13	size_t c = W[0].size();
14	vector<double> v(c), u(r);
15	normal_distribution<double> nd(0.0, 1.0);
16	for (size_t j = 0; j < c; ++j) v[j] = nd(rng3);
17	auto normalize = [](vector<double>& a){ double s=0; for(double x:a) s+=x*x; s=sqrt(s); if(s>0) for(double& x:a) x/=s; };
18	normalize(v);
19	for (int t = 0; t < iters; ++t) {
20	// u = W v
21	fill(u.begin(), u.end(), 0.0);
22	for (size_t i = 0; i < r; ++i)
23	for (size_t j = 0; j < c; ++j)
24	u[i] += W[i][j] * v[j];
25	normalize(u);
26	// v = W^T u
27	fill(v.begin(), v.end(), 0.0);
28	for (size_t j = 0; j < c; ++j)
29	for (size_t i = 0; i < r; ++i)
30	v[j] += W[i][j] * u[i];
31	normalize(v);
32	}
33	// Rayleigh quotient approximation: \|\|W v\|\|_2
34	vector<double> Wv(r, 0.0);
35	for (size_t i = 0; i < r; ++i)
36	for (size_t j = 0; j < c; ++j)
37	Wv[i] += W[i][j] * v[j];
38	double norm = 0.0; for (double x : Wv) norm += x*x; return sqrt(norm);
39	}
40
41	double frobenius_norm(const vector<vector<double>>& W) {
42	double s = 0.0; for (auto& row : W) for (double w : row) s += w*w; return sqrt(s);
43	}
44
45	int main(){
46	ios::sync_with_stdio(false);
47	cin.tie(nullptr);
48
49	// Create a simple 3-layer MLP weight set: dimensions 20->50->30->10
50	auto makeW = [](size_t r, size_t c){
51	normal_distribution<double> nd(0.0, 0.1);
52	vector<vector<double>> W(r, vector<double>(c));
53	for(size_t i=0;i<r;++i) for(size_t j=0;j<c;++j) W[i][j]=nd(rng3);
54	return W;
55	};
56	vector<vector<vector<double>>> weights;
57	weights.push_back(makeW(50, 20));
58	weights.push_back(makeW(30, 50));
59	weights.push_back(makeW(10, 30));
60
61	// Suppose inputs satisfy \|\|x\|\|_2 <= X.
62	double X = 1.0; // radius bound on inputs
63	size_t n = 1000; // sample size
64
65	double prod_spec = 1.0;
66	double sum_ratio = 0.0;
67	cout << fixed << setprecision(6);
68	for (size_t l = 0; l < weights.size(); ++l) {
69	double s = spectral_norm_power_iteration(weights[l], 80);
70	double F = frobenius_norm(weights[l]);
71	prod_spec *= s;
72	sum_ratio += (FF) / (ss + 1e-12);
73	cout << "Layer " << l+1 << ": spectral= " << s << ", Frobenius= " << F << "\n";
74	}
75
76	double c = 2.0; // a loose constant for illustration
77	double rc_bound = (c * X / sqrt((double)n)) * prod_spec * sqrt(max(0.0, sum_ratio));
78	cout << "RC upper bound (illustrative): " << rc_bound << "\n";
79	return 0;
80	}
81