The Grimmer--Shu--Wang Certificate and the Drori--Teboulle Minimax Constant-Stepsize Bound for $N\ge 3$
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910260088799232 |
|---|---|
| author | Zhang, Lixing |
| author_facet | Zhang, Lixing |
| contents | 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\). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_11421 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Grimmer--Shu--Wang Certificate and the Drori--Teboulle Minimax Constant-Stepsize Bound for $N\ge 3$ Zhang, Lixing Optimization and Control 90C25, 90C30, 65K05, 49M37 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\). |
| title | The Grimmer--Shu--Wang Certificate and the Drori--Teboulle Minimax Constant-Stepsize Bound for $N\ge 3$ |
| topic | Optimization and Control 90C25, 90C30, 65K05, 49M37 |
| url | https://arxiv.org/abs/2605.11421 |