Generalization Bounds for Deep Learning

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes empirical risk (average bounded loss in [0,1])
5
// and applies Hoeffding's inequality to bound population risk.
6
// Build: g++ -O2 -std=c++17 hoeffding_bound.cpp -o hoeffding_bound
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    // Example input: n losses in [0,1]
12
    // You can replace this with reading from stdin or a file.
13
    vector<double> losses = {0, 0, 1, 0, 0, 0, 0, 1}; // toy example
14
    const int n = (int)losses.size();
15
    double delta = 0.05; // 95% confidence
16
17
    if (n == 0) {
18
        cerr << "No data provided.\n";
19
        return 1;
20
    }
21
22
    // Compute empirical risk \hat{R}
23
    double sum = 0.0;
24
    for (double l : losses) {
25
        // Ensure boundedness (defensive programming)
26
        l = max(0.0, min(1.0, l));
27
        sum += l;
28
    }
29
    double R_emp = sum / n;
30
31
    // Hoeffding's inequality: R <= R_emp + sqrt( ln(2/delta) / (2n) )
32
    double gap = sqrt(log(2.0 / delta) / (2.0 * n));
33
    double R_bound = min(1.0, R_emp + gap);
34
35
    cout << fixed << setprecision(6);
36
    cout << "n = " << n << "\n";
37
    cout << "delta = " << delta << "\n";
38
    cout << "Empirical risk = " << R_emp << "\n";
39
    cout << "Gap (Hoeffding) = " << gap << "\n";
40
    cout << "Population risk bound <= " << R_bound << "\n";
41
42
    return 0;
