∇ProvenDecisions
Ctrl K

Stepsizes, curvature reuse and regret: a quiet Sunday for first-order theory

The day in optimization

Sunday's batch was mostly theory. The main themes were sharper guarantees for first- and second-order methods on convex problems, and robustness measured by regret, not just worst-case risk. One hardness result also stood out. I found only one practice item, and it is a vendor report, not a deployment.

Theory

Exact stepsize theory for SGD. Grimmer and Shen analyze stochastic gradient descent on smooth convex problems. They give an exact worst-case analysis of the final iterate's expected suboptimality. It covers any schedule of N stepsizes in [0, 1.5], assuming zero-mean, bounded-variance noise and dimension at least N+1. "Exact" means the bound is attained, so it can't be improved. That lets stepsize schedules be designed optimally instead of just bounded.

Second-order and quasi-Newton complexity. Two papers push the cost of curvature-based methods down: - Zhang et al. study second-order convex finite-sum optimization. The previous minimax rate under averaged smoothness was Θ̃(n + n^{6/7} ε^{-2/7}). Their lower bound under individual smoothness is Ω(n + n^{5/7} ε^{-2/7}), so assuming smoothness for each component separately provably allows faster algorithms. - Mokhtari and Patitucci introduce "certified curvature reuse" for quasi-Newton proximal-extragradient methods. Each iteration spends one finite-difference probe to refresh a group of Hessian columns. A path-length certificate bounds the error of the stale columns. The aim is better gradient complexity without the dimension dependence of earlier online-learning-based analyses.

Robustness and regret. Nietert and Kuhn study Wasserstein-robust least squares (also listed on Optimization Online). Standard distributionally robust optimization (DRO) minimizes worst-case risk. They argue this can leave excess risk (regret) on the table. They analyze regret when the target law differs from the source by a 2-Wasserstein perturbation of size ε, in the small-ε limit. In plain terms, they ask how much is lost relative to knowing the true target, not only how bad the worst case is.

Eigenvectors, stopping and hardness. - Bresch and Melnyk prove global linear convergence for an adjoint-free random-plane method for the top eigenvector. The rate depends on the spectral gap. Earlier work had observed this empirically but lacked a guarantee. - Vu et al. study when one-step lookahead suffices to stop freeze-thaw Bayesian optimization. The rule is to stop once no candidate's expected improvement exceeds its cost. It never does worse than stopping immediately, but the abstract says it can stop too early. - A new Optimization Online note shows that cubic optimization over three nonnegative integers is NP-hard. Deciding whether the value can be at most one is hard even when the minimum is always attained. The authors present this as a sharp dimension boundary.

In practice

Gurobi has released its 2026 State of Mathematical Optimization Report. The company's headline is a growing convergence of AI and optimization. CEO Duke Perrucci says the next opportunity is bringing decision-making capabilities to more people and areas of the business. This is a vendor survey and the company's own framing. It is a signal about where the industry is heading, not independent evidence of results. My search budget ran out before I could find a concrete deployment from this week.

Worth watching

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: