Harnessing Bandit Online Learning to Low-Latency Fog Computing
The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Abstract
This paper focuses on the online fog computing tasks in the Internet-of-Things (IoT), where online decisions must flexibly adapt to the changing user preferences (loss functions), and the temporally unpredictable availability of resources (constraints). Tailored for such human-in-the-loop systems where the loss functions are hard to model, a family of bandit online saddle-point (BanSP) schemes are developed, which adaptively adjust the online operations based on (possibly multiple) bandit feedback of the loss functions, and the changing environment. Performance here is assessed by: i) dynamic regret that generalizes the widely used static regret; and, ii) fit that captures the accumulated amount of constraint violations. Specifically, BanSP is proved to simultaneously yield sub-linear dynamic regret and fit, provided that the best dynamic solutions vary slowly over time. Numerical tests on fog computing tasks corroborate that BanSP offers desired performance under such limited information.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“At this background, large state and action spaces in the whole offloading problem make the conventional learning algorithms [245] [256] [247] infeasible actually.”
From Convergence of Edge Computing and Deep Learning: A Comprehensive Survey (2020) · cites this paper as [256]
Citations
Cites
Mobile Edge Computing: A Survey on Architecture and Computation Offloading
Mach, P., & Becvar, Z. (2017) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2682318 · Cited by 3,258
Weik, M. H. (2000) · Computer Science and Communications Dictionary · doi:10.1007/1-4020-0613-6_12436 · Cited by 2,570
Fog and IoT: An Overview of Research Opportunities
Chiang, M., & Zhang, T. (2016) · IEEE Internet of Things Journal · doi:10.1109/jiot.2016.2584538 · Cited by 2,362 · cited 2×
“From the network design vantage point, fog is viewed as a promising architecture for IoT that distributes computation and communication closer to the IoT users, along the cloud-to-things continuum [2, 3].”
Background(2003) · Cited by 1,733
Energy-Efficient Resource Allocation for Mobile-Edge Computation Offloading
You, C., Huang, K., Chae, H., & Kim, B.-H. (2017) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2633522 · Cited by 1,503
Joint Offloading and Computing Optimization in Wireless Powered Mobile-Edge Computing Systems
Wang, F., Xu, J., Wang, X., & Cui, S. (2018) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2017.2785305 · Cited by 922
Joint Optimization of Radio and Computational Resources for Multicell Mobile-Edge Computing
Sardellitti, S., Scutari, G., & Barbarossa, S. (2015) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2015.2448520 · Cited by 891
Logarithmic regret algorithms for online convex optimization
Hazan, E., Agarwal, A., & Kale, S. (2007) · Machine Learning · doi:10.1007/s10994-007-5016-8 · Cited by 828 · cited 1×
“Regarding the data arrival rate bt , it is generated according to bt = q sin(πt/96) + ν t , with q and ν t uniformly distributed over [40, 50] and [45, 55] for n ∈ N\{1, 2, 3} ⋃ {4, 5}, and q ∈ [32, 40], ν t ∈ [36, 44], n ∈ {1, 2, 3}, and q ∈ [20, 25], ν t ∈ [22.”
Random Gradient-Free Minimization of Convex Functions
Nesterov, Y., & Spokoiny, V. (2017) · Foundations of Computational Mathematics · doi:10.1007/s10208-015-9296-2 · Cited by 822 · cited 2×
“The key idea behind BCO is to construct (possibly stochastic) gradient estimates using the limited function value information [15, 20].”
BackgroundOnline convex optimization in the bandit setting: gradient descent without a gradient
Flaxman, A. D., Kalai, A. T., & McMahan, H. B. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0408007 · Cited by 546
Communicating While Computing: Distributed mobile cloud computing over 5G heterogeneous networks
Barbarossa, S., Sardellitti, S., & Di Lorenzo, P. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2334709 · Cited by 468 · cited 1×
“From the network design vantage point, fog is viewed as a promising architecture for IoT that distributes computation and communication closer to the IoT users, along the cloud-to-things continuum [2, 3].”
BackgroundOptimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
Duchi, J. C., Jordan, M. I., Wainwright, M. J., & Wibisono, A. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2409256 · Cited by 370
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.
Agarwal, A., Dekel, O., & Xiao, L. (2010) · Cited by 261
An Online Convex Optimization Approach to Proactive Network Resource Allocation
Chen, T., Ling, Q., & Giannakis, G. B. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2750109 · Cited by 236
Self-citationOnline Convex Optimization in Dynamic Environments
Hall, E. C., & Willett, R. M. (2015) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2015.2404790 · Cited by 219 · cited 1×
“The notion of dynamic regret has been recently adopted in [22,23] to assess performance of online algorithms under time-invariant constraints.”
Adaptive routing with end-to-end feedback: distributed learning and geometric approaches
Awerbuch, B., & Kleinberg, R. D. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007367 · Cited by 190 · cited 1×
“Clearly, the explicit form of functions ct (·), c t (·), and ht (·) is unknown to the network operator due to the unpredictable traffic patterns [18]; but they are convex (thus ft(xt) is convex) with respect to their arguments, which implies that the marginal computation/communication latency is increasing as the offl…”
BackgroundOnline Optimization : Competing with Dynamic ComparatorsPreprint
Jadbabaie, A., Rakhlin, A., Shahrampour, S., & Sridharan, K. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1501.06225 · Cited by 175
Mobile Edge Computing: Survey and Research Outlook.Preprint
Mao, Y., You, C., Zhang, J., Huang, K., & Letaief, K. B. (2017) · arXiv (Cornell University) · Cited by 173
Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
Mahdavi, M., Jin, R., & Yang, T. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.6082 · Cited by 157 · cited 2×
“Regarding feasibility of decisions generated by a BCO algorithm, the notion of dynamic fit will be used to measure the accumulated violation of constraints [24], that is”
BackgroundMethodAn Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point FeedbackPreprint
Shamir, O. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.08752 · Cited by 151 · cited 1×
“Specifically, extending the BCO framework [14, 19] to accommodate such time-varying constraints, we consider the following online problem”
BackgroundComputation offloading and resource allocation for low-power IoT edge devices
Samie, F., Tsoutsouras, V., Bauer, L., Xydis, S., Soudris, D., & Henkel, J. (2016) · 2016 IEEE 3rd World Forum on Internet of Things (WF-IoT) · doi:10.1109/wf-iot.2016.7845499 · Cited by 146
Online Convex Optimization with Time-Varying ConstraintsPreprint
Neely, M. J., & Yu, H. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.04783 · Cited by 143 · cited 2×
“Here (9) is updated along the first-order approximation of gt(x̂t+1) at x̂t [13, 21].”
BackgroundBandit Convex Optimization for Scalable and Dynamic IoT Management
Chen, T., & Giannakis, G. B. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2839563 · Cited by 139
Self-citationAn online secretary framework for fog network formation with minimal latency
Lee, G., Saad, W., & Bennis, M. (2017) · 2017 IEEE International Conference on Communications (ICC) · doi:10.1109/icc.2017.7996574 · Cited by 78 · cited 1×
“Consider a mobile network with a sensor layer, a fog layer, and a cloud layer [2, 16].”
BackgroundDistributed QoS management for internet of things under resource constraints
Samie, F., Tsoutsouras, V., Xydis, S., Bauer, L., Soudris, D., & Henkel, J. (2016) · Proceedings of the Eleventh IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis · doi:10.1145/2968456.2974005 · Cited by 39 · cited 1×
“Internet-of-Things (IoT) envisions an intelligent infrastructure of networked smart devices offering task-specific monitoring and control services [1].”
BackgroundCollaborative Resource Allocation over a Hybrid Cloud Center and Edge Server Network
Huang, H. H. H., Ling, Q. H., Shi, W., & Wang, J. W. J. (2017) · Journal of Computational Mathematics · doi:10.4208/jcm.1608-m2016-0561 · Cited by 15
Research works printed but not linked: 1
- chen, 2017, Online learning for “thing-adaptive” fog computing in IoT, Proc of ASILOMAR
Cited by
Convergence of Edge Computing and Deep Learning: A Comprehensive Survey
Wang, X., Han, Y., Leung, V. C. M., Niyato, D., Yan, X., & Chen, X. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.2970550 · Cited by 1,498
“At this background, large state and action spaces in the whole offloading problem make the conventional learning algorithms [245], [256], [247] infeasible actually.”
BackgroundBandit Convex Optimization for Scalable and Dynamic IoT Management
Chen, T., & Giannakis, G. B. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2839563 · Cited by 139
“This paper was presented in part at the International Conference on Acoustics, Speech and Signal Processing, Calgary, AB, Canada, April 2018 [1].”
BackgroundSelf-citationThe Online Saddle Point Problem and Online Convex Optimization with Knapsacks
Cardoso, A. R., Wang, H., & Xu, H. (2024) · Mathematics of Operations Research · doi:10.1287/moor.2018.0330 · Cited by 28
“Motivated by an application in low-latency fog computing, [24] consider a problem similar to that in [43] however there is bandit feedback in the loss function.”
MethodCentralized and Collaborative RL-Based Resource Allocation in Virtualized Dynamic Fog Computing
Mseddi, A., Jaafar, W., Elbiaze, H., & Ajib, W. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3283143 · Cited by 22
“These solutions were mainly developed for cloud computing [8], [9], [10], and only recently, its use in FC platforms is explored [11], [12], [13], [14], [15], [16], [17], [18], [19], [20].”
BackgroundBandit Learning-Based Distributed Computation in Fog Computing Networks: A Survey
Tran‐Dang, H., Kwon, G.-H., & Kim, D. (2023) · IEEE Access · doi:10.1109/access.2023.3314889 · Cited by 9
Metadata
- Authors
- Chen, T., & Giannakis, G. B.
- Affiliations
- University of Minnesota (US)
- Venue
- 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
- Publisher
- IEEE
- Published
- 2018-04
- Pages
- 6418-6422
- ISSN
- 1520-6149 (ISSN-L)
- OpenAlex
- W2890535477
- Cited by
- 8
- References
- 26
- Citations by year
- 2024: 1 · 2023: 3 · 2020: 2 · 2018: 2
- FWCI
- 1.48
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE International Conference on Acoustics Speech and Signal Processing (publishedVersion)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Physical Sciences › Computer Science › Computer Networks and Communications › IoT and Edge/Fog Computing
- Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
- Keywords
- Internet of Things, dynamic regret, constraint violation, human-in-the-loop systems, low-latency computing, resource constraints
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.