🤖 AI

Leveraging Data Symmetries to Select an Optimal Subset of Training Data under Label Noise

This paper demonstrates that leveraging data symmetries and invariances to improve k-nearest neighbor accuracy significantly enhances the selection of optimal, low-noise training subsets in high-dimensional settings, even when underlying invariance information is only partially known.

Original authors: Kumar Shubham, Pavan Karjol, Kiran M K, Prathosh AP

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kumar Shubham, Pavan Karjol, Kiran M K, Prathosh AP

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize different types of fruit. You give it a huge pile of photos, but unfortunately, a mischievous gremlin has swapped the labels on many of them. Some photos of apples are labeled "bananas," and some oranges are labeled "grapes."

If you just feed all these photos to the robot, it gets confused and learns the wrong things. The standard way to fix this is to try to make the robot "tougher" so it ignores the bad labels. But this paper suggests a different, smarter approach: Instead of making the robot tougher, let's just throw away the bad photos before we start teaching.

Here is the story of how the authors figured out the best way to find and keep only the "good" photos, even when the pile is messy and the photos are very complex.

The Problem: The "Nearest Neighbor" Mistake

The researchers looked at a popular method called CutStats. Think of CutStats as a detective who tries to find the bad labels by looking at a photo's neighbors.

How it works: If you have a photo of an apple, the detective looks at the 10 photos closest to it. If 9 of them are labeled "apple" and 1 is labeled "banana," the detective assumes the "banana" label is a mistake and throws that photo out.
The Catch: This detective works great in a small, simple room (low-dimensional data). But if you put the detective in a massive, multi-dimensional warehouse (high-dimensional data, like complex images), the concept of "closest" breaks down. In a huge warehouse, everything feels equally far away from everything else. The detective gets lost, can't tell who is really close, and starts throwing out the wrong photos.

The Solution: The "Magic Mirror" (Symmetries)

The authors realized that many real-world objects have symmetries.

Rotation Symmetry: A coffee mug looks like a coffee mug whether it's turned left, right, or upside down.
Permutation Symmetry: A set of dice looks like the same set of dice no matter how you shuffle the order of the dice.

The paper argues that if you know these rules (symmetries), you can build a Magic Mirror (called an Invariant Representation).

Without the mirror: The detective sees a mug turned 90 degrees and thinks, "That's a different object than the mug turned 0 degrees!" They are too far apart in the detective's mind.
With the mirror: The mirror takes the mug, rotates it, and shows the detective the "essence" of the mug. Suddenly, the mug at 0 degrees and the mug at 90 degrees look identical to the detective.

By using this mirror, the detective can once again easily find the "true" neighbors, even in a massive warehouse. They can accurately spot the photos with the wrong labels and remove them.

The Three Big Discoveries

1. The Detective Needs a Map
The authors proved mathematically that the success of the "throwing away bad photos" strategy depends entirely on how good the detective (the k-NN algorithm) is at finding neighbors. In simple rooms, the detective is naturally good. In huge, complex rooms, the detective fails unless you give them a map (the symmetry rules).

2. The Magic Mirror Saves the Day
They showed that if you use a mirror that respects the object's symmetry (like rotation or shuffling), the detective works perfectly again, even in the most complex, high-dimensional rooms. The mirror effectively shrinks the massive warehouse down to a manageable size where "closeness" makes sense again.

3. You Don't Need the Perfect Map
In the real world, you might not know the exact rules of symmetry (e.g., you might not know exactly how the data was rotated). The authors showed that even if you have to learn the mirror from the data itself (using techniques like contrastive learning), it still works wonders. It's like giving the detective a slightly blurry map instead of a perfect one; it's not perfect, but it's still good enough to find the bad photos and save the robot's training.

The Results: Cleaning the Data

The team tested this on synthetic data (made-up math problems) and real-world data (like rotated images of handwritten digits and Tetris blocks).

The Old Way: Using the standard detective on messy data resulted in a confused robot.
The New Way: Using the "Magic Mirror" to clean the data first resulted in a robot that performed almost as well as if it had been trained on perfectly clean data from the start.

In a Nutshell

When your training data is noisy and messy, don't just try to teach your AI to be tough. Instead, use the hidden rules of the world (symmetries) to build a special filter. This filter helps you find the "true" neighbors of every data point, allowing you to easily spot and remove the corrupted labels. This leaves you with a clean, high-quality dataset that makes your AI learn much faster and more accurately, even when the original data was a mess.

Technical Summary: Leveraging Data Symmetries to Select an Optimal Subset of Training Data under Label Noise

1. Problem Definition

Modern machine learning relies heavily on large labeled datasets, yet data collected from diverse sources often suffers from label noise due to cost-effective annotation strategies (e.g., heuristics, weak supervision). While many existing approaches focus on enhancing model robustness to noisy labels, they often treat the noisy dataset as fixed. This paper addresses the problem of directly mitigating label noise at the data level by identifying and selecting an optimal subset of training data.

The authors focus on cutstats, a data-centric method that uses $k$ -nearest neighbors ( $k$ -NN) to detect low-noise samples by comparing a sample's label with its neighbors. However, the effectiveness of cutstats is largely unexplored in high-dimensional regimes. The core problem investigated is the performance gap between classifiers trained on subsets selected by cutstats and those trained on noise-free data, specifically analyzing how high dimensionality degrades the ability of standard $k$ -NN to approximate the Bayes optimal classifier, thereby failing to recover the theoretically optimal subset.

2. Methodology

Theoretical Framework

The paper establishes a formal relationship between the accuracy of a downstream classifier trained on a selected subset and the accuracy of the $k$ -NN heuristic used for selection.

Error Propagation: The generalization gap is shown to depend on the noise rates within the selected subset ( $\alpha_S, \gamma_S$ ). These rates are directly governed by the class-wise accuracy of the $k$ -NN classifier ( $\lambda_0, \lambda_1$ ) in identifying correct samples.
High-Dimensional Limitation: Citing Bahri et al. [2020a], the authors demonstrate that while $k$ -NN can approximate the Bayes optimal classifier in low dimensions, this approximation breaks down in high dimensions. Specifically, the upper bound on the number of neighbors $k$ required for convergence shrinks super-exponentially as the feature dimension $d$ increases, eventually making it impossible to find a valid $k$ that guarantees Bayes optimality.

Proposed Solution: Invariant Representations

To overcome the high-dimensional curse, the authors propose leveraging data symmetries and invariances.

Invariant Representation Function ( $F$ ): If a dataset admits an underlying symmetry group $G$ (e.g., orthogonal rotations $SO(d)$ or permutations $S_d$ ) such that class labels are invariant under the group action ( $f(g \cdot x) = f(x)$ ), an invariant representation function $F$ can be constructed. This function maps points in the same orbit to the same representation ( $F(x) = F(g \cdot x)$ ).
Modified Cutstats: Instead of using raw input features for distance calculations in $k$ -NN, the method utilizes the invariant representation $F$ . The weights and nearest neighbors are computed in the representation space:
$w_{i,j} = (1 + \|F(x_i) - F(x_j)\|^2)^{-1}$
Theoretical Recovery: The authors prove that for orthogonal and permutation groups, using $F$ effectively reduces the dimensionality or increases the data density in the representation space. This restores the conditions required for $k$ -NN to approximate the Bayes optimal classifier, even in high-dimensional settings.
Practical Adaptation: In scenarios where the underlying symmetry is unknown, the paper suggests using learned invariant representations via group-equivariant networks or contrastive learning to approximate $F$ .

3. Key Contributions

Theoretical Characterization of Cutstats: The authors formally establish that the performance of a classifier trained on a cutstats-selected subset is governed by the accuracy of $k$ -NN under label noise. They demonstrate that while $k$ -NN approximates the Bayes classifier in low dimensions, this guarantee fails in high dimensions.
Symmetry-Driven Subset Selection: The paper provides a theoretical analysis showing that incorporating knowledge of data symmetries (specifically orthogonal and permutation groups) via invariant representations preserves the approximation of the Bayes classifier in high-dimensional regimes, enabling the recovery of optimal subsets.
Practical Validation with Learned Representations: The work demonstrates that even when the exact invariant function is unknown, learned representations (via group-invariant learning or contrastive learning) can significantly enhance cutstats performance, allowing for the selection of near-optimal subsets in real-world scenarios.

4. Experimental Results

The authors evaluated their approach on synthetic data, rotated MNIST, and the Tetris dataset, comparing their method ("Ours") against baselines like Vanilla Cutstats, Entropy-based selection, and robustness-based loss functions (GCE).

Synthetic Data (Orthogonal & Permutation Groups): On synthetic data with known symmetries, the proposed method achieved the highest downstream classifier accuracy (68.52% for Orthogonal, 86.00% for Permutation) and subset accuracy (74.31% and 74.42%, respectively), significantly outperforming Vanilla Cutstats and other baselines.
Rotated MNIST: Under varying noise levels (0.4, 0.6, 0.8), the group-invariant representation method ("Ours (group inv)") consistently outperformed contrastive learning and Vanilla Cutstats. For instance, at noise level 0.6, it achieved 89.37% classifier accuracy compared to 83.78% for Vanilla Cutstats.
Tetris Dataset: The method demonstrated robustness on the Tetris dataset (satisfying $SE(3)$ invariance), achieving 75.72% accuracy at noise level 0.4, whereas other subset selection methods largely failed.
High-Dimensional Analysis: Ablation studies on synthetic data with dimensions ranging from 200 to 1000 showed that Vanilla Cutstats performance degraded significantly as dimensionality increased, while the invariant representation method maintained stable, high accuracy.
CIFAR-10N: On the CIFAR-10N (Worst Labels) dataset, the contrastive learning variant of the proposed method outperformed all baselines, achieving 65.30% classifier accuracy and 90.48% subset accuracy.

5. Significance and Claims

The paper claims that leveraging data symmetries provides a principled way to select clean training subsets in high-dimensional spaces where standard distance-based methods fail. The significance lies in shifting the focus from merely training robust models to curating high-quality data by exploiting the geometric structure of the data.

The authors modestly note that the effectiveness of their method is bounded by how accurately the group invariance can be modeled and the extent to which class-relevant information is preserved in the learned representations. They conclude that while learned representations may not perfectly capture underlying symmetries, they are sufficient to facilitate the identification of near-optimal subsets, offering a practical solution for noisy, high-dimensional data scenarios common in enterprise and crowdsourcing settings.