Document Open Access Logo

One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation

Authors Amit Deshpande, Rameshwar Pratap

PDF

Files

Thumbnail PDF
PDF
LIPIcs.ICALP.2022.51.pdf
  • Filesize: 0.71 MB
  • 14 pages
PDF
LIPIcs.ICALP.2022.51-corrigendum.pdf
  • Filesize: 429 kB

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation β†’ Streaming models
  • Mathematics of computing β†’ Dimensionality reduction
  • Computing methodologies β†’ Dimensionality reduction and manifold learning
  • Theory of computation β†’ Sketching and sampling
Keywords
  • Subspace approximation
  • streaming algorithms
  • low-rank approximation
  • adaptive sampling
  • volume sampling
  • subset selection

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We consider the problem of subset selection for 𝓁_p subspace approximation, that is, to efficiently find a small subset of data points such that solving the problem optimally for this subset gives a good approximation to solving the problem optimally for the original input. Previously known subset selection algorithms based on volume sampling and adaptive sampling [Deshpande and Varadarajan, 2007], for the general case of p ∈ [1, ∞), require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for 𝓁_p subspace approximation, for any p ∈ [1, ∞). Earlier subset selection algorithms that give a one-pass multiplicative (1+Ξ΅) approximation work under the special cases. Cohen et al. [Michael B. Cohen et al., 2017] gives a one-pass subset section that offers multiplicative (1+Ξ΅) approximation guarantee for the special case of 𝓁₂ subspace approximation. Mahabadi et al. [Sepideh Mahabadi et al., 2020] gives a one-pass noisy subset selection with (1+Ξ΅) approximation guarantee for 𝓁_p subspace approximation when p ∈ {1, 2}. Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any p ∈ [1, ∞).

Cite As Get BibTex

Amit Deshpande and Rameshwar Pratap. One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.51

Author Details

Amit Deshpande
  • Microsoft Research, Bengaluru, India
Rameshwar Pratap
  • Indian Institute of Technology, Mandi, H.P., India

Acknowledgements

We would like to thank anonymous reviewers for their careful reading of our manuscript and their insightful comments and suggestions.

