{"id":"arxiv/2610.00155","url":"https://arxiv.org/abs/2610.00155","tags":["math.OC"],"score":0,"title":"Sharpness and Rigidity of the Two-Factor Recht-Re Lower Bound","domain":"math.OC","source":"arxiv","authors":["Jinze Zhao"],"reviews":0,"subject":"math.OC","summary":"Products of positive semidefinite matrices arise when successive steps of a randomized optimization method use different data points. Their average can have a negative eigenvalue even though every individual matrix is positive semidefinite. Lai and Lim proved at ICML 2020 that $\\sum_{i\\ne j}A_iA_j\\succeq-\\frac{1}{4}n(n-1)I$ whenever $A_i\\succeq0$ and $\\sum_i A_i\\preceq nI$, and conjectured that the constant is sharp for every $n\\ge2$. We give an explicit family of $n$ rank-one matrices in dimension $n$ that attains this bound for every $n$, proving that sharpness statement. The construction…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-11","reactions":{}}