Logarithmic Sample Complexity in High Dimensional Learning

283 concepts207 papers2 proposals

In classical statistics, the "curse of dimensionality" dictates that the difficulty of learning a model grows exponentially with the number of variables. If a system depends on $p$ features, traditional wisdom suggests that the number of samples $n$ required to understand it must scale polynomially or even exponentially with $p$.

However, a profound realization across modern machine learning is that this curse can be bypassed if the underlying phenomenon is sparse—meaning that out of a massive sea of $p$ ambient variables, only a small subset of $k$ active variables actually drive the system. In these settings, the required sample size does not scale with the total dimension $p$, but rather logarithmically with $p$ (i.e., $n = \mathcal{O}(k \log p)$). This logarithmic sample complexity scaling fundamentally changes what is learnable, allowing researchers to reliably extract structures from datasets where the number of features vastly exceeds the number of observations.

To understand why logarithmic scaling is possible, it helps to view structure recovery as an information-theoretic search problem. Suppose we want to identify exactly which $k$ features are active out of $p$ total possibilities. The number of possible configurations is given by the binomial coefficient:

$$\binom{p}{k} \approx \left(\frac{ep}{k}\right)^k$$

To uniquely identify the correct configuration, an algorithm must extract enough information from the data to distinguish it from all other alternatives. The total amount of information needed to specify the correct subset is proportional to the logarithm of the number of possibilities:

$$\log \binom{p}{k} \approx k \log\left(\frac{p}{k}\right)$$

Each high-quality data sample provides a slice of information about the underlying structure. Therefore, as long as our estimation methods can efficiently harvest this information, the required sample size only needs to grow linearly with the true complexity ($k$) and logarithmically with the ambient dimension ($\log p$). As the number of irrelevant noise features grows, the statistical cost of filtering them out grows incredibly slowly.

The Mechanism: Sparse Regularization and Thresholding

How do algorithms practically achieve this logarithmic scaling without performing an exhaustive, NP-hard search over all $\binom{p}{k}$ combinations? The primary mechanism is continuous convex relaxation—specifically, penalizing models using $\ell_1$ or group-sparse regularizers, or applying iterative thresholding.

In a foundational result for graphical models, Su-In Lee et al. demonstrated in Efficient Structure Learning of Markov Networks using L1-Regularization that transforming the combinatorial problem of network structure learning into an $\ell_1$-penalized convex optimization problem allows the required training samples to scale logarithmically with the number of irrelevant features.

To refine this process and weaken the strict conditions often required by simple $\ell_1$ optimization, Shuheng Zhou 0002 proposed a multi-step thresholding procedure in Thresholding Procedures for High Dimensional Variable Selection and Statistical Estimation. By taking an initial sparse estimator and refining it with Ordinary Least Squares, the author proved that near-oracle performance is achievable with a sample size that scales almost linearly with the number of relevant features and logarithmically with total observations, even in dense-sparse regimes.

[High-Dimensional Input Space: p variables]
       │
       ▼  (L1 Regularization / Multi-step Thresholding)
[Continuous Convex Filter] ───► Eliminates p - k irrelevant features
       │
       ▼  (Logarithmic Sample Cost: O(k log p))
[Recovered Sparse Structure: k active variables]

When multiple regression tasks share underlying features, the data requirements can be optimized even further. Sahand N. Negahban et al. analyzed this in Phase transitions for high-dimensional joint support recovery, demonstrating a sharp phase transition for joint support recovery using $\ell_{1,\infty}$-regularization. The authors showed that the required sample size scales linearly with the sparsity of the model and logarithmically with the total number of features, with the exact efficiency bound modulated by the fraction of shared features across tasks.

Structure Recovery in Graphs and Networks

This logarithmic scaling principle extends deeply into recovering the topologies of complex networks, such as social graphs, physical systems, and multi-agent games.

Consider an Ising model or a discrete Markov Random Field where variables interact locally. In Ising Model Selection Using $\ell_{1}$-Regularized Linear Regression: A Statistical Mechanics Analysis, Xiangming Meng utilized tools from statistical mechanics to prove that simple $\ell_1$-regularized linear regression achieves an $\mathcal{O}(\log N)$ sample complexity for topology reconstruction, despite being mathematically misspecified for binary data. Similarly, Ali Jalali et al. showed in On Learning Discrete Graphical Models using Group-Sparse Regularization that node-wise logistic regression with group-sparse ($\ell_1/\ell_2$) regularization consistently recovers complex, higher-order interactions with a sample size that scales logarithmically with the total number of variables.

