The Grimmer--Shu--Wang Certificate and the Drori--Teboulle Minimax Constant-Stepsize Bound for $N\ge 3$

Abstract

We prove, for every horizon \(N\ge 3\), the existence of the strengthened low-rank performance-estimation certificate proposed by Grimmer, Shu, and Wang for the Drori--Teboulle constant-step gradient-descent bound. For each \(N\ge 3\), let \(ρ_N\in(0,1)\) be determined by \(ρ_N^{2N}(2Nρ_N+2N+1)=1\). We show that the GSW certificate equations admit positive vectors \(a,b,c,d\) satisfying all residual equations. The proof proceeds through a reduced residual system in the variables \(d\), a simplex existence argument for a positive reduced zero, a terminal residual completion identity, and a tail-square convolution argument proving the cumulative margins that force \(b>0\) and then \(a>0\). Consequently, the GSW low-rank PEP certificate exists for every \(N\ge 3\) and yields the Drori--Teboulle upper bound. We also include the one-dimensional quadratic and Huber lower-bound examples for nonnegative steps, while the quadratic example excludes negative constant steps from being optimal. Together these prove the Drori--Teboulle minimax constant-stepsize value over all real constant steps for every \(N\ge 3\).

58 pages