| title | Non-Oblivious Performance of Random Projections | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| booktitle | Proceedings of the 16th Asian Conference on Machine Learning | ||||||||||
| year | 2025 | ||||||||||
| volume | 260 | ||||||||||
| series | Proceedings of Machine Learning Research | ||||||||||
| month | 0 | ||||||||||
| publisher | PMLR | ||||||||||
| https://raw.githubusercontent.com/mlresearch/v260/main/assets/skorski25a/skorski25a.pdf | |||||||||||
| url | https://proceedings.mlr.press/v260/skorski25a.html | ||||||||||
| software | https://github.com/maciejskorski/NonobliviousRademacherProjections/ | ||||||||||
| openreview | 9XBg73M0BE | ||||||||||
| abstract | Random projections are a cornerstone of high-dimensional computations. However, their analysis has proven both difficult and inadequate in capturing the empirically observed accuracy. To bridge this gap, this paper studies random projections from a novel perspective, focusing on data-dependent, that is, \emph{non-oblivious}, performance. The key contribution is the precise and data-dependent accuracy analysis of Rademacher random projections, achieved through elegant geometric methods of independent interest, namely, \emph{Schur-concavity}. The result formally states the following property: the less spread-out the data is, the better the accuracy. This leads to notable improvements in accuracy guarantees for data characterized by sparsity or distributed with a small spread. The key tool is a novel algebraic framework for proving Schur-concavity properties, which offers an alternative to derivative-based criteria commonly used in related studies. We demonstrate its value by providing an alternative proof for the extension of the celebrated Khintchine inequality. | ||||||||||
| layout | inproceedings | ||||||||||
| issn | 2640-3498 | ||||||||||
| id | skorski25a | ||||||||||
| tex_title | Non-Oblivious Performance of Random Projections | ||||||||||
| firstpage | 1128 | ||||||||||
| lastpage | 1143 | ||||||||||
| page | 1128-1143 | ||||||||||
| order | 1128 | ||||||||||
| cycles | false | ||||||||||
| bibtex_editor | Nguyen, Vu and Lin, Hsuan-Tien | ||||||||||
| editor |
|
||||||||||
| bibtex_author | Skorski, Maciej and Temperoni, Alessandro | ||||||||||
| author |
|
||||||||||
| date | 2025-01-14 | ||||||||||
| address | |||||||||||
| container-title | Proceedings of the 16th Asian Conference on Machine Learning | ||||||||||
| genre | inproceedings | ||||||||||
| issued |
|
||||||||||
| extras |