This property is also vital when learning behavioral structures. In From Behavior to Sparse Graphical Games: Efficient Recovery of Equilibria, Asish Ghoshal et al. studied the problem of mapping interactions in multi-agent systems. By assuming sparsity in how players influence one another, the authors proved that the observational data needed to identify Pure-Strategy Nash Equilibria scales logarithmically with the total population size, making the analysis of massive strategic networks statistically viable.

Tracking Large-Scale Dynamical Systems

One of the most compelling validations of logarithmic sample complexity occurs in time-series analysis and system identification. For a dynamical system with a state-space of dimension $d$, tracking interactions typically requires an immense amount of independent data points. However, if the underlying physical connectivity is sparse (e.g., in power grids or robotic swarms), the system's topology can be mapped using surprisingly little data.

In Learning Sparse Dynamical Systems from a Single Sample Trajectory, Salar Fattahi et al. provided finite-time guarantees showing that a Lasso-based estimator can identify large-scale sparse linear systems from a single continuous trajectory of data. The length of the required trajectory scales logarithmically with the system's total dimension. Salar Fattahi expanded on this mechanism in Learning Partially Observed Linear Dynamical Systems from Logarithmic Number of Samples, proving that the inherent stability of physical systems allows researchers to overcome the curse of dimensionality, requiring a sample size that scales logarithmically with the state space dimension rather than linearly.

[Continuous Trajectory Data] ──► [Lasso-Based Estimator] ──► [Exact Network Topology]
       ▲                                                            ▲
       └─────────────────── Scales Logarithmically ─────────────────┘
                            with State Dimension (d)

This efficiency carries over directly to causal discovery. In Information Theoretically Optimal Sample Complexity of Learning Dynamical Directed Acyclic Graphs, Mishfad Shaikh Veedu et al. established that the information-theoretic optimal sample complexity for learning the structure of Dynamical Directed Acyclic Graphs (DDAGs) is $\Theta(q \log(p/q))$, where $p$ is the total number of variables and $q$ is the maximum sparsity per node. This proves that mapping temporal causal dependencies is fundamentally no more data-intensive than learning static structures.

Beyond Inputs: High-Dimensional Outputs and Functions

The mathematical machinery that enables logarithmic sample complexity for feature inputs can be inverted or adapted to handle complexity in outputs, mixtures, and non-linear combinations.

High-Dimensional Output Spaces

When predicting massive numbers of labels simultaneously (such as tagging millions of images), the output space explodes. Krishna Balasubramanian et al. addressed this in The Landmark Selection Method for Multiple Output Prediction, proving that if a high-dimensional output space can be represented by a small, sparse subset of landmark variables, the sample complexity for learning the entire prediction model scales logarithmically with the total number of outputs.

Non-Linear Functions and Set Functions

Logarithmic scaling is not restricted to linear relationships. In Efficient Sampling for Learning Sparse Additive Models in High Dimensions, Hemant Tyagi et al. combined Taylor expansions, compressive sensing, and cubic spline optimization to reconstruct high-dimensional functions. The authors showed that for functions following a sparse additive structure, the sample complexity scales logarithmically with the total dimensions, effectively bypassing the curse of dimensionality.

For combinatorial domains, Amir Zandieh et al. demonstrated in Efficiently Learning Fourier Sparse Set Functions that complex set functions can be exactly reconstructed with a sample complexity scaling logarithmically with the number of elements, provided the function's Fourier representation is sparse and low-degree.

Conclusion

Logarithmic sample complexity works because sparsity fundamentally alters the geometry of the learning problem. By utilizing regularizers and thresholding techniques that act as continuous proxies for combinatorial selection, algorithms can isolate the true, low-dimensional subspace driving a system. Whether applied to linear regressions, graphical models, evolving dynamical trajectories, or high-dimensional outputs, the statistical cost of filtering out irrelevant dimensions grows at a manageable, logarithmic rate—turning seemingly intractable high-dimensional problems into computationally and statistically solvable tasks.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_logarithmic_sample_complexity_9e6ed1c3,
  title = {logarithmic sample complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-sample-complexity/rdr_9e6ed1c327ba401fb7869dfeca16af28},
  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_9e6ed1c3_v1,
  title = {logarithmic sample complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-sample-complexity/rdr_9e6ed1c327ba401fb7869dfeca16af28/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake