Bandit Convex Optimization for Scalable and Dynamic IoT Management
Open accessThe DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Abstract
This paper deals with online convex optimization involving both time-varying loss functions, and time-varying constraints. The loss functions are not fully accessible to the learner, and instead only the function values (also known as bandit feedback) are revealed at queried points. The constraints are revealed after making decisions, and can be instantaneously violated, yet they must be satisfied in the long term. This setting fits nicely the emerging online network tasks such as fog computing in the Internet-of-Things, 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 online bandit saddle-point (BanSaP) 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: 1) dynamic regret that generalizes the widely used static regret and 2) fit that captures the accumulated amount of constraint violations. Specifically, BanSaP is proved to simultaneously yield sublinear dynamic regret and fit, provided that the best dynamic solutions vary slowly over time. Numerical tests in fog computation offloading tasks corroborate that our proposed BanSaP approach offers competitive performance relative to existing approaches that are based on gradient feedback.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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?
The check wasn’t confident either way, so it gives no verdict — never disputed.
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 [247]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(2010) · Cited by 8,261
A Survey on Mobile Edge Computing: The Communication Perspective
Mao, Y., You, C., Zhang, J., Huang, K., & Letaief, K. B. (2017) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2745201 · Cited by 5,607 · cited 3×
“The online computational offloading task of fog computing in IoT [5], [6], [8] takes the form of BCO with long-term constraints (1).”
BackgroundMobile 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 · cited 3×
“, N} with moderate processing capability; thus, part of workloads will be collaboratively processed by the local fog servers to meet the stringent latency requirement, and the rest will be offloaded to the remote data center in the cloud layer [6] (see Fig.”
BackgroundEfficient multi-user computation offloading for mobile-edge cloud computing
Chen, X., Jiao, L., Li, W., & Fu, X. (2016) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2015.2487344 · Cited by 2,675 · cited 1×
“Online optimization with time-varying and long-term constraints is well motivated for applications from power control in wireless communication [26], geographical load balancing in cloud networks [14], [27], to computation offloading in fog computing [28], [29].”
BackgroundWeik, 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×
“Consider a mobile network with a sensor layer, a fog layer, and a cloud layer [3], [4].”
BackgroundStochastic Network Optimization with Application to Communication and Queueing Systems
Neely, M. J. (2010) · Synthesis lectures on communication networks · doi:10.2200/s00271ed1v01y201006cnt007 · Cited by 2,218
(2003) · Cited by 1,733
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S. (2012) · now publishers, Inc. eBooks · doi:10.1561/9781601986276 · Cited by 1,404
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
Bubeck, S., & Cesa-Bianchi, N. (2012) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000024 · Cited by 1,295
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 · cited 1×
“Online optimization with time-varying and long-term constraints is well motivated for applications from power control in wireless communication [26], geographical load balancing in cloud networks [14], [27], to computation offloading in fog computing [28], [29].”
BackgroundLogarithmic 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 3×
“Assumptions (as1) and (as2) are typical in OCO with both full- and partial-information feedback [10], [17], [23]; (as3) is Slater’s condition modified for our BCO setting, which guarantees the existence of a bounded Lagrange multiplier [32] in the constrained optimization; and (as4) requires the action set to”
BackgroundRandom 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 6×
“The key idea behind BCO is to construct (possibly stochastic) gradient estimates using the limited function value information [17]–[19], [21], [22].”
BackgroundInfluentialOnline 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 · cited 9×
“The key idea behind BCO is to construct (possibly stochastic) gradient estimates using the limited function value information [17]–[19], [21], [22].”
BackgroundMethodInfluentialIOT Gateway: BridgingWireless Sensor Networks into Internet of Things
Zhu, Q., Wang, R., Chen, Q., Liu, Y., & Qin, W. (2010) · 2010 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing · doi:10.1109/euc.2010.58 · Cited by 443 · cited 1×
“, smart home gateways), and a remote cloud center [34].”
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 · cited 5×
“The key idea behind BCO is to construct (possibly stochastic) gradient estimates using the limited function value information [17]–[19], [21], [22].”
BackgroundMethodInfluentialNon-stationary stochastic optimization
Besbes, O., Gur, Y., & Zeevi, A. (2015) · Operations Research · doi:10.1287/opre.2015.1408 · Cited by 337 · cited 2×
“Unfortunately, the sublinear dynamic regret is not achievable under arbitrary underlying dynamics, even when the time-varying constraint in (1) is absent [31].”
BackgroundOptimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.
Agarwal, A., Dekel, O., & Xiao, L. (2010) · Cited by 261
The Cloud is Not Enough: Saving IoT from the Cloud.
Zhang, B., Mor, N., Kolb, J., Chan, D. S., Goyal, N., Lutz, K., Allman, E., Wawrzynek, J., Lee, E. A., & Kubiatowicz, J. D. (2015) · eScholarship (California Digital Library) · Cited by 247
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 · cited 9×
“Finally, BanSaP is benchmarked by: 1) the full-information modified online saddle-point method (MOSP) in [14] that takes gradient-based update for primal-dual variables; 2) the heuristic cloud-only approach that offloads all data requests to the remote cloud; 3) the heuristic fog-only approach that processes all data…”
BackgroundMethodInfluentialSelf-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 2×
“The notion of dynamic regret has been recently adopted in [12] and [13] to assess performance of online algorithms under time-invariant constraints.”
BackgroundAdaptive 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 2×
“Clearly, the explicit form of functions ct (·), cnk t (·), and ht (·) is unknown to the network operator due to the unpredictable traffic patterns [24]; 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 of…”
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 · cited 4×
“The notion of dynamic regret has been recently adopted in [12] and [13] to assess performance of online algorithms under time-invariant constraints.”
BackgroundInfluentialTrading 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 10×
“Finally, BanSaP is benchmarked by: 1) the full-information modified online saddle-point method (MOSP) in [14] that takes gradient-based update for primal-dual variables; 2) the heuristic cloud-only approach that offloads all data requests to the remote cloud; 3) the heuristic fog-only approach that processes all data…”
BackgroundMethodInfluentialAn 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 4×
“Specifically, extending the BCO framework [17]–[19] to”
BackgroundResultInfluentialComputation 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 · cited 2×
“, smartphones, and high-tech routers, and only a portion of tasks will be offloaded to the powerful cloud for further processing (also known as computation offloading) [5]–[7].”
BackgroundOnline 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 5×
“Although this standard BCO setting is appealing to various applications such as online end-to-end routing [24] and task assignment [25], it does not account for potential variations of (possibly unknown) constraints, and does not deal with constraints that can possibly be satisfied in the long term rather than a slot-…”
BackgroundMethodInfluentialJoint offloading and computing optimization in wireless powered mobile-edge computing systems
Wang, F., Xu, J., Wang, X., & Cui, S. R. (2017) · International Conference on Communications · doi:10.1109/icc.2017.7997477 · Cited by 105
An 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 2×
“Consider a mobile network with a sensor layer, a fog layer, and a cloud layer [3], [4].”
BackgroundExtracting spatiotemporal human activity patterns in assisted living using a home sensor network
Lymberopoulos, D., Bamis, A., & Savvides, A. (2010) · Universal Access in the Information Society · doi:10.1007/s10209-010-0197-5 · Cited by 71
Stochastic Averaging for Constrained Optimization With Application to Online Resource Allocation
Chen, T., Mokhtari, A., Wang, X., Ribeiro, A., & Giannakis, G. B. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2679690 · Cited by 47 · cited 1×
“Online optimization with time-varying and long-term constraints is well motivated for applications from power control in wireless communication [26], geographical load balancing in cloud networks [14], [27], to computation offloading in fog computing [28], [29].”
BackgroundSelf-citationDistributed 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 2×
“For a communication link offloading loads from fog node n to k, we consider the lowpower wireless connection such as Bluetooth or ZigBee [2], whose the offloading limit is ȳnk = 10; and for all the fog-cloud offloading communication links, we consider the high-bandwidth WiFi connection with the offloading limits {z̄n}…”
BackgroundA Survey on Mobile Edge Computing: The Communication PerspectivePreprint
Mao, Y., You, C., Zhang, J., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1701.01090 · Cited by 24 · cited 3×
“From the management perspective, online network control, which is robust to non-stationary dynamics and amenable to light-weight implementations, remains a largely uncharted territory [5], [7].”
BackgroundJoint Offloading and Computing Optimization in Wireless Powered Mobile-Edge Computing SystemsPreprint
Wang, F., Xu, J., Wang, X., et al. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.00606 · Cited by 23 · cited 1×
“, smartphones, and high-tech routers, and only a portion of tasks will be offloaded to the powerful cloud for further processing (also known as computation offloading) [5]–[7].”
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 · cited 1×
“, smartphones and high-tech routers) in the fog layer for further processing [30].”
BackgroundOnline learning for “thing-adaptive” Fog Computing in IoT
Chen, T., Shen, Y., Ling, Q. H., & Giannakis, G. B. (2017) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2017.8335425 · Cited by 9 · cited 6×
“Considering the full-information setting in [15] as a special case, the regret and fit of BanSaP outperform those in [15].”
BackgroundMethodInfluentialSelf-citationAn Online Secretary Framework for Fog Network Formation with Minimal LatencyPreprint
Lee, G., Saad, W., & Bennis, M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1702.05569 · Cited by 9 · cited 2×
“Consider a mobile network with a sensor layer, a fog layer, and a cloud layer [3], [4].”
BackgroundHarnessing Bandit Online Learning to Low-Latency Fog Computing
Chen, T., & Giannakis, G. B. (2018) · 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2018.8461641 · Cited by 8 · cited 1×
“This paper was presented in part at the International Conference on Acoustics, Speech and Signal Processing, Calgary, AB, Canada, April 2018 [1].”
BackgroundSelf-citationOnline Learning for Wireless Distributed ComputingPreprint
Kao, Y.-H., Wright, K.-L., Krishnamachari, B., & Bai, F. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.02830 · Cited by 6 · cited 2×
“Regarding the data arrival rate bt , it is generated according to bt = qn sin(π t/96)+νn t , with qn and νn t uniformly distributed over [40, 50] and [45, 55] for n ∈ N \{1, 2, 3}{4, 5}, and qn ∈ [32, 40], νn t ∈ [36, 44], n ∈ {1, 2, 3}, and qn ∈ [20, 25], νn t ∈ [22.”
BackgroundMethod
Research works printed but not linked: 2
- chen, 2017, Bandit convex optimization for scalable and dynamic IoT management, arXiv preprint 1707 09060
- 2017, 8 Sensors to Help You Create a Smart Home
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.”
BackgroundIntroduction to Multi-Armed Bandits
Slivkins, A. (2019) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000068 · Cited by 780
Feng, J., Richard Yu, F., Pei, Q., Chu, X., Du, J., & Zhu, L. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2961707 · Cited by 332
“3) Dynamic Optimization: Moreover, most of the existing works [6], [10], [11] in the computation offloading decision and resource allocation strategies are optimized based on a one-time slot, and the long-term computation offloading performance cannot be characterized [12], [13].”
BackgroundLiu, S., Chen, P.-Y., Kailkhura, B., Zhang, G., Hero, A. O., & Varshney, P. K. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.3003837 · Cited by 185
“Online sensor management provides an example of such a scenario [27], [72].”
BackgroundDistributed Online Convex Optimization With Time-Varying Coupled Inequality Constraints
Yi, X., Li, X., Xie, L., & Johansson, K. H. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2964200 · Cited by 167
“The papers [13], [14] used a virtual queue, which essentially is a modified Lagrange multiplier, to handle stochastic and time-varying constraints and the authors of [15] extended the algorithm proposed in [14] with bandit feedback.”
Method
Metadata
- Authors
- Chen, T., & Giannakis, G. B.
- Affiliations
- University of Minnesota (US)
- Venue
- IEEE Internet of Things Journal
- Published
- 2019-02
- Volume
- 6
- Issue
- 1
- Pages
- 1276-1286
- ISSN
- 2327-4662 (ISSN-L)
- 2372-2541
- OpenAlex
- W2739805727
- Cited by
- 139
- References
- 38
- Citations by year
- 2026: 2 · 2025: 8 · 2024: 14 · 2023: 21 · 2022: 16 · 2021: 21 · 2020: 27 · 2019: 23
- FWCI
- 15.48
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Internet of Things Journal (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1509040, 1508993, 1711471)
- 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
- online convex optimization, bandit feedback, time-varying constraints, dynamic regret, constraint violation, fog computing, computation offloading, Internet of Things, human-in-the-loop systems
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.