AI Theory

New algorithms achieve optimal weak regret in K-armed dueling bandits by leveraging the full problem structure, improving upon state-of-the-art methods.

This paper presents efficient algorithms for approximating equilibria in non-concave games, focusing on tractable ɸ-equilibria and addressing computational challenges posed by infinite strategy sets.

Researchers rigorously prove the Strong Lottery Ticket Hypothesis, offering the first theoretical guarantees on the sparsity of winning neural network subnetworks.

High-dimensional spectral algorithms show saturation effects: Kernel Ridge Regression underperforms optimal algorithms like gradient flow when regression functions are very smooth.

Transformers’ self-attention mechanism, while powerful, suffers from rank collapse with increasing depth. This paper reveals that while masked attention still leads to exponential collapse, sparse att…

Spectral algorithms for graph bisection show surprising robustness to helpful adversaries in semirandom models, with unnormalized Laplacian consistently outperforming the normalized one.

Small-size Graph Neural Networks effectively solve Linear Programs!

Researchers achieve full parameter identifiability in partially observed linear causal models using novel graphical conditions and a likelihood-based estimation method, addressing previous limitations…

Researchers discover Dilated Entropy is the optimal distance-generating function for solving extensive-form games using first-order methods, achieving near-optimal regret bounds.

Standard initialization in neural networks negatively impacts generalization ability under Neural Tangent Kernel theory, contradicting real-world performance, urging the development of improved theore…

Graph Neural Networks (GNNs) struggle with heterophilic link prediction; this paper introduces formal definitions, theoretical analysis, improved designs, and real-world benchmarks to address this cha…

Researchers developed a novel, efficient causal discovery method using Probability Generating Functions to identify causal structures within Poisson Branching Structural Causal Models, overcoming limi…

Boosting GNN expressivity and generalization: Novel node individualization schemes lower sample complexity, improving substructure identification.

Tree-structured probabilistic circuits are surprisingly efficient: this paper proves a quasi-polynomial upper bound on their size, showing they’re almost as expressive as more complex DAG structures.

This paper reveals surprising computational connections between algorithmic replicability and other learning paradigms, offering novel algorithms and demonstrating separations between replicability an…

This paper proposes a computationally efficient, differentially private best subset selection method for high-dimensional sparse linear regression, achieving both strong statistical utility and provab…

New polynomial-space algorithm for causal parameter identification in linear models vastly improves upon existing methods, showing that this crucial task is computationally hard.

Average-link hierarchical clustering gets a comprehensive evaluation using new criteria, showing it outperforms other methods when both cohesion and separability matter.

Public data boosts private AI accuracy even with extreme distribution shifts, improving private model training by up to 67% in three tasks. This is due to shared low-dimensional representations betwe…

Even a few data changes can break the Benjamini-Hochberg (BH) procedure, a widely used multiple testing method, highlighting a critical vulnerability.