Lower bounds on queries needed for finding stationary points in non-convex optimization.
problem Finding ε ε ε -stationary points in non-convex stochastic optimization. method Proving lower bounds on the number of queries required by stochastic first-order methods.
result Lower bounds on the number of queries required to find ε ε ε -stationary points are tight and optimal. This work sets lower bounds on the number of score queries needed for diffusion sampling.
problem Establishing information-theoretic limits on the number of score evaluations required for diffusion sampling.
method Proving lower bounds on the number of adaptive score queries needed for sampling.
result Any sampling algorithm requires at least \(\widetilde{\Omega}(\sqrt{d})\) adaptive score queries for \(d\)-dimensional distributions.
New lower bounds for sampling from log-concave distributions in higher dimensions.
problem Proving lower bounds for sampling from log-concave distributions in higher dimensions.
method Multiscale construction inspired by geometric measure theory and reduction to block Krylov algorithms.
result Query lower bounds for sampling from log-concave distributions in higher dimensions are established.
New insights into query complexity for Nash equilibrium learning.
problem Characterizing the number of queries needed to learn approximate Nash equilibria in matrix games.
method Introduced a new technique to prove lower bounds on query complexity, improving previous techniques.
result Lower bounds of order Ω ( log ( 1 K ε ) ) Ω(\log(\frac{1}{Kε})) Ω ( log ( K ε 1 )) for any ε ≤ 1 / ( c K 4 ) ε\leq 1 / (cK^4) ε ≤ 1/ ( c K 4 ) , where c c c is a constant. 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 2 n c ε 2^{n^c} ε 2 n c ε queries. Lower bounds on query complexity for reconstructing private learner's training data.
problem Query complexity of reconstructing private learner's training data.
method Minimax analysis, Rényi DP, Metric DP framework.
result First known lower bounds on adversary's query complexity for various DP learners.
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 d p o l y ( 1 / α ) d^{\mathrm{poly}(1/α)} d poly ( 1/ α ) for list-decodable linear regression. BILBO optimizes bilevel problems without repeated lower-level optimizations.
problem Challenges in bilevel optimization, especially in noisy, constrained, and derivative-free settings.
method BILevel Bayesian Optimization (BILBO) that optimizes both levels simultaneously, using confidence-bounds and function query selection.
result Theoretical and empirical evidence of BILBO's effectiveness on various problems.
This paper explores the adaptive (active) PAC (probably approximately correct) top- k k k ranking (i.e., top- k k k item selection) and total ranking problems from l l l -wise ( l ≥ 2 l\geq 2 l ≥ 2 ) comparisons under the multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output of the most favored …
Fairly allocate items with noisy queries, reducing envy.
problem Fairly allocate indivisible goods with unknown valuations.
method Use Gaussian noisy queries to find an envy-free allocation.
result The optimal number of queries scales as \( \frac{m^{2.5}}{Δ^2} \) for large negative-envy.
Lower bounds on queries for Bayesian private learning.
problem Estimating a target within error ε while keeping it hidden from an adversary.
method Lower bound proof using Fano's inequality and proportional-sampling estimators.
result Query complexity is on the order of L log ( 1 / ε ) L\log(1/\varepsilon) L log ( 1/ ε ) for accurate estimation. In adaptive data analysis, the user makes a sequence of queries on the data, where at each step the choice of query may depend on the results in previous steps. The releases are often randomized in order to reduce overfitting for such adaptively chosen queries. In this paper, we propose a minimax framework for adaptive…
Proves SQ lower bounds for learning two-hidden-layer neural networks.
problem Learning two-hidden-layer ReLU networks with Gaussian inputs.
method Refined lifting procedure to reduce Boolean PAC learning to Gaussian.
result Superpolynomial SQ lower bounds for Gaussian inputs.
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.
Lower bounds show many sampling algorithms need many gradient queries.
problem Sampling from strongly log-concave densities in high dimensions.
method Information theory and stochastic gradient methods.
result Lower bound on number of gradient queries needed.
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.
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. Gradient descent fails to learn simple neural networks efficiently.
problem Learning one-layer neural networks efficiently using gradient descent.
method Gradient descent and statistical query algorithms.
result Superpolynomial lower bounds for learning one-layer neural networks.
We show that for the problem of testing if a matrix A ∈ F n × n A \in F^{n \times n} A ∈ F n × n has rank at most d d d , or requires changing an ε ε ε -fraction of entries to have rank at most d d d , there is a non-adaptive query algorithm making O ~ ( d 2 / ε ) \widetilde{O}(d^2/ε) O ( d 2 / ε ) queries. Our algorithm works for any field F F F . This improves upon the previous…
Study reduces memory needs for active learning with enriched queries.
problem Expensive labeling costs in active learning.
method Introduces bounded memory active learning through enriched queries, introduces lossless sample compression.
result Can learn classifiers with bounded memory and query optimality.
Lower bound shows super-polynomial gap for estimating truncated Gaussian means.
problem Estimating mean of truncated Gaussian distribution with limited samples.
method Statistical Query (SQ) lower bounds for learning.
result Super-polynomial information-computation gap for the task.
We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of query learning in terms of various combinatorial quantities. Our approach is flexible and powerful enough to enough to give new and very short proofs of the efficient learnability…
We prove a \emph{query complexity} lower bound on rank-one principal component analysis (PCA). We consider an oracle model where, given a symmetric matrix M ∈ R d × d M \in \mathbb{R}^{d \times d} M ∈ R d × d , an algorithm is allowed to make T T T \emph{exact} queries of the form w ( i ) = M v ( i ) w^{(i)} = Mv^{(i)} w ( i ) = M v ( i ) for i ∈ { 1 , … , T } i \in \{1,\dots,T\} i ∈ { 1 , … , T } , where v ( i ) v^{(i)} v ( i ) …
New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.
problem Learning mixtures of Gaussians with bounded covariance matrices is hard.
method Statistical Query (SQ) lower bounds.
result Any SQ algorithm requires complexity at least d Ω ( 1 / ε ) d^{Ω(1/ε)} d Ω ( 1/ ε ) for learning mixtures of bounded covariance Gaussians. Lower bounds for geodesically convex optimization show curvature negatively impacts complexity.
problem Understanding the impact of curvature on the query complexity of geodesically convex optimization.
method Building on recent lower bounds, the study proposes and proves new lower bounds for various settings of geodesically convex optimization.
result Negative curvature is detrimental to the complexity of geodesically convex optimization.
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.
Study exact partition recovery with same-cluster oracle, bounded error.
problem Exact recovery of partitions with same-cluster oracle in adversarial error.
method Novel connection to correlation clustering, Rényi-Ulam framework, upper and lower bounds, randomized algorithm analysis, adaptivity-query complexity study.
result Upper and lower bounds on worst-case query complexity, expected performance bounds of randomized algorithm.
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 ( ε , δ ) (\varepsilon,δ) ( ε , δ ) -differentially private synthetic data with minimax optimal error rates for smooth queries. result Achieves a minimax error rate of O k , d ( n − min { 1 , k d } ) O_{k,d}(n^{-\min \{1, \frac{k}{d}\}}) O k , d ( n − m i n { 1 , d k } ) for k k k -smooth queries, up to a log ( n ) \log(n) log ( n ) factor. Optimal SQ bounds for learning binary product distributions and Ising models.
problem Learning binary product distributions and Ising models robustly.
method Statistical Query (SQ) lower bounds for robust learning.
result Optimal SQ lower bounds match known algorithm error guarantees.
New research shows exponential lower bounds for planning in MDPs with linearly-realizable optimal action-value functions.
problem Determining the minimum number of queries needed for sound planners in MDPs with linear function approximation.
method Analyzing fixed-horizon and discounted MDPs with a generative model, showing lower bounds on the number of queries required.
result Sound planners need at least exponential number of queries in both fixed-horizon and discounted settings.
New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.
problem Smoothed agnostic learning of halfspaces under subgaussian distributions.
method Statistical Query (SQ) lower bound using moment-matching hard distribution and linear programming duality.
result First non-trivial lower bound on complexity nearly matches known upper bound.
Study on how many queries an adversary needs to make to match the best attack in white-box model.
problem Query complexity of adversarial attacks in machine learning models.
method Investigates the number of queries required for an adversary to match the best possible attack in the white-box model, using entropy of decision boundaries as a measure.
result Lower bound on the number of queries required for an adversary to match the best possible attack in the white-box model.
Paper proposes a 1-bit mean estimation method with near-optimal sample complexity.
problem Distributed mean estimation with 1-bit communication constraints.
method Randomized and sequentially-chosen interval queries to estimate mean.
result Sample complexity bound matches minimax lower bound with logarithmic factors.
Quadratic memory is essential for optimal convex optimization queries.
problem Optimal query complexity for convex optimization and feasibility problems.
method Lower bounds on query complexity for convex optimization and feasibility problems.
result Center-of-mass algorithms are Pareto-optimal for both convex optimization and feasibility problems.
TensorPlan shows an exponential lower bound for planning in MDPs with linearly realizable value functions.
problem Finding an exponential lower bound for planning in MDPs with linearly realizable value functions.
method TensorPlan and a few action lower bound approach.
result An exponentially large lower bound is shown for planning in MDPs with linearly realizable value functions.
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.
The paper develops algorithms to restore monotonicity in non-monotone functions.
problem Non-monotone solutions from heuristic algorithms need to be corrected.
method Develops algorithms to restore monotonicity with limited queries.
result Restores monotonicity while degrading the function value by at most ε.
Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is O ( d / ε + d / ( max { p , ε } ) 2 ) O(d/ε + d/(\max\{p, ε\})^2) O ( d / ε + d / ( max { p , ε } ) 2 ) , SQ lower bound is Ω ( d 1 / 2 / ( max { p , ε } ) 2 ) Ω(d^{1/2}/(\max\{p, ε\})^2) Ω ( d 1/2 / ( max { p , ε } ) 2 ) . Paper develops an efficient mean estimator for 1-bit communication constraints.
problem Mean estimation under 1-bit communication constraints.
method Adaptive mean estimator based on randomized threshold queries.
result Order-optimal sample complexity in various tail regimes.
Proposes efficient bounds for causal effect estimation under weak confounding.
problem Estimating causal effects with weakly confounded variables.
method Develops an efficient linear program to derive upper and lower bounds on causal effect under small entropy of unobserved confounders.
result Bounds are consistent and tighter for weakly confounded variables.
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 SQ lower bounds for NGCA without requiring chi-squared condition.
problem Proving SQ hardness for NGCA under moment-matching conditions.
method General SQ lower bound methodology applied to NGCA under moment-matching conditions.
result Proved near-optimal SQ lower bounds for NGCA without chi-squared condition.
The study establishes SQ lower bounds for learning halfspaces and ReLUs under Gaussian marginals.
problem Agnostically learning halfspaces and ReLUs under Gaussian marginals.
method Statistical Query (SQ) lower bounds analysis.
result Proves SQ lower bounds of d p o l y ( 1 / ε ) d^{\mathrm{poly}(1/ε)} d poly ( 1/ ε ) for both problems. Improved sampling from high-dimensional Gaussians using smoothed scores.
problem Sampling from high-dimensional Gaussian distributions with gradient information.
method Using smoothed scores, which are gradients of the logarithms of Gaussian-convolved densities, to overcome approximation barriers.
result Improved sampling efficiency with a complexity of \(O\left(\left(\logκ+\log(e\sqrt d/δ_{
m TV})
ight)\log(e\sqrt d/δ_{
m TV})
ight)\) smoothed-score queries.
In this paper, we initiate a rigorous theoretical study of clustering with noisy queries (or a faulty oracle). Given a set of n n n elements, our goal is to recover the true clustering by asking minimum number of pairwise queries to an oracle. Oracle can answer queries of the form : "do elements u u u and v v v belong to the…
Improved efficient robust regression with near-linear time and subquadratic samples.
problem Robust linear regression with unknown covariance matrix under Gaussian covariates.
method Near-linear time algorithm using subquadratic samples, complemented by SQ and polynomial lower bounds.
result Achieves prediction error O ( ε κ ) O(\sqrt{εκ}) O ( ε κ ) for ε κ ≲ 1 εκ\lesssim 1 ε κ ≲ 1 , improving over prior works. In this paper we study the limitations of parallelization in convex optimization. A convenient approach to study parallelization is through the prism of \emph{adaptivity} which is an information theoretic measure of the parallel runtime of an algorithm [BS18]. Informally, adaptivity is the number of sequential rounds a…
New algorithm for learning ReLU networks with Gaussian noise, improving previous results.
problem PAC learning one-hidden-layer ReLU networks with Gaussian marginals and label noise.
method First polynomial-time algorithm for k k k up to i l d e O ( log d ) ilde{O}(\sqrt{\log d}) i l d e O ( log d ) for positive coefficients, no assumptions on rank or condition number. result Proves a Statistical Query lower bound of d Ω ( k ) d^{Ω(k)} d Ω ( k ) for arbitrary real coefficients, separating learnability classes.