arXiv research

Survey of statistical queries and their applications.

Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.

New bounds show complex neural networks need many queries to learn.

FAQ efficiently evaluates LLMs with statistical guarantees using adaptive query selection.

New algorithm learns disjunctions faster than previous methods.

Statistical Query lower bound shows difficulty in list-decodable linear regression.

A new method for private query release using Johnson-Lindenstrauss projection.

Study shows limitations and possibilities of learning quantum circuit output distributions.

Tensor PCA problem analyzed with statistical query lower bounds.

Unified model for interactive estimation with improved learnability measure.

Active learning aims to obtain a classifier of high accuracy by using fewer label requests in comparison to passive learning by selecting effective queries. Many active learning methods have been developed in the past two decades, which sample queries based on informativeness or representativeness of unlabeled data poi…

Paper develops online statistical inference methods for stochastic optimization using Kiefer-Wolfowitz algorithms.

Quantum circuits are hard to learn on average.

Unified approach for quantum and classical learning from evaluation oracles.

Adapts data analysis for growing data, improving generalization guarantees.

Study finds a method to discover causal relationships that are invariant to marginal distributions.

We formalize the notion of nesting probabilistic programming queries and investigate the resulting statistical implications. We demonstrate that while query nesting allows the definition of models which could not otherwise be expressed, such as those involving agents reasoning about other agents, existing systems take …

New framework limits SGD for multi-index models, addressing SQ framework shortcomings.

Overlapping clusters are common in models of many practical data-segmentation applications. Suppose we are given $n$ elements to be clustered into $k$ possibly overlapping clusters, and an oracle that can interactively answer queries of the form "do elements $u$ and $v$ belong to the same cluster?" The goal is to recov…

Study shows computational and statistical gaps in Gaussian Single-Index Models.

In many real-world machine learning applications, unlabeled data are abundant whereas class labels are expensive and scarce. An active learner aims to obtain a model of high accuracy with as few labeled instances as possible by effectively selecting useful examples for labeling. We propose a new selection criterion tha…

Paper introduces data-dependent SSP for private linear and logistic regression.

Paper solves k-sparse parity problem with sign SGD, matching SQ lower bound.

Statistical query (SQ) algorithms are algorithms that have access to an {\em SQ oracle} for the input distribution $D$ instead of i.i.d.~ samples from $D$. Given a query function $φ:X \rightarrow [-1,1]$, the oracle returns an estimate of ${\bf E}_{ x\sim D}[φ(x)]$ within some tolerance $τ_φ$ that roughly corresponds t…

Study private query release with public data, reducing sample sizes.

The paper proposes methods to infer from privacy-protected data using simulation-based techniques.

Near-optimal SQ hardness shows learning halfspaces with Massart noise is hard.

TRAM-DAG models bridge interpretability and flexibility in causal modeling.

New algorithm tackles dynamic query routing to multiple embedding models.

Proposes CRA framework for certifying fair predictive models.

Paper develops PAC verification for hypothesis classes and statistical algorithms.

In this paper we address cardinality estimation problem which is an important subproblem in query optimization. Query optimization is a part of every relational DBMS responsible for finding the best way of the execution for the given query. These ways are called plans. The execution time of different plans may differ b…

Optimized Franz-Parisi criterion matches SQ lower bounds for various statistical models.

Proves SQ lower bounds for learning two-hidden-layer neural networks.

Early stopping methods reduce unnecessary reasoning steps in LLMs by monitoring uncertainty signals.

The study examines how many samples are needed to minimize a noisy convex function with inaccurate gradient estimates.

We study active learning where the labeler can not only return incorrect labels but also abstain from labeling. We consider different noise and abstention conditions of the labeler. We propose an algorithm which utilizes abstention responses, and analyze its statistical consistency and query complexity under fairly nat…

Task-agnostic data valuation without validation requirements.

Lower bounds show density estimation requires linear samples or query time.

The study sets limits on how well halfspaces can be learned when labels are corrupted.

Unified study of active learning for deep neural networks.

A common problem in disciplines of applied Statistics research such as Astrostatistics is of estimating the posterior distribution of relevant parameters. Typically, the likelihoods for such models are computed via expensive experiments such as cosmological simulations of the universe. An urgent challenge in these rese…

New algorithms learn multi-index models via harmonic analysis, achieving statistical and computational trade-offs.

Hard problem of learning simple generative models from i.i.d. samples.

New algorithm for reliable learning of Gaussian halfspaces with improved sample and computational complexity.

Estimating the normalizing constant of an unnormalized probability distribution has important applications in computer science, statistical physics, machine learning, and statistics. In this work, we consider the problem of estimating the normalizing constant $Z=\int_{\mathbb{R}^d} e^{-f(x)}\,\mathrm{d}x$ to within a m…

Study shows SQ hardness for multiclass linear classification with random noise.

Gradient descent fails to learn simple neural networks efficiently.