The paper aims to develop new combinatorial dimensions for bounded memory learning.
problem Characterize bounded memory learning using combinatorial dimensions.
method Proposes a candidate solution based on the SQ dimension of neighboring distributions and proves upper and lower bounds.
result Characterizes bounded memory learning in a specific parameter regime, matching equivalence between bounded memory and SQ learning.
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…
Statistical query (SQ) algorithms are algorithms that have access to an {\em SQ oracle} for the input distribution D D D instead of i.i.d.~ samples from D D D . Given a query function φ : X → [ − 1 , 1 ] φ:X \rightarrow [-1,1] φ : X → [ − 1 , 1 ] , the oracle returns an estimate of E x ∼ D [ φ ( x ) ] {\bf E}_{ x\sim D}[φ(x)] E x ∼ D [ φ ( x )] within some tolerance τ φ τ_φ τ φ that roughly corresponds t…
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 operations match Steenrod squares on Khovanov homology.
problem Matching Steenrod squares with operations on Khovanov homology.
method Applied cup-i products to Khovanov functor and proved agreement with Steenrod squares.
result Lipshitz-Sarkar's Sq^2 agrees with Morán's sq^2.
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.
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.
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.
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.
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.
Study shows SQ lower bounds for learning ReLUs with Massart noise.
problem Learning a single neuron in the presence of Massart noise.
method Statistical Query (SQ) lower bounds for efficient learning algorithms.
result No efficient SQ algorithm can approximate the optimal error within any constant factor.
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. Computes Steenrod squares on Khovanov homology for knots up to 11 crossings.
problem Computing Steenrod squares on Khovanov homology.
method Spatial refinements of even and odd Khovanov homology, computation of Sq^2.
result Steenrod squares Sq^2 on Khovanov homology spaces are determined for knots up to 11 crossings.
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. 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.
Framework for robust decision making in changing environments with privacy constraints.
problem Interactive decision making in changing environments with constraints.
method Hybrid Decision Making with Structured Observations (hybrid DMSO) framework, local differentially private decision making, query-based learning, robust and smooth decision making.
result Strong connections and bounds derived for DEC, SQ dimension, local minimax complexity, learnability, and joint differential privacy.
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…
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 ) . A new invariant for braids and knots uses secants and trisecants.
problem Creating an invariant for braids and knots.
method Defining secant-quandle (SQ) with secants and trisecants as generators and relations.
result Secant-quandle (SQ) is a novel invariant for braids and knots.
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.
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.
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. 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…
The study optimizes polynomial regression for learning under Gaussian distributions.
problem Agnostic learning of Boolean and real-valued functions under Gaussian distributions.
method LP duality and polynomial degree analysis for L 1 L^1 L 1 -regression. result Optimal SQ lower bounds for various function classes.
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. Differentiable learning via SGD and GD can simulate various learning problems, depending on precision and minibatch size.
problem Understanding the power of differentiable learning via SGD and GD compared to statistical query (SQ) learning.
method Comparing the learning power of SGD and GD on population and empirical losses with statistical query learning.
result The learning power of SGD and GD depends on the precision of gradient calculations relative to the minibatch size or sample size.
SQS uses quantum kernels to improve credit scoring with fewer data points.
problem Credit scoring models struggle with scarce and skewed data.
method Systemic Quantum Score (SQS) leverages quantum kernels for better pattern extraction.
result SQS shows improved performance and pattern extraction with fewer data points.
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.
Study shows SQ hardness for multiclass linear classification with random noise.
problem Complexity of multiclass linear classification with random noise.
method Proves super-polynomial SQ lower bounds for MLC with RCN.
result Super-polynomial SQ lower bounds for MLC with RCN.
Lower bounds show learning mixtures of linear classifiers is nearly impossible.
problem Learning mixtures of linear classifiers under Gaussian covariates.
method Statistical Query (SQ) lower bounds and new spherical designs.
result Complexity of any SQ algorithm is \( n^{\mathrm{poly}(1/Δ) \log(r)} \), where Δ is the pairwise \(\ell_2\)-separation.
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 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.
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.
Study identifies personality traits from dance movements in music.
problem Predicting individual differences from music-induced movement.
method Identified Big Five personality traits and EQ/SQ scores from dance movements.
result Successfully explored unseen space for personality and EQ/SQ.
We propose a method for calculating cohomology operations for finite simplicial complexes. Of course, there exist well--known methods for computing (co)homology groups, for example, the reduction algorithm consisting in reducing the matrices corresponding to the differential in each dimension to the Smith normal form, …
New algorithm learns disjunctions faster than previous methods.
problem Learning Boolean disjunctions in the agnostic PAC model.
method Developed an agnostic learner with complexity 2 i l d e O ( n 1 / 3 ) 2^{ ilde{O}(n^{1/3})} 2 i l d e O ( n 1/3 ) . result First separation between SQ and CSQ models in distribution-free agnostic learning.
Study shows squared loss is robust for binary classification with noisy features.
problem Learning binary classifiers with noisy features.
method Sy-De and Asy-In attribute noise models, analyzing l 0 − 1 l_{0-1} l 0 − 1 and l s q l_{sq} l s q losses. result Squared loss is robust in Sy-De model but not in Asy-In model.
Gradient descent can efficiently learn a target function with diverse and near-orthogonal features.
problem Learning a target function with additive structure and diverse features.
method Gradient descent training of a two-layer neural network.
result A large subset of polynomial target functions can be efficiently learned.
Study shows a tradeoff between sample complexity and computational efficiency for learning halfspaces with random noise.
problem PAC learning γ-margin halfspaces with Random Classification Noise.
method Established an information-computation tradeoff and provided a simple efficient algorithm with sample complexity O(1/(γ^2 ε^2)). Also, proved lower bounds for SQ algorithms and low-degree polynomial tests.
result Inherent gap between sample complexity and computational efficiency for learning halfspaces with random noise.
Neural networks can achieve optimal sample complexity for learning single-index models.
problem Achieving optimal computational-statistical tradeoff in learning Gaussian single-index models.
method Unified gradient-based algorithm for training a two-layer neural network, adaptable to various loss and activation functions.
result Sample complexity of d s ⋆ / 2 ∨ d d^{s^\star/2} \lor d d s ⋆ /2 ∨ d matches the SQ lower bound up to a polylogarithmic factor. Near-optimal SQ hardness shows learning halfspaces with Massart noise is hard.
problem Learning halfspaces with Massart noise in the presence of label corruption.
method Statistical Query (SQ) model analysis.
result No efficient SQ algorithm can achieve better than Ω ( η ) Ω(η) Ω ( η ) error, even for optimal noise levels. Reduces learning periodic neural networks to lattice problems, proving hardness under cryptographic assumptions.
problem Learning single periodic neurons in noisy environments.
method Reduction to worst-case lattice problems, using LLL algorithm.
result Polynomial-time algorithms for learning these functions are hard under cryptographic assumptions.
New inequality for refined knot invariants in a specific space.
problem General adjunction inequality for refined s s s -invariants does not hold. method Introduced an adjunction inequality for a specific spatial refinement in k C P 2 ‾ k\overline{\mathbb{CP}^2} k CP 2 . result An adjunction inequality holds for the s s s -version of the S q 1 Sq^1 S q 1 -refinement in k C P 2 ‾ k\overline{\mathbb{CP}^2} k CP 2 . 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. This paper introduces a new Lagrangian for the Information Bottleneck problem to simplify optimization.
problem Optimizing compressed representations for predicting Y Y Y while limiting information about X X X . method Introduces a general family of Lagrangians to explore the Information Bottleneck curve.
result Solves the original constrained optimization problem with a single optimization.
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 n n real-valued inputs. We give an agnostic learning guarantee for GD: starting from a randomly initialized …
Mapping the spatial distribution of poverty in developing countries remains an important and costly challenge. These "poverty maps" are key inputs for poverty targeting, public goods provision, political accountability, and impact evaluation, that are all the more important given the geographic dispersion of the remain…
Study learning halfspaces with Massart noise under Gaussian distribution, improving previous results.
problem Learning halfspaces with Massart noise under Gaussian distribution, especially when the parameter is 1/2.
method Developed algorithms for general and homogeneous halfspaces with sample and computational complexities.
result Established qualitatively matching lower bounds for the complexities of learning algorithms.