SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker
Assumptions
- URL: http://arxiv.org/abs/2403.04744v1
- Date: Thu, 7 Mar 2024 18:49:32 GMT
- Title: SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker
Assumptions
- Authors: Ilias Diakonikolas, Daniel Kane, Lisheng Ren and Yuxin Sun
- Abstract summary: We study the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query model.
We prove near-optimal SQ lower bounds for NGCA under the moment-matching condition only.
- Score: 50.20087216230159
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the complexity of Non-Gaussian Component Analysis (NGCA) in the
Statistical Query (SQ) model. Prior work developed a general methodology to
prove SQ lower bounds for this task that have been applicable to a wide range
of contexts. In particular, it was known that for any univariate distribution
$A$ satisfying certain conditions, distinguishing between a standard
multivariate Gaussian and a distribution that behaves like $A$ in a random
hidden direction and like a standard Gaussian in the orthogonal complement, is
SQ-hard. The required conditions were that (1) $A$ matches many low-order
moments with the standard univariate Gaussian, and (2) the chi-squared norm of
$A$ with respect to the standard Gaussian is finite. While the moment-matching
condition is necessary for hardness, the chi-squared condition was only
required for technical reasons. In this work, we establish that the latter
condition is indeed not necessary. In particular, we prove near-optimal SQ
lower bounds for NGCA under the moment-matching condition only. Our result
naturally generalizes to the setting of a hidden subspace. Leveraging our
general SQ lower bound, we obtain near-optimal SQ lower bounds for a range of
concrete estimation tasks where existing techniques provide sub-optimal or even
vacuous guarantees.
Related papers
- A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum
Optimization [7.014966911550542]
We consider the problem of training a deep neural network with nonsmooth regularization to retrieve a sparse sub-structure.
We derive a new solver, called SR2, whose convergence and worst-case complexity are established without knowledge or approximation of the gradient's Lipschitz constant.
Experiments on network instances trained on CIFAR-10 and CIFAR-100 show that SR2 consistently achieves higher sparsity and accuracy than related methods such as ProxGEN and ProxSGD.
arXiv Detail & Related papers (2022-06-14T00:28:44Z) - Optimal SQ Lower Bounds for Robustly Learning Discrete Product
Distributions and Ising Models [45.14286976373306]
We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions.
Our SQ lower bounds match the error guarantees of known algorithms for these problems, providing evidence that current upper bounds for these tasks are best possible.
arXiv Detail & Related papers (2022-06-09T16:10:23Z) - Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models [15.857373057387669]
We prove concentration properties at any constant level (number of layers) on ensembles of random optimization problems in the infinite size limit.
Our analysis can be understood via a saddle-point approximation of a sum-over-paths integral.
We show that the performance of the QAOA at constant levels is bounded away from optimality for pure $q$-spin models when $qge 4$ and is even.
arXiv Detail & Related papers (2022-04-21T17:40:39Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms.
The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
arXiv Detail & Related papers (2022-02-26T19:10:48Z) - Near-Optimal Statistical Query Lower Bounds for Agnostically Learning
Intersections of Halfspaces with Gaussian Marginals [10.06689891744466]
We consider the well-studied problem of learning intersections halfspaces under the Gaussian distribution in the challenging emphagnostic learning model.
We prove two variants of our lower bound, each of which combines ingredients from Diakonikolas et al. (2021) with (an extension of) a different earlier approach for SQ lower bounds for the Boolean setting.
arXiv Detail & Related papers (2022-02-10T15:34:10Z) - Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
Non-Gaussian Component Analysis (NGCA) is a distribution learning problem.
We provide an efficient algorithm for NGCA in the regime that $A$ is discrete or nearly discrete.
arXiv Detail & Related papers (2021-12-16T18:38:02Z) - Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem.
We introduce a emphmisspecified kernelized bandit setting where the unknown function can be $epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS)
We show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
arXiv Detail & Related papers (2021-11-09T09:00:02Z) - Constrained Optimization Involving Nonconvex $\ell_p$ Norms: Optimality
Conditions, Algorithm and Convergence [4.886985244621422]
We provide the calculation of the subgradients of the $ell_p$ norm and the normal cones of the $ell_p$ ball.
We show that the sequential optimality conditions can be easily satisfied for iteratively reweighted algorithms.
arXiv Detail & Related papers (2021-10-27T02:17:42Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems.
"vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
arXiv Detail & Related papers (2021-07-23T19:38:17Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.