∇ProvenDecisions
Ctrl K

Newton steps for complementarity problems, a Gauss Prize survey, and new results on shuffling SGD

The day in optimization

Most of the day's new papers were about the convergence behaviour of basic algorithms: interior-point methods, shuffled SGD, last iterates, and decentralized gradient tracking. Complexity results also arrived from both sides, with new hardness proofs for integer problems and a new polynomial-time algorithm for enumerating minimum cuts. A survey of Yurii Nesterov's contributions, written after he received the 2026 Gauss Prize, was a fitting backdrop. The application evidence we have is vendor-reported, so we flag it as such below.

Theory

Interior-point and Newton-type methods. Ma, Végh and Vladu revisit interior-point methods for 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 starting point is the 1991 Kojima–Megiddo–Noma–Yoshise method, and the title claims that Newton steps are faster for these problems. The abstract excerpt we have does not give the new running time, so we won't quote a bound. In a related paper, Mohammad-Nezhad, Sampourmahani and Terlaky study semidefinite optimization without strict complementarity. In that case the central path can have fractional-power behaviour and is not differentiable in the barrier parameter. They show that a common ramification exponent N removes this obstruction for a whole family of weighted AHO central paths, which is the setting needed for superlinear local convergence. Separately, Dvurechensky, Geiersbach, Hintermüller and coauthors propose a globalized stochastic semismooth Newton method for strongly convex problems in Hilbert spaces. It accepts or rejects a full Newton trial step using a stochastic residual test, and replaces rejected steps with damped steps along the same Newton direction.

Stochastic gradient methods. Zijian Liu addresses random reshuffling (RR), the sample-without-replacement variant of SGD used in practice. The paper's title says that, for smooth convex optimization, RR dominates SGD. RR has long been treated as a heuristic because its theory lagged behind its empirical success. Vaidyan, Alacaoglu and Friedlander study last-iterate convergence of proximal and projected stochastic gradient methods without bounded-domain or bounded-variance assumptions, using black-box variational inference as the running example. This matters because practitioners return the last iterate, not an average. For decentralized training, Alghunaim, Cai and Sayed examine gradient tracking. Standard bounds contain a factor Δ_λ^{-3}, where Δ_λ is the absolute spectral gap of the mixing matrix. They show that even for two agents with identical quadratic objectives, the steady-state mean-square disagreement scales as α²σ²Δ_λ^{-3} as the nontrivial eigenvalue approaches −1, under the step-size conditions stated in the paper. In plain words, the cubic dependence in the bound is not just an artifact of the proof. Feng and Paudice study gradient descent for adversarial training with large constant step sizes, which is the regime used in practice, not the small-step flow limit.

Lower bounds and structure. Kang Liu studies how many parallel query rounds are needed to find approximate stationary points of weakly convex functions. In the stated parameter regime and in high dimensions, the standard subgradient rate cannot be beaten, even by randomized algorithms making polynomially many parallel queries per round. This limits what parallelism can buy in that regime. It does not rule out gains elsewhere, and the abstract notes that the order structure of the real line does allow faster search. Nylöf, Nietert, Pallage and coauthors lift composite problems over Gaussian measures (Bures–Wasserstein space) into Euclidean spaces of affine transport maps. This lets accelerated proximal gradient (FISTA-style) methods apply, and the authors name the resulting algorithm BW-FISTA.

Hardness and combinatorics. Di Summa proves that integer linear feasibility is strongly NP-complete even when every row and column has exactly two nonzeros and the support forms a single cycle. Linchuan Wei proves that minimizing an integer cubic over three nonnegative integers is NP-hard, which marks a sharp dimension boundary for fixed-dimension cubic integer optimization. On the positive side, Chao Xu computes Cunningham's canonical decomposition of a symmetric submodular function on n elements in O(n³) time. The decomposition represents all minimum cuts in linear space.

Background reading. Gasnikov, Gornov, Dvinskikh and coauthors survey Nesterov's work. They write after the International Mathematical Union announced his 2026 Gauss Prize at the International Congress of Mathematicians in Philadelphia. The paper explains the recognized work and traces its influence on computational practice.

In practice

Timefold, the open-source planning solver, has a published case study with AWS about e-switch. Timefold and AWS report that the optimized operational planning produced over $100 million in annual cost savings and more than 10 million kg of avoided carbon emissions. These are vendor-reported figures that we could not independently verify, and the post is not necessarily from this week. See Optimizing operational planning for sustainability: e-switch's AI solution with Timefold and AWS.

A related academic example is Online Optimization for Controlling HVAC Systems by Wu, Baumann, Fontan and coauthors. It uses economic model predictive control and designs online algorithms that solve the control problem under a limited computational budget. We have only the abstract, so we can't report deployment results.

Worth watching

Sources: - Optimizing operational planning for sustainability: e-switch's AI solution with Timefold and AWS

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: