FAST: Topology-Aware Frequency-Domain Distribution Matching for Coreset Selection

This paper introduces FAST, a novel DNN-free coreset selection framework that leverages spectral graph theory and an Attenuated Phase-Decoupled Characteristic Function Distance within a progressive sampling strategy to achieve superior distribution matching, energy efficiency, and accuracy compared to existing state-of-the-art methods.

The Gist

Imagine you are a chef trying to teach a new apprentice how to cook a complex, 100-course banquet. You have a massive library of 10,000 recipe books. If you make the apprentice read all of them, it will take years, cost a fortune in electricity, and they might get overwhelmed.

Coreset Selection is the art of picking just a few "perfect" recipe books that, if studied, will teach the apprentice everything they need to know to cook the whole banquet.

The problem? Most existing methods for picking these books are flawed:

1. The "Expert Bias" Method: They use a specific, famous chef (a Deep Neural Network) to pick the books. But if that chef hates spicy food, they'll only pick spicy recipes, and the apprentice will fail when asked to cook Italian.
2. The "Gut Feeling" Method: They use simple rules (like "pick the most colorful books"). This often misses the subtle, complex flavors needed for a great dish.

Enter FAST (Frequency-domain Aligned Sampling via Topology). It's a new, smarter way to pick those recipe books without needing a famous chef to guide it.

Here is how FAST works, broken down into simple concepts:

1. The "Sound Wave" Analogy (Frequency Domain)

Imagine every dataset (like a collection of photos) is a piece of music.

• Low Frequencies are the bass and drums: the big shapes, the general colors, and the overall vibe (e.g., "This is a picture of a cat").
• High Frequencies are the cymbals and violins: the tiny details, the whiskers, the texture of the fur, and the sharp edges.

Most old methods only listen to the bass (low frequencies). They pick books that look like cats but might miss the specific breed or the texture of the fur. FAST listens to the entire symphony, from the deep bass to the highest violin note. It uses a mathematical tool called the Characteristic Function to capture every single note and rhythm in the data, ensuring the small subset of books represents the whole library perfectly.

2. The "Vanishing Phase" Problem

There was a catch with listening to the whole symphony. In the high notes (high frequencies), the volume (amplitude) gets very quiet, almost silent. Because the volume is so low, the old methods ignored the timing (phase) of those notes.

Think of it like a movie with the sound turned down. You can see the actors moving (amplitude), but you can't hear their dialogue (phase). In the high-frequency notes, the "dialogue" contains the most important details (like the texture of a bird's feather or the edge of a building). If you ignore the dialogue, you lose the story.

FAST's Solution: They invented a special "Phase-Decoupled" microphone. It turns up the volume specifically for the timing of the quiet notes, so the system can hear the fine details even when the overall sound is faint. This allows it to capture textures and edges that other methods miss.

3. The "Curriculum Learning" Strategy

Imagine trying to learn a language. If you start by memorizing complex, obscure idioms before you even know the alphabet, you will fail. You need to learn in order: first the letters, then words, then sentences.

FAST does the same with data. It uses a strategy called Progressive Discrepancy-Aware Sampling.

• Step 1: It picks books that match the "bass" (the big, global shapes).
• Step 2: Once the big picture is right, it starts adding books that match the "mid-range" sounds.
• Step 3: Finally, it adds the books with the "high notes" (the tiny, specific details).

This prevents the system from getting confused by the tiny details before it understands the big picture. It builds the perfect subset layer by layer.

4. The "Map" Constraint (Topology)

When you pick a few books from a library of 10,000, you don't want to pick 10 books that are all about "Cats" and ignore "Dogs." You need a map to ensure you cover the whole territory.

FAST builds a Topological Map of the data. It treats the data points like cities on a map connected by roads. It ensures that the few books it picks are spread out across the map, covering every "neighborhood" of the data, rather than clustering in just one corner. This guarantees that the small subset is a true, representative mini-version of the whole.

Why Does This Matter?

• It's Faster and Cheaper: Because FAST doesn't need a giant AI chef to do the picking, it runs on a standard computer chip (CPU) and uses almost no electricity. It's 96% more energy-efficient than current methods.
• It's Smarter: It works on any type of data, from simple photos to complex textures and even language models. It doesn't care what kind of "chef" (neural network) you eventually use to train on the data.
• It's Accurate: By listening to the whole "symphony" of the data and learning in the right order, the small subset it picks teaches the AI just as well as the massive original dataset.

In short: FAST is like a master librarian who doesn't need a computer to pick the best books. Instead, they listen to the "music" of the entire library, learn the songs in the right order, and pick a tiny, perfect playlist that captures the soul of the whole collection.

Technical Summary

1. Problem Statement

Coreset selection aims to compress large datasets into compact, representative subsets to reduce the computational and energy costs of training Deep Neural Networks (DNNs). However, existing methods suffer from significant limitations:

• DNN-based methods: Rely on proxy networks to evaluate sample importance. This introduces architectural bias, limiting generalization across different network structures and incurring high computational overhead.
• DNN-free methods: Rely on heuristics (e.g., geometric sampling) that lack rigorous theoretical guarantees for stability and accuracy.
• Distribution Matching Failures: Neither paradigm explicitly enforces distributional equivalence. Common metrics like MSE, KL Divergence, and Cross-Entropy fail to capture higher-order moments and complex multivariate correlations. Furthermore, applying continuous distribution matching (like gradient descent in feature space) to discrete dataset sampling creates a "continuous-to-discrete gap," often leading to suboptimal subsets that do not truly represent the original data.

