We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We … Read more
We present AutoOPT, a domain-specific harness for end-to-end automation of optimization research. AutoOPT organizes the discovery of optimal first-order methods into four stages: numerical design through the BnB-PEP methodology; symbolic discovery of the analytic description and a convergence proof through frontier large language models (LLMs); formal verification in the Lean 4 proof assistant; and human … Read more
Augmented Lagrangian (AL) methods are a classical framework for constrained optimization, but for directly verifiable approximate KKT points, known first-order complexity bounds for standard inexact AL methods are suboptimal, while the best known proximal augmented Lagrangian (PAL) bounds retain an additional logarithmic factor. We consider linearly constrained convex composite problems with a smooth convex term … Read more
We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this … Read more
Very recently (2026), Bauschke and Tung extended from finite- to infinite-dimensional Hilbert spaces a result published by Meshulam in 1996 (following an earlier result of Aharoni-Duchet-Wajnryb from 1984) regarding the boundedness of infinite products of relaxed projections onto a finite family of closed affine subspaces. In the present note we extend in various ways the … Read more
The pair \( (p,e) \) is hyperbolic if \( p : \mathbb{R}^{n} \to \mathbb{R} \) is a homogeneous polynomial, if \( e \in \mathbb{R}^{n} \), if \( p(e) > 0 \), and if the roots of \( t \mapsto p(te – x) \) are real for all \( x \in \mathbb{R}^{n} \). In that case, … Read more
We consider a general class of “inexactly smooth” convex functions, providing a universal model capturing as special cases $L$-smooth, $M$-Lipschitz, and H\”older smooth functions, and any combination thereof. Such functions possess a calculus closely following that of smooth functions. Our main results provide inexactly smooth functions with interpolation theorems that are necessary and sufficient … Read more
It is well-known that first-order methods can offer accelerated convergence rates in the presence of growth structures. Restarting schemes provide a general tool for such speed-ups. These schemes typically either require unrealistic problem knowledge, incur logarithmic overhead factors in oracle complexity, and/or have a nontrivial initial burn-in phase. We present a parameter-free approach for restarting … Read more
We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more
We propose Log-Averaged Mirror Prox (LAMP), a linear-space primal-dual method for large-scale optimal transport. LAMP implements primal mirror prox updates by tracking an averaged dual sequence, reducing storage complexity from \({O}(nm)\) to \({O}(n+m)\) while preserving dense, GPU-friendly reductions. Consequently, LAMP preserves the last-iterate \(\widetilde{{O}}( nm\varepsilon^{-1})\) arithmetic complexity of conservatively parameterized primal-dual mirror prox. We further … Read more