Remove logarithmic gaps in minimax sample complexity for matrix normal covariance estimation
Sourced from the work of Rafael Mendes de Oliveira, William Cole Franks, Akshay Ramachandran, Michael Walter
§ Problem Statement
Setup
Let and let denote the set of real symmetric positive-definite matrices. Assume i.i.d. matrix-normal observations with mean zero and
for unknown and . This implies
The parameterization is non-identifiable up to reciprocal scaling: and , , induce the same distribution.
For , define the Fisher--Rao distance
and the Thompson distance
For pairs, use scale-invariant losses
For , define minimax risk
where the infimum is over all measurable estimators based on .
Unsolved Problem
Determine the exact finite-sample order (up to universal constant factors, with no slack) of and , and equivalently determine the sharp minimax sample complexities
by proving matching upper and lower bounds that differ only by absolute constants and contain no extra logarithmic factors in .
§ Discussion
§ Significance & Implications
The source paper reports that matrix-normal bounds are minimax-optimal only up to logarithmic factors; closing this would remove the remaining known finite-sample rate gap. Absent a dedicated post-2021 resolution sweep, this problem appears open.
§ Known Partial Results
Oliveira et al. (2021): This paper proves nonasymptotic guarantees for the MLE with sample complexity/rates minimax-optimal up to logarithmic factors, without conditioning/sparsity assumptions or initialization requirements.
§ References
Near Optimal Sample Complexity for Matrix and Tensor Normal Models via Geodesic Convexity
Rafael Mendes de Oliveira, William Cole Franks, Akshay Ramachandran, Michael Walter (2021)
Annals of Statistics (accepted; to appear, 2025+ context)
📍 Abstract, p. 1 (arXiv v3 full text): "For the matrix normal model, all our bounds are minimax optimal up to logarithmic factors." Related open-direction discussion is in Section 8 (Conclusion and open problems).
Primary source paper (preprint first posted in 2021; later revised and accepted to Annals of Statistics).