Optimization

A novel inventory reserving algorithm achieves near-optimal performance for bandit problems with knapsacks in piecewise-stationary settings, offering a competitive ratio of O(log(nmax/min)).

Spectral distances on k-nearest neighbor graphs enable robust topological analysis of high-dimensional noisy data using persistent homology, overcoming limitations of Euclidean distance.

This paper proposes penalty-based methods for simple bilevel optimization, achieving (ε, εβ)-optimal solutions with improved complexity under Hölderian error bounds.

In n-player games, a satisficing path always exists leading from any initial strategy profile to a Nash equilibrium by allowing unsatisfied players to explore suboptimal strategies.

Parameter-free optimization is revolutionized! Inexact Polyak Stepsize achieves the same convergence rate as clipped gradient descent but without any hyperparameter tuning, saving time and computatio…

SGD’s dynamics are precisely characterized by the interplay of noise and symmetry in loss functions, leading to unique, initialization-independent fixed points.

This research introduces a novel framework that overcomes the brittleness of Pareto-optimal learning-augmented algorithms by enforcing smoothness in performance using user-specified profiles and devel…

Outlier-robust distributionally robust optimization achieved via a novel Unbalanced Optimal Transport (UOT) distance, improving efficiency and accuracy.

OT4P: a novel temperature-controlled differentiable transformation efficiently relaxes permutation matrices onto the orthogonal group for gradient-based optimization.

Two novel algorithms, Local-Greedy and Greedy-Grid, optimize coalition gain in online auctions with limited observations, achieving constant regret and problem-independent guarantees while respecting …

Optimization can learn optimal Johnson-Lindenstrauss embeddings, avoiding the limitations of randomized methods and achieving comparable theoretical guarantees.

Design provably convergent optimization algorithms swiftly using electric circuit analogies; a novel methodology automating discretization for diverse algorithms.

Optimal multi-objective optimization achieved via hypervolume scalarization, offering sublinear regret bounds and outperforming existing methods.

This paper closes the performance gap in parallel boosting algorithms by presenting improved lower bounds and a novel algorithm matching these bounds, settling the parallel complexity of sample-optima…

This paper proves the minimax optimal U-calibration error is Θ(√KT) for online multiclass prediction, resolving an open problem and showing logarithmic error is achievable for specific loss functions.

This paper presents the first almost linear-time algorithm achieving the optimal accuracy parameter for hypothesis selection, solving a decades-long open problem.

Optimal Flow Matching (OFM) learns straight trajectories for generative modeling in a single step, eliminating iterative processes and improving efficiency.

Optimal algorithms for online convex optimization with adversarial constraints are developed, achieving O(√T) regret and Õ(√T) constraint violation—a breakthrough in the field.

Optimal algorithms for learning partitions are designed, achieving minimum query complexity even with up to l faulty oracle responses.

Leveraging predictions, this research presents novel algorithms for uniformity, identity, and closeness testing of discrete distributions, achieving information-theoretically optimal sample complexity…