Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.
problem High-dimensional hypothesis testing and information-computation gaps.
method Analysis of statistical query framework and low-degree polynomials.
result Statistical query algorithms and low-degree polynomials are almost equivalent in power under mild conditions.
Unified approach for quantum and classical learning from evaluation oracles.
problem Learning from evaluation oracles in quantum and classical settings.
method Inspired by Kearns' SQ and Valiant's weak evaluation oracle, a unified framework is established.
result Characterizes query complexity for learning linear function classes and extends learnability results for quantum circuits.
Unified model for interactive estimation with improved learnability measure.
problem Improving learnability in interactive estimation models.
method Introducing a combinatorial measure (dissimilarity dimension) and a general algorithm with polynomial bounds.
result Unified model subsumes statistical-query learning and structured bandits.
Survey of statistical queries and their applications.
problem Understanding statistical queries and their applications.
method Exploration of statistical queries model, definitions, and connections to learnability.
result Connections to learnability and applications in optimization, evolvability, and differential privacy.
New framework limits SGD for multi-index models, addressing SQ framework shortcomings.
problem Limitations of SGD for multi-index models beyond SQ framework.
method Developed a new non-SQ framework to study SGD limitations for single-index and multi-index models.
result Applies to broad settings and architectures, including neural networks.
Proposes CRA framework for certifying fair predictive models.
problem Certifying fairness of predictive models trained on biased data.
method Formulates CRA for fairness queries, uses background knowledge and limited target population stats.
result Builds certifiably fair predictive models on target population.
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 …
Active inference framework improves U-statistic estimation efficiency.
problem Costly acquisition of labels for U-statistics. method Active inference framework with optimal sampling rule.
result Substantial gains in estimation efficiency over baseline methods.
A new method for private query release using Johnson-Lindenstrauss projection.
problem Private release of query answers with minimal privacy loss.
method Random projection of query answers to a lower dimension, followed by noise addition.
result Optimal worst-case sample complexity for answering a workload of k queries.
New bounds show complex neural networks need many queries to learn.
problem Learning non-polynomial activation functions with Gaussian marginals.
method Gradient boosting procedure to amplify lower bounds on SQ dimension of neural networks.
result Statistical-query lower bounds for ReLU regression with 2ncε queries. Optimizes reward learning design for complex tasks using nonparametric methods.
problem Challenges in specifying reward functions for complex tasks.
method Models rewards and policies as nonparametric functions in RKHSs, derives risk bounds, and optimizes query design.
result Derives non-asymptotic excess risk bounds and finite sample statistical rates for reward learning.
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.
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…
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…
FAQ efficiently evaluates LLMs with statistical guarantees using adaptive query selection.
problem Efficiently evaluating many LLMs on a large suite of benchmarks is expensive.
method FAQ uses Bayesian factor models, adaptive sampling, and proactive active inference to select queries.
result FAQ delivers up to 5x effective sample size gains over baselines, matching CI width with fewer queries.
Statistical Query lower bound shows difficulty in list-decodable linear regression.
problem List-decodable linear regression with adversarial corruption.
method Statistical Query (SQ) lower bound analysis.
result Lower bound of dpoly(1/α) for list-decodable linear regression. The study sets limits on how well halfspaces can be learned when labels are corrupted.
problem Learning halfspaces in the presence of Massart noise.
method Statistical query (SQ) lower bounds.
result No SQ algorithm can achieve misclassification error better than the corruption rate η with superpolynomial accuracy or a superpolynomial number of queries. New method generates private synthetic data with optimal utility for smooth queries.
problem Achieving strong utility guarantees for meaningful downstream analysis of sensitive datasets.
method Proposes a polynomial-time algorithm for generating (ε,δ)-differentially private synthetic data with minimax optimal error rates for smooth queries. result Achieves a minimax error rate of Ok,d(n−min{1,dk}) for k-smooth queries, up to a log(n) factor. Adapts data analysis for growing data, improving generalization guarantees.
problem Challenges of overfitting and statistical validity in adaptive workflows with growing data.
method Generalizes adaptive analysis on dynamic data, incorporating time-varying empirical accuracy bounds and mechanisms.
result First generalization bounds for adaptive analysis on dynamic data, matching prior works' improvement over data splitting.
Framework generates precise synthetic populations for scalable modeling.
problem Generating accurate synthetic populations without personal data.
method Constraint-programming framework encoding aggregated statistics and structural relations.
result Exact control of demographic profiles without requiring microdata.
Study finds a method to discover causal relationships that are invariant to marginal distributions.
problem Current causal discovery methods are sensitive to marginal distributions, leading to unreliable results.
method Proposes a non-parametric estimator that marginalizes the marginals to find intrinsic causal relationships.
result The proposed method yields causal estimators competitive with current methodologies and emphasizes uncertainty.
New algorithm learns disjunctions faster than previous methods.
problem Learning Boolean disjunctions in the agnostic PAC model.
method Developed an agnostic learner with complexity 2ildeO(n1/3). result First separation between SQ and CSQ models in distribution-free agnostic learning.
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.
New algorithms learn multi-index models via harmonic analysis, achieving statistical and computational trade-offs.
problem Learning multi-index models with unknown projections of input data.
method Exploiting the equivariance of the problem under the orthogonal group, we derive lower bounds and construct spectral algorithms based on harmonic tensor unfolding.
result Achieve statistical and computational trade-offs between sample and runtime complexity.
We provide a new theoretical analysis framework to investigate online gradient descent in the dynamic environment. Comparing with the previous work, the new framework recovers the state-of-the-art dynamic regret, but does not require extra gradient queries for every iteration. Specifically, when functions are α stron…
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.
Probabilistic representations, such as Bayesian and Markov networks, are fundamental to much of statistical machine learning. Thus, learning probabilistic representations directly from data is a deep challenge, the main computational bottleneck being inference that is intractable. Tractable learning is a powerful new p…
Optimized Franz-Parisi criterion matches SQ lower bounds for various statistical models.
problem Understanding computational hardness in statistical inference.
method Proposed and refined Franz-Parisi criterion, established equivalence with SQ lower bounds.
result Optimized Franz-Parisi criterion is equivalent to Statistical Query (SQ) lower bounds.
New lower bounds show learning intersections of halfspaces is hard even for a few halfspaces.
problem Learning intersections of halfspaces in polynomial time under standard assumptions.
method Unified connection to parallel pancakes distribution for proving hardness.
result Learning ω(loglogN) halfspaces in dimension N requires super-polynomial time under standard assumptions. Develops a framework for modeling set-valued data in continuous-time.
problem Handling sequences where each event is associated with a set of items.
method General framework for modeling set-valued data, developed inference methods, and importance sampling techniques.
result Orders-of-magnitude improvements in efficiency for probabilistic queries over direct sampling.
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→[−1,1], the oracle returns an estimate of Ex∼D[φ(x)] within some tolerance τφ that roughly corresponds t…
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.
Paper develops online statistical inference methods for stochastic optimization using Kiefer-Wolfowitz algorithms.
problem Online statistical inference of model parameters in stochastic optimization problems.
method Kiefer-Wolfowitz algorithm with random search directions, asymptotic distribution analysis.
result Developed valid confidence intervals for online statistical inference.
We propose a framework for Semi-Supervised Active Clustering framework (SSAC), where the learner is allowed to interact with a domain expert, asking whether two given instances belong to the same cluster or not. We study the query and computational complexity of clustering in this framework. We consider a setting where…
Study shows limitations and possibilities of learning quantum circuit output distributions.
problem Learnability of output distributions of local quantum circuits.
method Investigated within two oracle models: statistical query model and direct sample access model.
result Output distributions of super-logarithmic depth Clifford circuits are not efficiently learnable in the statistical query model.
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…
The paper bridges theory and practice in query-driven selectivity learning.
problem Insufficient theoretical understanding of query-driven selectivity learning.
method Demonstrates learnability of selectivity predictors and establishes favorable OOD generalization error bounds.
result Theoretical advances improve OOD generalization of query-driven selectivity models.
Proposes an active RBI framework using Rényi information measures for more informed decision-making.
problem Optimal latent variable estimates in real-time settings with streaming noisy observations.
method Unified inference and query selection steps through Rényi entropy and α-divergence; new objective called Momentum for exploration.
result Analytically demonstrates superior performance compared to conventional methods like mutual information.
We describe a framework for designing efficient active learning algorithms that are tolerant to random classification noise and are differentially-private. The framework is based on active learning algorithms that are statistical in the sense that they rely on estimates of expectations of functions of filtered random e…
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…
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.
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.
problem Valuing data without specific task assumptions.
method Estimating data diversity and relevance through queries without raw data.
result Estimates capture the diversity and relevance of seller's data for the buyer.
Optimal query allocation improves extractive QA efficiency with LLMs.
problem Efficiency and reliability in extractive question answering with LLMs.
method Learning-to-Defer framework that allocates queries to specialized models.
result Enhanced answer reliability with reduced computational overhead.
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.
Paper introduces data-dependent SSP for private linear and logistic regression.
problem Private linear and logistic regression with better performance.
method Data-dependent sufficient statistic perturbation (SSP) for linear and logistic regression.
result Data-dependent SSP outperforms state-of-the-art methods for linear and logistic regression.
Paper solves k-sparse parity problem with sign SGD, matching SQ lower bound.
problem Solving k-sparse parity problems efficiently.
method Sign stochastic gradient descent on neural networks.
result Matches Statistical Query lower bound for solving k-sparse parity problems.
In query learning, the goal is to identify an unknown object while minimizing the number of "yes" or "no" questions (queries) posed about that object. A well-studied algorithm for query learning is known as generalized binary search (GBS). We show that GBS is a greedy algorithm to optimize the expected number of querie…