Optimization

Optimal matrix denoising with doubly heteroscedastic noise achieved!

Sign Stochastic Gradient Descent (SGD) achieves optimal sample complexity for solving k-sparse parity problems, matching Statistical Query lower bounds.

This paper establishes tight lower bounds for the uniform stability of gradient-based bilevel programming algorithms used for hyperparameter optimization, resolving a key open problem regarding the ti…

First optimal algorithms matching lower bounds for non-smooth convex decentralized optimization over time-varying networks are presented, substantially improving theoretical performance.

FRLC: a novel algorithm for low-rank optimal transport using latent coupling, enabling faster computation and better interpretability for diverse applications.

Low-degree polynomials fail to efficiently infer roots in broadcasting tree problems below the Kesten-Stigum bound.

Deep learning optimization is revolutionized by a new function class, enabling convergence guarantees without over-parameterization and accommodating saddle points.

Generative image restoration models face a critical trade-off: higher perceptual quality often leads to increased hallucinations (unreliable predictions).

This paper enhances prophet inequalities by allowing lookback, improving competitive ratios and providing algorithms for diverse observation orders, thereby bridging theory and real-world online selec…

This paper introduces robust Dikin walks for log-concave sampling, achieving faster mixing times and lower iteration costs than existing methods, particularly for high-dimensional settings.

Linear transformers surprisingly learn intricate optimization algorithms, even surpassing baselines on noisy regression problems, showcasing their unexpected learning capabilities.

LightUnbalancedOptimalTransport: A fast, theoretically-justified solver for continuous unbalanced optimal transport problems, enabling efficient analysis of large datasets with imbalanced classes.

This paper introduces learning-augmented priority queues, using predictions to boost efficiency and optimality, achieving significant performance gains over traditional methods.

Leveraging predictions, this paper presents a novel algorithm for dynamic submodular maximization achieving significantly faster update times (O(poly(log n, log w, log k)) amortized) compared to exist…

This paper shows how noisy predictions about optimal solutions can improve approximation algorithms for NP-hard problems like MAX-CUT, exceeding classical hardness bounds.

This paper introduces a novel framework for learning-augmented algorithms that improves performance by integrating the learning process into the algorithm itself, rather than treating the predictor as…

PFSUM, a novel learning-augmented algorithm, leverages short-term predictions to achieve superior performance in solving the Bahncard problem, outperforming existing methods with improved consistency …

Tighter losses than Fenchel-Young losses are presented, refining Fenchel-Young inequalities using the Fitzpatrick function to improve model accuracy while preserving prediction link functions.

Researchers developed Value Classification Model (VCM), a neural solver that swiftly solves quadratic unconstrained binary optimization (QUBO) problems by directly generating solutions using a classif…

Economists learn to resolve externalities efficiently even when players lack perfect information, maximizing social welfare by leveraging bargaining and online learning.