{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:41Z","timestamp":1750220081061,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2022,5,26]]},"abstract":"<jats:p>We analyze the convergence rate of gradient flows on objective functions induced by Dropout and Dropconnect, when applying them to shallow linear Neural Networks(NN) ---which can also be viewed as doing matrix factorization using a particular regularizer. Dropout algorithms such as these are thus regularization techniques that use 0,1-valued random variables to filter weights during training in order to avoid coadaptation of features. By leveraging a recent result on nonconvex optimization and conducting a careful analysis of the set of minimizers as well as the Hessian of the loss function, we are able to obtain (i) a local convergence proof of the gradient flow and (ii) a bound on the convergence rate that depends on the data, the dropout probability, and the width of the NN. Finally, we compare this theoretical bound to numerical simulations, which are in qualitative agreement with the convergence bound and match it when starting sufficiently close to a minimizer.<\/jats:p>","DOI":"10.1145\/3530898","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T17:16:18Z","timestamp":1654535778000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Asymptotic Convergence Rate of Dropout on Shallow Linear Neural Networks"],"prefix":"10.1145","volume":"6","author":[{"given":"Albert","family":"Senen-Cerda","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jaron","family":"Sanders","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/0024-3795(89)90580-6"},{"key":"e_1_2_1_2_1","volume-title":"7th International Conference on Learning Representations, ICLR","author":"Arora Sanjeev","year":"2019","unstructured":"Sanjeev Arora , Noah Golowich , Nadav Cohen , and Wei Hu . 2019 . A convergence analysis of gradient descent for deep linear neural networks . In 7th International Conference on Learning Representations, ICLR 2019. Sanjeev Arora, Noah Golowich, Nadav Cohen, and Wei Hu. 2019. A convergence analysis of gradient descent for deep linear neural networks. In 7th International Conference on Learning Representations, ICLR 2019."},{"volume-title":"\u00af An introduction to Lie groups and the geometry of homogeneous spaces","author":"Arvanitogeorgos Andreas","unstructured":"Andreas Arvanitogeorgos . 2003. \u00af An introduction to Lie groups and the geometry of homogeneous spaces . Vol. 22 . American Mathematical Soc . Andreas Arvanitogeorgos. 2003. \u00af An introduction to Lie groups and the geometry of homogeneous spaces. Vol. 22. American Mathematical Soc.","key":"e_1_2_1_3_1"},{"unstructured":"Jimmy Ba and Brendan Frey. 2013. Adaptive Dropout for training deep neural networks. In Advances in Neural Information Processing Systems. 3084--3092.  Jimmy Ba and Brendan Frey. 2013. Adaptive Dropout for training deep neural networks. In Advances in Neural Information Processing Systems. 3084--3092.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1093\/imaiai\/iaaa039"},{"key":"e_1_2_1_6_1","volume-title":"Sadowski","author":"Baldi Pierre","year":"2013","unstructured":"Pierre Baldi and Peter J . Sadowski . 2013 . Understanding Dropout. In Advances in Neural Information Processing Systems . 2814--2822. Pierre Baldi and Peter J. Sadowski. 2013. Understanding Dropout. In Advances in Neural Information Processing Systems. 2814--2822."},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.5555\/2743145.2743774"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1162\/neco_a_01164"},{"key":"e_1_2_1_9_1","volume-title":"Tsitsiklis","author":"Bertsekas Dimitri P.","year":"1996","unstructured":"Dimitri P. Bertsekas and John N . Tsitsiklis . 1996 . Neuro-dynamic programming. Athena Scientific . Dimitri P. Bertsekas and John N. Tsitsiklis. 1996. Neuro-dynamic programming. Athena Scientific."},{"volume-title":"Real algebraic geometry","author":"Bochnak Jacek","unstructured":"Jacek Bochnak , Michel Coste , and Marie-Fran\u00e7oise Roy . 2013. Real algebraic geometry . Vol. 36 . Springer Science & Business Media . Jacek Bochnak, Michel Coste, and Marie-Fran\u00e7oise Roy. 2013. Real algebraic geometry. Vol. 36. Springer Science & Business Media.","key":"e_1_2_1_10_1"},{"volume-title":"Stochastic approximation: a dynamical systems viewpoint","author":"Borkar Vivek S.","unstructured":"Vivek S. Borkar . 2009. Stochastic approximation: a dynamical systems viewpoint . Vol. 48 . Springer . Vivek S. Borkar. 2009. Stochastic approximation: a dynamical systems viewpoint. Vol. 48. Springer.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 435--444","author":"Cavazza Jacopo","year":"2018","unstructured":"Jacopo Cavazza , Pietro Morerio , Benjamin Haeffele , Connor Lane , Vittorio Murino , and Rene Vidal . 2018 . Dropout as a low-rank regularizer for matrix factorization . In International Conference on Artificial Intelligence and Statistics. PMLR, 435--444 . Jacopo Cavazza, Pietro Morerio, Benjamin Haeffele, Connor Lane, Vittorio Murino, and Rene Vidal. 2018. Dropout as a low-rank regularizer for matrix factorization. In International Conference on Artificial Intelligence and Statistics. PMLR, 435--444."},{"key":"e_1_2_1_13_1","volume-title":"Taylor","author":"DeVries Terrance","year":"2017","unstructured":"Terrance DeVries and Graham W . Taylor . 2017 . Improved regularization of convolutional neural networks with Cutout . arXiv preprint arXiv:1708.04552 (2017). Terrance DeVries and Graham W. Taylor. 2017. Improved regularization of convolutional neural networks with Cutout. arXiv preprint arXiv:1708.04552 (2017)."},{"key":"e_1_2_1_14_1","first-page":"136","article-title":"Convergence rates for the stochastic gradient descent method for non-convex objective functions","volume":"21","author":"Fehrman Benjamin","year":"2020","unstructured":"Benjamin Fehrman , Benjamin Gess , and Arnulf Jentzen . 2020 . Convergence rates for the stochastic gradient descent method for non-convex objective functions . Journal of Machine Learning Research 21 (2020), 136 . Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. 2020. Convergence rates for the stochastic gradient descent method for non-convex objective functions. Journal of Machine Learning Research 21 (2020), 136.","journal-title":"Journal of Machine Learning Research"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1016\/j.commatsci.2018.07.052"},{"key":"e_1_2_1_16_1","volume-title":"Salakhutdinov","author":"Hinton Geoffrey E.","year":"2012","unstructured":"Geoffrey E. Hinton , Nitish Srivastava , Alex Krizhevsky , Ilya Sutskever , and Ruslan R . Salakhutdinov . 2012 . Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv:1207.0580 (2012). Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R. Salakhutdinov. 2012. Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint arXiv:1207.0580 (2012)."},{"key":"e_1_2_1_17_1","volume-title":"On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks. arXiv preprint arXiv:2112.09684","author":"Jentzen Arnulf","year":"2021","unstructured":"Arnulf Jentzen and Adrian Riekert . 2021. On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks. arXiv preprint arXiv:2112.09684 ( 2021 ). Arnulf Jentzen and Adrian Riekert. 2021. On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks. arXiv preprint arXiv:2112.09684 (2021)."},{"key":"e_1_2_1_18_1","first-page":"586","article-title":"Deep Learning without Poor Local Minima","volume":"29","author":"Kawaguchi Kenji","year":"2016","unstructured":"Kenji Kawaguchi . 2016 . Deep Learning without Poor Local Minima . Advances in Neural Information Processing Systems 29 (2016), 586 -- 594 . Kenji Kawaguchi. 2016. Deep Learning without Poor Local Minima. Advances in Neural Information Processing Systems 29 (2016), 586--594.","journal-title":"Advances in Neural Information Processing Systems"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.22489\/CinC.2016.181-266"},{"unstructured":"Durk P. Kingma Tim Salimans and Max Welling. 2015. Variational Dropout and the local reparameterization trick. In Advances in Neural Information Processing Systems. 2575--2583.  Durk P. Kingma Tim Salimans and Max Welling. 2015. Variational Dropout and the local reparameterization trick. In Advances in Neural Information Processing Systems. 2575--2583.","key":"e_1_2_1_20_1"},{"unstructured":"Alex Krizhevsky. 2009. Learning multiple layers of features from tiny images. (2009).  Alex Krizhevsky. 2009. Learning multiple layers of features from tiny images. (2009).","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","volume-title":"Hinton","author":"Krizhevsky Alex","year":"2012","unstructured":"Alex Krizhevsky , Ilya Sutskever , and Geoffrey E . Hinton . 2012 . ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems . 1097--1105. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2012. ImageNet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems. 1097--1105."},{"key":"e_1_2_1_23_1","volume-title":"Yin","author":"Kushner Harold J.","year":"2003","unstructured":"Harold J. Kushner and George G . Yin . 2003 . Stochastic approximation and recursive algorithms and applications. Vol. 35 . Springer Science & Business Media . Harold J. Kushner and George G. Yin. 2003. Stochastic approximation and recursive algorithms and applications. Vol. 35. Springer Science & Business Media."},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1109\/5.726791"},{"key":"e_1_2_1_25_1","volume-title":"MNIST handwritten digit database. ATT Labs [Online]. Available: http:\/\/yann.lecun.com\/exdb\/mnist 2","author":"LeCun Yann","year":"2010","unstructured":"Yann LeCun , Corinna Cortes , and CJ Burges . 2010. MNIST handwritten digit database. ATT Labs [Online]. Available: http:\/\/yann.lecun.com\/exdb\/mnist 2 ( 2010 ). Yann LeCun, Corinna Cortes, and CJ Burges. 2010. MNIST handwritten digit database. ATT Labs [Online]. Available: http:\/\/yann.lecun.com\/exdb\/mnist 2 (2010)."},{"key":"e_1_2_1_26_1","volume-title":"Gradient descent converges to minimizers. arXiv preprint arXiv:1602.04915","author":"Lee Jason D.","year":"2016","unstructured":"Jason D. Lee , Max Simchowitz , Michael I. Jordan , and Benjamin Recht . 2016. Gradient descent converges to minimizers. arXiv preprint arXiv:1602.04915 ( 2016 ). Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. 2016. Gradient descent converges to minimizers. arXiv preprint arXiv:1602.04915 (2016)."},{"volume-title":"Introduction to Smooth Manifolds","author":"Lee John M.","unstructured":"John M. Lee . 2013. Smooth manifolds . In Introduction to Smooth Manifolds . Springer , 1--31. John M. Lee. 2013. Smooth manifolds. In Introduction to Smooth Manifolds. Springer, 1--31.","key":"e_1_2_1_27_1"},{"unstructured":"Zhe Li Boqing Gong and Tianbao Yang. 2016. Improved Dropout for shallow and deep learning. In Advances in Neural Information Processing Systems. 2523--2531.  Zhe Li Boqing Gong and Tianbao Yang. 2016. Improved Dropout for shallow and deep learning. In Advances in Neural Information Processing Systems. 2523--2531.","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","volume-title":"Arnold","author":"Marshall Albert W.","year":"1979","unstructured":"Albert W. Marshall , Ingram Olkin , and Barry C . Arnold . 1979 . Inequalities: theory of majorization and its applications. Vol. 143 . Springer . Albert W. Marshall, Ingram Olkin, and Barry C. Arnold. 1979. Inequalities: theory of majorization and its applications. Vol. 143. Springer."},{"key":"e_1_2_1_30_1","volume-title":"On Dropout and Nuclear Norm Regularization. In International Conference on Machine Learning. 4575--4584","author":"Mianjy Poorya","year":"2019","unstructured":"Poorya Mianjy and Raman Arora . 2019 . On Dropout and Nuclear Norm Regularization. In International Conference on Machine Learning. 4575--4584 . Poorya Mianjy and Raman Arora. 2019. On Dropout and Nuclear Norm Regularization. In International Conference on Machine Learning. 4575--4584."},{"key":"e_1_2_1_31_1","volume-title":"On Convergence and Generalization of Dropout Training. Advances in Neural Information Processing Systems 33","author":"Mianjy Poorya","year":"2020","unstructured":"Poorya Mianjy and Raman Arora . 2020. On Convergence and Generalization of Dropout Training. Advances in Neural Information Processing Systems 33 ( 2020 ). Poorya Mianjy and Raman Arora. 2020. On Convergence and Generalization of Dropout Training. Advances in Neural Information Processing Systems 33 (2020)."},{"key":"e_1_2_1_32_1","volume-title":"On the Implicit Bias of Dropout. In International Conference on Machine Learning. 3540--3548","author":"Mianjy Poorya","year":"2018","unstructured":"Poorya Mianjy , Raman Arora , and Rene Vidal . 2018 . On the Implicit Bias of Dropout. In International Conference on Machine Learning. 3540--3548 . Poorya Mianjy, Raman Arora, and Rene Vidal. 2018. On the Implicit Bias of Dropout. In International Conference on Machine Learning. 3540--3548."},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.5555\/3305890.3305939"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/3305890.3305950"},{"volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition. 7671--7679","author":"Pal Ambar","unstructured":"Ambar Pal , Connor Lane , Ren\u00e9 Vidal , and Benjamin D. Haeffele . 2020. On the regularization properties of structured Dropout . In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition. 7671--7679 . Ambar Pal, Connor Lane, Ren\u00e9 Vidal, and Benjamin D. Haeffele. 2020. On the regularization properties of structured Dropout. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition. 7671--7679.","key":"e_1_2_1_35_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1109\/ICFHR.2014.55"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers. 1757-- 1766","author":"Semeniuta Stanislau","year":"2016","unstructured":"Stanislau Semeniuta , Aliaksei Severyn , and Erhardt Barth . 2016 . Recurrent Dropout without Memory Loss . In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers. 1757-- 1766 . Stanislau Semeniuta, Aliaksei Severyn, and Erhardt Barth. 2016. Recurrent Dropout without Memory Loss. In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers. 1757-- 1766."},{"key":"e_1_2_1_38_1","volume-title":"Almost sure convergence of Dropout algorithms for neural networks. arXiv preprint arXiv:2002.02247","author":"Senen-Cerda Albert","year":"2020","unstructured":"Albert Senen-Cerda and Jaron Sanders . 2020. Almost sure convergence of Dropout algorithms for neural networks. arXiv preprint arXiv:2002.02247 ( 2020 ). Albert Senen-Cerda and Jaron Sanders. 2020. Almost sure convergence of Dropout algorithms for neural networks. arXiv preprint arXiv:2002.02247 (2020)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1007\/978-1-4757-4497-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.5555\/2627435.2670313"},{"key":"e_1_2_1_41_1","volume-title":"Deep learning for drug discovery and cancer research: Automated analysis of vascularization images","author":"Urban Gregor","year":"2018","unstructured":"Gregor Urban , Kevin Bache , Duc T.T. Phan , Agua Sobrino , Alexander K. Shmakov , Stephanie J. Hachey , Christopher C.W. Hughes , and Pierre Baldi . 2018. Deep learning for drug discovery and cancer research: Automated analysis of vascularization images . IEEE\/ACM transactions on computational biology and bioinformatics 16, 3 ( 2018 ), 1029--1035. Gregor Urban, Kevin Bache, Duc T.T. Phan, Agua Sobrino, Alexander K. Shmakov, Stephanie J. Hachey, Christopher C.W. Hughes, and Pierre Baldi. 2018. Deep learning for drug discovery and cancer research: Automated analysis of vascularization images. IEEE\/ACM transactions on computational biology and bioinformatics 16, 3 (2018), 1029--1035."},{"key":"e_1_2_1_42_1","volume-title":"Liang","author":"Wager Stefan","year":"2013","unstructured":"Stefan Wager , Sida Wang , and Percy S . Liang . 2013 . Dropout training as adaptive regularization. In Advances in Neural Information Processing Systems . 351--359. Stefan Wager, Sida Wang, and Percy S. Liang. 2013. Dropout training as adaptive regularization. In Advances in Neural Information Processing Systems. 351--359."},{"key":"e_1_2_1_43_1","volume-title":"International Conference on Machine Learning. 1058--1066","author":"Wan Li","year":"2013","unstructured":"Li Wan , Matthew Zeiler , Sixin Zhang , Yann Le Cun , and Rob Fergus . 2013 . Regularization of neural networks using Dropconnect . In International Conference on Machine Learning. 1058--1066 . Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. 2013. Regularization of neural networks using Dropconnect. In International Conference on Machine Learning. 1058--1066."},{"key":"e_1_2_1_44_1","volume-title":"International Conference on Machine Learning. PMLR, 10181--10192","author":"Wei Colin","year":"2020","unstructured":"Colin Wei , Sham Kakade , and Tengyu Ma . 2020 . The implicit and explicit regularization effects of Dropout . In International Conference on Machine Learning. PMLR, 10181--10192 . Colin Wei, Sham Kakade, and Tengyu Ma. 2020. The implicit and explicit regularization effects of Dropout. In International Conference on Machine Learning. PMLR, 10181--10192."},{"key":"e_1_2_1_45_1","volume-title":"Recurrent neural network regularization. arXiv preprint arXiv:1409.2329","author":"Zaremba Wojciech","year":"2014","unstructured":"Wojciech Zaremba , Ilya Sutskever , and Oriol Vinyals . 2014. Recurrent neural network regularization. arXiv preprint arXiv:1409.2329 ( 2014 ). Wojciech Zaremba, Ilya Sutskever, and Oriol Vinyals. 2014. Recurrent neural network regularization. arXiv preprint arXiv:1409.2329 (2014)."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530898","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:26Z","timestamp":1750183766000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5,26]]}},"alternative-id":["10.1145\/3530898"],"URL":"https:\/\/doi.org\/10.1145\/3530898","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"2022-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}