Optimization

Derandomizing multi-distribution learning is computationally hard, but a structural condition allows efficient black-box conversion of randomized predictors to deterministic ones.

Deep linear networks implicitly regularize towards flat minima, with sharpness (Hessian’s largest eigenvalue) of minimizers linearly increasing with depth but bounded by a constant times the lower bou…

New Perturbation Gradient losses connect expected decisions with directional derivatives, enabling Lipschitz continuous surrogates for predict-then-optimize, asymptotically yielding best-in-class poli…

Sublinear coresets for Poisson regression are developed, offering 1±ε approximation guarantees, with complexity analyzed using a novel parameter and domain shifting.

CSPG: a novel framework boosting Approximate Nearest Neighbor Search speed by 1.5-2x, using sparse proximity graphs and efficient two-staged search.

Score estimation, crucial for diffusion models, is computationally hard even with polynomial sample complexity unless strong distributional assumptions are made.

Cost-aware Bayesian optimization gets a boost with the Pandora’s Box Gittins Index, a novel acquisition function that efficiently balances exploration and exploitation while considering evaluation cos…

In symmetric zero-sum games, no-swap-regret dynamics guarantee strong convergence to Nash Equilibrium under symmetric initial conditions, but this advantage disappears when constraints are relaxed.

Gradient-based methods for solving large zero-sum games achieve polynomial smoothed complexity, demonstrating efficiency even in high-precision scenarios without condition number dependence.

Contrastive losses unlock efficient fitness function modeling by leveraging the ranking information inherent in global epistasis, significantly improving accuracy and data efficiency in protein engine…

Repeated contracts with learning agents are optimized by a simple dynamic contract: initially linear, then switching to zero-cost, causing the agent’s actions to ‘free-fall’ and yield non-zero rewards…

This paper introduces induced empirical risk minimization for contextual linear optimization with bandit feedback, providing theoretical guarantees and computationally tractable solutions for improved…

This work unveils a novel algorithm for contextual decision-making with knapsacks, achieving significantly improved regret bounds beyond worst-case scenarios, thereby offering a more practical and eff…

Constrained sampling made easy! Primal-Dual Langevin Monte Carlo efficiently samples from complex probability distributions while satisfying statistical constraints.

This paper presents a unified framework for solving binary statistical decision-making problems, enabling efficient derivation of optimal strategies for diverse applications like OOD detection and sel…

Conformal inverse optimization learns uncertainty sets for parameters in optimization models, then solves a robust optimization model for high-quality, human-aligned decisions.

Distributed Lion: Training large AI models efficiently by communicating only binary or low-precision vectors between workers and a server, significantly reducing communication costs and maintaining co…

This paper presents communication-efficient protocols for the distributed experts problem, achieving near-optimal regret with theoretical and empirical validation.

A novel Collaborative Neural Framework (CNF) enhances the robustness of neural vehicle routing methods against adversarial attacks by collaboratively training multiple models and intelligently distrib…

New method for eigenvector estimation achieves optimal rates without coherence dependence, improving low-rank matrix denoising and related tasks.