arXiv research

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…

Average teaching complexity for locating target regions among halfspace intersections is Θ(d).

New analysis shows halting time is predictable for large models, improving optimization efficiency.

This paper investigates the average-case time complexity of certifying RIP matrices.

Quantum circuits are hard to learn on average.

This paper develops several average-case reduction techniques to show new hardness results for three central high-dimensional statistics problems, implying a statistical-computational gap induced by robustness, a detection-recovery gap and a universality principle for these gaps. A main feature of our approach is to ma…

The paper improves error bounds for Bayesian quadrature in noisy settings.

Proposes a new framework for balancing average- and worst-case performance in machine learning.

New framework analyzes SGD dynamics in large samples and dimensions.

AMP algorithms can be efficiently simulated by SDPs even with corrupted data.

Analysis of momentum methods on quadratic models, showing SGD's superiority.

Backward exploration reduces sample complexity in policy evaluation.

This paper strengthens the computational separation between multimodal and unimodal learning, showing unimodal learning is hard on typical instances.

The Lasso performs well in ultra-sparse linear models with finite support size.

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…

Transformers excel at sparse token selection, surpassing FCNs in both worst and average cases.

We study least squares linear regression over $N$ uncorrelated Gaussian features that are selected in order of decreasing variance. When the number of selected features $p$ is at most the sample size $n$, the estimator under consideration coincides with the principal component regression estimator; when $p>n$, the esti…

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 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'…

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 …

In three-dimensional computational topology, the theory of normal surfaces is a tool of great theoretical and practical significance. Although this theory typically leads to exponential time algorithms, very little is known about how these algorithms perform in "typical" scenarios, or how far the best known theoretical…

New insights link diverse statistical problems via secret leakage planted clique.

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…

SLR tackles sparse linear regression problems, showing hardness for efficient algorithms.

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 $\infty$ with the universe size). Can it be that all concepts in the class require leaking a large amount of inform…

Survey on using low-degree polynomials to assess statistical tasks complexity.

Data structure for Heegaard splittings reduces complexity.

This paper studies the problem of detecting the presence of a small dense community planted in a large Erdős-Rényi random graph $\mathcal{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…

Barren plateaus are not an average-case phenomenon, but a highly non-unique problem.

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…

New attacks exploit neural network energy and latency, increasing costs by 10-200x.

Tackles the computational hardness of HPC detection, conjecturing equivalence to PC detection.

Online TERM improves robustness and fairness in streaming data.

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 $\ell_2$ norm on CIFAR-10. We obtain verifiable average case and worst case robustness guarantees, based on the expected and maximum values of the…

This work explores the trade-offs between stability and accuracy in statistical estimation.

ACOL learns constraints from human preferences in driving simulations.

Survey of reinforcement learning guarantees with data constraints.

New algorithms optimize spectral risk measures, improving interpolation between average and worst-case performance.

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…

Paper improves Frank-Wolfe algorithm's efficiency bounds.

Lower class selectivity makes networks more robust to natural perturbations but more vulnerable to adversarial attacks.

We build a theoretical framework for designing and understanding practical meta-learning methods that integrates sophisticated formalizations of task-similarity with the extensive literature on online convex optimization and sequential prediction algorithms. Our approach enables the task-similarity to be learned adapti…

This paper tackles denoising of complex measures using optimal transport and curvature analysis.

A new algorithm avoids worst-case outcomes in risky contexts.

Study on InstaHide's security, linking to phase retrieval problem.

Study active learning of PTFs with derivative access.

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…

New findings on tensor decomposition complexity, showing polynomial functions can estimate the largest component under certain conditions.