AI Theory

Shallow ReLU neural networks face topological training obstructions due to gradient flow confinement on disconnected quadric hypersurfaces.

New topology-based complexity measures reliably predict deep learning model generalization, outperforming existing methods and offering practical computational efficiency.

Shuffled SGD’s convergence is now better understood through a primal-dual analysis, yielding tighter bounds that align with its superior empirical performance.

This paper presents an algorithm achieving Õ(√T) optimal regret for bandit non-stochastic control with strongly-convex and smooth cost functions, overcoming prior limitations of suboptimal bounds.

Learning user preferences accurately from limited data is key; this paper shows that surprisingly small datasets suffice for precise prediction, and provides efficient algorithms to achieve this.

Novel theoretical guarantees for Diffusion Flow Matching (DFM) models are established, bounding the KL divergence under mild assumptions on data and base distributions.

Deep learning’s sequence modeling is revolutionized by selective state-space models (SSMs)! This paper provides theoretical grounding for their superior performance, revealing the crucial role of gati…

New theoretical bounds reveal how neural network architecture impacts the Gauss-Newton matrix’s conditioning, paving the way for improved optimization.

Researchers unveil the origins of degree bias in Graph Neural Networks (GNNs), proving high-degree nodes’ lower misclassification probability and proposing methods to alleviate this bias for fairer GN…

Strong student models can learn from weaker teachers, even correcting errors and generalizing beyond the teacher’s expertise. This paper provides new theoretical bounds explaining this ‘weak-to-strong…

Partial preferences and noisy votes hinder accurate ranking recovery; this paper introduces scalable SP voting variants, empirically demonstrating superior performance in recovering ground truth ranki…

This paper proves fundamental space complexity lower bounds for approximating logistic loss, revealing that existing coreset constructions are surprisingly optimal.

Beat the 1/e barrier in the secretary problem using only an additive gap prediction!

Gradient descent’s sample complexity in non-smooth stochastic convex optimization is Õ(d/m+1/√m), matching worst-case ERMs and showing no advantage over naive methods.

OKRidge’s reliability for solving sparse ridge regression problems is rigorously proven through theoretical error analysis, enhancing its applicability in machine learning.

Optimization’s implicit bias in robust machine learning hurts generalization; this work reveals how algorithm/architecture choices impact robustness, suggesting better optimization strategies are need…

Hard attention transformers show surprisingly greater power when processing numerical data sequences, exceeding capabilities on string data; this advancement is theoretically analyzed via circuit comp…

Neural circuits for goal-directed navigation are modeled as Lie group operator searches, implemented by a two-layer feedforward circuit mimicking Drosophila’s navigation system.

Researchers found the minimax optimal rate of HSIC estimation for translation-invariant kernels is O(n⁻¹/²), settling a two-decade-old open question and validating many existing HSIC estimators.

This paper reveals fundamental limits of differential privacy in online learning, demonstrating a clear separation between pure, approximate, and non-private settings.