arXiv research

This work sets lower bounds on the number of score queries needed for diffusion sampling.

New lower bounds for sampling from log-concave distributions in higher dimensions.

New insights into query complexity for Nash equilibrium learning.

We lower bound the complexity of finding $ε$-stationary points (with gradient norm at most $ε$) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (i…

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

Lower bounds on query complexity for reconstructing private learner's training data.

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

BILBO optimizes bilevel problems without repeated lower-level optimizations.

This paper explores the adaptive (active) PAC (probably approximately correct) top-$k$ ranking (i.e., top-$k$ item selection) and total ranking problems from $l$-wise ($l\geq 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.

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.

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

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

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

Gradient descent fails to learn simple neural networks efficiently.

We study the query complexity of Bayesian Private Learning: a learner wishes to locate a random target within an interval by submitting queries, in the presence of an adversary who observes all of her queries but not the responses. How many queries are necessary and sufficient in order for the learner to accurately est…

We show that for the problem of testing if a matrix $A \in F^{n \times n}$ has rank at most $d$, or requires changing an $ε$-fraction of entries to have rank at most $d$, there is a non-adaptive query algorithm making $\widetilde{O}(d^2/ε)$ queries. Our algorithm works for any field $F$. This improves upon the previous…

Study reduces memory needs for active learning with enriched queries.

Lower bound shows super-polynomial gap for estimating truncated Gaussian means.

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 \in \mathbb{R}^{d \times d}$, an algorithm is allowed to make $T$ \emph{exact} queries of the form $w^{(i)} = Mv^{(i)}$ for $i \in \{1,\dots,T\}$, where $v^{(i)}$…

New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.

Lower bounds for geodesically convex optimization show curvature negatively impacts complexity.

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

Study exact partition recovery with same-cluster oracle, bounded error.

New method generates private synthetic data with optimal utility for smooth queries.

Optimal SQ bounds for learning binary product distributions and Ising models.

New research shows exponential lower bounds for planning in MDPs with linearly-realizable optimal action-value functions.

New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.

Study on how many queries an adversary needs to make to match the best attack in white-box model.

Paper proposes a 1-bit mean estimation method with near-optimal sample complexity.

Quadratic memory is essential for optimal convex optimization queries.

TensorPlan shows an exponential lower bound for planning in MDPs with linearly realizable value functions.

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

The paper develops algorithms to restore monotonicity in non-monotone functions.

Study near-optimal bounds for learning Gaussian halfspaces with random noise.

Paper develops an efficient mean estimator for 1-bit communication constraints.

Proposes efficient bounds for causal effect estimation under weak confounding.

We consider the problem of sampling from a strongly log-concave density in $\mathbb{R}^d$, and prove an information theoretic lower bound on the number of stochastic gradient queries of the log density needed. Several popular sampling algorithms (including many Markov chain Monte Carlo methods) operate by using stochas…

Tensor PCA problem analyzed with statistical query lower bounds.

New SQ lower bounds for NGCA without requiring chi-squared condition.

The study establishes SQ lower bounds for learning halfspaces and ReLUs under Gaussian marginals.

Improved sampling from high-dimensional Gaussians using smoothed scores.

In this paper, we initiate a rigorous theoretical study of clustering with noisy queries (or a faulty oracle). Given a set of $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$ and $v$ belong to the…

Improved efficient robust regression with near-linear time and subquadratic samples.

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.