∇ProvenDecisions
Ctrl K

Newton steps speed up LCPs, random reshuffling gets a proof, and Nesterov's Gauss Prize gets a survey

The day in optimization

Most of the day's arXiv items were about convergence guarantees. Several papers extended or tightened rates for first-order, interior-point and Newton-type methods, and a few established what cannot be done. A survey of Yurii Nesterov's work, written after the 2026 Gauss Prize announcement, gave the day a historical frame. The survey is worth a look for readers who want the background to much of what follows.

Theory

Interior-point and Newton-type methods. Ma, Végh and Vladu study linear complementarity problems (LCPs) with sufficient matrices. This class covers convex quadratic programs and has reductions from discounted stochastic games and mean-payoff games. The abstract revisits the 1991 interior-point method of Kojima, Megiddo, Noma and Yoshise, and the title claims that Newton steps are faster for these problems. The excerpt cuts off before the actual bounds, so see the paper for the improvement. On the semidefinite side, Mohammad-Nezhad, Sampourmahani and Terlaky look at central paths without strict complementarity. These paths can have fractional-power behaviour and need not be differentiable in the usual barrier parameter. They show that a common "ramification exponent" removes this obstruction for a whole family of weighted AHO central paths. That is the route to superlinear local convergence. Separately, Dvurechensky, Geiersbach, Hintermüller and coauthors propose a globalized stochastic semismooth Newton method for strongly convex problems in Hilbert spaces. Each full Newton trial step is accepted or rejected by a stochastic residual test, and rejected steps are replaced by damped steps in the same direction.

Stochastic first-order methods. Zijian Liu's paper on random reshuffling addresses a gap between practice and theory. Reshuffling means going through the data in a fresh random order each epoch instead of sampling with replacement. It is popular and works well, but has often been treated as a heuristic. The title claims that for smooth convex problems it dominates plain SGD. The excerpt gives no rates, so check the paper for the exact statement. Vaidyan, Alacaoglu and Friedlander analyse last-iterate convergence of proximal and projected stochastic gradient methods without bounded-domain or bounded-variance assumptions. Black-box variational inference is the running example. In decentralized optimization, Alghunaim, Cai and Sayed show that gradient tracking can degrade as the mixing matrix's nontrivial eigenvalue approaches −1. Even for two agents with identical quadratics, the steady-state disagreement scales like α²σ²Δ⁻³. Here α is the step size, σ² the gradient noise, and Δ the absolute spectral gap. In plain words, a network that nearly oscillates hurts much more than the usual spectral-gap bounds suggest.

Limits and hardness. Kang Liu shows that for nonsmooth weakly convex problems, parallel queries cannot beat the standard subgradient rate in sufficiently high dimensions, even for randomized algorithms. This holds only in the stated parameter regime. The same paper shows that the order structure of the real line permits faster search. On the discrete side, Di Summa proves that integer linear feasibility is strongly NP-complete even when the constraint matrix has two nonzeros per row and column, arranged in a single cycle. Wei shows that deciding whether a cubic over three nonnegative integers takes a value at most 1 is NP-hard. Both are hardness results and say nothing about algorithms that might exist for easier cases. In the other direction, Chao Xu gives an O(n³) algorithm for Cunningham's canonical decomposition of a symmetric submodular function. The decomposition stores all minimum cuts in linear space.

Structure-exploiting convex methods. Nylöf, Nietert, Pallage and coauthors lift certain composite problems over Gaussian measures (Bures–Wasserstein space) into Euclidean space. The lift acts on affine transport maps, which lets accelerated proximal gradient methods apply. Their algorithm, BW-FISTA, is described as achieving minimax-optimal rates under convex smooth and proximable lifts. For certification, Nagerl, Naceur and Berloff give an instance-specific upper bound on how many binary configurations beat a returned state by a given margin. This is useful for benchmarking analogue optimisers.

In practice

A Slalom write-up on NVIDIA cuOpt describes a rail repair scheduling case. Slalom reports that planning that used to take hours now takes about ten minutes, and that the tool supports rerouting when schedules change. This is a consultancy and vendor-partner account, so the figures are self-reported. I found no independent verification.

Worth watching

Sources: - How to Look Inside the Black Box: A Survey of Yu. E. Nesterov's Contributions - Slalom: Revolutionizing route optimization with NVIDIA cuOpt

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: