Sharpness and Rigidity of the Two-Factor Recht-Re Lower Bound
Abstract
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 ∑i≠ jAiAj⪰−1/4n(n−1)I whenever Ai⪰0 and ∑i Ai⪯ nI, and conjectured that the constant is sharp for every n≥2. 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 compresses one direction of an orthonormal basis by a factor 1/√2. We also give a short, self-contained proof of the known inequality and classify all equality cases: every extremizer contains a common invariant n-dimensional block equivalent to the construction. Consequently, dimension n is necessary for equality, and positive definite matrices approach but never attain the lower endpoint. Finally, strongly convex quadratic objectives realize the extremal negative eigenvalue as a two-step expected gradient-descent update.
Related
- A sharp lower bound for torsional rigidity of convex domains
- Spectral almost rigidity on Kähler manifolds with positive Ricci lower bound
- Pseudodifferential structure, rigidity, and sharpness for the Steklov problem on differential forms
- CRANDALL-PAZY RIGIDITY FOR LOWER SEMICONTINUOUS CONVEX FUNCTIONS: A BALANCED MEDIAN-FLOW ARGUMENT
- Direct-product rigidity and factor reconstruction for monoids with zero
BibTeX
@misc{zhao2026sharpness,
title = {{Sharpness and Rigidity of the Two-Factor Recht-Re Lower Bound}},
author = {Jinze Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00155},
eprint = {2610.00155},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00155},
}
RIS
TY - UNPB
TI - Sharpness and Rigidity of the Two-Factor Recht-Re Lower Bound
AU - Jinze Zhao
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00155
UR - https://arxiv.org/abs/2610.00155
AB - 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 ∑_i≠ jA_iA_j⪰−1/4n(n−1)I whenever A_i⪰0 and ∑_i A_i⪯ nI, and conjectured that the constant is sharp for every n≥2. 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 compresses one direction of an orthonormal basis by a factor 1/√2. We also give a short, self-contained proof of the known inequality and classify all equality cases: every extremizer contains a common invariant n-dimensional block equivalent to the construction. Consequently, dimension n is necessary for equality, and positive definite matrices approach but never attain the lower endpoint. Finally, strongly convex quadratic objectives realize the extremal negative eigenvalue as a two-step expected gradient-descent update.
ER -