Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

Jie Gao, Rajesh Jayaram, Benedikt Kolbe, Shay Sapir, Chris Schwiegelshohn, Sandeep Silwal, Erik Waingarten
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:18363-18385, 2025.

Abstract

Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the doubling dimension $\lambda_X$ of the underlying dataset $X$—a quantity measuring intrinsic dimensionality of point sets. Specifically, the dimension required is $O(\lambda_X)$, which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence grow with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-gao25e, title = {Randomized Dimensionality Reduction for {E}uclidean Maximization and Diversity Measures}, author = {Gao, Jie and Jayaram, Rajesh and Kolbe, Benedikt and Sapir, Shay and Schwiegelshohn, Chris and Silwal, Sandeep and Waingarten, Erik}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {18363--18385}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/gao25e/gao25e.pdf}, url = {https://proceedings.mlr.press/v267/gao25e.html}, abstract = {Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the doubling dimension $\lambda_X$ of the underlying dataset $X$—a quantity measuring intrinsic dimensionality of point sets. Specifically, the dimension required is $O(\lambda_X)$, which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence grow with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.} }
Endnote
%0 Conference Paper %T Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures %A Jie Gao %A Rajesh Jayaram %A Benedikt Kolbe %A Shay Sapir %A Chris Schwiegelshohn %A Sandeep Silwal %A Erik Waingarten %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-gao25e %I PMLR %P 18363--18385 %U https://proceedings.mlr.press/v267/gao25e.html %V 267 %X Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the doubling dimension $\lambda_X$ of the underlying dataset $X$—a quantity measuring intrinsic dimensionality of point sets. Specifically, the dimension required is $O(\lambda_X)$, which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence grow with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.
APA
Gao, J., Jayaram, R., Kolbe, B., Sapir, S., Schwiegelshohn, C., Silwal, S. & Waingarten, E.. (2025). Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:18363-18385 Available from https://proceedings.mlr.press/v267/gao25e.html.

Related Material