Learning with Asynchronous Labels
Article No.: 186, Pages 1 - 27
Abstract
Learning with data streams has attracted much attention in recent decades. Conventional approaches typically assume that the feature and label of a data item can be timely observed at each round. In many real-world tasks, however, it often occurs that either the feature or the label is observed firstly while the other arrives with delay. For instance, in distributed learning systems, a central processor collects training data from different sub-processors to train a learning model, whereas the feature and label of certain data items can arrive asynchronously due to network latency. The problem of learning with asynchronous feature or label in streams encompasses many applications but still lacks sound solutions. In this article, we formulate the problem and propose a new approach to alleviate the negative effect of asynchronicity and mining asynchronous data streams. Our approach carefully exploits the timely arrived information and builds an online ensemble structure to adaptively reuse historical models and instances. We provide the theoretical guarantees of our approach and conduct extensive experiments to validate its effectiveness.
References
[1]
Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, and Jorge Luis Reyes-Ortiz. 2013. A Public Domain Dataset for Human Activity Recognition Using Smartphones. In Proceedings of the 21st European Symposium on Artificial Neural Networks. 3.
[2]
Yong Bai, Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama, and Zhi-Hua Zhou. 2022. Adapting to Online Label Shift with Provable Guarantees. In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS). 29960–29974.
[3]
Amrit Singh Bedi, Alec Koppel, and Ketan Rajawat. 2019. Asynchronous Online Learning in Multi-agent Systems with Proximity Constraints. IEEE Transactions on Signal and Information Processing over Networks 5, 3 (2019), 479–494.
[4]
Hamed R. Bonab and Fazli Can. 2018. GOOWE: Geometrically Optimum and Online-Weighted Ensemble Classifier for Evolving Data Streams. ACM Transactions on Knowledge Discovery from Data 12, 2 (2018), 25:1–25:33.
[5]
Nicolo Cesa-Bianchi and Gábor Lugosi. 2006. Prediction, Learning, and Games. Cambridge University Press
[6]
Olivier Chapelle. 2014. Modeling Delayed Feedback in Display Advertising. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD). 1097–1105.
[7]
Gong Chen and Marc Teboulle. 1993. Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions. SIAM Journal on Optimization 3, 3 (1993), 538–543.
[8]
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. 2012. Online Optimization with Gradual Variations. In Proceedings of the 25th Annual Conference on Computational Learning Theory (COLT). 6.1–6.20.
[9]
Joãao Duarte, Joãao Gama, and Albert Bifet. 2016. Adaptive Model Rules From High-Speed Data Streams. ACM Transactions on Knowledge Discovery from Data 10, 3 (2016), 30:1–30:22.
[10]
Genevieve Flaspohler, Francesco Orabona, Judah Cohen, Soukayna Mouatadid, Miruna Oprescu, Paulo Orenstein, and Lester Mackey. 2021. Online Learning with Optimism and Delay. In Proceedings of the 38th International Conference on Machine Learning (ICML). 3363–3373.
[11]
Shiry Ginosar, Kate Rakelly, Sarah Sachs, Brian Yin, Crystal Lee, Philipp Krähenbühl, and Alexei A. Efros. 2017. A Century of Portraits: A Visual Historical Record of American High School Yearbooks. IEEE Transactions on Computational Imaging 3, 3 (2017), 421–431.
[12]
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning. MIT Press.
[13]
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. 2017. Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour. arXiv:1706.02677. DOI:
[14]
Maciej Grzenda, Heitor Murilo Gomes, and Albert Bifet. 2020. Delayed Labelling Evaluation for Data Streams. Data Mining and Knowledge Discovery 34, 5 (2020), 1237–1266.
[15]
Lei Guo, Lennart Ljung, and Pierre Priouret. 1993. Performance Analysis of the Forgetting Factor RLS Algorithm. International Journal of Adaptive Control and Aignal Processing 7, 6 (1993), 525–537.
[16]
Elad Hazan. 2016. Introduction to Online Convex Optimization. Foundations and Trends in Optimization 2, 3–4 (2016), 157–325.
[17]
Amélie Héliou, Panayotis Mertikopoulos, and Zhengyuan Zhou. 2020. Gradient-Free Online Learning in Continuous Games with Delayed Rewards. In Proceedings of the 37th International Conference on Machine Learning (ICML). 4172–4181.
[18]
Juan Isidro González Hidalgo, Silas G. T. C. Santos, and Roberto S. M. Barros. 2022. Dynamically Adjusting Diversity in Ensembles for the Classification of Data Streams with Concept Drift. ACM Transactions on Knowledge Discovery from Data 16, 2 (2022), 31:1–31:20.
[19]
Yu-Guan Hsieh, Franck Iutzeler, Jérome Malick, and Panayotis Mertikopoulos. 2022. Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism. Journal of Machine Learning Research 23, 78 (2022), 1–49.
[20]
Pooria Joulani, András György, and Csaba Szepesvári. 2013. Online Learning under Delayed Feedback. In Proceedings of the 34th International Conference on Machine Learning (ICML). 1453–1461.
[21]
Bartosz Krawczyk, Leandro L. Minku, Joao Gama, Jerzy Stefanowski, and Michal Wozniak. 2017. Ensemble Learning for Data Stream Analysis: A Survey. Information Fusion 37 (2017), 132–156.
[22]
Harold W. Kuhn. 1955. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly 2, 1–2 (1955), 83–97.
[23]
Ananya Kumar, Tengyu Ma, and Percy Liang. 2020. Understanding Self-Training for Gradual Domain Adaptation. In Proceedings of the 37th International Conference on Machine Learning (ICML). 5468–5479.
[24]
Jennifer R. Kwapisz, Gary M. Weiss, and Samuel Moore. 2010. Activity Recognition Using Cell Phone Accelerometers. ACM SIGKDD Explorations Newsletter 12, 2 (2010), 74–82.
[25]
Qingyang Li, Zhiwen Yu, Huang Xu, and Bin Guo. 2022. Human-Machine Interactive Streaming Anomaly Detection by Online Self-Adaptive Forest. Frontiers of Computer Science 17, 2 (2022), 172317.
[26]
Yu-Feng Li, James T. Kwok, and Zhi-Hua Zhou. 2009. Semi-Supervised Learning Using Label Mean. In Proceedings of the 26th International Conference on Machine Learning (ICML). 633–640.
[27]
Yair Meidan, Michael Bohadana, Yael Mathov, Yisroel Mirsky, Asaf Shabtai, Dominik Breitenbacher, and Yuval Elovici. 2018. N-BaIoT—Network-Based Detection of IoT Botnet Attacks Using Deep Autoencoders. IEEE Pervasive Computing 17, 3 (2018), 12–22.
[28]
Xin Mu, Kai-Ming Ting, and Zhi-Hua Zhou. 2017. Classification Under Streaming Emerging New Classes: A Solution Using Completely-Random Trees. IEEE Transaction on Knowledge and Data Engineering 29, 8 (2017), 1605–1618. DOI:
[29]
Francesco Orabona. 2019. A Modern Introduction to Online Learning. arXiv:1912.13213.
[30]
Joshua Plasse and Niall M. Adams. 2016. Handling Delayed Labels in Temporally Evolving Data Streams. In Proceedings of the 4th IEEE International Conference on Big Data. 2416–2424.
[31]
Yu-Yang Qian, Yong Bai, Zhen-Yu Zhang, Peng Zhao, and Zhi-Hua Zhou. 2023. Handling New Class in Online Label Shift. In Proceedings of the 23rd IEEE International Conference on Data Mining (ICDM). 1283–1288.
[32]
Kent Quanrud and Daniel Khashabi. 2015. Online Learning with Adversarial Delays. In Proceedings of the Advances in Neural Information Processing Systems 28 (NeurIPS). 1270–1278.
[33]
Alexander Rakhlin and Karthik Sridharan. 2013. Online Learning with Predictable Sequences. In Proceedings of the 26th Annual Conference on Computational Learning Theory (COLT). 993–1019.
[34]
Yuta Saito, Gota Morishita, and Shota Yasui. 2020. Dual Learning Algorithm for Delayed Conversions. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 1849–1852.
[35]
Shai Shalev-Shwartz. 2011. Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning 4, 2 (2011), 107–194.
[36]
Vinicius M. A. Souza, Diego F. Silva, Gustavo EAPA Batista, and Joãao Gama. 2015. Classification of Evolving Data Streams with Infinitely Delayed Labels. In Proceedings of the 14th IEEE International Conference on Machine Learning and Applications. 214–219.
[37]
Suvrit Sra, Adams Wei Yu, Mu Li, and Alexander J. Smola. 2015. AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization. arXiv:1508.05003. DOI:
[38]
Allan Stisen, Henrik Blunck, Sourav Bhattacharya, Thor Siiger Prentow, Mikkel Baun Kjærgaard, Anind Dey, Tobias Sonne, and Mads Møller Jensen. 2015. Smart Devices Are Different: Assessing and Mitigatingmobile Sensing Heterogeneities for Activity Recognition. In Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems. 127–140.
[39]
Yumin Su, Liang Zhang, Quanyu Dai, Bo Zhang, Jinyao Yan, Dan Wang, Yongjun Bao, Sulong Xu, Yang He, and Weipeng Yan. 2021. An Attention-Based Model for Conversion Rate Prediction with Delayed Feedback via Post-Click Calibration. In Proceedings of the 29th International Conference on International Joint Conferences on Artificial Intelligence (IJCAI). 3522–3528.
[40]
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. 2022a. Online Strongly Convex Optimization with Unknown Delays. Machine Learning 111, 3 (2022), 871–893.
[41]
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. 2022b. Online Frank-Wolfe with Arbitrary Delays. In Proceedings of the Advances in Neural Information Processing Systems 35 (NeurIPS). 19703–19715.
[42]
Yuanyu Wan, Yibo Wang, Chang Yao, Wei-Wei Tu, and Lijun Zhang. 2022c. Projection-Free Online Learning with Arbitrary Delays. arXiv:2204.04964. DOI:
[43]
Yuanyu Wan, Chang Yao, Mingli Song, and Lijun Zhang. 2024. Improved Regret for Bandit Convex Optimization with Delayed Feedback. arXiv:2402.09152. DOI:
[44]
Jing Wang, Peng Zhao, and Zhi-Hua Zhou. 2023. Revisiting Weighted Strategy for Non-Stationary Parametric Bandits. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS). 7913–7942.
[45]
Yanshi Wang, Jie Zhang, Qing Da, and Anxiang Zeng. 2020. Delayed Feedback Modeling for the Entire Space Conversion Rate Prediction. arXiv:2011.11826. DOI:
[46]
Marcelo J. Weinberger and Erik Ordentlich. 2002. On Delayed Prediction of Individual Sequences. IEEE Transactions on Information Theory 48, 7 (2002), 1959–1976.
[47]
Muning Wen, Runji Lin, Hanjing Wang, Yaodong Yang, Ying Wen, Luo Mai, Jun Wang, Hai-Feng Zhang, and Weinan Zhang. 2023. Large Sequence Models for Sequential Decision-Making: A Survey. Frontiers of Computer Science 17, 6 (2023), 176349.
[48]
Xindong Wu, Kui Yu, Wei Ding, Hao Wang, and Xingquan Zhu. 2012. Online Feature Selection with Streaming Features. IEEE Transactions on Pattern Analysis and Machine Intelligence 35, 5 (2012), 1178–1192.
[49]
Min Yang, Ying Shen, Xiaojun Chen, and Chengming Li. 2020. Multi-Source Domain Adaptation for Sentiment Classification with Granger Causal Inference. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 1849–1852.
[50]
Xiao Zhang, Haonan Jia, Hanjing Su, Wenhan Wang, Jun Xu, and Ji-Rong Wen. 2021. Counterfactual Reward Modification for Streaming Recommendation with Delayed Feedback. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 41–50.
[51]
Yu-Jie Zhang, Zhen-Yu Zhang, Peng Zhao, and Masashi Sugiyama. 2023b. Adapting to Continuous Covariate Shift via Online Density Ratio Estimation. In Proceedings of the Advances in Neural Information Processing Systems 36 (NeurIPS). 29074–29113.
[52]
Zhao Zhang, Yong Zhang, Da Guo, Shuang Zhao, and Xiaolin Zhu. 2023a. Communication-Efficient Federated Continual Learning for Distributed Learning System with Non-IID Data. Science China Information Sciences 66, 2 (2023).
[53]
Zhen-Yu Zhang, Yu-Yang Qian, Yu-Jie Zhang, Yuan Jiang, and Zhi-Hua Zhou. 2022. Adaptive Learning for Weakly Labeled Streams. In Proceedings of the 28th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD). 2556–2564.
[54]
Peng Zhao, Le-Wen Cai, and Zhi-Hua Zhou. 2020a. Handling Concept Drift via Model Reuse. Machine Learning 109, 3 (2020), 533–568.
[55]
Peng Zhao, Xinqiang Wang, Siyu Xie, Lei Guo, and Zhi-Hua Zhou. 2021. Distribution-Free One-Pass Learning. IEEE Transaction on Knowledge and Data Engineering 33, 3 (2021), 951–963.
[56]
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. 2020b. Dynamic Regret of Convex and Smooth Functions. In Proceedings of the Advances in Neural Information Processing Systems 33 (NeurIPS). 12510–12520.
[57]
Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. 2024. Adaptivity and Non-Stationarity: Problem-Dependent Dynamic Regret for Online Convex Optimization. Journal of Machine Learning Research 25, 98 (2024), 1–52.
[58]
Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhiming Ma, and Tie-Yan Liu. 2017. Asynchronous Stochastic Gradient Descent with Delay Compensation. In Proceedings of the 34th International Conference on Machine Learning (ICML). 4120–4129.
[59]
Zhi-Hua Zhou and Zhi-Hao Tan. 2023. Learnware: Small Models Do Big. Science China Information Sciences 67, 1 (2023), 112102.
[60]
Zhi-Hua Zhou. 2012. Ensemble Methods: Foundations and Algorithms. CRC Press.
[61]
Zhi-Hua Zhou. 2022a. Open-Environment Machine Learning. National Science Review 9, 8 (2022), nwac123.
[62]
Zhi-Hua Zhou. 2022b. Rehearsal: Learning from Prediction to Decision. Frontiers of Computer Science 16, 4 (2022), 164352.
Index Terms
- Learning with Asynchronous Labels
Recommendations
Learning from Reduced Labels for Long-Tailed Data
ICMR '24: Proceedings of the 2024 International Conference on Multimedia RetrievalLong-tailed data is prevalent in real-world classification tasks and heavily relies on supervised information, which makes the annotation process exceptionally labor-intensive and time-consuming. Unfortunately, despite being a common approach to mitigate ...
Acknowledging the Unknown for Multi-label Learning with Single Positive Labels
Computer Vision – ECCV 2022AbstractDue to the difficulty of collecting exhaustive multi-label annotations, multi-label datasets often contain partial labels. We consider an extreme of this weakly supervised learning problem, called single positive multi-label learning (SPML), where ...
Hierarchical Multi-Label Classification with Partial Labels and Unknown Hierarchy
CIKM '23: Proceedings of the 32nd ACM International Conference on Information and Knowledge ManagementHierarchical multi-label classification aims at learning a multi-label classifier from a dataset whose labels are organized into a hierarchical structure. To the best of our knowledge, we propose for the first time the problem of finding a multi-label ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 31 July 2024
Online AM: 03 May 2024
Accepted: 08 March 2024
Revised: 29 December 2023
Received: 22 October 2022
Published in TKDD Volume 18, Issue 8
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Science and Technology Major Project
- National Science Foundation of China
- National Postdoctoral Program for Innovative Talent, and China Postdoctoral Science Foundation
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 261Total Downloads
- Downloads (Last 12 months)261
- Downloads (Last 6 weeks)19
Reflects downloads up to 21 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in