[{"day":"01","type":"conference","intvolume":"       139","status":"public","publication":"Proceedings of the 38th International Conference on Machine Learning","file_date_updated":"2023-06-19T10:49:12Z","page":"8119-8129","month":"07","date_published":"2021-07-01T00:00:00Z","scopus_import":"1","publisher":"ML Research Press","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"MaMo"}],"conference":{"start_date":"2021-07-18","end_date":"2021-07-24","name":"International Conference on Machine Learning","location":"Virtual"},"date_created":"2023-06-18T22:00:48Z","file":[{"access_level":"open_access","date_updated":"2023-06-19T10:49:12Z","file_size":591332,"file_name":"2021_PMLR_Nguyen.pdf","checksum":"19489cf5e16a0596b1f92e317d97c9b0","date_created":"2023-06-19T10:49:12Z","relation":"main_file","content_type":"application/pdf","file_id":"13155","creator":"dernst","success":1}],"citation":{"ama":"Nguyen Q, Mondelli M, Montufar G. Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks. In: <i>Proceedings of the 38th International Conference on Machine Learning</i>. Vol 139. ML Research Press; 2021:8119-8129.","mla":"Nguyen, Quynh, et al. “Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks.” <i>Proceedings of the 38th International Conference on Machine Learning</i>, vol. 139, ML Research Press, 2021, pp. 8119–29.","short":"Q. Nguyen, M. Mondelli, G. Montufar, in:, Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 8119–8129.","ista":"Nguyen Q, Mondelli M, Montufar G. 2021. Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks. Proceedings of the 38th International Conference on Machine Learning. International Conference on Machine Learning vol. 139, 8119–8129.","apa":"Nguyen, Q., Mondelli, M., &#38; Montufar, G. (2021). Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks. In <i>Proceedings of the 38th International Conference on Machine Learning</i> (Vol. 139, pp. 8119–8129). Virtual: ML Research Press.","ieee":"Q. Nguyen, M. Mondelli, and G. Montufar, “Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks,” in <i>Proceedings of the 38th International Conference on Machine Learning</i>, Virtual, 2021, vol. 139, pp. 8119–8129.","chicago":"Nguyen, Quynh, Marco Mondelli, and Guido Montufar. “Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks.” In <i>Proceedings of the 38th International Conference on Machine Learning</i>, 139:8119–29. ML Research Press, 2021."},"publication_status":"published","abstract":[{"lang":"eng","text":"A recent line of work has analyzed the theoretical properties of deep neural networks via the Neural Tangent Kernel (NTK). In particular, the smallest eigenvalue of the NTK has been related to the memorization capacity, the global convergence of gradient descent algorithms and the generalization of deep nets. However, existing results either provide bounds in the two-layer setting or assume that the spectrum of the NTK matrices is bounded away from 0 for multi-layer networks. In this paper, we provide tight bounds on the smallest eigenvalue of NTK matrices for deep ReLU nets, both in the limiting case of infinite widths and for finite widths. In the finite-width setting, the network architectures we consider are fairly general: we require the existence of a wide layer with roughly order of N neurons, N being the number of data samples; and the scaling of the remaining layer widths is arbitrary (up to logarithmic factors). To obtain our results, we analyze various quantities of independent interest: we give lower bounds on the smallest singular value of hidden feature matrices, and upper bounds on the Lipschitz constant of input-output feature maps."}],"author":[{"first_name":"Quynh","full_name":"Nguyen, Quynh","last_name":"Nguyen"},{"id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco","last_name":"Mondelli","full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020"},{"first_name":"Guido","full_name":"Montufar, Guido","last_name":"Montufar"}],"arxiv":1,"article_processing_charge":"No","date_updated":"2024-09-10T13:03:17Z","volume":139,"oa":1,"publication_identifier":{"isbn":["9781713845065"],"eissn":["2640-3498"]},"_id":"13146","project":[{"_id":"059876FA-7A3F-11EA-A408-12923DDC885E","name":"Prix Lopez-Loretta 2019 - Marco Mondelli"}],"quality_controlled":"1","oa_version":"Published Version","acknowledgement":"The authors would like to thank the anonymous reviewers for their helpful comments. MM was partially supported by the 2019 Lopez-Loreta Prize. QN and GM acknowledge support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no 757983).","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2021","title":"Tight bounds on the smallest Eigenvalue of the neural tangent kernel for deep ReLU networks","external_id":{"arxiv":["2012.11654"]},"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"]},{"citation":{"short":"F. Alimisis, P. Davies, D.-A. Alistarh, in:, Proceedings of the 38th International Conference on Machine Learning, ML Research Press, 2021, pp. 196–206.","ista":"Alimisis F, Davies P, Alistarh D-A. 2021. Communication-efficient distributed optimization with quantized preconditioners. Proceedings of the 38th International Conference on Machine Learning. International Conference on Machine Learning vol. 139, 196–206.","ama":"Alimisis F, Davies P, Alistarh D-A. Communication-efficient distributed optimization with quantized preconditioners. In: <i>Proceedings of the 38th International Conference on Machine Learning</i>. Vol 139. ML Research Press; 2021:196-206.","mla":"Alimisis, Foivos, et al. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” <i>Proceedings of the 38th International Conference on Machine Learning</i>, vol. 139, ML Research Press, 2021, pp. 196–206.","chicago":"Alimisis, Foivos, Peter Davies, and Dan-Adrian Alistarh. “Communication-Efficient Distributed Optimization with Quantized Preconditioners.” In <i>Proceedings of the 38th International Conference on Machine Learning</i>, 139:196–206. ML Research Press, 2021.","ieee":"F. Alimisis, P. Davies, and D.-A. Alistarh, “Communication-efficient distributed optimization with quantized preconditioners,” in <i>Proceedings of the 38th International Conference on Machine Learning</i>, Virtual, 2021, vol. 139, pp. 196–206.","apa":"Alimisis, F., Davies, P., &#38; Alistarh, D.-A. (2021). Communication-efficient distributed optimization with quantized preconditioners. In <i>Proceedings of the 38th International Conference on Machine Learning</i> (Vol. 139, pp. 196–206). Virtual: ML Research Press."},"publication_status":"published","abstract":[{"lang":"eng","text":"We investigate fast and communication-efficient algorithms for the classic problem of minimizing a sum of strongly convex and smooth functions that are distributed among n\r\n different nodes, which can communicate using a limited number of bits. Most previous communication-efficient approaches for this problem are limited to first-order optimization, and therefore have \\emph{linear} dependence on the condition number in their communication complexity. We show that this dependence is not inherent: communication-efficient methods can in fact have sublinear dependence on the condition number. For this, we design and analyze the first communication-efficient distributed variants of preconditioned gradient descent for Generalized Linear Models, and for Newton’s method. Our results rely on a new technique for quantizing both the preconditioner and the descent direction at each step of the algorithms, while controlling their convergence rate. We also validate our findings experimentally, showing faster convergence and reduced communication relative to previous methods."}],"author":[{"first_name":"Foivos","last_name":"Alimisis","full_name":"Alimisis, Foivos"},{"id":"11396234-BB50-11E9-B24C-90FCE5697425","full_name":"Davies, Peter","last_name":"Davies","orcid":"0000-0002-5646-9524","first_name":"Peter"},{"first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"arxiv":1,"article_processing_charge":"No","oa":1,"volume":139,"date_updated":"2023-06-19T10:44:38Z","publication_identifier":{"eissn":["2640-3498"],"isbn":["9781713845065"]},"_id":"13147","oa_version":"Published Version","project":[{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"}],"quality_controlled":"1","acknowledgement":"The authors would like to thank Janne Korhonen, Aurelien Lucchi, Celestine MendlerDunner and Antonio Orvieto for helpful discussions. FA ¨and DA were supported during this work by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). PD was supported by the European Union’s Horizon 2020 programme under the Marie Skłodowska-Curie grant agreement No. 754411.","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2021","ec_funded":1,"title":"Communication-efficient distributed optimization with quantized preconditioners","external_id":{"arxiv":["2102.07214"]},"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"],"day":"01","type":"conference","intvolume":"       139","status":"public","publication":"Proceedings of the 38th International Conference on Machine Learning","file_date_updated":"2023-06-19T10:41:05Z","page":"196-206","month":"07","date_published":"2021-07-01T00:00:00Z","scopus_import":"1","publisher":"ML Research Press","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"DaAl"}],"conference":{"name":"International Conference on Machine Learning","end_date":"2021-07-24","location":"Virtual","start_date":"2021-07-18"},"file":[{"relation":"main_file","content_type":"application/pdf","creator":"dernst","file_id":"13154","success":1,"access_level":"open_access","date_updated":"2023-06-19T10:41:05Z","file_size":429087,"file_name":"2021_PMLR_Alimisis.pdf","checksum":"7ec0d59bac268b49c76bf2e036dedd7a","date_created":"2023-06-19T10:41:05Z"}],"date_created":"2023-06-18T22:00:48Z"}]