Optimization

MCCFVFP, a novel Monte Carlo-based algorithm, accelerates Nash equilibrium convergence in large-scale games by combining CFR’s counterfactual value calculations with fictitious play’s best response st…

Fast imprecise oracles drastically reduce query times in matroid optimization, achieving near-optimal performance with few accurate queries.

Accelerating ERM for data-driven algorithm design using output-sensitive techniques achieves computationally efficient learning by scaling with the actual number of pieces in the dual loss function, n…

Accelerated learning in games achieved! FTXL algorithm exponentially speeds up convergence to Nash equilibria in finite N-person games, even under limited feedback.

This paper presents efficient algorithms for abductive reasoning in Logical Credal Networks (LCNs), addressing the MAP and Marginal MAP inference tasks to enable scalable solutions for complex real-wo…

This paper reveals a universal square-root growth rate for H-consistency bounds of smooth surrogate losses in classification, significantly advancing our understanding of loss function selection.

This paper fully characterizes concept classes optimistically universally learnable online, introducing novel algorithms and revealing equivalences between agnostic and realizable settings.

A novel universal online learning algorithm achieves optimal gradient-variation regret across diverse function curvatures, boasting efficiency with only one gradient query per round.

A new adaptive learning rate for FTRL achieves minimax regret of O(T²/³) in online learning, improving existing best-of-both-worlds algorithms for various hard problems.

Stable oracles outperform Gaussian oracles in high-accuracy heavy-tailed sampling, overcoming limitations of Gaussian-based proximal samplers.

New framework directly controls neural network sensitivity by precisely parameterizing overall bi-Lipschitzness, offering improved robustness and generalization.

BLOCC, a novel first-order algorithm, efficiently solves bilevel optimization problems with coupled constraints, offering improved scalability and convergence for machine learning applications.

A novel neural network efficiently answers arbitrary Most Probable Explanation (MPE) queries in large probabilistic models, eliminating the need for slow inference algorithms.

Revolutionizing probabilistic inference, PLIA₁ uses tensor operations and FFT to scale integer arithmetic, achieving orders-of-magnitude speedup in inference and learning times.

A new combinatorial algorithm dramatically speeds up semi-discrete optimal transport calculations, offering an efficient solution for large datasets and higher dimensions.

Solved a long-standing open problem: Factorized ADABOOST.MH now has a proven convergence rate!

Researchers discovered four distinct compute-optimal phases for training neural networks, offering new predictions for resource-efficient large model training.