Logarithmic Sample Complexity for High-Dimensional Sparse Recovery

This direction is merged into another direction: logarithmic sample complexity. Its last version stays readable and citable here.

Version 1 of 130 papers36 conceptsfrozen 2026-10-04

In modern machine learning, we often face the "curse of dimensionality": as the number of features $p$ grows, the amount of data needed to learn a model typically grows exponentially. However, a significant body of research demonstrates that if the underlying signal is sparse—meaning only a small subset of features $k$ actually matters—we can bypass this curse. The core intuition across these papers is that the required sample size $n$ scales logarithmically with the total number of dimensions ($n \propto \log p$).

The Geometry of Sparsity

The reason we can recover a signal from $p$ dimensions using far fewer than $p$ samples is that sparsity drastically reduces the "search space" of possible models. Instead of searching the entire high-dimensional space, we are looking for a small number of active coordinates.

Bo Chen and Andreas Krause show in Joint Optimization and Variable Selection of High-dimensional Gaussian Processes that this logarithmic scaling holds even for complex, non-linear functions. When only a handful of variables are "active," the cost of discovering them remains manageable even as the number of irrelevant "noise" features grows to the thousands or millions.

Scaling Laws Across Domains

This logarithmic relationship is a universal principle that applies to various statistical tasks beyond simple regression:

From Theory to Practice: Screening and Testing

The logarithmic scaling property enables a powerful two-stage experimental design. If we know that $n$ only needs to grow with $\log p$, we can conduct a small "pilot study" to screen for relevant variables before committing to a large-scale experiment.

Alfred O. Hero and colleagues describe this in Predictive Correlation Screening, where a screening phase identifies a candidate subset of variables. Similarly, Utkarsh Porwal and Ce Zhang take inspiration from "group testing" in Parallel Feature Selection Inspired by Group Testing. By testing groups of features together rather than one by one, they achieve the same logarithmic efficiency, allowing for feature selection on datasets with millions of dimensions.

Why It Works

The intuition is similar to a game of "20 Questions." To find one specific item out of a million ($p=10^6$), you don't need a million questions; you only need about 20 ($\log_2 10^6 \approx 20$). In high-dimensional sparse recovery, each sample acts like a "question" that narrows down the space of possible active features. Because each sample provides information about many dimensions simultaneously, we can identify the needle in the haystack with surprisingly little data.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_logarithmic_sample_complexity_for_high_d_06755955,
  title = {Logarithmic Sample Complexity for High-Dimensional Sparse Recovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-sample-complexity-for-high-dimensional-sparse-recovery/rdr_06755955ce154605b1c791ce95973994},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_logarithmic_sample_complexity_for_high_d_06755955_v1,
  title = {Logarithmic Sample Complexity for High-Dimensional Sparse Recovery},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-sample-complexity-for-high-dimensional-sparse-recovery/rdr_06755955ce154605b1c791ce95973994/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}