Survey on using low-degree polynomials to assess statistical tasks complexity.
problem Understanding the complexity of statistical tasks using polynomial functions.
method Applying low-degree polynomials to measure the complexity of statistical tasks, including detection, recovery, and estimation.
result Low-degree polynomials provide a framework to predict and explain statistical-computational tradeoffs.
Reduces average-case complexity of sparse PCA from weak PC conjectures.
problem Characterizing the average-case complexity of sparse PCA.
method Reduction from planted clique conjecture to spiked covariance model.
result First full characterization of computational barrier in spiked covariance model, providing tight lower bounds at all sparsities.
How should statistical procedures be designed so as to be scalable computationally to the massive datasets that are increasingly the norm? When coupled with the requirement that an answer to an inferential question be delivered within a certain time budget, this question has significant repercussions for the field of s…
New data structure identifies close match from multiple distributions.
problem Identify the closest distribution to a given sample.
method Developed a sublinear-time data structure for identifying the closest distribution.
result First data structure that identifies the closest distribution in sublinear time.
New insights link diverse statistical problems via secret leakage planted clique.
problem Statistical-computational gaps in inference problems.
method Secret leakage planted clique as a new hardness assumption for reductions.
result Establishes tight statistical-computational tradeoffs for various problems.
First DP algorithm for Wasserstein barycenters on private data.
problem Computing Wasserstein barycenters on private datasets.
method Differentially private algorithms for Wasserstein barycenters.
result High-quality private barycenters with strong accuracy-privacy tradeoffs.
A statistical framework for removing unwanted data domains in machine learning.
problem Removing unwanted data domains in machine learning while preserving desired performance.
method Modeling domains as probability distributions and using hypothesis testing to select samples to remove.
result Characterization of allowable edited data distributions and removal-preservation Pareto frontiers for various distribution families.
Efficiently transforms Gaussian data to simulate various target distributions.
problem Generating observations from different target distributions given a single Gaussian observation.
method Designs computationally efficient procedures to approximate target distributions.
result Establishes reduction-based computational lower bounds for high-dimensional statistical models.
ParK efficiently solves kernel ridge regression for large datasets.
problem Large-scale kernel ridge regression efficiency and accuracy.
method Partitioning feature space with random projections and iterative optimization.
result Provably maintains statistical accuracy with reduced space and time complexity.
New insights into statistical and computational limits for mixed sparse linear regression.
problem Recovering two sparse signals from noisy linear measurements.
method Analysis of low-degree polynomials and a simple thresholding algorithm.
result Identification of a smooth information-computation tradeoff and order-optimality of the thresholding algorithm.
This article is the rejoinder for the paper "Probabilistic Integration: A Role in Statistical Computation?" to appear in Statistical Science with discussion. We would first like to thank the reviewers and many of our colleagues who helped shape this paper, the editor for selecting our paper for discussion, and of cours…
Statistical-computational gap found in aligning multiple Gaussian graphs.
problem Aligning multiple Gaussian graphs with unknown signals.
method Generalized informational threshold and computational barrier analysis.
result Existence of a statistical-computational gap in multiple Gaussian graph alignment.
Improved statistical computation through efficient matrix sampling.
problem Reducing computational cost in large-scale statistical methods.
method Accumulative sub-sampling method to improve statistical efficiency.
result Effective matrix size control improves computational efficiency.
Study on using random subspaces for ERM with various loss functions.
problem Improving learning accuracy with computational savings from random subspaces.
method Random subspaces of a hypothesis space, considering data-dependent subspaces.
result Unified analysis showing computational efficiency can be improved without performance loss.
We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hid…
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.
The paper explores how supervision level affects both statistical accuracy and computational efficiency in weakly supervised binary classification.
problem The impact of label flip probability on statistical and computational efficiency in weakly supervised binary classification.
method Information-theoretic and computational boundaries were established to characterize the relationship between supervision level and performance.
result The gap between statistical and computational boundaries narrows as the supervision level increases, indicating improved computational efficiency with more supervision.
New methods solve tensor-on-tensor regression with unknown rank, revealing benefits of over-parameterization.
problem Connecting tensor responses to tensor covariates with unknown intrinsic rank.
method Riemannian gradient descent and Riemannian Gauss-Newton methods for tensor-on-tensor regression.
result Riemannian optimization methods converge linearly and quadratically to a statistically optimal estimate in rank over-parameterized settings.
Study shows computational limits for robust classification tasks, leading to cryptographic implications.
problem Computational limitations in learning robust classifiers for classification tasks.
method Extending previous work on statistical/computational tradeoffs, using average-case hard functions and one-way functions.
result Computational hardness of learning robust classifiers even when efficient non-robust classifiers exist.
Paper shows statistical-computational gaps in learning sparse mixtures and robust estimation.
problem Statistical-computational gaps in learning sparse mixtures and robust estimation.
method Average-case reduction techniques, Imbalanced Sparse Gaussian Mixtures, and algorithmic change of measure.
result New hardness results for robust sparse mean estimation, semirandom planted dense subgraph, and universality principle for sparse mixture problems.
New computational lower bounds for clustering and related problems.
problem Statistical-computational gaps in high-dimensional clustering problems.
method Investigation of low-degree polynomials in latent space models to derive lower bounds.
result New and sharper computational lower bounds for clustering, sparse clustering, and biclustering.
Noise Sensitivity Exponent controls statistical-computational gaps in learning.
problem Understanding when learning is statistically possible yet computationally hard in high-dimensional statistics.
method Investigating statistical-computational gaps in single- and multi-index models using Noise Sensitivity Exponent.
result Noise Sensitivity Exponent governs statistical-computational gaps in high-dimensional learning.
Greedy training of recursive partitioning estimators faces a computational barrier when the true function doesn't satisfy a specific property.
problem Computational inefficiency of greedy training for recursive partitioning estimators.
method Analysis of greedy training for sparse regression functions over binary features.
result Greedy training requires exponential samples when the true function doesn't satisfy a specific property (MSP), but only logarithmic samples when it does.
New method uses almost orthonormal bases to prove low-degree lower bounds in complex statistical models.
problem Proving statistical-computational gaps in high-dimensional models with planted structures.
method Constructing an almost orthonormal polynomial basis under the planted distribution.
result Established new low-degree lower bounds for various complex models.
Lower bounds show density estimation requires linear samples or query time.
problem Statistical-computational trade-offs in density estimation.
method Lower bound analysis on data structures.
result Lower bounds demonstrate statistical-computational trade-offs for density estimation.
A research frontier has emerged in scientific computation, wherein numerical error is regarded as a source of epistemic uncertainty that can be modelled. This raises several statistical challenges, including the design of statistical methods that enable the coherent propagation of probabilities through a (possibly dete…
We study the fundamental tradeoffs between computational tractability and statistical accuracy for a general family of hypothesis testing problems with combinatorial structures. Based upon an oracle model of computation, which captures the interactions between algorithms and data, we establish a general lower bound tha…
The bias-variance tradeoff doesn't always apply in neural networks, contradicting textbook claims.
problem The bias-variance tradeoff is not universally applicable in neural networks, contradicting textbook teachings.
method Extensive experiments and analysis on neural networks, revisiting Geman et al. (1992) experiments.
result Neural networks do not exhibit a bias-variance tradeoff when increasing network width, contradicting textbook claims.
Study wSAA for contextual decisions, improving uncertainty quantification under computational constraints.
problem Uncertainty quantification limitations in wSAA for contextual stochastic optimization.
method Establish central limit theorems and asymptotic-normality-based confidence intervals for optimal costs.
result Over-optimizing can mitigate misspecification and preserve asymptotic normality, albeit at a slower convergence rate.
Develops methods to estimate high rank tensors from noisy data.
problem Estimating high rank tensors from noisy observations.
method Generative latent variable tensor model, polynomial-time spectral algorithm.
result Achieves computationally optimal rate for signal tensor estimation.
EFI automates statistical inference for big data.
problem Statistical inference for model parameters based on observations.
method EFI uses stochastic gradient Markov chain Monte Carlo and sparse deep neural networks.
result EFI provides higher fidelity in parameter estimation and automates the inference process.
A new tradeoff between regularization and sharpness improves model performance in overparameterized settings.
problem Improving model performance in overparameterized settings with minimum-norm interpolators.
method Proposes a regularization-sharpness tradeoff for overparameterized linear regression with an ℓ^p penalty.
result Empirical validation shows the tradeoff terms can distinguish performant linear interpolators.
Study the tradeoff between signal distortion and human perception over finite channels.
problem Characterize the distortion-perception tradeoff for finite channels with arbitrary metrics.
method Solve linear programming problems to compute the distortion-perception function and optimal reconstructions.
result DP function is piecewise linear in the perception index.
New study shows limits of low-degree algorithms in finding large independent sets in sparse hypergraphs.
problem Finding large independent sets in sparse random hypergraphs.
method Low-degree polynomial algorithms are analyzed to determine their limits.
result Low-degree algorithms can find independent sets of density up to \(\left(\frac{\log d}{(r-1)d}
ight)^{1/(r-1)}\), but no larger.
We perform the first study of the tradeoff space of access methods and replication to support statistical analytics using first-order methods executed in the main memory of a Non-Uniform Memory Access (NUMA) machine. Statistical analytics systems differ from conventional SQL-analytics in the amount and types of memory …
The paper studies adversarial training for linear regression models.
problem Understanding the tradeoffs between robust and standard accuracy in adversarial training.
method Characterizes the fundamental tradeoff and specific adversarial training approach for linear regression with Gaussian features.
result Precise characterization of the standard and robust accuracy tradeoff in high-dimensional settings.
Paper explores tradeoff between standard and robust accuracy for latent models.
problem Tradeoff between standard accuracy and robust accuracy in adversarial training.
method Revisits adversarial training for latent models, considering Gaussian mixture and generalized linear models.
result Low-dimensional manifold structure mitigates the tradeoff between standard and robust accuracy.
Proposes a new adversarial model to avoid accuracy vs. adversarial accuracy tradeoff.
problem Inherent tradeoff between accuracy and adversarial accuracy in existing adversarial robustness definitions.
method Introduces Voronoi-epsilon adversary that balances perturbation constraints.
result Voronoi-epsilon adversary avoids accuracy vs. adversarial accuracy tradeoff even with large ε. We propose a data-driven framework for optimizing privacy-preserving data release mechanisms to attain the information-theoretically optimal tradeoff between minimizing distortion of useful data and concealing specific sensitive information. Our approach employs adversarially-trained neural networks to implement random…
Researchers study fairness-accuracy tradeoffs in predictive models for multiple groups.
problem Understanding the tradeoff between fairness and accuracy in models serving multiple demographic groups.
method Characterizing the fairness-accuracy (FA) Pareto frontier, approximating it from limited data, and bounding the worst-case gap.
result Derivation of worst-case-optimal estimators and uniform finite-sample bounds for the entire FA frontier.
Proposes a GNN-based method for robust missing data imputation.
problem Missing data imputation in scientific datasets.
method Graph denoising autoencoder with adversarially-trained GNNs.
result Robustly outperforms state-of-the-art approaches for MDI.
The paper explores robustness in linear regression models under adversarial attacks.
problem The impact of test-time adversarial attacks on linear regression models.
method Quantitative estimates and phase transitions analysis.
result Precise characterization of tradeoffs between adversarial robustness and accuracy.
Adversarial training can degrade standard accuracy even when optimal for robust accuracy.
problem Tradeoff between standard and robust accuracy in adversarial training.
method Analyzes adversarial training's impact on standard accuracy, even when optimal for robust accuracy.
result Even with optimal predictors, adversarial training can still degrade standard accuracy.
The paper analyzes the bias-variance tradeoff for Bregman divergences.
problem Understanding the bias-variance tradeoff for Bregman divergences.
method Analyzes the bias-variance tradeoff through operations in dual space.
result Derives several results including a generalized law of total variance and ensembling operations.
CDC-FM improves generative model quality-generalization tradeoff by regularizing with geometry-aware noise.
problem Tradeoff between high sample quality and memorization in deep generative models.
method Introduces Carré du champ flow matching (CDC-FM) that replaces homogeneous noise with anisotropic Gaussian noise capturing latent data manifold geometry.
result CDC-FM consistently offers better quality-generalization tradeoff across diverse datasets and architectures.
This paper explores tradeoffs between standard and adversarial risks in distributionally adversarial training.
problem Understanding the impact of adversarial training on standard risk and adversarial risk.
method Study of distributionally adversarial training with different learning settings and models.
result Derives Pareto-optimal tradeoff curves between standard and adversarial risks.
Estimation under missing data shows computational and statistical limits for Gaussian data.
problem Estimation of population parameters in high-dimensional data with missing data.
method Analysis of computational and statistical limits for mean and covariance estimation, and linear regression.
result Statistical-computational gaps exist for mean and covariance estimation, but not for linear regression.
This paper considers portfolio construction in a dynamic setting. We specify a loss function comprised of utility and complexity components with an unknown tradeoff parameter. We develop a novel regret-based criterion for selecting the tradeoff parameter to construct optimal sparse portfolios over time.