2. Methodology: The FAST Framework

The authors propose FAST (Frequency-domain Aligned Sampling via Topology), the first DNN-free framework that formulates coreset selection as a graph-constrained optimization problem grounded in spectral graph theory.

A. Graph Construction & Topological Constraints

To bridge the gap between continuous optimization and discrete selection, FAST constructs a multi-scale manifold graph based on fuzzy topological theory (inspired by UMAP).

• Spectral Embedding: The graph's Laplacian eigenvectors serve as manifold features, capturing the intrinsic geometry of the data.
• Topology-Aware Alignment: The optimization process is constrained by:
  1. Diversity Constraint (DPP): Ensures the selected subset covers the full feature space without redundancy.
  2. Graph-Aware Alignment (GUNN): Uses the Hungarian algorithm to map continuous optimization points to discrete anchors in the original dataset, preserving topological consistency (i.e., if two points are connected in the original manifold, their continuous counterparts remain close).

B. Frequency-Domain Distribution Matching (CFD)

Instead of matching raw pixels or low-level features, FAST matches distributions in the frequency domain using the Characteristic Function Distance (CFD).

• Theoretical Basis: The Characteristic Function (CF) is the Fourier transform of a probability distribution. It uniquely determines the distribution and encodes all moments and intrinsic correlations.
• The "Vanishing Phase Gradient" Problem: Standard CFD suffers from a flaw where the phase gradient vanishes in medium-to-high frequency regions because the magnitude (amplitude) of the CF decays. This causes the optimizer to ignore critical structural details like edges and textures.
• Solution: Attenuated Phase-Decoupled CFD (PD-CFD): The authors introduce a novel loss function that decouples the phase from the magnitude. It applies an adaptive penalty to the phase difference, allowing the optimizer to focus on high-frequency structural details even when the amplitude is low.

C. Progressive Discrepancy-Aware Sampling (PDAS)

To ensure stable convergence, FAST employs a curriculum-learning strategy for frequency selection:

• Anisotropic Initialization: Constructs a frequency space sensitive to the specific data distribution.
• Progressive Selection: Frequencies are selected progressively from low to high. The model first aligns global structures (low frequencies) before refining local details (high frequencies). This prevents the optimization from being destabilized by noise in high-frequency components early in the process.

3. Key Contributions

1. Novel Framework: Proposes the first DNN-free distribution-matching coreset selection framework that eliminates architectural bias while enabling distribution matching in the discrete domain via graph constraints.
2. PD-CFD Metric: Introduces Characteristic Function Distance to coreset selection for capturing full distributional information (all moments). Crucially, it solves the "vanishing phase gradient" issue with Phase-Decoupled CFD, enabling accurate preservation of fine-grained semantics (textures, edges).
3. PDAS Strategy: Designs a Progressive Discrepancy-Aware Sampling strategy that schedules frequency matching from low to high, ensuring robust convergence with minimal frequencies.
4. Efficiency & Performance: Achieves State-of-the-Art (SOTA) performance with significantly lower computational overhead, making it suitable for resource-constrained environments.

4. Experimental Results

The authors evaluated FAST on diverse benchmarks including CIFAR-10/100, SVHN, Tiny ImageNet, and high-resolution texture/remote sensing datasets (DTD, RESISC45), as well as LLM instruction tuning (Alpaca/LLaMA).

• Accuracy Gains:
  • Outperforms all SOTA coreset selection methods.
  • Achieves an average accuracy gain of 9.12% over SOTA DNN-free methods and 17.63% over DNN-based methods.
  • Shows massive improvements (21.93% average gain) on texture-rich datasets (DTD, RESISC45), proving the efficacy of PD-CFD in capturing high-order structural details.
• Generalization:
  • Demonstrates strong cross-architecture generalization. Unlike DNN-based methods that degrade when transferred to different architectures, FAST maintains stable performance (negligible accuracy drop of ~0.53%) across CNNs, MobileNets, and Transformers.
• Efficiency:
  • Energy: Reduces power consumption by 96.57% compared to baselines.
  • Speed: Achieves a 2.2× speedup even on CPU.
  • Memory: Operates effectively with only 1.7 GB of memory, enabling deployment on edge devices (tested on Rockchip RK3588).
• LLM Application: Successfully applied to LLM fine-tuning (LLaMA-7B), outperforming the SOTA DNN-free baseline by 2.6% on the MMLU benchmark, demonstrating that spectral-graph alignment can preserve high-level semantic structure without neural feature extractors.

5. Significance

The FAST framework represents a paradigm shift in dataset compression. By moving away from model-dependent heuristics and leveraging spectral graph theory and frequency-domain analysis, it achieves a mathematically rigorous form of distribution matching.

• Theoretical Rigor: It provides a solution to the "continuous-to-discrete" gap in coreset selection, ensuring that the selected subset is topologically and statistically equivalent to the original.
• Practical Impact: Its extreme energy efficiency and low memory footprint make it a viable solution for on-device AI, edge computing, and large-scale model training where energy costs are prohibitive.
• Generalizability: The "Write once, run anywhere" property (model-agnostic performance) suggests that distributional equivalence is a more fundamental requirement for effective training data than fitting a specific proxy model.