Rennala NSGD paper accepted at NeurIPS 2026: high-probability SGD bounds beyond Euclidean geometry
peter_richtarik · x · 2026-11-06
- Problem: The success of matrix-aware optimizers like Muon and Shampoo hints at the power of non-Euclidean geometry for deep learning, but the theory of stochastic optimization in general normed spaces—especially distributed settings—remains limited.
- Theory: The paper analyzes minibatch SGD for smooth nonconvex optimization under arbitrary norms, using κ-regular normed spaces to derive high-probability oracle complexity bounds under a light-tail condition in the dual norm. In the Euclidean case it recovers the standard minibatch rate up to log factors; for some non-Euclidean geometries it is sharper, reducing linear dimension dependence to logarithmic.
- Algorithm: Introduces Rennala NSGD, a semi-asynchronous distributed algorithm with wall-clock complexity guarantees under fixed, heterogeneous worker compute times.
- Authors: Igor Sokolov, Alexander Tyurin, Peter Richtárik (KAUST).
More from Research
- ICLR reviews starting to leak, authors still waiting on scores — Invariant_n_Cauchy · 2026-11-06
- Researcher defends AI-based ranking of 1660 STOC submissions after backlash — vitalyFM · 2026-11-06
- Stanford launches Collaborative Intelligence project on human-agent teamwork for future of work — Diyi_Yang · 2026-11-06
- Chai Discovery launches, open-sources Chai-1, lands deals with seven big pharma firms — chaitjo · 2026-11-06
- Johns Hopkins study compares four failure data sources for robot reward models — mangahomanga · 2026-11-06
- DFlash 2 parallel drafting lifts speculative decoding acceptance 21% for 1.3% latency cost — songhan_mit · 2026-11-06