∇ProvenDecisions
Ctrl K

Stochastic gradient tails, Broximal steps and a quantum speedup headline the day

The day in optimization

Stochastic gradient descent (SGD) analysis was the main theme. Three papers cover it: tail bounds, almost-sure rates and statistical inference for Newton-type methods. Methods for non-Euclidean and non-monotone settings also drew attention, including Broximal descent and proximal point beyond monotone operators. Applied items were mostly about energy, warehouses and mining. Sources: Galli et al., Ou et al., Richtárik and Qian.

Theory

SGD, with guarantees that hold with high probability and almost surely. Galli, Parletta and Paudice study SGD when the sample losses share a minimizer with the population objective (the "interpolation regime"). Most earlier analyses bound the expected error. This paper gives high-probability bounds. In the convex case the rate is of order log(1/β)·n⁻¹ after n iterations, with failure probability at most β. In plain words, a single run, not just the average over many runs, is fast with high confidence. Source. Ou, Paudice and Wang look at the last iterate of SGD for convex objectives, a different mode of convergence (almost sure). They get rates of about k⁻¹/³ for smooth objectives when a stationary minimizer exists and k⁻¹/⁴ otherwise, up to log factors. The k⁻¹/⁴ rate extends to nonsmooth convex objectives. The authors call these rates nearly tight, and the stepsizes are deterministic and anytime. Source.

Newton sketch. Wang, Ye and Na address a known trade-off in online sketched Newton methods. Sketching cuts the per-step cost from O(d³) to O(d²) but inflates the limiting covariance of the iterates, which hurts statistical inference. Their title claims that averaging gradients gives optimal statistical efficiency "for free". The abstract excerpt provided does not say how. Source.

Beyond Euclidean and monotone structure. Richtárik and Qian study Broximal Gradient Descent in a general norm. Each step minimizes a linear model over the feasible set intersected with a norm ball. Unlike the Euclidean case, the distance to a solution can grow, so the usual Fejér-monotonicity argument fails. They use a comparator inequality and an observable stationarity certificate instead. For convex objectives, prescribed radii give value convergence. Source. A related theme is proximal point methods without monotonicity. Brito, Lara and Yuan study set-valued "star-monotone" operators, meaning ⟨u, x − x⟩ ≥ 0 for some zero x (the inner product of the operator's value with the direction back to a solution is nonnegative). This class strictly contains monotone and pseudomonotone operators that have zeros. They prove that Id + cT is surjective for every c > 0 under conditions given in the paper, so proximal iterates exist. Source. Combettes and Pesquet likewise move from single-valued firmly nonexpansive operators to set-valued maximally cohypomonotone ones, for recovering a vector from multiple Wiener systems. They design a splitting method. Source.

Quasi-Newton variants. Two papers adapt BFGS. AG-BFGS adds momentum to learning the inverse-Hessian approximation. The authors prove stability conditions and preservation of positive definiteness, and report consistent numerical gains. Source. Tian, Hu, Yao and coauthors run BFGS on matrix manifolds through "almost-global coordinates". These turn the manifold problem into an unconstrained one, with chart restarts and a limited-memory version. They show stationary points correspond and prove local q-superlinear convergence. Source.

Quantum. Zheng constructs functions on {0,1}ⁿ where vanilla adiabatic quantum optimization finds the global minimizer in polynomial time. Any classical algorithm in the black-box model needs exp(n^Ω(1)) time. This is a subexponential separation in an oracle model, built on earlier work by Leng et al. It says nothing about practical problems. Source.

Risk and robustness. Shapiro and Li show that law-invariant coherent risk measures are not robust to contamination: an arbitrarily small contamination of the probability measure can change their values by an arbitrary amount. Value-at-Risk does not have this problem. Source. Luo, Wang and Liu give an exact reformulation of infinity-Wasserstein distributionally robust PCA, with a finite-sample guarantee and an efficient algorithm. Source.

Inventory and discrete optimization. Hu constructs an echelon-stock (s,S) policy for a one-warehouse multi-retailer system whose long-run expected cost is at most 5/2 times the optimum over all nonanticipative policies, under conditions on penalty and holding rates. This is an upper bound on the policy's cost, not a statement about what is optimal. Source. Akçay, Delorme and Sotirov compare mixed-integer formulations of the quadratic bin packing problem. Source.

In practice

An Evalueserve case study reports that a logistics provider saves over $100M a year after re-optimizing its linehaul network. The model is a mixed-integer program covering a network of more than $700M. It includes fixed facility costs, transport costs for loaded and empty miles, and operational constraints. This is the consultancy's own account, and the page does not appear to be dated this week. Source.

In field-service planning, Timefold reports that its customers see an average 25% reduction in travel time after implementation. This is a vendor claim. Source. The two cases give the vendor-reported scale of savings, not independent verification.

Worth watching

Sources: Evalueserve, Timefold

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: