AI Theory

Smoothed online classification can be harder than batch classification when label spaces are unbounded, challenging existing assumptions in machine learning.

AI for science faces hidden biases in causal inference; this paper reveals these flaws using ant behavior data, introducing ISTAnt benchmark, and provides guidelines for more accurate causal AI.

A novel slack-free spiking neural network efficiently solves the Hypergraph Minimum Vertex Cover problem on neuromorphic hardware, outperforming CPU-based methods in both speed and energy consumption.

SkipPredict optimizes scheduling by prioritizing cheap predictions and using expensive ones only when necessary, achieving cost-effective performance.

Sketchy Moment Matching (SkMM) is a fast and theoretically sound data selection method for deep learning finetuning. By controlling variance-bias tradeoffs in high dimensions, SkMM drastically reduces…

New shuffling gradient methods achieve state-of-the-art oracle complexity for nonconvex-concave minimax optimization problems, offering improved performance and efficiency.

Sharpness Reduction Interactive Teaching (SRIT) boosts interactive teaching’s performance by integrating SAM’s generalization capabilities, leading to improved model accuracy and generalization.

Researchers developed a recurrent neural circuit model that efficiently transforms sensory signals into neural representations by dynamically adjusting interneuron connectivity and activation function…

SGD surprisingly diminishes network rank, unlike GD, due to a repulsive force between eigenvalues, offering insights into deep learning generalization.

Sequential Signal Mixing Aggregation (SSMA) boosts message-passing graph neural network performance by effectively mixing neighbor features, achieving state-of-the-art results across various benchmark…

This paper introduces contextual Shtarkov sums, a new complexity measure characterizing minimax regret in sequential probability assignment with contexts, and derives the minimax optimal algorithm, co…

Deep Equilibrium Models (DEQs) outperform standard neural networks, but lack theoretical understanding. This paper provides general separation results showing DEQ’s superior expressivity and character…

This paper introduces a novel, tractable semidefinite program (SDP) relaxation for the Gromov-Wasserstein distance, enabling the computation of globally optimal transportation plans.

New nearly-linear time algorithm achieves high-accuracy semi-random matrix completion, overcoming previous limitations on accuracy and noise tolerance.

SEEV framework efficiently verifies ReLU neural barrier functions by reducing activation regions and using tight over-approximations, significantly improving verification efficiency without sacrificin…

AI agents can secretly collude using steganography, hiding their interactions from oversight. This research formalizes this threat, analyzes LLMs’ capabilities, and proposes mitigation strategies.

Score-based generative models are provably robust to multiple error sources, as shown via a novel Wasserstein uncertainty propagation theorem.

Schur Nets boost higher-order GNNs by efficiently exploiting local graph structure for automorphism equivariance, achieving improved performance without the computational burden of traditional methods…

Deep learning’s neural scaling laws defy conventional wisdom; this paper uses infinite-dimensional linear regression to theoretically explain this phenomenon, showing that implicit regularization of S…

BICCOS: Scalable neural network verification via branch-and-bound inferred cutting planes.