2023/03/21 by Maciej Skórski, Skorski, Maciej, Alessandro Temperoni +1
Mathematics · #Advanced Combinatorial Mathematics #Algebraic number #Artificial intelligence #Computer science #Corollary #Discrete mathematics #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Mathematics #Novelty #Perspective (graphical) #Property (philosophy) #Random Matrices and Applications #Theoretical computer science
paper · pdf · doi:10.48550/arxiv.2303.11774
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper revisits the performance of Rademacher random projections, establishing novel statistical guarantees that are numerically sharp and non-oblivious with respect to the input data. More specifically, the central result is the Schur-concavity property of Rademacher random projections with respect to the inputs. This offers a novel geometric perspective on the performance of random projections, while improving quantitatively on bounds from previous works. As a corollary of this broader result, we obtained the improved performance on data which is sparse or is distributed with small spread. This non-oblivious analysis is a novelty compared to techniques from previous work, and bridges the frequently observed gap between theory and practise. The main result uses an algebraic framework for proving Schur-concavity properties, which is a contribution of independent interest and an elegant alternative to derivative-based criteria.