Optimization

OptEx significantly speeds up first-order optimization by cleverly parallelizing iterations, enabling faster convergence for complex tasks.

Predictive coding networks learn faster than backpropagation by changing the loss landscape’s geometry, making saddles easier to escape and improving robustness to vanishing gradients.

First algorithm for online weighted paging that learns page weights from samples, achieving optimal O(log k) competitiveness and sublinear regret.

New algorithms conquer delayed feedback in online choice modeling, achieving optimal decision-making even with unknown customer preferences and delayed responses.

This paper introduces a novel information-theoretic framework, showing how to convert offline into online estimation algorithms efficiently, impacting interactive decision-making.

Algorithm RESET achieves optimal switching regret simultaneously across all segmentations, offering efficiency and parameter-free operation.

The 1-nearest neighbor rule achieves online consistency under surprisingly broad conditions: measurable label functions and mild assumptions on instance generation in doubling metric spaces.

Researchers achieve optimal regret bounds in online composite optimization under stochastic and adversarial settings using a novel optimistic composite mirror descent algorithm and a universal strateg…

MetaAd, a novel meta-algorithm, achieves provable competitive ratios for online budgeted matching with general bids, removing prior restrictive assumptions.

Researchers developed a novel online Bayesian persuasion algorithm that achieves sublinear regret without prior knowledge of the receiver or the state distribution, providing tight theoretical guarant…

One-layer transformers provably learn the one-nearest neighbor prediction rule, offering theoretical insights into their in-context learning capabilities.

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.

Small-size Graph Neural Networks effectively solve Linear Programs!

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

Fragile SGD & Amelie SGD achieve near-optimal speed in decentralized asynchronous optimization, handling diverse worker & communication speeds.

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…

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