Research map / Architectures and efficiency / CNN design
On the VC dimension of deep group convolutional neural networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives upper and lower bounds on the VC (pseudo)dimension of ReLU group convolutional neural networks (GCNNs) on finite discretized groups, relating them to parameter count, depth, and group resolution r, and compares them with DNN bounds.
Problem
Generalization of equivariant group convolutional networks is poorly understood theoretically; prior VC results for GCNNs covered only two-layer continuous-group networks with infinite VC dimension.
Approach
Treat ReLU GCNNs on discretized groups as piecewise-polynomial parameterized classes, bound their sign-pattern growth function layer by layer, and obtain a lower bound by embedding DNNs into GCNNs via a sum over group elements, yielding an extra W log2(r) term that grows with input resolution.
Key results
- Upper bound: VC(H) <= L+1 + 4(sum_l W_l) log2(8 e r sum_l m_l) for ReLU GCNNs with W_l parameters up to layer l.
- Lower bound: VC(H_{W,L,r}) >= c max{VC(F_{W,L}), W log2 r}, so the two bounds match up to a factor L in the resolution-dependent term.
- The GCNN VC dimension is similar to that of DNNs with the same parameter count, plus an extra W log2(r) term that grows logarithmically with group resolution r.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the discretized group resolution r | ReLU GCNNs with W parameters and depth at most L · Discretized group GCNNs | VC dimension: W log₂(r) | Helped |
| Use a GCNN rather than a DNN with comparable architecture | ReLU GCNNs versus ReLU DNNs · Discretized group GCNNs and DNNs | VC dimension upper bound: UB(H) ≤ 2k UB(F) + 4 (∑_{ℓ=1}^{L} W_ℓ(H)) log₂(2r) | Mixed |
Surprising findings
- VC dimension of GCNNs grows with the group resolution r, which is consistent with prior results that continuous-group GCNNs have infinite VC dimension.
Limitations
- Analysis restricted to GCNN layers without feedforward head and to ReLU activation.
- Upper and lower bounds differ by a factor L in the resolution term, and lower bound assumes a specific kernel parametrization (k=1 indicator basis) and L>3 with L <= W^0.99.
- Results are theoretical; no experiments are reported.
Experimental setup
Metrics: VC dimension upper bound VC dimension lower bound
Baselines: DNN VC bounds (Bartlett et al.) CNN VC bounds
Builds on: VC dimension bounds for piecewise-polynomial DNNs (Bartlett et al.) Warren-type sign pattern bound for polynomials group convolutional neural networks (Cohen and Welling)
Closest papers by meaning
- Group Equivariant Convolutional Networks (ICML 2016 · similarity 0.89)
- Universality of Group Convolutional Neural Networks Based on Ridgelet Analysis on Groups (NeurIPS 2022 · similarity 0.87)
- Variational Partial Group Convolutions for Input-Aware Partial Equivariance of Rotations and Color-Shifts (ICML 2024 · similarity 0.86)
- Deep Ridgelet Transform and Unified Universality Theorem for Deep and Shallow Joint-Group-Equivariant Machines (ICML 2025 · similarity 0.85)
- Continuous Rotation Group Equivariant Network Inspired by Neural Population Coding (AAAI 2024 · similarity 0.85)
- Group Downsampling with Equivariant Anti-aliasing (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.