RPCD worst-case conjecture for positive-definite quadratics
Let be the dimension, let be a positive-definite quadratic Hessian with , and let . If denotes the output of random-permutation coordinate descent (RPCD) after epochs, then
RPCD worst-case conjecture. The upper bound above, proved for the specified permutation-invariant class of quadratic Hessians, extends to all positive-definite quadratic functions. This would imply that the class contains worst-case examples for RPCD among all positive-definite quadratics. The conjecture is motivated by numerical searches and is presented as an open extension beyond the class analyzed in the paper.
References
- Donghwa Kim, Jaewook Lee and Chulhee Yun, “Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent”, arXiv:2505.23152 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.