Optimization

Clipped SGD achieves near-optimal sub-Gaussian rates for high-dimensional heavy-tailed statistical estimation in streaming settings, improving upon existing state-of-the-art results.

SVOGS: Near-optimal distributed minimax optimization is achieved under second-order similarity, balancing communication, computation, and achieving near-optimal complexities.

Sparse navigable graphs enable efficient nearest neighbor search, but their construction and limits in high dimensions remain unclear. This paper presents an efficient method to construct navigable gr…

Inspired by nature, researchers introduce a novel spatiotemporal local algorithm for machine learning that outperforms backpropagation in online learning scenarios with limited data or long video stre…

Unbounded label spaces conquered! New algorithm achieves optimal mistake bounds in multiclass transductive online learning.

This paper introduces a novel model for multi-winner reconfiguration, analyzing the computational complexity of transitioning between committees using four approval-based voting rules, demonstrating b…

Multi-Stage Predict+Optimize tackles optimization problems where parameters are revealed sequentially, improving predictions and decisions through stage-wise updates.

Novel surrogate losses with label-independent H-consistency bounds enable stronger guarantees for multi-label learning.

Motif-oriented influence maximization tackles viral marketing’s challenge of reaching groups by proving a greedy algorithm with guaranteed approximation ratio and near-linear time complexity.

A new formula unifies lazy and active neural network training regimes, revealing a mixed regime that combines their strengths for faster convergence and low-rank bias.

This paper presents novel mirror and preconditioned gradient descent algorithms for optimizing functionals over Wasserstein space, offering improved convergence and efficiency for various machine lear…

A novel lossy compression framework, Minimum Entropy Coupling with Bottleneck (MEC-B), extends existing methods by integrating a bottleneck for controlled stochasticity, enhancing performance in scen…

MinUCB and LA-MinUCB, novel local Bayesian optimization algorithms, replace gradient descent with UCB minimization for efficient, theoretically-sound local search.

MILP-StuDio generates high-quality mixed-integer linear programming instances by preserving crucial block structures, significantly improving learning-based solver performance.

MG-Net dynamically designs optimal mixer Hamiltonians for QAOA, overcoming the limitation of fixed-depth quantum circuits and significantly improving approximation ratios.

Researchers unveil novel linear-algebraic tools revealing the limits of fast attention, classifying positive definite kernels for Manhattan distance, and fully characterizing metric transforms for Man…

Mechanism design enhanced with output advice improves approximation guarantees by using imperfect predictions of the output, not agent types, offering robust, practical solutions.

This paper presents a novel bilevel approach to extend mean-field Langevin dynamics to solve convex optimization problems over signed measures, achieving stronger guarantees and faster convergence rat…

Researchers establish basis-free conditions for SGD learnability in two-layer neural networks learning subspace-sparse polynomials with Gaussian input, offering insights into training dynamics.

Optimizing against learning agents: New algorithms and computational limits revealed!