arXiv research

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

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

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

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

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

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

Study shows SQ lower bounds for learning ReLUs with Massart noise.

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

The study optimizes polynomial regression for learning under Gaussian distributions.

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

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

Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning with statistical queries, and Littlestone dimension characterizes online learning. In this paper we aim to develop combinatorial dimensions th…

Lower bounds show learning mixtures of linear classifiers is nearly impossible.

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

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

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

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

Tensor PCA problem analyzed with statistical query lower bounds.

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

We study the complexity of training neural network models with one hidden nonlinear activation layer and an output weighted sum layer. We analyze Gradient Descent applied to learning a bounded target function on $n$ real-valued inputs. We give an agnostic learning guarantee for GD: starting from a randomly initialized …

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

Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.

Study learning halfspaces with Massart noise under Gaussian distribution, improving previous results.

New algorithm for learning mixtures with mostly uniform weights, improving on previous bounds.

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

Gradient descent can efficiently learn a target function with diverse and near-orthogonal features.

Neural networks can achieve optimal sample complexity for learning single-index models.

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

Gradient descent fails to learn simple neural networks efficiently.

Unified approach for quantum and classical learning from evaluation oracles.

Framework for robust decision making in changing environments with privacy constraints.

We study the problem of high-dimensional linear regression in a robust model where an $ε$-fraction of the samples can be adversarially corrupted. We focus on the fundamental setting where the covariates of the uncorrupted samples are drawn from a Gaussian distribution $\mathcal{N}(0, Σ)$ on $\mathbb{R}^d$. We give near…

New algorithm for learning ReLU networks with Gaussian noise, improving previous results.

New operations match Steenrod squares on Khovanov homology.

Polynomial-time algorithm for list-decodable linear regression with batches.

Computes Steenrod squares on Khovanov homology for knots up to 11 crossings.

New algorithm learns disjunctions faster than previous methods.

Study on estimating Gaussian mean with missing data in high dimensions.

We observe that the Poincare duality isomorphism for a string manifold is an isomorphism of modules over the subalgebra A(2) of the modulo 2 Steenrod algebra. In particular, the pattern of the operations Sq^1, Sq^2, and Sq^4 on the cohomology of a string manifold has a symmetry around the middle dimension. We character…

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

New lower bounds show learning intersections of halfspaces is hard even for a few halfspaces.

Lipshitz and Sarkar recently introduced a space-level refinement of Khovanov homology. This refinement induces a Steenrod square operation $\Sq^2$ on Khovanov homology which they describe explicitly. This paper presents some computations of $\Sq^2$. In particular, we give examples of links with identical integral Khova…

A new invariant for braids and knots uses secants and trisecants.

We use self-report and electrodermal activity (EDA) wearable sensor data from 77 nights of sleep on six participants to test the efficacy of EDA data for sleep monitoring. We used factor analysis to find latent factors in the EDA data, and causal model search to find the most probable graphical model accounting for sel…

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

The present paper deals with the study of Chaki-pseudo parallel and Deszcz-pseudo parallel invariant submanifolds of SQ-Sasakian manifolds with respect to Levi-Civita connection and semisymmetric metric connection and obtain that these two classes are equivalent with a certain condition. Also the invariant and anti-inv…

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…

In a previous paper we constructed a spectrum-level refinement of Khovanov homology. This refinement induces stable cohomology operations on Khovanov homology. In this paper we show that these cohomology operations commute with cobordism maps on Khovanov homology. As a consequence we obtain a refinement of Rasmussen's …