Proceedings

Ridgeless Regression with Random Features

Video #1 Video #2 Download BibTeX Cite

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence. Main Track. Pages 3208-3214.

https://doi.org/10.24963/ijcai.2022/445

Abstract

Recent theoretical studies illustrated that kernel ridgeless regression can guarantee good generalization ability without an explicit regularization. In this paper, we investigate the statistical properties of ridgeless regression with random features and stochastic gradient descent. We explore the effect of factors in the stochastic gradient and random features, respectively. Specifically, random features error exhibits the double-descent curve. Motivated by the theoretical findings, we propose a tunable kernel algorithm that optimizes the spectral density of kernel during training. Our work bridges the interpolation theory and practical algorithm.

  1. [Advani et al., 2020] Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of gen- eralization error in neural networks. Neural Networks, 132:428-446, 2020.
  2. [Bartlett et al., 2005] Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities. The Annals of Statistics, 33(4):1497-1537, 2005.
  3. [Bartlett et al., 2020] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in lin- ear regression. Proceedings of the National Academy of Sciences, 117(48):30063-30070, 2020.
  4. [Belkin et al., 2018] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. arXiv preprint arXiv:1802.01396, 2018.
  5. [Caponnetto and De Vito, 2007] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
  6. [Carratino et al., 2018] Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with sgd and random fea- tures. In Advances in Neural Information Processing Sys- tems 31 (NeurIPS), pages 10192-10203, 2018.
  7. [Geiger et al., 2020] Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d'Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scal- ing description of generalization with number of parame- ters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2):023401, 2020.
  8. [Ghorbani et al., 2021] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Lin- earized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-1054, 2021.
  9. [Hastie et al., 2019] Trevor Hastie, Andrea Montanari, Sa- haron Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560, 2019.
  10. [Jacot et al., 2020] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Im- plicit regularization of random feature models. In Inter- national Conference on Machine Learning, pages 4631- 4640. PMLR, 2020.
  11. [Li and Liu, 2022] Jian Li and Yong Liu. Optimal rates for distributed learning with random features. In Proceedings of the 31st International Joint Conference on Artificial In- telligence (IJCAI), 2022.
  12. [Li et al., 2018] Jian Li, Yong Liu, Rong Yin, Hua Zhang, Lizhong Ding, and Weiping Wang. Multi-class learning: From theory to algorithm. In Advances in Neural Informa- tion Processing Systems 31, pages 1591-1600, 2018.
  13. [Li et al., 2019] Jian Li, Yong Liu, Rong Yin, and Weiping Wang. Multi-class learning using unlabeled samples : Theory and algorithm. In Proceedings of the 28th Interna- tional Joint Conference on Artificial Intelligence (IJCAI), 2019. IJCAI
  14. [Li et al., 2020] Jian Li, Yong Liu, and Weiping Wang. Au- tomated spectral kernel learning. In Thirty-Four AAAI Conference on Artificial Intelligence, 2020.
  15. [Liang and Rakhlin, 2020] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329-1347, 2020.
  16. [Mei and Montanari, 2019] Song Mei and Andrea Monta- nari. The generalization error of random features regres- sion: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2019.
  17. [Nakkiran et al., 2021] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.
  18. [Rahimi and Recht, 2007] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems 21 (NIPS), pages 1177-1184, 2007.
  19. [Rahimi and Recht, 2008] Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing min- imization with randomization in learning. In Advances in Neural Information Processing Systems 22 (NIPS), pages 1313-1320, 2008.
  20. [Rudi and Rosasco, 2017] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with ran- dom features. In Advances in Neural Information Process- ing Systems 30 (NIPS), pages 3215-3225, 2017.
  21. [Rudi et al., 2018] Alessandro Rudi, Daniele Calandriello, Luigi Carratino, and Lorenzo Rosasco. On fast lever- age score sampling and optimal learning. In Advances in Neural Information Processing Systems, pages 5672- 5682, 2018.
  22. [Smale and Zhou, 2007] Steve Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their approximations. Constructive approximation, 26(2):153- 172, 2007.
  23. [Zhang et al., 2021] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards