{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T15:39:17Z","timestamp":1768923557454,"version":"3.49.0"},"reference-count":52,"publisher":"MIT Press","issue":"7","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Gradient descent methods are simple and efficient optimization algorithms with widespread applications. To handle high-dimensional problems, we study compressed stochastic gradient descent (SGD) with low-dimensional gradient updates. We provide a detailed analysis in terms of both optimization rates and generalization rates. To this end, we develop uniform stability bounds for CompSGD for both smooth and nonsmooth problems, based on which we develop almost optimal population risk bounds. Then we extend our analysis to two variants of SGD: batch and mini-batch gradient descent. Furthermore, we show that these variants achieve almost optimal rates compared to their high-dimensional gradient setting. Thus, our results provide a way to reduce the dimension of gradient updates without affecting the convergence rate in the generalization analysis. Moreover, we show that the same result also holds in the differentially private setting, which allows us to reduce the dimension of added noise with \u201calmost free\u201d cost.<\/jats:p>","DOI":"10.1162\/neco_a_01588","type":"journal-article","created":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T22:20:11Z","timestamp":1684189211000},"page":"1234-1287","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":3,"title":["Optimization and Learning With Randomly Compressed Gradient Updates"],"prefix":"10.1162","volume":"35","author":[{"given":"Zhanliang","family":"Huang","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Birmingham B15 277, U.K. zxh898@student.bham.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunwen","family":"Lei","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Hong Kong Baptist University, Hong Kong, China yunwen@hkbu.edu.hk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ata","family":"Kab\u00e1n","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Birmingham B15 277, U.K. A.Kaban@bham.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2023,6,12]]},"reference":[{"key":"2023061316474734400_B1","author":"Agarwal","year":"2018","journal-title":"CPSGD: Communication-efficient and differentially-private distributed SGD"},{"key":"2023061316474734400_B2","article-title":"QSGD: Communication-efficient SGD via gradient quantization and encoding","volume-title":"Advances in neural information processing systems","author":"Alistarh","year":"2017"},{"key":"2023061316474734400_B3","first-page":"5973","article-title":"The convergence of sparsified gradient methods","volume-title":"Advances in neural information processing systems","author":"Alistarh","year":"2018"},{"issue":"4","key":"2023061316474734400_B4","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1214\/12-STS394","article-title":"Structured sparsity through convex optimization","volume":"27","author":"Bach","year":"2012","journal-title":"Statistical Science"},{"key":"2023061316474734400_B5","article-title":"Privacy amplification by subsampling: Tight analyses via couplings and divergences","volume-title":"Advances in neural information processing systems","author":"Balle","year":"2018"},{"key":"2023061316474734400_B6","first-page":"4529","article-title":"Stability and generalization of bilevel programming in hyperparameter optimization","volume-title":"Advances in neural information processing systems","author":"Bao","year":"2021"},{"issue":"473","key":"2023061316474734400_B7","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1198\/016214505000000907","article-title":"Convexity, classification, and risk bounds","volume":"101","author":"Bartlett","year":"2006","journal-title":"Journal of the American Statistical Association"},{"key":"2023061316474734400_B8","first-page":"4381","article-title":"Stability of stochastic gradient descent on nonsmooth convex losses","volume-title":"Advances in neural information processing systems","author":"Bassily","year":"2020"},{"key":"2023061316474734400_B9","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1109\/FOCS.2014.56","article-title":"Private empirical risk minimization: Efficient algorithms and tight error bounds","volume-title":"Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Bassily","year":"2014"},{"issue":"2","key":"2023061316474734400_B10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/16M1080173","article-title":"Optimization methods for large-scale machine learning","volume":"60","author":"Bottou","year":"2018","journal-title":"Siam Review"},{"key":"2023061316474734400_B11","first-page":"499","article-title":"Stability and generalization","volume":"2","author":"Bousquet","year":"2002","journal-title":"Journal of Machine Learning Research"},{"key":"2023061316474734400_B12","first-page":"745","article-title":"Stability and generalization of learning algorithms that converge to global optima","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Charles","year":"2018"},{"key":"2023061316474734400_B13","first-page":"13773","article-title":"Understanding gradient clipping in private SGD: A geometric perspective","volume-title":"Advances in neural information processing systems","author":"Chen","year":"2020"},{"key":"2023061316474734400_B14","author":"Chen","year":"2018","journal-title":"Stability and convergence trade-off of iterative optimization algorithms"},{"issue":"1","key":"2023061316474734400_B15","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","article-title":"An elementary proof of a theorem of Johnson and Lindenstrauss","volume":"22","author":"Dasgupta","year":"2003","journal-title":"Random Structures and Algorithms"},{"issue":"5","key":"2023061316474734400_B16","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1109\/TIT.1979.1056087","article-title":"Distribution-free performance bounds for potential function rules","volume":"25","author":"Devroye","year":"1979","journal-title":"IEEE Transactions on Information Theory"},{"key":"2023061316474734400_B17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/11787006_1","article-title":"Differential privacy","volume-title":"Proceedings of the 33rd International Colloquium on Automata, Languages and Programming","author":"Dwork","year":"2006"},{"key":"2023061316474734400_B18","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/11681878_14","article-title":"Calibrating noise to sensitivity in private data analysis","volume-title":"Theory of cryptography","author":"Dwork","year":"2006"},{"issue":"3\u20134","key":"2023061316474734400_B19","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1561\/0400000042","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork","year":"2014","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"2023061316474734400_B20","first-page":"55","article-title":"Stability of randomized learning algorithms","volume":"6","author":"Elisseeff","year":"2005","journal-title":"Journal of Machine Learning Research"},{"key":"2023061316474734400_B21","first-page":"451","article-title":"Multi-task sparse structure learning","volume-title":"Proceedings of the 23rd ACM International Conference on Information and Knowledge Management","author":"Gon\u00e7alves","year":"2014"},{"key":"2023061316474734400_B22","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/BFb0081737","article-title":"On Milman's inequality and random subspaces which escape through a mesh in Rn","volume-title":"Geometric aspects of functional analysis","author":"Gordon","year":"1988"},{"key":"2023061316474734400_B23","first-page":"1225","article-title":"Train faster, generalize better: Stability of stochastic gradient descent","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Hardt","year":"2016"},{"key":"2023061316474734400_B24","author":"Jaggi","year":"2011","journal-title":"Sparse convex optimization methods for machine learning"},{"key":"2023061316474734400_B25","first-page":"65","article-title":"A new look at nearest neighbours: Identifying benign input geometries via random projections","volume-title":"Proceedings of the Asian Conference on Machine Learning","author":"Kab\u00e1n","year":"2016"},{"key":"2023061316474734400_B26","first-page":"1905","article-title":"SGD with low-dimensional gradients with applications to private and distributed learning","volume-title":"Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence","author":"Kasiviswanathan","year":"2021"},{"key":"2023061316474734400_B27","author":"Kenthapadi","year":"2012","journal-title":"Privacy via the Johnson-Lindenstrauss transform"},{"issue":"2","key":"2023061316474734400_B28","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1109\/JSTSP.2015.2505682","article-title":"Mini-batch semi-stochastic gradient descent in the proximal setting","volume":"10","author":"Kone\u010dn\u1ef3","year":"2015","journal-title":"IEEE Journal of Selected Topics in Signal Processing"},{"key":"2023061316474734400_B29","first-page":"2815","article-title":"Data-dependent stability of stochastic gradient descent","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Kuzborskij","year":"2018"},{"key":"2023061316474734400_B30","first-page":"5809","article-title":"Fine-grained analysis of stability and generalization for stochastic gradient descent","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Lei","year":"2020"},{"key":"2023061316474734400_B31","article-title":"Sharper generalization bounds for learning with gradient-dominated objective functions","volume-title":"Proceedings of the ICLR Conference Paper","author":"Lei","year":"2021"},{"key":"2023061316474734400_B32","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/1557019.1557082","article-title":"Large-scale sparse logistic regression","volume-title":"ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Liu","year":"2009"},{"key":"2023061316474734400_B33","first-page":"2159","article-title":"Algorithmic stability and hypothesis complexity","volume-title":"Proceedings of the 34th International Conference on Machine Learning","author":"Liu","year":"2017"},{"issue":"1","key":"2023061316474734400_B34","first-page":"7808","article-title":"Stability and generalization in structured prediction","volume":"17","author":"London","year":"2016","journal-title":"Journal of Machine Learning Research"},{"key":"2023061316474734400_B35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ins.2018.05.004","article-title":"Large-scale distributed sparse class-imbalance learning","volume":"456","author":"Maurya","year":"2018","journal-title":"Information Sciences"},{"key":"2023061316474734400_B36","volume-title":"Introductory lectures on convex optimization","author":"Nesterov","year":"2003"},{"key":"2023061316474734400_B37","author":"Nikolakakis","year":"2022","journal-title":"Beyond Lipschitz: Sharp generalization and excess risk bounds for full-batch"},{"key":"2023061316474734400_B38","first-page":"8609","article-title":"Stability and generalization of gradient descent for shallow neural networks without the neural tangent kernel","volume-title":"Advances in neural information processing systems","author":"Richards","year":"2021"},{"key":"2023061316474734400_B39","first-page":"2635","article-title":"Learnability, stability and uniform convergence","volume":"11","author":"Shalev-Shwartz","year":"2010","journal-title":"Journal of Machine Learning Research"},{"key":"2023061316474734400_B40","first-page":"71","article-title":"Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes","volume-title":"International Conference on Machine Learning","author":"Shamir","year":"2013"},{"key":"2023061316474734400_B41","first-page":"186","article-title":"Privacy-utility trade-off of linear regression under random projections and additive noise","volume-title":"Proceedings of the 2018 IEEE International Symposium on Information Theory","author":"Showkatbakhsh","year":"2018"},{"key":"2023061316474734400_B42","first-page":"245","article-title":"Stochastic gradient descent with differentially private updates","volume-title":"Proceedings of the 2013 IEEE Global Conference on Signal and Information processing","author":"Song","year":"2013"},{"key":"2023061316474734400_B43","first-page":"4447","article-title":"Sparsified SGD with memory","volume-title":"Advances in neural information processing systems","author":"Stich","year":"2018"},{"issue":"4","key":"2023061316474734400_B44","first-page":"769","article-title":"A convex formulation for high-dimensional sparse sliced inverse regression","volume":"105","author":"Tan","year":"2018","journal-title":"Biometrika"},{"key":"2023061316474734400_B45","first-page":"6526","article-title":"Differentially private empirical risk minimization with non-convex loss functions","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Wang","year":"2019"},{"key":"2023061316474734400_B46","first-page":"9850","article-title":"ATOMO: Communication-efficient learning via atomic sparsification","volume-title":"Advances in neural information processing systems","author":"Wang","year":"2018"},{"key":"2023061316474734400_B47","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1016\/j.acha.2021.09.001","article-title":"Differentially private SGD with non-smooth losses","volume":"56","author":"Wang","year":"2022","journal-title":"Applied and Computational Harmonic Analysis"},{"key":"2023061316474734400_B48","first-page":"26523","article-title":"On the algorithmic stability of adversarial training","volume-title":"Advances in neural information processing systems","author":"Xing","year":"2021"},{"issue":"12","key":"2023061316474734400_B49","doi-asserted-by":"publisher","first-page":"3081","DOI":"10.1109\/TIFS.2017.2737966","article-title":"DPPro: Differentially private high-dimensional data release via random projection","volume":"12","author":"Xu","year":"2017","journal-title":"IEEE Transactions on Information Forensics and Security"},{"key":"2023061316474734400_B50","first-page":"568","article-title":"Generalization bounds for stochastic saddle point problems","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Zhang","year":"2021"},{"key":"2023061316474734400_B51","doi-asserted-by":"crossref","DOI":"10.1145\/1015330.1015332","article-title":"Solving large scale linear prediction problems using stochastic gradient descent algorithms","volume-title":"Proceedings of the Twenty-First International Conference on Machine Learning","author":"Zhang","year":"2004"},{"key":"2023061316474734400_B52","author":"Zhao","year":"2014","journal-title":"Accelerating minibatch stochastic gradient descent using stratified sampling"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/7\/1234\/2127140\/neco_a_01588.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/neco\/article-pdf\/35\/7\/1234\/2127140\/neco_a_01588.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T16:48:28Z","timestamp":1686674908000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/35\/7\/1234\/115999\/Optimization-and-Learning-With-Randomly-Compressed"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,12]]},"references-count":52,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,6,12]]},"published-print":{"date-parts":[[2023,6,12]]}},"URL":"https:\/\/doi.org\/10.1162\/neco_a_01588","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,7]]},"published":{"date-parts":[[2023,6,12]]}}}