Optimization

A new, surprisingly simple boosting algorithm achieves provably optimal sample complexity and outperforms existing algorithms on large datasets.

Leveraging data heterogeneity, this study reveals that standard SGD implicitly learns invariant features across multiple environments, achieving robust generalization without explicit regularization.

Adam’s implicit bias revealed: On separable data, Adam converges towards the maximum l∞-margin solution, a finding contrasting with gradient descent’s l2-margin preference. This polynomial-time conver…

Researchers developed a framework for analyzing stochastic adaptive learning rate algorithms, providing exact risk and learning rate curves, revealing the importance of data covariance and uncovering …

Breaking neural network parameter symmetries leads to faster training, better generalization, and improved loss landscape behavior, as demonstrated by novel asymmetric network architectures.

Physics-Informed Neural Networks (PINNs) training dynamics for nonlinear PDEs are fundamentally different than linear ones; this paper reveals why using second-order methods is crucial for solving non…

Diverse inhibitory neurons in brain circuits enable faster Bayesian computation via Hamiltonian sampling.

Overparametrized neural networks’ learning dynamics are analyzed under data symmetries using mean-field theory, revealing that data augmentation, feature averaging, and equivariant architectures asymp…

SymILO: A novel symmetry-aware learning framework dramatically improves integer linear program (ILP) solutions by addressing data variability caused by ILP symmetry.

This paper introduces the Strategic Littlestone Dimension, a novel complexity measure for online strategic classification, proving instance-optimal mistake bounds in the realizable setting and improve…

Strategic agents gaming recommender systems is solved by a novel mechanism that incentivizes truthful behavior while minimizing regret, offering a solution to a key challenge in online learning.

This paper presents a novel probabilistic regret bound (PRB) framework for Bayesian optimization, replacing the traditional fixed-budget stopping rule with a criterion based on the probability of find…

Stochastic zeroth-order optimization of strongly convex functions with Lipschitz Hessian achieves optimal sample complexity, as proven by matching upper and lower bounds with a novel two-stage algorit…

Bias-free performative prediction is achieved using a novel lazy deployment scheme with SGD, handling non-convex loss functions.

Stochastic Optimal Control Matching (SOCM) significantly reduces errors in stochastic optimal control by learning a matching vector field using a novel iterative diffusion optimization technique.

A novel algorithm significantly improves stochastic optimal control by accurately modeling sensorimotor noise, achieving substantially lower costs than current state-of-the-art solutions, particularly…

Stochastic Newton Proximal Extragradient (SNPE) achieves faster global and local convergence rates for strongly convex functions, improving upon existing stochastic Newton methods by requiring signifi…

Stochastic extragradient with flip-flop shuffling & anchoring achieves provably faster convergence in minimax optimization.

Density estimation algorithms face inherent trade-offs: reducing sample needs often increases query time. This paper proves these trade-offs are fundamental, showing limits to how much improvement is…

Quantum Approximate Optimization Algorithm (QAOA) achieves weak recovery in spiked tensor models matching classical methods, but with potential constant factor advantages for certain parameters.