The present paper deals with online convex optimization involving time-varying loss functions and time-varying constraints. The constraints are revealed after making decisions, and allow instantaneous violations yet they must be satisfied in the long term. This setting fits nicely emerging online tasks such as fog computing, where online decisions need to flexibly adapt to the temporally unpredictable availability of resources. Tailored for heterogeneous systems such as those involved in the Internet of Things (IoT), a 'thing-adaptive' online saddle-point (TAOSP) scheme is developed, which automatically adjusts the stepsize to offer desirable task-specific learning rates. Performance here is assessed by: i) dynamic regret that generalizes the widely used static regret; and, ii) dynamic fit that captures the accumulated amount of constraint violations. Specifically, TAOSP is proved to simultaneously yield sub-linear dynamic regret and fit, provided that the best dynamic solutions vary slowly over time. Numerical tests in fog offloading tasks corroborate that our TAOSP approach outperforms the state of the art in speeding up computations.
|Original language||English (US)|
|Title of host publication||Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017|
|Editors||Michael B. Matthews|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||5|
|State||Published - Apr 10 2018|
|Event||51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 - Pacific Grove, United States|
Duration: Oct 29 2017 → Nov 1 2017
|Name||Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017|
|Other||51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017|
|Period||10/29/17 → 11/1/17|
Bibliographical noteFunding Information:
Work in this paper was supported by NSF 1509040, 1508993, 1509005, NSF China 61573331, NSF Anhui 1608085QF130, and CAS-XDA06011203.
© 2017 IEEE.
- Internet of Things
- Online learning
- convex optimization
- mobile edge computing
- saddle-point method