43
}
44

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Utility: KL divergence between diagonal Gaussians Q = N(mu1, sigma1^2), P = N(mu0, sigma0^2)
5
double kl_diag_gaussians(const vector<double>& mu1, const vector<double>& s1,
6
                         const vector<double>& mu0, const vector<double>& s0) {
7
    size_t d = mu1.size();
8
    assert(mu0.size() == d && s1.size() == d && s0.size() == d);
9
    double kl = 0.0;
10
    for (size_t j = 0; j < d; ++j) {
11
        double v1 = s1[j] * s1[j];
12
        double v0 = s0[j] * s0[j];
13
        double term = v1 / v0 + ( (mu0[j] - mu1[j]) * (mu0[j] - mu1[j]) ) / v0 - 1.0 + 2.0 * log(s0[j] / s1[j]);
14
        kl += 0.5 * term;
15
    }
16
    return kl;
17
}
18
19
// Sample from diagonal Gaussian
20
vector<double> sample_diag_gaussian(const vector<double>& mu, const vector<double>& s, mt19937& rng) {
21
    normal_distribution<double> ndist(0.0, 1.0);
22
    size_t d = mu.size();
23
    vector<double> w(d);
24
    for (size_t j = 0; j < d; ++j) w[j] = mu[j] + s[j] * ndist(rng);
25
    return w;
26
}
27
28
// Simple linear classifier with bias: sign(w^T x + b). Here w includes bias as last entry.
29
double predict_score(const vector<double>& w, const vector<double>& x) {
30
    // w.size() = d+1, x.size() = d. Last weight is bias.
31
    double s = w.back(); // bias
32
    for (size_t j = 0; j + 1 < w.size(); ++j) s += w[j] * x[j];
33
    return s;
34
}
35
36
int main() {
37
    ios::sync_with_stdio(false);
38
    cin.tie(nullptr);
39
40
    // Toy 2D binary dataset (linearly separable with margin)
41
    // Labels in {-1, +1}
42
    vector<vector<double>> X = {{1.0, 2.0}, {2.0, 1.0}, {2.0, 3.0}, {3.0, 1.5},
43
                                {-1.0, -1.5}, {-2.0, -0.5}, {-1.5, -2.5}, {-3.0, -1.0}};
44
    vector<int> y = {+1, +1, +1, +1, -1, -1, -1, -1};
45
    const int n = (int)X.size();
46
47
    // Posterior Q: diagonal Gaussian around a trained solution (here, hand-crafted)
48
    // Dimension d=2, plus bias => d+1=3
49
    vector<double> muQ = {1.0, 1.0, 0.0}; // weights and bias
50
    vector<double> sQ  = {0.2, 0.2, 0.1}; // standard deviations
51
52
    // Prior P: zero-mean, small-variance Gaussian
53
    vector<double> muP = {0.0, 0.0, 0.0};
54
    vector<double> sP  = {1.0, 1.0, 1.0};
55
56
    // Monte Carlo estimate of empirical Gibbs risk \hat{R}_S(Q)
57
    int m_samples = 2000; // increase for lower variance
58
    mt19937 rng(42);
59
    int errors = 0;
60
    for (int m = 0; m < m_samples; ++m) {
61
        vector<double> w = sample_diag_gaussian(muQ, sQ, rng);
62
        for (int i = 0; i < n; ++i) {
63
            double s = predict_score(w, X[i]);
64
            int yhat = (s >= 0.0) ? +1 : -1;
65
            if (yhat != y[i]) errors++;
66
        }
67
    }
68
    double R_emp = (double)errors / (m_samples * n); // Gibbs 0/1 loss in [0,1]
69
70
    // KL(Q||P)
71
    double KL = kl_diag_gaussians(muQ, sQ, muP, sP);
72
73
    // PAC-Bayes (Seeger/McAllester-style) square-root bound
74
    double delta = 0.05;
75
    if (n <= 1) {
76
        cerr << "Need n > 1 for this bound form.\n";
77
        return 1;
78
    }
79
    double complexity = (KL + log(2.0 * sqrt((double)n) / delta)) / (2.0 * (n - 1));
80
    double gap = sqrt(max(0.0, complexity));
81
    double R_bound = min(1.0, R_emp + gap);
82
83
    cout << fixed << setprecision(6);
84
    cout << "Empirical Gibbs risk (Monte Carlo) = " << R_emp << "\n";
85
    cout << "KL(Q||P) = " << KL << "\n";
86
    cout << "delta = " << delta << "\n";
87
    cout << "PAC-Bayes gap = " << gap << "\n";
88
    cout << "Population Gibbs risk bound <= " << R_bound << "\n";
89
90
    return 0;
91
}
92

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute log2(n choose k) via log-gamma for numerical stability
5
// log2 C(n,k) = (1/ln 2) * (ln Gamma(n+1) - ln Gamma(k+1) - ln Gamma(n-k+1))
6
double log2_nCk(int n, int k) {
7
    if (k < 0 || k > n) return -INFINITY;
8
    if (k == 0 || k == n) return 0.0;
9
    double lnC = lgamma((double)n + 1.0) - lgamma((double)k + 1.0) - lgamma((double)(n - k) + 1.0);
10
    return lnC / log(2.0);
11
}
12
13
int main() {
14
    ios::sync_with_stdio(false);
15
    cin.tie(nullptr);
16
17
    // Suppose we have p weights after training; many are pruned to zero.
18
    int p = 10000; // total parameters
19
    vector<double> w(p);
20
21
    // Create a synthetic sparse vector: keep ~2% large weights, rest near zero
22
    mt19937 rng(123);
23
    normal_distribution<double> big(0.0, 1.0);
24
    normal_distribution<double> small(0.0, 0.05);
25
    for (int i = 0; i < p; ++i) w[i] = (i % 50 == 0) ? big(rng) : small(rng);
26
27
    // Prune by magnitude threshold
28
    double tau = 0.1;
29
    vector<int> idx_nonzero;
30
    vector<double> vals_nonzero;
31
    for (int i = 0; i < p; ++i) {
32
        if (fabs(w[i]) > tau) {
33
            idx_nonzero.push_back(i);
34
            vals_nonzero.push_back(w[i]);
35
        }
36
    }
37
    int k = (int)idx_nonzero.size();
38
39
    // Quantize each nonzero to b bits (uniform quantization over a dynamic range)
40
    int b = 8; // bits per nonzero value
41
42
    // Description length in bits: positions + values
43
    // L_bits = log2( C(p, k) ) + k * b
44
    double L_bits = log2_nCk(p, k) + (double)k * b;
45
46
    // Example empirical risk from training (bounded in [0,1])
47
    double R_emp = 0.02; // e.g., 2% training error on classification
48
49
    // Confidence parameter
50
    double delta = 0.05;
51
52
    // Compression bound (in nats): R <= R_emp + sqrt( (L + ln(1/delta)) / (2n) )
53
    // Convert bits to nats: L_nats = L_bits * ln 2
54
    int n = 50000; // sample size
55
    double L_nats = L_bits * log(2.0);
56
    double gap = sqrt((L_nats + log(1.0 / delta)) / (2.0 * n));
57
    double R_bound = min(1.0, R_emp + gap);
58
59
    cout << fixed << setprecision(6);
60
    cout << "Total params p = " << p << ", nonzeros k = " << k << ", bits/value = " << b << "\n";
61
    cout << "L_bits (positions + values) = " << L_bits << "\n";
62
    cout << "Empirical risk = " << R_emp << ", delta = " << delta << ", n = " << n << "\n";
63
    cout << "Compression gap = " << gap << "\n";
64
    cout << "Population risk bound <= " << R_bound << "\n";
65
66
    return 0;
67
}
68