{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T20:57:13Z","timestamp":1790542633337,"version":"4.1.0"},"reference-count":47,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T00:00:00Z","timestamp":1586908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7,1]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>We provide a new computationally efficient class of estimators for risk minimization. We show that these estimators are robust for general statistical models, under varied robustness settings, including in the classical Huber \u03b5-contamination model, and in heavy-tailed settings. Our workhorse is a novel robust variant of gradient descent, and we provide conditions under which our gradient descent variant provides accurate estimators in a general convex risk minimization problem. We provide specific consequences of our theory for linear regression and logistic regression and for canonical parameter estimation in an exponential family. These results provide some of the first computationally tractable and provably robust estimators for these canonical statistical models. Finally, we study the empirical performance of our proposed methods on synthetic and real data sets, and we find that our methods convincingly outperform a variety of baselines.<\/jats:p>","DOI":"10.1111\/rssb.12364","type":"journal-article","created":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T07:41:46Z","timestamp":1586936506000},"page":"601-627","source":"Crossref","is-referenced-by-count":54,"title":["Robust Estimation via Robust Gradient Estimation"],"prefix":"10.1093","volume":"82","author":[{"given":"Adarsh","family":"Prasad","sequence":"first","affiliation":[{"name":"Carnegie Mellon University , Pittsburgh , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arun Sai","family":"Suggala","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University , Pittsburgh , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivaraman","family":"Balakrishnan","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University , Pittsburgh , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pradeep","family":"Ravikumar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University , Pittsburgh , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2020,4,15]]},"reference":[{"key":"2023022408364342500_","first-page":"20","volume-title":"Proc. 28th A. Symp. Theory of Computing","author":"Alon","year":"1996"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1214\/16-AOS1435","article-title":"Statistical guarantees for the EM algorithm: from population to sample-based analysis","volume":"45","author":"Balakrishnan","year":"2017","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","first-page":"721","volume-title":"Advances in Neural Information Processing Systems 28","author":"Bhatia","year":"2015"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1093\/biomet\/40.3-4.318","article-title":"Non-normality and tests on variances","volume":"40","author":"Box","year":"1953","journal-title":"Biometrika"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"2507","DOI":"10.1214\/15-AOS1350","article-title":"Empirical risk minimization for heavy-tailed losses","volume":"43","author":"Brownlees","year":"2015","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1561\/2200000050","article-title":"Convex optimization: algorithms and complexity","volume":"8","author":"Bubeck","year":"2015","journal-title":"Foundns Trends Mach. Learn."},{"issue":"no. 3","key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1970392.1970395","article-title":"Robust principal component analysis","volume":"58","author":"Cand\u00e8s","year":"2011","journal-title":"J. Ass. Comput. Mach."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1214\/11-AIHP454","article-title":"Challenging the empirical mean and empirical variance: a deviation study","volume":"48","author":"Catoni","year":"2012","journal-title":"Ann. Inst. H. Poincar\u00e9"},{"key":"2023022408364342500_","volume-title":"Proc. 49th A. Symp. Theory of Computing","author":"Charikar","year":"2017"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"3752","DOI":"10.1214\/16-EJS1216","article-title":"A general decision theory for Huber\u2019s epsilon-contamination model","volume":"10","author":"Chen","year":"2016","journal-title":"Electron. J. Statist."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"1932","DOI":"10.1214\/17-AOS1607","article-title":"Robust covariance and scatter matrix estimation under Huber\u2019s contamination model","volume":"46","author":"Chen","year":"2018","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","first-page":"774","volume-title":"Robust sparse regression under adversarial corruption","author":"Chen","year":"2013"},{"key":"2023022408364342500_","volume-title":"Nonparametric Density Estimation: the L1 View","author":"Devroye","year":"1985"},{"key":"2023022408364342500_","first-page":"655","volume-title":"Foundations of Computer Science","author":"Diakonikolas","year":"2016"},{"key":"2023022408364342500_","first-page":"999","volume-title":"Proc. Int. Conf. Machine Learning","author":"Diakonikolas","year":"2017"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1214\/aos\/1176350820","article-title":"The \u201cautomatic\u201d robustness of minimum distance functionals","volume":"16","author":"Donoho","year":"1988","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","first-page":"169","article-title":"Computationally efficient robust estimation of sparse functionals","author":"Du","year":"2017","journal-title":"Proc. 30th Conf. Learning Theory, Amsterdam, July 7th\u201310th"},{"key":"2023022408364342500_","volume-title":"Variance-based regularization with convex objectives","author":"Duchi","year":"2016"},{"key":"2023022408364342500_","volume-title":"A shrinkage principle for heavy-tailed data: high-dimensional robust low-rank matrix recovery","author":"Fan","year":"2016"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/358669.358692","article-title":"Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography","volume":"24","author":"Fischler","year":"1981","journal-title":"Communs ACM"},{"key":"2023022408364342500_","volume-title":"Robust regression via mutivariate regression depth","author":"Gao","year":"2017"},{"key":"2023022408364342500_","volume-title":"Empirical Processes in M-estimation","author":"van de Geer","year":"2000"},{"key":"2023022408364342500_","volume-title":"Robust Statistics: the Approach based on Influence Functions","author":"Hampel","year":"2011"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1214\/aoms\/1177730388","article-title":"Low moments for small samples: a comparative study of order statistics","volume":"18","author":"Hastings","year":"1947","journal-title":"Ann. Math. Statist."},{"key":"2023022408364342500_","volume-title":"Sub-Gaussian mean estimation in polynomial time","author":"Hopkins","year":"2018"},{"key":"2023022408364342500_","first-page":"1","article-title":"Loss minimization and parameter estimation with heavy tails","volume":"17","author":"Hsu","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1214\/aoms\/1177703732","article-title":"Robust estimation of a location parameter","volume":"35","author":"Huber","year":"1964","journal-title":"Ann. Math. Statist."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"1753","DOI":"10.1214\/aoms\/1177699803","article-title":"A robust version of the probability ratio test","volume":"36","author":"Huber","year":"1965","journal-title":"Ann. Math. Statist."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","DOI":"10.1002\/0471725250","volume-title":"Robust Statistics","author":"Huber","year":"1981"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random generation of combinatorial structures from a uniform distribution","volume":"43","author":"Jerrum","year":"1986","journal-title":"Theor. Comput. Sci."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1007\/978-3-319-46128-1_50","volume-title":"Proc. Eur. Conf. Machine Learning and Knowledge Discovery in Databases","author":"Karimi","year":"2016"},{"key":"2023022408364342500_","first-page":"665","volume-title":"Foundations of Computer Science","author":"Lai","year":"2016"},{"key":"2023022408364342500_","volume-title":"Robust machine learning by median-of-means: theory and practice","author":"Lecu\u00e9","year":"2017"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1109\/TPAMI.2005.92","article-title":"Acquiring linear subspaces for face recognition under variable lighting","volume":"27","author":"Lee","year":"2005","journal-title":"IEEE Trans. Pattn Anal. Mach. Intell."},{"key":"2023022408364342500_","volume-title":"Robust empirical mean estimators","author":"Lerasle","year":"2011"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1214\/16-AOS1471","article-title":"Statistical consistency and asymptotic normality for high-dimensional robust m-estimators","volume":"45","author":"Loh","year":"2017","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","first-page":"2726","volume-title":"Advances in Neural Information Processing Systems","author":"Loh","year":"2011"},{"key":"2023022408364342500_","first-page":"783","article-title":"Sub-Gaussian estimators of the mean of a random vector","volume":"45","author":"Lugosi","year":"2017","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"925","DOI":"10.4171\/JEMS\/937","article-title":"Risk minimization by median-of-means tournaments","volume":"22","author":"Lugosi","year":"2019","journal-title":"J. Eur. Math. Soc."},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"2308","DOI":"10.3150\/14-BEJ645","article-title":"Geometric median and robust estimation in Banach spaces","volume":"21","author":"Minsker","year":"2015","journal-title":"Bernoulli"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"1681","DOI":"10.1214\/aos\/1043351254","article-title":"On depth and deep points: a calculus","volume":"30","author":"Mizera","year":"2002","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovski","year":"1983"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","article-title":"Regression shrinkage and selection via the lasso","volume":"58","author":"Tibshirani","year":"1996","journal-title":"J. R. Statist. Soc."},{"key":"2023022408364342500_","first-page":"523","volume-title":"Proc. Int. Congr. Mathematicians","author":"Tukey","year":"1975"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1214\/aos\/1176349553","article-title":"Rates of convergence of minimum distance estimators and Kolmogorov\u2019s entropy","volume":"13","author":"Yatracos","year":"1985","journal-title":"Ann. Statist."},{"key":"2023022408364342500_","first-page":"4152","volume-title":"Advances in Neural Information Processing Systems 29","author":"Yi","year":"2016"},{"key":"2023022408364342500_","doi-asserted-by":"crossref","first-page":"1904","DOI":"10.1214\/17-AOS1606","article-title":"A new perspective on robust M-estimation: finite sample theory and applications to dependence-adjusted multiple testing","volume":"46","author":"Zhou","year":"2018","journal-title":"Ann. Statist."}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1111%2Frssb.12364","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/82\/3\/601\/49323880\/jrsssb_82_3_601.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/82\/3\/601\/49323880\/jrsssb_82_3_601.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,4]],"date-time":"2024-08-04T00:56:40Z","timestamp":1722733000000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/82\/3\/601\/7056105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,15]]},"references-count":47,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2020,4,15]]},"published-print":{"date-parts":[[2020,7,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12364","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,7]]},"published":{"date-parts":[[2020,4,15]]}}}