Clustering-based self-supervised video learning turns unlabeled clips into training labels by grouping their features and asking a network to predict the group. Cross-modal deep clustering, which clusters audio features and uses those clusters to supervise a video network, beats fully supervised pre-training on standard benchmarks. Its label generator, though, is a plain $k$-means vocabulary: a flat list of cluster centers with no internal structure, refitted from scratch over the whole dataset every round. Coding theory has a name for this kind of object. It is a random-codebook-style solution: it works, but its storage and search costs grow with the size of the vocabulary, and nothing protects it from degenerate solutions. This note proposes replacing it with a sparse regression code, a codebook in which each label is the sum of one entry chosen from each of $L$ small sections. A label is computed greedily, one section at a time, and the scheme comes with proven near-optimal compression for Gaussian sources. The result is a pseudo-label with $M^L$ possible values that costs only $L\cdot M$ stored vectors, needs no global clustering pass, and orders itself from coarse to fine.
The claim is specific and could fail. At a matched label budget, structured superposition pseudo-labels should give video representations at least as good as $k$-means pseudo-labels, at a fraction of the labeling cost, with no cluster collapse. If a learned residual quantizer gives the same accuracy, then the coding-theory structure buys only speed. The experiments are designed to tell those two outcomes apart.
Core Claim
The two research directions fit together as mechanism and application. On the video side, the annotation bottleneck is being attacked by pseudo-labeling methods. The clearest of these is Self-Supervised Learning by Cross-Modal Audio-Video Clustering (XDC). XDC encodes video with a 3D-CNN and audio spectrograms with a 2D-CNN, runs $k$-means in one modality, and trains the other modality to predict the resulting cluster indices, iterating between the two. Pre-trained on 65M IG-Kinetics videos, it reaches 95.5% on UCF101 and 68.9% on HMDB51, above supervised Kinetics-400 pre-training at 94.2% and 65.1%. The paper's own limitation, as summarized in the file, is that repeated $k$-means over tens of millions of clips is a heavy infrastructure cost. This is the practical implementation gap in miniature: an unstructured codebook whose fitting and assignment scale with vocabulary size times dataset size.
Sparse Regression Codes (SPARCs) supply the method. A codeword is $x = A\beta$. Here $A \in \mathbb{R}^{d \times LM}$ is a dictionary split into $L$ sections of $M$ columns each, and $\beta$ has exactly one nonzero entry per section. For lossy compression, the encoder uses successive cancellation: it picks the column of section 1 most correlated with the input, subtracts its scaled contribution, and moves on to section 2. Section coefficients follow a decaying power allocation, so early sections carry most of the energy. Venkataramanan, Tatikonda and Barron prove this structure reaches the Gaussian rate-distortion limit. With Hadamard-structured dictionaries, it runs in $O(L\, d \log d)$ time.
Our pseudo-label for a clip is the tuple of chosen indices $(j_1,\dots,j_L)$, computed from the whitened teacher-modality feature. The student predicts it with $L$ independent $M$-way classification heads.
Three properties follow from the construction. First, there is no global clustering step: labeling is a per-sample streaming operation. Second, there is no collapse, because a fixed dictionary cannot lose its centers. Labels change between rounds only as features move. Third, the label is hierarchical: section 1 gives a coarse partition and later sections refine it. The rate is $R = L\log M/d$ nats per dimension. For a near-Gaussian whitened feature with per-dimension variance $\sigma^2$, the Gaussian rate-distortion bound puts the best achievable distortion near $\sigma^2 e^{-2R}$. Because SPARC encoding approaches that bound, the label keeps close to the maximum information about the teacher feature that its label entropy allows.
Research Program
We first build a SPARC labeler that drops into an XDC-style pipeline. The audio encoder's features are whitened, then encoded with successive cancellation against either a Gaussian random dictionary or a randomized Hadamard dictionary, with exponentially decaying section power. The video encoder trains on the $L$ section labels with a sum of cross-entropies. The roles then alternate, as in XDC.
We then study three design questions. The first is whether the dictionary should stay fixed, which maximizes stability and minimizes cost, or be refreshed lightly by per-section mean updates. The second is how the power allocation shapes the coarse-to-fine split, which we measure by the normalized mutual information (NMI) between each section's labels and Kinetics classes. The third is how downstream accuracy changes with rate $R$ when we sweep $L$ and $M$ at fixed $L\log M$. This sweep tests whether the rate-distortion view predicts anything: accuracy should track retained information until labels become too fine to be learnable.
A secondary, audio-free variant uses two temporally separated clips of the same video as teacher and student. This matters because XDC needs synchronized audio, which silent domains lack. It is a stretch goal, not part of the core claim.
Baselines
The naive reference point is training from random initialization. The file's only number for it is 55.8% on UCF101, reported in Video Playback Rate Perception for Self-Supervised Spatio-Temporal Representation Learning with that paper's backbone. We will rerun random initialization with our own backbone, and that rerun is the number to beat by a wide margin.
The strongest existing method is XDC itself. The file reports 95.5% UCF101 and 68.9% HMDB51 after IG-Kinetics pre-training. We cannot match 65M videos, and the file contains no reported XDC result for Kinetics-400-only pre-training. We will therefore reimplement XDC on Kinetics-400 with the same backbones, epochs, augmentation, and number of alternation rounds, and with $k$ tuned over the same grid budget we give $L$ and $M$. Beating it means equal or higher UCF101 and HMDB51 fine-tuning accuracy, averaged over three seeds, at substantially lower labeling wall-clock and memory. Matching accuracy at much lower cost counts as a partial win. Losing accuracy at any cost counts as failure.
For context against non-clustering pretext tasks pre-trained on Kinetics-400, the file reports Video Representation Learning by Dense Predictive Coding at 75.7% and Self-supervised Video Representation Learning by Pace Prediction at 77.1% on UCF101. Their backbones differ from ours, so we report them as context only.
Two ablations isolate the key ingredient. Residual $k$-means, a learned $L$-stage quantizer fitted on residuals with the same $L$ and $M$, isolates whether a learned superposition codebook is better than a structured fixed one. Random hashing, which assigns each section index by nearest atom in an independent random section with no cancellation and no power allocation, isolates the role of successive cancellation and of the coarse-to-fine ordering.
Why not just…?
Why not just run faster $k$-means, such as mini-batch or GPU $k$-means with a larger $k$? This cuts cost, but it keeps the flat vocabulary. Memory and assignment time still scale linearly in $k$, while SPARC reaches $M^L$ labels at cost linear in $L\cdot M$. A large flat $k$ also invites empty or collapsed clusters. We include a GPU mini-batch $k$-means variant of XDC at the largest $k$ that fits our compute and report label-space utilization (the entropy of label usage) alongside accuracy.
Why not just use a learned residual or product quantizer? This is the real threat. Residual $k$-means is structurally close to SPARC's successive cancellation, and learning could fit the feature distribution better than a random dictionary. Its downsides are that it reintroduces per-round fitting and that it can still collapse within a stage. The residual $k$-means ablation settles the question directly. If it matches SPARC on accuracy, we will report that the contribution is cost and stability, not representation quality, and drop the stronger claim.
Why not just scale data, as XDC did with 65M videos? Scaling works, as the 95.5% result shows. But it is exactly the regime where XDC's clustering overhead hurts most, and it does not help domains without audio. Our compute-matched comparison at Kinetics-400 scale measures how much accuracy each unit of labeling compute buys. A labeling cost that grows per sample rather than per clustering pass is what would make the scaled regime cheaper.
Proposed Experiments
All models pre-train on Kinetics-400 and fine-tune on UCF101 and HMDB51 with the official three splits. We report top-1 accuracy, nearest-neighbor retrieval accuracy on UCF101 (the protocol in which pace prediction reports 25.6% top-1), per-round labeling wall-clock and peak memory, label utilization entropy, the fraction of labels that change between rounds, and per-section NMI with Kinetics classes.
The first decisive check is the matched-budget comparison of XDC, residual $k$-means, random hashing, and SPARC labels. The second is the rate sweep. If accuracy does not rise with $R$ before saturating, the rate-distortion motivation is not doing work. The third is the coarse-to-fine check: section-1 labels alone should carry most of the class NMI. If NMI is spread evenly across sections, the power allocation adds nothing and we will say so.