Optimization

InvBO: Inversion-based Latent Bayesian Optimization solves the misalignment problem in LBO, boosting optimization accuracy and efficiency.

Generalized eigenvalue problems get solved in nearly matrix multiplication time, providing new, faster PCA algorithms!

This paper unveils the information-theoretic limits of online classification with noisy labels, showing that the minimax risk is tightly characterized by the Hellinger gap of noisy label distributions…

This paper proves that inexact ALMs applied to SDPs achieve linear convergence for both primal and dual iterates, contingent solely on strict complementarity and a bounded solution set, thus resol…

IGNITE improves offline optimization by incorporating surrogate gradient norm to reduce model sharpness, boosting performance up to 9.6%

This paper significantly improves our understanding of multiclass PAC learning by reducing the sample complexity gap and proposing two novel approaches to fully resolve the optimal sample complexity.

A novel algorithm, D-FTBL, achieves improved regret bounds for bandit convex optimization with delayed feedback, tightly matching existing lower bounds in worst-case scenarios.

A novel fully dynamic algorithm achieves a (4+ε)-approximate solution for the k-center clustering problem with outliers in general metric spaces, boasting an efficient update time.

A new algorithm, AOGS, achieves significantly lower regret in two-sided matching markets by cleverly integrating exploration and exploitation, thus removing the dependence on the number of arms (K) in…

New algorithms achieve optimal regret bounds for contextual dynamic pricing under minimal assumptions, improving revenue management with better price adjustments.

Decentralized Gradient Descent achieves statistically optimal sparse model learning via implicit regularization, even with communication-efficient truncation.

Mirror descent’s implicit bias on separable data is formally characterized, revealing convergence towards a maximum margin classifier determined by the potential’s ‘horizon function’.

New framework uses Koopman operator theory to identify equivalent training dynamics in deep neural networks, enabling quantitative comparison of different architectures and optimization methods.

This paper proves that non-active exploration suffices for identifying linearly parameterized nonlinear systems with real-analytic features, providing non-asymptotic guarantees for least-squares and s…

Boosting, traditionally limited by assumptions about loss functions, is proven in this paper to efficiently optimize any loss function regardless of differentiability or convexity.

Higher-order PDEs hinder Physics-Informed Neural Network (PINN) convergence; this paper provides theoretical explanation and proposes variable splitting for improved accuracy.

Neural networks learn features effectively through gradient descent, not just at the beginning, but also at the end of training, even with carefully regularized objectives.

This study reveals how black-box settings affect the learning guarantee of stochastic compositional optimization, offering sharper generalization bounds and novel learning guarantees for derivative-fr…

First high-probability complexity guarantees for solving stochastic nonconvex minimax problems using a single-loop method are established.

Adversarial training achieves minimax-optimal prediction error in high-dimensional linear regression under l∞-perturbation, improving upon existing methods.