{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:36:36Z","timestamp":1787315796428,"version":"build-2736575974"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T00:00:00Z","timestamp":1634860800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>In today\u2019s era of big data, robust least-squares regression becomes a more challenging problem when considering the extremely corrupted labels along with explosive growth of datasets. Traditional robust methods can handle the noise but suffer from several challenges when applied in huge dataset including (1) computational infeasibility of handling an entire dataset at once, (2) existence of heterogeneously distributed corruption, and (3) difficulty in corruption estimation when data cannot be entirely loaded. This article proposes online and distributed robust regression approaches, both of which can concurrently address all the above challenges. Specifically, the distributed algorithm optimizes the regression coefficients of each data block via heuristic hard thresholding and combines all the estimates in a distributed robust consolidation. In addition, an online version of the distributed algorithm is proposed to incrementally update the existing estimates with new incoming data. Furthermore, a novel online robust regression method is proposed to estimate under a biased-batch corruption. We also prove that our algorithms benefit from strong robustness guarantees in terms of regression coefficient recovery with a constant upper bound on the error of state-of-the-art batch methods. Extensive experiments on synthetic and real datasets demonstrate that our approaches are superior to those of existing methods in effectiveness, with competitive efficiency.<\/jats:p>","DOI":"10.1145\/3473038","type":"journal-article","created":{"date-parts":[[2021,10,23]],"date-time":"2021-10-23T00:28:40Z","timestamp":1634948920000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Online and Distributed Robust Regressions with Extremely Noisy Labels"],"prefix":"10.1145","volume":"16","author":[{"given":"Shuo","family":"Lei","sequence":"first","affiliation":[{"name":"Virginia Tech, Falls Church, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuchao","family":"Zhang","sequence":"additional","affiliation":[{"name":"NEC Laboratories America, Princeton, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liang","family":"Zhao","sequence":"additional","affiliation":[{"name":"Emory University, Atlanta, GA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnold P.","family":"Boedihardjo","sequence":"additional","affiliation":[{"name":"Maxar Technologies Inc., Herndon, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chang-Tien","family":"Lu","sequence":"additional","affiliation":[{"name":"Virginia Tech, Falls Church, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOS918"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.econlet.2011.09.031"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1120.1641"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/2969239.2969320"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/3042817.3042862"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/3042817.3043023"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248566"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-009-9639-8"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0741"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2011.610456"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021068"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0824-9"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2004.830985"},{"key":"e_1_3_2_17_2","unstructured":"Jiashi Feng Huan Xu and Shie Mannor. 2017. Outlier robust online learning. arXiv:1701.00251. Retrieved from http:\/\/arxiv.org\/abs\/1701.00251."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358163"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330790"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-013-1467-4"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/2986459.2986763"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1756008"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/0470010940"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2010.2055862"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/2968826.2968873"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2240435"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOS793"},{"key":"e_1_3_2_28_2","volume-title":"Robust Regression and Outlier Detection","author":"Rousseeuw Peter J.","year":"2005","unstructured":"Peter J. Rousseeuw and Annick M. Leroy. 2005. Robust Regression and Outlier Detection. Vol. 589, John Wiley & Sons."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1967.1089674"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/cem.2792"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2011.tm10390"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2048473"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2014.2306328"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.6165"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00199"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314105"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.6166"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.72"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.72"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/3172077.3172369"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2012.2183773"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3473038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:11:57Z","timestamp":1750176717000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3473038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,22]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3473038"],"URL":"https:\/\/doi.org\/10.1145\/3473038","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,22]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}