Diffusion models learn simple statistics before complex ones, revealing a sample complexity exponent.
problem Understanding the learning dynamics of diffusion models.
method Empirical observations and theoretical analysis of diffusion models and denoisers.
result Diffusion models learn simple statistics (pair-wise correlations) at linear sample complexity, while higher-order statistics (e.g., fourth cumulant) require cubic sample complexity.
Two statistical tasks are shown to have equivalent sample complexity.
problem Determining if a function depends on only a few variables and identifying those variables.
method Proved statistical equivalence of feature selection and junta testing through sample complexity analysis.
result Brute-force algorithm is sample-optimal for both tasks with optimal sample size.
Optimizes ICA performance in high dimensions with computational constraints.
problem Statistical optimality and computational tractability in ICA.
method Characterization of optimal sample complexity, development of computationally tractable estimates.
result Optimal sample complexity is linear in dimensionality, quadratic with low-degree polynomial algorithms.
The paper extends statistical estimation techniques under differential privacy.
problem Establishing sample complexity bounds for estimation tasks under differential privacy.
method Proposes analogues of Le Cam's method, Fano's inequality, and Assouad's lemma under central differential privacy.
result Optimal sample complexity bounds for discrete distribution estimation under total variation and ℓ2 distances. Polyak step size GD reaches final radius of convergence after log iterations.
problem Statistical and computational complexities of Polyak step size GD.
method Generalized smoothness and Lojasiewicz conditions, stability of gradients.
result Polyak step size GD reaches final statistical radius of convergence after logarithmic number of iterations.
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
Proves minimax sample complexity for turn-based stochastic games.
problem Proving theoretical guarantees for reinforcement learning in turn-based stochastic games.
method Developing absorbing TBSG and reward perturbation techniques to handle statistical dependence.
result Empirical Nash equilibrium strategy approximates true Nash equilibrium in turn-based stochastic games.
The paper explores when linear system identification is hard or easy, especially for under-actuated systems.
problem Statistical hardness of learning linear systems, especially under-actuated or under-excited systems.
method Using tools from minimax theory and recent statistical tools for finite sample analysis of system identification.
result The controllability index of linear systems affects the sample complexity of identification, making some systems hard to learn.
Study shows computational and statistical gaps in Gaussian Single-Index Models.
problem Statistical and computational trade-offs in high-dimensional regression problems.
method Analysis of SQ and LDP frameworks, partial-trace algorithm.
result Computational algorithms require significantly more samples than information-theoretic limits.
The Morse-Smale complex of a function f decomposes the sample space into cells where f is increasing or decreasing. When applied to nonparametric density estimation and regression, it provides a way to represent, visualize, and compare multivariate functions. In this paper, we present some statistical results on es…
Study replicability in high-dimensional statistics, resolving open problems.
problem Ensuring consistent results in high-dimensional statistical tasks.
method Introduced replicable learning algorithms and established computational and statistical equivalence with high-dimensional isoperimetric tilings.
result Matching sample complexity upper and lower bounds for replicable mean estimation and coin problem.
New bounds for score matching in polynomial exponential families.
problem Understanding the sample complexity of score matching for polynomial exponential families.
method Non-asymptotic sample complexity analysis for score matching.
result First finite sample bounds for score matching in polynomial exponential families.
We investigate the statistical complexity of estimating the parameters of a discrete-state Markov chain kernel from a single long sequence of state observations. In the finite case, we characterize (modulo logarithmic factors) the minimax sample complexity of estimation with respect to the operator infinity norm, while…
Improves sampling, rounding, and integration of logconcave functions.
problem Sampling, rounding, and integration of logconcave functions.
method Algorithmic diffusion approach.
result First complexity improvements in nearly two decades for general logconcave functions.
New methods improve confidence set calibration in complex models.
problem Challenges in maintaining confidence set coverage in complex models.
method TRUST and TRUST++ methods using simulated data for calibration.
result Methods achieve distribution-free conditional coverage and robust inference.
New complexity measure for interactive learning reduces regret to near-optimal levels.
problem Challenges in sample-efficient, adaptive learning algorithms for interactive decision making.
method Introduces the Decision-Estimation Coefficient and the Estimation-to-Decisions (E2D) principle.
result Unified algorithm design principle E2D achieves optimal sample-efficient learning.
Paper studies statistical-computational trade-offs in tensor PCA and related problems.
problem Statistical-computational gap in tensor PCA estimation.
method Derives computational lower bounds using communication complexity.
result Lower bounds specify trade-off among passes, sample size, and memory.
Sharp statistical theory for conditional diffusion models.
problem Lack of theoretical foundation for conditional diffusion models.
method Sharp statistical theory with approximation of conditional score function.
result Sample complexity bound that adapts to data distribution smoothness.
Tensor PCA problem analyzed with statistical query lower bounds.
problem Estimating the expected value of a rank-1 tensor from Gaussian samples.
method Sharp analysis of optimal sample complexity in the Statistical Query model.
result SQ algorithms with polynomial query complexity fail in the conjectured hard phase and have sub-optimal sample complexity.
We study the problem of hypothesis testing between two discrete distributions, where we only have access to samples after the action of a known reversible Markov chain, playing the role of noise. We derive instance-dependent minimax rates for the sample complexity of this problem, and show how its dependence in time is…
The method to derive uniform bounds with Gaussian and Rademacher complexities is extended to the case where the sample average is replaced by a nonlinear statistic. Tight bounds are obtained for U-statistics, smoothened L-statistics and error functionals of l2-regularized algorithms.
Replicable clustering algorithms for k-medians, k-means, and k-centers are proposed.
problem Designing clustering algorithms that produce the same partition on repeated runs under the same distribution.
method Utilizing approximation routines for combinatorial clustering problems in a black-box manner.
result Replicable algorithms for statistical k-medians, k-means, and k-centers with specified approximation and sample complexities. Study nonparametric estimator for Markov chain transition matrices in offline setting.
problem Estimating transition matrices of finite controlled Markov chains from logged data.
method Developed sample complexity bounds and conditions for minimaxity.
result Achieving certain statistical risk requires balancing mixing properties and sample size.
This paper improves learning complex functions with CoT supervision, reducing sample complexity.
problem Learning complex functions with multi-step reasoning.
method Develops a statistical theory linking CoT risk and end-to-end risk, using CoT information measure.
result CoT supervision can achieve significantly faster learning rates compared to standard E2E supervision.
This study shows neural nets can approximate Turing machines with meaningful statistical properties.
problem Theoretical limitations in approximating Turing machines with neural networks.
method Formal definition of statistically meaningful approximation, analysis of boolean circuits and Turing machines using neural nets.
result Transformers can statistically meaningfully approximate Turing machines with polynomial sample complexity.
Estimates proportions of LLM-generated text in mixed documents.
problem Estimating the proportion of text generated by a pre-specified LLM in mixed documents.
method Developed estimators for two observation regimes: full observation and pivotal reduction, and established sample complexity bounds.
result Full observation estimators require fewer samples than pivotal reduction estimators.
Study shows multi-distribution learning has slower rates than single-task learning.
problem Understanding the statistical complexity of learning from heterogeneous sources.
method Structured hypothesis-testing framework to capture the statistical cost of certifying near-optimality under bounded noise.
result Learning across multiple distributions incurs slow rates scaling with k/ε2, even under constant noise levels. Establishes statistical and computational bounds for influence diagnostics.
problem Identifying influential datapoints or subsets in machine learning models.
method Finite-sample statistical bounds and computational complexity for influence functions and approximate maximum influence perturbations.
result Established statistical and computational guarantees for influence diagnostics.
New bounds on learning from multiple distributions for VC classes.
problem Understanding the sample complexity of learning from multiple data distributions.
method Analyzing the gap between known upper and lower bounds for PAC-learnable classes.
result Recent progress on sample complexity for VC dimension d classes on k distributions.
A new method uses neural tangent kernel to efficiently compute MMD statistic.
problem Efficiently computing Maximum Mean Discrepancy (MMD) statistic with low memory and computational complexity.
method Identifies a connection between neural tangent kernel (NTK) and MMD to develop a computationally and memory-efficient approach.
result The proposed NTK-MMD statistic is validated through numerical experiments on synthetic and real-world datasets.
Study on distributional TD learning with linear approximations for better return estimation.
problem Estimating the return distribution of a policy in reinforcement learning.
method Finite-sample analysis of distributional TD learning with linear function approximation, using the linear-categorical Bellman equation and exponential stability arguments for products of random matrices.
result Sample complexity of linear distributional TD learning matches that of classic linear TD learning, indicating similar difficulty in estimating return distribution versus its expectation.
Study on estimating Gumbel--Max watermark proportions in edited documents.
problem Estimating the proportion of a document generated from a watermarked LLM.
method Comparison of full observation and pivotal reduction observation regimes; development of estimators and information-theoretic lower bounds.
result Full observation yields a substantially smaller sample complexity compared to pivotal reduction.
Study on multi-agent decision making complexity, showing sample efficiency gaps.
problem Understanding sample efficiency in multi-agent decision making.
method General framework for interactive decision making, focusing on equilibrium computation.
result No 'reasonable' complexity measure can close gaps between single and multiple agents.
Unified method for MMD variance estimation improves accuracy and computational efficiency.
problem Variance estimation for MMD in nonparametric testing.
method Unified finite-sample characterization of MMD variance through U-statistic and Hoeffding decomposition; exact acceleration method for univariate case.
result Unified estimators improve accuracy and computational efficiency for MMD variance.
Study private query release with public data, reducing sample sizes.
problem Answering a wide range of statistical queries while maintaining privacy.
method Combines public and private samples to answer queries with differential privacy.
result Private and public sample complexities for different query classes.
New tools quantify deep generative models' performance.
problem Measuring the quality-diversity trade-off in deep generative models.
method Established non-asymptotic bounds on sample complexity and introduced frontier integrals.
result Smoothed estimators improve convergence rates of divergence frontiers.
The paper analyzes the statistical cost of tuning kernel hyperparameters in robust regression.
problem Finding the best interpolant from a class of kernels with unknown hyperparameters under adversarial noise.
method Finite-sample guarantees, subsampling guarantee for linear regression, ε-net argument for discretizing kernel parameterizations.
result Hyperparameter optimization increases sample complexity by just a logarithmic factor, compared to known parameters.
Many random processes can be simulated as the output of a deterministic model accepting random inputs. Such a model usually describes a complex mathematical or physical stochastic system and the randomness is introduced in the input variables of the model. When the statistics of the output event are known, these input …
This paper provides theoretical foundations for using quantized actions in behavior cloning.
problem Applying autoregressive models to continuous control requires discretizing actions through quantization, which is poorly understood.
method The paper analyzes quantization error propagation and statistical sample complexity, and proposes model-based augmentation.
result Behavior cloning with quantized actions achieves optimal sample complexity, matching existing lower bounds.
Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is O(d/ε+d/(max{p,ε})2), SQ lower bound is Ω(d1/2/(max{p,ε})2). We study sparse group Lasso for high-dimensional double sparse linear regression, where the parameter of interest is simultaneously element-wise and group-wise sparse. This problem is an important instance of the simultaneously structured model -- an actively studied topic in statistics and machine learning. In the noi…
Study shows efficient algorithms for noiseless linear regression require quadratic sample complexity in contamination rate.
problem Efficient algorithms for noiseless linear regression under Gaussian covariates with oblivious contamination.
method Formal evidence using Statistical Query complexity.
result Any efficient Statistical Query algorithm requires VSTAT complexity at least Ω(d^(1/2)/α^2).
Triangular flows ensure statistical consistency and fast rates in generative modeling.
problem Ensuring statistical consistency and fast rates in generative models.
method Statistical guarantees and sample complexity bounds for triangular flow models using empirical process theory.
result Established statistical consistency and finite sample convergence rates for Kullback-Leibler estimator of Knöthe-Rosenblatt measure coupling.
Computing equilibrium states in condensed-matter many-body systems, such as solvated proteins, is a long-standing challenge. Lacking methods for generating statistically independent equilibrium samples in "one shot", vast computational effort is invested for simulating these system in small steps, e.g., using Molecular…
The study examines how weight sharing, equivariance, and locality affect the sample complexity of neural networks.
problem Understanding the impact of design choices on the generalization error of neural networks.
method Statistical learning theory applied to single hidden layer networks with weight sharing, equivariance, and locality.
result Lower and upper bounds for sample complexity are derived, showing that locality has benefits but comes with a trade-off.
We uncover scaling laws and statistical structure in complex datasets.
problem Understanding universal traits in complex datasets.
method Analogizing data to physical systems, using statistical physics and RMT.
result Real-world datasets and Gaussian data with long-range correlations share the same RMT universality class.
Identifies bilinear systems from a single trajectory with optimal sample complexity.
problem Learning bilinear systems from a single trajectory of states and inputs.
method Uses a mild marginal mean-square stability assumption and martingale small-ball condition.
result Sample complexity and statistical error rates are optimal.
This guide explains statistical distances for evaluating generative models.
problem Evaluating the quality of samples from generative models.
method Four statistical distances: SW, C2ST, MMD, FID.
result Different distances can yield varying results on similar data.