Optimization

This paper presents novel, efficient algorithms and formulations for Sparse Canonical Correlation Analysis (SCCA), a method that improves the interpretability of traditional CCA. SCCA is especially us…

Autoregressively trained transformers surprisingly learn algorithms during pretraining, enabling in-context learning; this paper reveals when and why this ‘mesa-optimization’ happens.

Adam optimizer achieves near-optimal convergence in non-convex scenarios with unbounded gradients and relaxed noise assumptions, improving its theoretical understanding and practical application.

A novel semi Forward-Backward Euler scheme provides convergence guarantees for non-geodesically-convex optimization in Wasserstein space, advancing both sampling and optimization.

BFGS algorithm achieves global linear and superlinear convergence rates with inexact Armijo-Wolfe line search, even without precise Hessian knowledge.

This paper reveals how a one-layer transformer’s training converges for next-token prediction, showing sub-linear convergence for both layers and shedding light on its surprising generalization abilit…

This paper rigorously analyzes biased adaptive stochastic gradient descent (SGD), proving convergence to critical points for non-convex functions even with biased gradient estimations. The analysis c…

This paper reveals efficient stochastic bandit algorithms for maximizing M-concave functions and proves NP-hardness for adversarial full-information settings.

Extrapolated FTRL ensures Nash equilibrium convergence in harmonic games, defying standard no-regret learning limitations.

No free lunch for adversarial optimization: This paper proves that no single algorithm universally outperforms others when finding Nash Equilibrium, introducing black-box complexity analysis to estab…

Newton Losses enhance training of neural networks with complex objectives by using second-order information from loss functions, achieving significant performance gains.

Neural Pfaffians revolutionize many-electron Schrödinger equation solutions by using fully learnable neural wave functions based on Pfaffians, achieving unprecedented accuracy and generalizability acr…

Accelerate molecular simulations using neural network reparametrization! This flexible method adjusts system complexity, enhances optimization, and maintains continuous access to fine-grained modes, o…

Neural networks efficiently solve robust routing problems with uncertain travel times, minimizing worst-case deviations from optimal routes under the min-max regret criterion.

Deep neural collapse, previously believed optimal, is shown suboptimal in multi-class, multi-layer networks due to a low-rank bias, yielding even lower-rank solutions.

NEUR2BILO: a neural network-based heuristic solves mixed-integer bilevel optimization problems extremely fast, achieving high-quality solutions for diverse applications.

AGNES, a novel accelerated gradient descent algorithm, achieves accelerated convergence even with very noisy gradients, significantly improving training efficiency for machine learning models.

Lanczos-FA, a simple algorithm for approximating matrix functions, surprisingly outperforms newer methods; this paper proves its near-optimality for rational functions, explaining its practical succes…

This research establishes the first minimax optimal algorithm for submodular maximization with bandit feedback, achieving a regret bound matching the lower bound.

This paper presents OFU-MNL+, a constant-time algorithm achieving nearly minimax optimal regret for contextual multinomial logistic bandits, closing the gap between existing upper and lower bounds.