Overview
This paper adapts the popular Iterative Hard Thresholding (IHT) algorithm to the challenge of learning sparse discrete probability distributions. While the authors prove that the core projection step for this task is NP-hard, they introduce a practical greedy approximation that achieves state-of-the-art results in distribution compression and prototype selection.
The Problem: Sparsity in Probability Space
In machine learning, we often want our models to be "sparse"—meaning they rely on only a few important features or data points. Sparsity makes models more interpretable, faster, and better at generalizing from limited data.
When dealing with probability distributions, sparsity means the distribution is supported on only a small subset of all possible states. However, optimizing for sparsity in the "space of measures" is significantly harder than in standard vector spaces. This is because any valid distribution must satisfy the simplex constraint: all probabilities must be non-negative and sum exactly to one.
Standard algorithms like IHT work by taking a gradient step and then "projecting" the result back onto the set of sparse solutions. The authors identify a major gap: while this projection is easy for simple vectors (you just pick the $k$ largest values), it becomes a combinatorial nightmare when you have to satisfy the simplex constraint and sparsity simultaneously. The authors term this the "Simplex Trap"—picking the $k$ largest values might make it impossible to satisfy the sum-to-one constraint efficiently.
Methods: Distribution IHT
To overcome these challenges, the authors propose Distribution IHT, a projected gradient descent framework tailored for discrete densities. The key components of their approach include:
- Hardness Proofs: They formally prove that the exact $\ell_2$-norm projection onto the set of $k$-sparse distributions is NP-hard. Furthermore, they show it is hard even to approximate within a constant factor without further assumptions.
- Greedy Sparse Projection (GSProj): Since exact projection is computationally unfeasible, they introduce a greedy algorithm. It iteratively selects the "best" support indices one by one and then performs an efficient projection onto the simplex for that specific support.
- Theoretical Guarantees: They provide a convergence analysis showing that if the objective function is "well-behaved" (specifically, satisfying strong convexity and smoothness), the IHT algorithm with this approximate greedy projection will still converge to a near-optimal solution.
Experiments and Key Results
Most previous work on sparse distributions relied on complex Bayesian priors. This paper demonstrates that a pure optimization approach—treating the distribution as a variable in a cost function—can be more flexible and performant. The authors evaluated their approach across three distinct setups:
1. Simulated Data
Using a 15-dimensional binary vector space (32,768 possible states), the authors compared IHT against global optima found via exhaustive search. IHT (especially when initialized with a greedy step) consistently found lower-cost solutions for both $\ell_2$ and KL-divergence objectives compared to pure greedy baselines.
2. Moment Reconstruction (Texas Hospital Data)
The authors used real-world public health data for "expectation-preserving distribution compression." The goal was to represent a large probability table using a very small number of entries while preserving the original statistical "moments" (averages).
As shown above, IHT significantly outperformed the Lasso (a standard sparse regression tool) and random baselines in accurately reconstructing the statistical moments of the data across various sparsity levels ($k$).
3. Dataset Compression (Digits Data)
Using a standard dataset of 9,298 handwritten grayscale images, the algorithm was tasked with selecting a small number of "prototype" images to represent the entire dataset for a nearest-neighbor classifier.
IHT achieved state-of-the-art compression. It yielded lower classification errors using fewer prototypes than existing methods like "Global Greedy" and the "Means" algorithm. Even with only a few hundred prototypes, IHT maintained a much higher accuracy than its competitors.
Limitations and Future Work
- Discrete Focus: The current framework is strictly designed for discrete distributions. Extending this to continuous measures (like Gaussian mixtures) would require a different mathematical toolkit.
- Computational Complexity: While much faster than exhaustive search, the greedy projection still scales with the number of states. For extremely high-dimensional distributions (e.g., millions of states), further algorithmic refinements are needed.
- Structured Sparsity: The authors suggest that future work could explore "structured" sparsity, where instead of picking $k$ random points, the algorithm selects points that follow a specific pattern or group structure.
Summary updated