References

  1. Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes. In 29th Annual Conference on Learning Theory (COLT), volume 49, pages 103-115. PMLR, 2016. URL: http://proceedings.mlr.press/v49/anari16.html.
  2. David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027-1035. SIAM, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283494.
  3. Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Approximate k-means++ in sublinear time. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI'16, pages 1459-1467. AAAI Press, 2016. Google Scholar
  4. Olivier Bachem, Mario Lucic, Seyed Hamed Hassani, and Andreas Krause. Fast and provably good seedings for k-means. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 55-63, 2016. URL: https://proceedings.neurips.cc/paper/2016/hash/d67d8ab4f4c10bf22aa353e27879133c-Abstract.html.
  5. Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, and David P. Woodruff. A PTAS for lp-low rank approximation. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 747-766. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.47.
  6. Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 517-528. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00055.
  7. Haiyan Cai. Exact bound for the convergence of metropolis chains. Stochastic Analysis and Applications, 18(1):63-71, 2000. URL: https://doi.org/10.1080/07362990008809654.
  8. M. T. CHAO. A general purpose unequal probability sampling plan. Biometrika, 69(3):653-656, December 1982. URL: https://doi.org/10.1093/biomet/69.3.653.
  9. Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P. Woodruff. Algorithms for 𝓁_p low-rank approximation. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 806-814. PMLR, 06-11 August 2017. URL: https://proceedings.mlr.press/v70/chierichetti17a.html.
  10. Kenneth L. Clarkson and David P. Woodruff. Low-rank approximation and regression in input sparsity time. J. ACM, 63(6), January 2017. URL: https://doi.org/10.1145/3019134.
  11. Michael B. Cohen, Cameron Musco, and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1758-1777. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.115.
  12. Chen Dan, Hong Wang, Hongyang Zhang, Yuchen Zhou, and Pradeep K Ravikumar. Optimal analysis of subset-selection based l_p low-rank approximation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dquotesingle AlchΓ©-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL: https://proceedings.neurips.cc/paper/2019/file/80a8155eb153025ea1d513d0b2c4b675-Paper.pdf.
  13. Michal Derezinski and Manfred K. Warmuth. Unbiased estimates for linear regression via volume sampling. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3084-3093, 2017. URL: https://proceedings.neurips.cc/paper/2017/hash/54e36c5ff5f6a1802925ca009f3ebb68-Abstract.html.
  14. Amit Deshpande, Praneeth Kacham, and Rameshwar Pratap. Robust k-means++. In Ryan P. Adams and Vibhav Gogate, editors, Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2020, virtual online, August 3-6, 2020, volume 124 of Proceedings of Machine Learning Research, pages 799-808. AUAI Press, 2020. URL: http://proceedings.mlr.press/v124/deshpande20a.html.
  15. Amit Deshpande, Luis Rademacher, Santosh S. Vempala, and Grant Wang. Matrix approximation and projective clustering via volume sampling. Theory Comput., 2(12):225-247, 2006. URL: https://doi.org/10.4086/toc.2006.v002a012.
  16. Amit Deshpande and Kasturi Varadarajan. Sampling-based dimension reduction for subspace approximation. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 641-650, New York, NY, USA, 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1250790.1250884.
  17. Amit Deshpande and Santosh S. Vempala. Adaptive sampling and fast low-rank matrix approximation. In Josep DΓ­az, Klaus Jansen, JosΓ© D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, volume 4110 of Lecture Notes in Computer Science, pages 292-303. Springer, 2006. URL: https://doi.org/10.1007/11830924_28.
  18. Inderjit S. Dhillon and Dharmendra S. Modha. Concept decompositions for large sparse text data using clustering. Mach. Learn., 42(1/2):143-175, 2001. URL: https://doi.org/10.1023/A:1007612920971.
  19. Charlie Dickens, Graham Cormode, and David Woodruff. Leveraging well-conditioned bases: Streaming and distributed summaries in Minkowski p-norms. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1243-1251. PMLR, 10-15 July 2018. URL: https://proceedings.mlr.press/v80/dickens18a.html.
  20. Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompositions. SIAM J. Matrix Anal. Appl., 30(2):844-881, 2008. URL: https://doi.org/10.1137/07070471X.
  21. Pavlos S. Efraimidis and Paul (Pavlos) Spirakis. Weighted random sampling. In Encyclopedia of Algorithms, pages 2365-2367. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_478.
  22. Dan Feldman. Introduction to core-sets: an updated survey, 2020. URL: http://arxiv.org/abs/2011.09384.
  23. Dan Feldman, Morteza Monemizadeh, Christian Sohler, and David P. Woodruff. Coresets and sketches for high dimensional subspace approximation problems. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 630-649. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.53.
  24. Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. ACM, 51(6):1025-1041, 2004. URL: https://doi.org/10.1145/1039488.1039494.
  25. Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions : Simple and deterministic matrix sketching. CoRR, abs/1501.01711, 2015. URL: http://arxiv.org/abs/1501.01711.
  26. Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff. Frequent directions: Simple and deterministic matrix sketching. SIAM J. Comput., 45(5):1762-1792, 2016. URL: https://doi.org/10.1137/15M1009718.
  27. Mina Ghashami and Jeff M. Phillips. Relative errors for deterministic low-rank matrix approximations. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, pages 707-717, USA, 2014. Society for Industrial and Applied Mathematics. Google Scholar
  28. Venkatesan Guruswami and Ali Kemal Sinop. Optimal column-based low-rank matrix reconstruction. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1207-1214. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.95.
  29. Yasutoshi Ida, Sekitoshi Kanai, Yasuhiro Fujiwara, Tomoharu Iwata, Koh Takeuchi, and Hisashi Kashima. Fast deterministic CUR matrix decomposition with accuracy assurance. In Hal DaumΓ© III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4594-4603. PMLR, 13-18 July 2020. URL: http://proceedings.mlr.press/v119/ida20a.html.
  30. Edo Liberty. Simple and deterministic matrix sketching. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '13, pages 581-588, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2487575.2487623.
  31. Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, and Samson Zhou. Non-adaptive adaptive sampling on turnstile streams. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1251-1264. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384331.
  32. Michael W Mahoney. Randomized algorithms for matrices and data. arXiv preprint, 2011. URL: http://arxiv.org/abs/1104.5557.
  33. Michael W. Mahoney and Petros Drineas. CUR matrix decompositions for improved data analysis. Proc. Natl. Acad. Sci. USA, 106(3):697-702, 2009. URL: https://doi.org/10.1073/pnas.0803205106.
  34. Rameshwar Pratap, Anup Anand Deshmukh, Pratheeksha Nair, and Tarun Dutt. A faster sampling algorithm for spherical dollarkdollar-means. In Jun Zhu and Ichiro Takeuchi, editors, Proceedings of The 10th Asian Conference on Machine Learning, ACML 2018, Beijing, China, November 14-16, 2018, volume 95 of Proceedings of Machine Learning Research, pages 343-358. PMLR, 2018. URL: http://proceedings.mlr.press/v95/pratap18a.html.
  35. Jeffrey Scott Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw., 11(1):37-57, 1985. URL: https://doi.org/10.1145/3147.3165.
  36. Shusen Wang and Zhihua Zhang. Improving CUR matrix decomposition and the nystrΓΆm approximation via adaptive sampling. J. Mach. Learn. Res., 14(1):2729-2769, 2013. URL: http://dl.acm.org/citation.cfm?id=2567748.
  37. Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 1954-1963, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
Β© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact