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 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.
In the past decade, sparse principal component analysis has emerged as an archetypal problem for illustrating statistical-computational tradeoffs. This trend has largely been driven by a line of research aiming to characterize the average-case complexity of sparse PCA through reductions from the planted clique (PC) con…
SLR tackles sparse linear regression problems, showing hardness for efficient algorithms.
problem Sparse linear regression with noisy data and k-sparse solutions.
method Reduction from lattice problems to SLR instances, showing hardness.
result Hardness of SLR instances, even for isotropic Gaussian design matrices.
New analysis shows halting time is predictable for large models, improving optimization efficiency.
problem Understanding the average-case complexity of optimization algorithms for large-scale models.
method Average-case analysis of first-order methods on random least squares and neural networks.
result Halting time is independent of input distribution, leading to tighter convergence rates.
We investigate the average-case complexity of decision problems for finitely generated groups, in particular the word and membership problems. Using our recent results on ``generic-case complexity'' we show that if a finitely generated group G has the word problem solvable in subexponential time and has a subgroup of…
CDP reduces point cloud dimensions by preserving detour-induced local non-convexity.
problem Preserving local non-convexity in point cloud dimensionality reduction.
method CDP builds a k-NN graph, identifies admissible pairs, aggregates normalized directions, and uses top-k eigenvectors for projection.
result CDP provides verifiable guarantees on post-projection distortion and direction energy.
Average teaching complexity for locating target regions among halfspace intersections is Θ(d).
problem Teaching the location of a target region among intersections of halfspaces.
method Novel insights from computational geometry to count convex polytopes and faces.
result Average-case teaching complexity is Θ(d), contrasting with Θ(n) worst-case complexity.
The paper improves error bounds for Bayesian quadrature in noisy settings.
problem Improving error bounds for Bayesian quadrature in noisy settings.
method Develops a two-step meta-algorithm to relate average-case quadrature error to L2-function approximation error. result Provides new average-case results for various kernels and noise settings.
This article considers algorithmic and statistical aspects of linear regression when the correspondence between the covariates and the responses is unknown. First, a fully polynomial-time approximation scheme is given for the natural least squares optimization problem in any constant dimension. Next, in an average-case…
This paper investigates the average-case time complexity of certifying RIP matrices.
problem Certifying the restricted isometry property (RIP) for large sparsity levels in random Gaussian matrices.
method Analysis of the low-degree likelihood ratio to determine the average-case time complexity.
result Subexponential runtime of NildeΩ(s2/M) is required for certifying RIP matrices. AMP algorithms can be efficiently simulated by SDPs even with corrupted data.
problem Optimizing average-case optimization problems with corrupted data.
method Local statistics hierarchy semidefinite programs (SDPs) simulate AMP algorithms robustly.
result Robust guarantees for many AMP algorithms are offered, contrasting with strong lower bounds for SDPs.
This paper strengthens the computational separation between multimodal and unimodal learning, showing unimodal learning is hard on typical instances.
problem Theoretical justification for empirical success of multimodal machine learning.
method Introduced a stronger average-case computational separation between unimodal and multimodal learning.
result For typical instances, unimodal learning is computationally hard, while multimodal learning is easy.
The paper analyzes the effectiveness of principal component regression with varying numbers of features.
problem The study examines the performance of principal component regression with different numbers of selected features.
method The analysis considers the least squares linear regression over uncorrelated Gaussian features selected in decreasing variance order. It also analyzes the prediction error in the average-case setting as the number of features and samples grow.
result The prediction error shows a 'double descent' shape as the number of features increases, and conditions are established for achieving minimum risk in the interpolating regime.
Pairwise comparison data arises in many domains, including tournament rankings, web search, and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items, we study the problem of estimating the underlying comparison probabilities under the assumption of strong stochastic transitivity (SST). We…
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.
Quantum circuits are hard to learn on average.
problem Learning the output distributions of quantum circuits is hard.
method Statistical query model analysis.
result Learning quantum circuits requires exponentially many queries.
Proposes a new framework for balancing average- and worst-case performance in machine learning.
problem Robustness issues in machine learning, especially in safety-critical domains.
method Probabilistic robustness framework that balances average- and worst-case performance.
result Effective algorithm balances average- and worst-case performance with lower computational cost.
Transformers excel at sparse token selection, surpassing FCNs in both worst and average cases.
problem Sparse token selection task
method One-layer transformer trained with gradient descent
result Transformers learn sparse token selection and exhibit strong out-of-distribution length generalization
The restricted isometry property (RIP) for design matrices gives guarantees for optimal recovery in sparse linear models. It is of high interest in compressed sensing and statistical learning. This property is particularly important for computationally efficient recovery methods. As a consequence, even though it is in …
Data structure for Heegaard splittings reduces complexity.
problem Representing Heegaard splittings efficiently.
method Data structure for normal curves with respect to triangulations.
result Exponential gains in space complexity for certain families.
New framework analyzes SGD dynamics in large samples and dimensions.
problem Analyzing stochastic gradient descent in large-scale settings.
method Inspired by random matrix theory, new framework for fixed stepsize and finite sum settings.
result SGD dynamics become deterministic in the large sample and dimensional limit, governed by a Volterra integral equation.
Analysis of momentum methods on quadratic models, showing SGD's superiority.
problem Analysis of stochastic gradient algorithms with momentum on quadratic models.
method Inspired by random matrix theory, exact characterization of loss values.
result Stochastic heavy-ball momentum does not improve over SGD in the strongly convex setting.
Options are generally learned by using an inaccurate environment model (or simulator), which contains uncertain model parameters. While there are several methods to learn options that are robust against the uncertainty of model parameters, these methods only consider either the worst case or the average (ordinary) case…
Barren plateaus are not an average-case phenomenon, but a highly non-unique problem.
problem Avoiding barren plateaus in neural network training
method First-moment framework for initialization strategies
result Many families of inequivalent initialization strategies can avoid concentration
The Lasso performs well in ultra-sparse linear models with finite support size.
problem Performance analysis of Lasso in ultra-sparse linear models.
method Novel application of replica method from statistical physics, rigorous analysis of average case performance.
result Average performance of Lasso assessed without scaling assumptions, offering sample complexity bounds.
New attacks exploit neural network energy and latency, increasing costs by 10-200x.
problem Energy and latency vulnerabilities in neural networks.
method Crafted sponge examples to maximize energy and latency.
result Adversaries can increase energy consumption by 10-200x and delay decisions.
Detects dense subhypergraphs in random hypergraphs using low-degree polynomials.
problem Detecting a planted dense subhypergraph in a random hypergraph model.
method Degree-n^o(1) polynomials of adjacency tensor entries.
result Thresholds for detection in different density regimes.
Online TERM improves robustness and fairness in streaming data.
problem Streaming data's lack of worst-case fairness and robustness in ERM.
method Proposes an online TERM formulation to balance average-case accuracy with worst-case fairness and robustness.
result Negative tilting effectively suppresses outlier influence, positive tilting improves recall with minimal precision loss.
Tackles the computational hardness of HPC detection, conjecturing equivalence to PC detection.
problem Computational hardness of hypergraphic planted clique detection.
method No specific method mentioned; focuses on conjecturing equivalence.
result Equivalence of computational hardness between HPC and PC detection.
We augment adversarial training (AT) with worst case adversarial training (WCAT) which improves adversarial robustness by 11% over the current state-of-the-art result in the ℓ2 norm on CIFAR-10. We obtain verifiable average case and worst case robustness guarantees, based on the expected and maximum values of the…
Backward exploration reduces sample complexity in policy evaluation.
problem Empirical policy evaluation in reinforcement learning.
method Backward exploration algorithms from high-cost states.
result Reduced average-case sample complexity to O(logS). This work explores the trade-offs between stability and accuracy in statistical estimation.
problem Understanding the statistical cost of algorithmic stability.
method Statistical decision-theoretic perspective, focusing on worst-case and average-case stability.
result Optimal stable estimators for mean estimation and regression settings are developed, revealing trade-offs between stability and accuracy.
This article attempts to place the emergence of probabilistic numerics as a mathematical-statistical research field within its historical context and to explore how its gradual development can be related both to applications and to a modern formal treatment. We highlight in particular the parallel contributions of Sul'…
New algorithms optimize spectral risk measures, improving interpolation between average and worst-case performance.
problem Optimizing spectral risk measures for learning systems.
method Developed stochastic algorithms to optimize spectral risk measures by characterizing their subdifferential and addressing challenges like biasedness of subgradient estimates and non-smoothness.
result Our approach outperforms out-of-the-box stochastic subgradient and dual averaging methods in optimizing spectral risk measures.
Lower class selectivity makes networks more robust to natural perturbations but more vulnerable to adversarial attacks.
problem Understanding how class selectivity affects robustness to different types of perturbations in neural networks.
method Investigated the relationship between class selectivity and robustness to natural and adversarial perturbations in neural networks.
result Lower class selectivity increases robustness to natural perturbations but decreases robustness to adversarial attacks.
A new algorithm avoids worst-case outcomes in risky contexts.
problem Risk-averse behavior in contextual bandits is challenging.
method Developed a first risk-averse contextual bandit algorithm with online regret guarantees.
result First algorithm with an online regret guarantee for risk-averse contextual bandits.
Study active learning of PTFs with derivative access.
problem Active learning of polynomial threshold functions (PTFs).
method Algorithm for active learning degree-d univariate PTFs with derivative access. result Computational efficient algorithm for active learning degree-d univariate PTFs. Low-rank tensor regression, a new model class that learns high-order correlation from data, has recently received considerable attention. At the same time, Gaussian processes (GP) are well-studied machine learning models for structure learning. In this paper, we demonstrate interesting connections between the two, espe…
How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension d? Previous works have shown that even for d=1 the amount of information may be unbounded (tend to ∞ with the universe size). Can it be that all concepts in the class require leaking a large amount of inform…
Adaptive meta-learning improves few-shot learning and federated learning performance.
problem Improving few-shot learning and federated learning performance.
method Adaptive gradient-based meta-learning methods integrating online convex optimization and sequential prediction algorithms.
result Improved meta-test-time performance on standard problems in few-shot learning and federated learning.
We present arguments for the formulation of unified approach to different standard continuous inference methods from partial information. It is claimed that an explicit partition of information into a priori (prior knowledge) and a posteriori information (data) is an important way of standardizing inference approaches …
This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph G(N,q), where the edge probability within the community exceeds q by a constant factor. Assuming the hardness of the planted clique detection problem, we show that the computatio…
Researchers prove it's impossible to partially recover graph alignments in certain conditions.
problem Recovering vertex correspondence between two random graphs with correlated edges.
method Used the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.
result Proved an impossibility result for partial recovery in the sparse regime with constant average degree and correlation.
Many active learning methods belong to the retraining-based approaches, which select one unlabeled instance, add it to the training set with its possible labels, retrain the classification model, and evaluate the criteria that we base our selection on. However, since the true label of the selected instance is unknown, …
Orthogonal Matching Pursuit (OMP) has long been considered a powerful heuristic for attacking compressive sensing problems; however, its theoretical development is, unfortunately, somewhat lacking. This paper presents an improved Restricted Isometry Property (RIP) based performance guarantee for T-sparse signal reconst…
RePULSe improves language model alignment by reducing undesired outputs without sacrificing overall performance.
problem Aligning language models with human preferences while minimizing undesired outputs.
method Integrates probabilistic inference into RL training to reduce undesired outputs.
result RePULSe achieves a better balance between expected reward and undesired output probability.
The paper develops efficient algorithms for sampling from random spanning trees and determinantal point processes.
problem Sampling from strongly Rayleigh distributions efficiently.
method Optimal sublinear sampling algorithms for random spanning trees and determinantal point processes.
result Achieves optimal sublinear sampling for strongly Rayleigh distributions.