Bandit Convex Optimization for Scalable and Dynamic IoT Management
Tianyi Chen Georgios B. Giannakis
cs.LG cs.NI








Bandit Convex Optimization for
 Scalable and Dynamic IoT Management
    
Tianyi Chen and Georgios B. Giannakis
Work in this paper was supported by NSF 1509040, 1508993, and 1711471.

T. Chen and G. B. Giannakis are with the Department of Electrical and Computer Engineering and the Digital Technology Center, University of Minnesota, Minneapolis, MN 55455 USA. Emails: {chen3827, georgios}@umn.edu




    December 30, 2023
=============================================================================================================================================================================================================================================================================================================================================









The present 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 (a.k.a. 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 (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 (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: i) dynamic regret that generalizes the widely used static regret; and, ii) fit that captures the accumulated amount of constraint violations. 
Specifically, BanSaP 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 computation offloading tasks corroborate that our proposed BanSaP approach offers competitive performance relative to existing approaches that are based on gradient feedback.




Online learning, bandit convex optimization, saddle-point method, Internet of Things, mobile edge computing.







§ INTRODUCTION

Internet-of-Things (IoT) envisions an intelligent infrastructure of networked smart devices offering task-specific monitoring and control services <cit.>. 
Leveraging advances in embedded systems, contemporary IoT devices are featured with small-size and low-power designs, but their computation and communication capabilities are limited. 
A prevalent solution during the past decade was to move computing, control, and storage resources to the remote cloud (a.k.a. data centers). 
Yet, the cloud-based IoT architecture is challenged by high latency due to directly communications with the cloud, which certainly prevents real-time applications <cit.>.
Along with other features of IoT, such as extreme heterogeneity and unpredictable dynamics, the need arises for innovations in network design and management to allow for adaptive online service provisioning, subject to stringent delay constraints <cit.>. 

From the network design vantage point, fog is viewed as a promising architecture for IoT that distributes computation, communication, and storage closer to the end IoT users, along the cloud-to-things continuum <cit.>. 
In the fog computing paradigm, service provisioning starts at the network edge, e.g., smartphones, and high-tech routers, and only a portion of tasks will be offloaded to the powerful cloud for further processing (a.k.a. computation offloading) <cit.>.
Existing approaches for computation offloading either focus on time-invariant static settings, or, rely on stochastic optimization approaches such as Lyapunov optimization to deal with time-varying cases; see <cit.> and references therein. 
Nevertheless, static settings cannot capture the changing IoT environment, and the stationarity commonly assumed in stochastic optimization literature may not hold in practice, especially when the stochastic process involves human participation as in IoT.
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 <cit.>.

Indeed, the primary goal of this paper is an algorithmic pursuit of online network optimization suitable for emerging tasks in IoT. 
Focusing on such algorithmic challenges, online convex optimization (OCO) is a promising methodology for
sequential tasks with well-documented merits, especially when the sequence of convex costs varies in an unknown and possibly adversarial manner <cit.>.
Aiming to empower traditional fog management policies with OCO, most available OCO works benchmark algorithms with a static regret, which measures the difference of costs (a.k.a. losses) between the online solution and the best static solution in hindsight <cit.>.
However, static regret is not a comprehensive performance metric in dynamic settings such as those encountered with IoT <cit.>.

Recent works extend the
analysis of static to that of dynamic regret <cit.>, but they deal with time-invariant constraints that cannot be violated instantaneously. 

Tailored for fog computing setups that need flexible adaptation of online decisions to dynamic resource availability, OCO with time-varying constraints was first studied in <cit.>,  along with its adaptive variant in <cit.>, and the optimal regret bound in this setting was first established in <cit.>.  
Yet, the approaches in <cit.> remain operational under the premise that the loss functions are explicitly known, or, their gradients are readily available. 
Clearly, none of these two assumptions can be easily satisfied in IoT settings, because i) the loss function capturing user dissatisfaction, e.g., service latency or reliability, is hard to model in dynamic environments; and, ii) even if modeling is possible in theory, the low-power IoT devices may not afford the complexity of running statistical learning tools such as deep neural networks “on-the-fly.”   
 
In this context, targeting a gradient-free light-weight solution, alternative online schemes have been advocated leveraging point-wise values of loss functions (partial-information feedback) rather than their gradients (full-information feedback). They are termed bandit convex optimization (BCO) in machine learning <cit.>, or referred as zeroth-order schemes in optimization circles <cit.>.  
While <cit.> and <cit.> employed on BCO with time-invariant constraints that cannot be violated instantaneously, the long-term effect of such instantaneous violations was studied in <cit.>, where the focus is still on static regret and time-invariant constraints.
Building on full-information precursors <cit.>, the present paper broadens the scope of BCO to the regime with time-varying constraints, and proposes a class of online algorithms termed online bandit saddle-point (BanSaP) approaches. 
With an eye on managing IoT with limited information, our contribution is the incorporation of long-term and time-varying constraints to expand the scope of BCO, as well as an improved regret-fit tradeoff relative to that in <cit.>; see a summary in Table <ref>.






In a nutshell, relative to existing works, the main contributions of the
present paper are summarized as follows.

c1) We generalize the standard BCO framework with only
time-varying costs <cit.>, to account for
both time-varying costs and constraints. Performance here is established relative to the best dynamic
benchmark, via metrics that we term dynamic regret and fit (Section III).

c2) We develop a class of BanSaP algorithms to tackle this novel BCO
problem, and analytically establish that BanSaP solvers yield
simultaneously optimal sub-linear dynamic regret and fit, given that
the accumulated variations of per-slot minimizers are known to grow sub-linearly with time (Section IV).

c3) Our BanSaP algorithms are applied to computation offloading tasks emerging in IoT management, and simulations demonstrate that the BanSaP solvers have comparable performance relative to full-information alternatives (Section V).










Notation. (·)^⊤ stands for
vector and matrix transposition, and 𝐱 denotes the ℓ_2-norm of a vector 𝐱. Inequalities for vectors 𝐱 > 0, and the projection [𝐚]^+:=max{𝐚,0} are entry-wise.




§ BANDIT ONLINE LEARNING WITH CONSTRAINTS


In this section, a generic BCO formulation with long-term and time-varying constraints will be introduced, along with its real-world application in IoT management. 



 §.§ Online learning with constraints under partial feedback


Before introducing BCO with long-term constraints, we begin with the classical BCO setting, where constraints are
time-invariant, and must be strictly satisfied <cit.>. 
Akin to its full-information counterpart <cit.>, BCO can be viewed as a repeated game between a learner and nature. 
Consider that time is discrete and indexed by t. Per slot t, a learner
selects an action 𝐱_t from a convex set
X⊆ℝ^d, and subsequently nature chooses a loss function f_t(·):
ℝ^d→ℝ through which the learner incurs a
loss f_t(𝐱_t). 
The convex feasible set X is a-priori known and fixed over the entire time horizon. 
Different from the OCO setup, at the end of each slot, only the value of f_t(𝐱_t) rather than the form of f_t(𝐱) is revealed to the learner in BCO.  
Although this standard BCO setting is appealing to various applications
such as online end-to-end routing <cit.> and task assignment 
<cit.>, 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-by-slot basis <cit.>.

Online optimization with time-varying and long-term constraints is
well motivated for applications from power control in wireless communication <cit.>, geographical load balancing in cloud networks <cit.>, to computation offloading in fog computing <cit.>. 
Motivated by these dynamic network management tasks, our recent works <cit.> studied OCO with time-varying constraints in full information setting, where the gradient feedback is available. 
Complementing <cit.> and <cit.>, the present paper broadens the applicability of BCO to the regime with time-varying long-term constraints.

Specifically, we consider that per slot t, a learner selects an action 𝐱_t from a known and fixed convex set X⊆ℝ^d, and then nature chooses not only a loss
function f_t(·): ℝ^d→ℝ, but also
a time-varying penalty function
𝐠_t(·): ℝ^d→ℝ^N. The later gives rise to the time-varying constraint
𝐠_t(𝐱)≤0, which is driven by the
unknown application-specific dynamics. 
Similar to the standard BCO setting, only the value of f_t(𝐱_t) at the queried point 𝐱_t is revealed to the learner here; but different from the standard BCO setting, besides  X, the constraint
𝐠_t(𝐱)≤0 needs to be carefully taken care of. 
And the fact that 𝐠_t is unknown to the learner when performing her/his decision, makes it impossible to satisfy in every time slot. 
Hence, a more realistic goal here
is to find a sequence of solutions {𝐱_t} that minimizes the aggregate loss, and ensures that the
constraints {𝐠_t(𝐱_t)≤0} are
satisfied in the long term on average. 
Specifically, extending the BCO framework <cit.> to
accommodate such time-varying constraints, we consider the following online optimization problem



[box=]align
min_{𝐱_t∈X,∀t}  ∑_t=1^T f_t(𝐱_t)   s. to ∑_t=1^T 𝐠_t(𝐱_t) ≤0

where T is the entire time horizon, 𝐱_t∈ℝ^d is
the decision variable, f_t represents the cost function,
𝐠_t:=[g_t^1,…,g_t^N]^⊤ denotes the constraint
function with nth entry g_t^n(·):ℝ^d→ℝ, and X∈ℝ^d is a convex set. 
In the current setting, we assume that only the values of loss function are available at queried points since e.g., its complete form related to user experience is hard to approximate, but the constraint function is revealed to the learner as it represents measurable physical requirements e.g., power budget, and data flow conservation constraints.     
Before the algorithm development in Section <ref> and performance analysis in Section <ref>, we will introduce a motivating example of fog computing in IoT.





 §.§ Motivating setup: mobile fog computing in IoT



The online computational offloading task of fog computing in IoT <cit.> takes the form of BCO with long-term constraints (<ref>). 
Consider a mobile network with a sensor layer, a fog layer, and a cloud layer <cit.>.
The sensor layer contains heterogeneous low-power IoT devices (e.g., wearable watches and smart cameras), which do not have enough computational capability, and usually offload their collected data to the local fog nodes (e.g., smartphones and high-tech routers) in the fog layer for further processing <cit.>. 
The fog layer consists of N nodes in the set N:={1,…,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 <cit.>; also see Fig. <ref>. 

Per time t, each fog node n collects data requests b_t^n from all its nearby sensors. 
Once receiving these requests, node n has three options: i) offloading the amount z_t^n to the remote data center; ii) offloading the amount y_t^nk to each of its nearby node k for collaborative computing; and, iii) locally processing the amount y_t^nn according to its resource availability. 
The optimization variable 𝐱_t in this case consists of the cloud offloading, local offloading, and local processing amounts; i.e., 𝐱_t:=[z_t^1,…,z_t^N,y_t^11,…,y_t^1N,…,y_t^N1,…,y_t^NN]^⊤.
Assuming that each fog node has a data queue to buffer unserved workloads, the instantaneously served workloads (offloading plus processing) is not necessarily equal to the data arrival rate.
Instead, a long-term constraint is common to ensure that the cumulative amount of served workloads is no less than the arrived amount at each node n over time <cit.> 

    ∑_t=1^T g_t^n(𝐱_t):=∑_t=1^T(b_t^n+∑_k∈ N_n^ in y_t^kn-∑_k∈ N_n^ out y_t^nk-z_t^n-y_t^nn) ≤ 0

where N_n^ in and N_n^ out represent the sets of fog nodes with in-coming links to node n and those with out-going links from node n, respectively.
The bandwidth limit of communication link (e.g., wireline) from fog node n to the remote cloud is
z̅^n; the limit of the transmission link (e.g., wireless) from node n to its neighbor k is
y̅^nk, and the computation capability of node n is
y̅^nn. 
With 𝐱̅ collecting all the aforementioned limits, the feasible region can be expressed by 𝐱_t ∈ X:={0≤𝐱_t≤𝐱̅}. 





Performance is assessed by the user dissatisfaction of the online processing and offloading decisions, e.g., aggregate delay <cit.>.  
Specifically, as the computation delay is usually negligible for data centers with thousands of high-performance servers, the latency for cloud offloading amount z_t^n is mainly due to the communication delay, which is denoted as a time-varying cost c_t^n(z_t^n) depending on the unpredictable network congestion during slot t. 
Likewise, the communication delay of the local offloading decision y_t^nk from node n to a nearby node k is denoted as c_t^nk(y_t^nk), but its magnitude is much lower than that of cloud offloading.
Regarding the processing amount y_t^nn, its latency comes from the computation delay due to its limited computational capability, which is presented as a time-varying function h_t^n(y_t^nn) capturing the dynamic CPU capability during the computing processes.
Per slot t, the network delay 
f_t(𝐱_t) aggregates the computation delay at all nodes plus the communication delay at all links, namely

    f_t(𝐱_t):=∑_n∈ N(c_t^n(z_t^n)+∑_k∈ N_n^ outc_t^nk(y_t^nk)_ communication+h_t^n
    (y_t^nn)_ computation).

Clearly, the explicit form of functions c_t^n(·), c_t^nk(·), and h_t^n(·) is unknown to the network operator due to the unpredictable traffic patterns <cit.>; but they are convex (thus f_t(𝐱_t) is convex) with respect to their arguments, which implies that the marginal computation/communication latency is increasing as the offloading/processing amount grows.    

Aiming to minimize the accumulated network delay while serving all the IoT workloads in the long term, the optimal offloading strategy in this mobile network is the solution of the following online optimization problem (cf. (<ref>))

    min_{𝐱_t∈ X,∀ t}    ∑_t=1^T f_t(𝐱_t), s. to  (<ref>)  for n=1,…,N.

Comparing to the generic form (<ref>), we consider an online fog computing problem in (<ref>), where the loss (network latency) function f_t(·) and the data requests {b_t^n} within slot t are not known when making the offloading and local processing decision 𝐱_t; after performing 𝐱_t, only the value of f_t(𝐱_t) (a.k.a. loss) as well as the measurements {b_t^n} are revealed to the network operator. 
In this example, measuring {b_t^n} is tantamount to knowing the constraint function g_t^n(·) in (<ref>). 
Therefore, (<ref>) is in the form of (<ref>). 






§ ONLINE BANDIT SADDLE-POINT METHODS


To solve the problem in Section <ref>, an online saddle-point method is revisited first, before developing its bandit variants for network optimization with only partial feedback.



 §.§ Online saddle-point approach with gradient feedback

Several works have studied the OCO setup with time-varying long-term constraints (cf. (<ref>)), including <cit.>, and the recent variant <cit.> incorporating with adaptive stepsizes. 
Consider now the per-slot problem (<ref>), which
contains the current objective f_t(𝐱), the current
constraint 𝐠_t(𝐱)≤0, and a
time-invariant feasible set X. 



With λ∈ℝ^N_+ denoting the Lagrange multiplier associated with
the time-varying constraint, the online Lagrangian of
(<ref>) can be expressed as

    L_t(𝐱,λ):=f_t(𝐱)+λ^⊤𝐠_t(𝐱).


Serving as a basis for developing the bandit approaches, we next revisit the online saddle-point scheme with full-information <cit.>, that is also equivalent to <cit.> when 𝐠_t(𝐱) is linear.
Specifically, given the primal iterate 𝐱_t and the dual iterate
λ_t at each slot t, the next decision
𝐱_t+1 is generated by

    𝐱_t+1∈min_𝐱∈ X∇_𝐱^⊤ L_t(𝐱_t,λ_t)(𝐱-𝐱_t)+1/2α𝐱-𝐱_t^2

where α is a pre-defined constant, and ∇_𝐱 L_t(𝐱_t,λ_t)=∇ f_t(𝐱_t)+∇^⊤𝐠_t(𝐱_t)λ_t is the gradient of L_t(𝐱,λ_t) with respect to (w.r.t.) the primal variable 𝐱 at 𝐱=𝐱_t. 
The minimization (<ref>) admits the closed-form solution, given by

    𝐱_t+1= P_ X(𝐱_t-α∇_𝐱 L_t(𝐱_t,λ_t))

where P_ X(𝐲):=_𝐱∈ X𝐱-𝐲^2 denotes the projection operator.
In addition, the dual update takes the modified online gradient ascent form

    λ_t+1=[λ_t+μ (𝐠_t(𝐱_t)+∇^⊤𝐠_t(𝐱_t)(𝐱_t+1-𝐱_t))]^+

where μ is a positive stepsize, and
∇_λ L_t(𝐱_t,λ_t)=𝐠_t(𝐱_t) is
the gradient of L_t(𝐱_t,λ) w.r.t. λ at λ=λ_t. 
Note that (<ref>) is a modified gradient update since the dual variable is updated along the first-order approximation of 𝐠_t(𝐱_t+1) at the previous iterate 𝐱_t rather than 𝐠_t(𝐱_t) used in <cit.>, which will be critical in our subsequent analytical derivations. 

To perform the online saddle-point recursion (<ref>)-(<ref>) however, the gradient ∇ f_t(𝐱) and the constraint 𝐠_t(𝐱) should be known to the learner at each slot t. 
When the gradient of f_t(𝐱) (or its explicit form) is unknown as it is in our setup, additional effort is needed. 
In this context, the systematic design of the online bandit saddle-point (BanSaP) methods will be leveraged to extend the online saddle-point method to the regime where gradient information is unavailable or computationally costly. 





 §.§ BanSaP with one-point partial feedback

The key idea behind BCO is to construct (possibly stochastic) gradient estimates using the limited function value information <cit.>. 
Depending on system variability, the online learner can afford one or multiple loss function evaluations (partial-information feedback) per time slot  <cit.>. 
Intuitively, the performance of a bandit algorithm will improve if multiple evaluations are available per time slot; see Fig. <ref> for a comparison of full- versus partial-information feedback settings. 

To begin with, we consider the case where the learner can only observe the function value of f_t(𝐱) at a single point per slot t. The crux here is to construct a (possibly unbiased) estimate of the gradient using this single piece of feedback.
Interestingly though, a stochastic gradient estimate of f_t(𝐱) can be obtained by one point random function evaluation <cit.>. 
The intuition can be readily revealed from the one-dimensional case (d=1): For a binary random variable u taking values {-1,1} equiprobable, and a small constant δ>0, the idea of forward differentiation implies that the derivative f_t' at x can be approximated by 

    f_t'(x)≈f_t(x+δ )-f_t(x-δ)/2δ=𝔼_u[u/δf_t(x+δ u)]

where the approximation is due to δ>0, and the equality follows from the definition of expectation. Hence, f_t(x+δ u)u/δ can serve as a stochastic estimator of f_t'(x) based only single function evaluation f_t(x+δ u).
Generalizing this approximation to high dimensions, with a random vector 𝐮 drawn from the unit sphere (a.k.a. the surface of a unit ball), the scaled function evaluation at a perturbed point 𝐱+δ𝐮 yields an estimate of the gradient ∇ f_t(𝐱), given by <cit.>

    ∇ f_t(𝐱)≈𝔼_𝐮[d/δf_t(𝐱+δ𝐮)𝐮]:=𝔼_𝐮[∇̂^1 f_t(𝐱)]

where we define one-point gradient ∇̂^1 f_t(𝐱):=d/δf_t(𝐱+δ𝐮)𝐮.

Building upon this intuition, consider a bandit version of the online saddle-point iteration, for which the primal update becomes (cf. (<ref>))

    𝐱̂_t+1= P_(1-γ) X(𝐱̂_t-α∇̂_𝐱^1 L_t(𝐱̂_t,λ_t))

where (1-γ) X:={(1-γ)𝐱:𝐱∈ X} is a subset of X,  γ∈[0,1) is a pre-selected constant depending on δ, and the one-point Langragian gradient is given by (cf. (<ref>))

    ∇̂_𝐱^1 L_t(𝐱̂_t,λ_t):=∇̂^1 f_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)λ_t.


In the full-information case, 𝐱_t in (<ref>) is the learner's action, but in the bandit case the learner's action is 𝐱_1,t:=𝐱̂_t+δ𝐮_t, which is the point for function evaluation but not 𝐱̂_t in (<ref>). 
Furthermore, the projection is performed on a smaller convex set (1-γ) X in (<ref>), which ensures feasibility of the perturbed 𝐱_1,t∈ X. 
Similar to the full-information case (<ref>), the dual update of BanSaP is given by

    λ_t+1=[λ_t+μ (𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t))]^+

where μ is again the stepsize, and the learning iterate 𝐱̂_t rather than the actual decision 𝐱_t is used in this update. 
Compared with the gradient-based recursions (<ref>)-(<ref>), the updates (<ref>)-(<ref>) with one-point bandit feedback do not increase computation or memory requirements, and thus provide a light-weight surrogate for gradient-free online bandit network optimization.










 §.§ BanSaP with multipoint partial feedback

Featuring a simple update given minimal information, the BanSaP with one-point bandit feedback is suitable for fast-varying environments, where multiple function evaluations are impossible.  
As shown later in Sections <ref> and <ref>, the theoretical and empirical performance of BanSaP with single-point evaluation is degraded relative to the full-information case. 

To improve the performance of BanSaP with one-point feedback, we will first rely on two-point function evaluation at each slot <cit.>, and then generalize to multipoint evaluation. 
Intuitively, this approach is justified when the underlying dynamics are slow, e.g., when the load and price profiles in power grids are piece-wise stationary. 
In this case, each slot can be further divided into multiple mini-slots, and one query is performed per mini-slot, over which the loss function and the constraints do not change. 
Compared to (<ref>)-(<ref>), the key difference is that the one-point estimate in (<ref>) is replaced by

    ∇̂^2 f_t(𝐱̂_t):=d/2δ(f_t(𝐱̂_t+δ𝐮_t)-f_t(𝐱̂_t-δ𝐮_t))𝐮_t

where the function values are evaluated on two points around the learning iterate 𝐱̂_t, namely, 𝐱_1,t:=𝐱̂_t+δ𝐮_t and 𝐱_2,t:=𝐱̂_t-δ𝐮_t with 𝐮_t again drawn uniformly from the unit sphere 𝕊:={𝐮∈ℝ^d:𝐮=1}. The primal update becomes 𝐱̂_t+1= P_(1-γ) X(𝐱̂_t-α∇̂_𝐱^2 L_t(𝐱̂_t,λ_t)),  
with Lagrangian gradient 

    ∇̂_𝐱^2 L_t(𝐱̂_t,λ_t):=∇̂^2 f_t(𝐱̂_t)	+∇𝐠_t(𝐱̂_t)^⊤λ_t.



Similar to the one-point case, it is instructive to consider the two-point gradient estimate in the one-dimensional case (d=1), where the expectation of the differentiation term in (<ref>) approximates well the derivative of f_t at x̂_t; that is, 

    𝔼_u[u_t/2δ(f_t(x̂_t+δ u_t)-f_t(x̂_t-δ u_t))]
    
    	=   1/2δ(f_t(x̂_t+δ )-f_t(x̂_t-δ))≈ f_t'(x̂_t)

where the equality follows because the random variable u_t takes values {-1,1} equiprobable. 



Relative to the one-point feedback case, the advantage of the two-point feedback is variance reduction in the gradient estimator. 
Specifically, the second moment of the stochastic gradient can be uniformly bounded, 𝔼[d/2δ(f_t(𝐱̂_t+δ𝐮_t)-f_t(𝐱̂_t-δ𝐮_t))𝐮_t^2]≤ d^2G^2, where G is the Lipschitz constant of f_t(𝐱). This is in contrast to the one-point feedback where the second moment is inversely proportional to δ, since 𝔼[d/δf_t(𝐱̂_t+δ𝐮_t)𝐮_t^2]≤ d^2 F^2/δ^2, with F denoting an upper-bound of f_t(𝐱). The proof of this argument can be found in the Appendix (Lemma <ref>).
In fact, a bias-variance tradeoff emerges in the one-point case, but not in the two-point case. 
This subtle yet critical difference will be responsible for an improved performance of BanSaP with two-point feedback, and its stable empirical performance, as will be seen later.



With the insights gained so far, the next step is to endow the BanSaP with more than two function evaluations <cit.>. 
With M>2 points, the gradient estimator is obtained by querying the function values over M points in the neighborhood of 𝐱̂_t. These points include 𝐱_m,t:=𝐱̂_t+δ𝐮_m,t, 1≤ m ≤ M-1, and the learning iterate 𝐱_m,t:=𝐱̂_t, where 𝐮_m,t is independently drawn from 𝕊. Specifically, the gradient becomes (cf. (<ref>))

    ∇̂_𝐱^M L_t(𝐱̂_t,λ_t):=
       d/δ (M-1)∑_m=1^M-1(f_t(𝐱̂_t+δ𝐮_m,t)-f_t(𝐱̂_t))𝐮_m,t+∇𝐠_t(𝐱̂_t)^⊤λ_t

where we define the M-point stochastic gradient as ∇̂^M f_t(𝐱̂_t):=d/δ (M-1)∑_m=1^M-1(f_t(𝐱̂_t+δ𝐮_m,t)-f_t(𝐱̂_t))𝐮_m,t. 
At the price of extra computations, simulations will validate that the BanSaP with multipoint feedback enjoys improved performance. 
The family of the BanSaP approaches with one- or multiple-point feedback is summarized in Algorithm <ref>. 


The BanSaP solvers here adopt uniform sampling for gradient estimation, meaning 𝐮 is drawn uniformly from the unit sphere. However, other sampling rules can be incorporated without affecting the order of regret bounds derived later.
For example, one can sample 𝐮 from the canonical basis of a d-dimensional space uniformly at random <cit.>, or, sample 𝐮 from a normal distribution <cit.>. 

The effectiveness of these schemes will be tested using simulations.  




§ PERFORMANCE ANALYSIS

In this section, we will introduce pertinent metrics to evaluate BanSaP algorithms in the online bandit learning with long-term constraints, and rigorously analyze the performance of the proposed algorithms.



 §.§ Optimality and feasibility metrics

With regard to performance of BCO schemes, static regret is a common metric, under time-invariant and strictly satisfied constraints, which measures the difference
between the aggregate loss and that of the best
fixed solution in hindsight
<cit.>.
Extending the definition of static regret to accommodate M-point function evaluations and time-varying constraints, let us first consider 


    Reg^ s_T:=1/M∑_t=1^T ∑_m=1^M 𝔼[f_t(𝐱_m,t)]-∑_t=1^T f_t(𝐱^*)

where the actual loss per slot is averaged over the losses of M actions (queried points), 𝔼 is taken over the sequence of random actions (due to δ𝐮 perturbations), and the best static solution is 𝐱^*∈min_𝐱∈ X ∑_t=1^T f_t(𝐱); s. to 𝐠_t(𝐱) ≤0, ∀ t.
A BCO algorithm yielding a
sub-linear regret implies that the algorithm
is “on average” no-regret <cit.>; or, in other words, asymptotically not worse than the
best fixed solution 𝐱^*. 
Though widely used, the static regret relies on a rather coarse benchmark, which is not as useful in dynamic IoT settings.
Specifically, the gap between the loss of the best static and that of the best dynamic
benchmark is as large as O(T) <cit.>.

In response to the quest for improved benchmarks in this dynamic setup with constraints, two metrics
are considered here: dynamic regret and dynamic fit. The notion of dynamic regret has been recently adopted in
<cit.> to assess performance of online algorithms under
time-invariant constraints. For our BCO setting of
(<ref>), we adopt

    Reg^ d_T:=1/M∑_t=1^T ∑_m=1^M 𝔼[f_t(𝐱_m,t)]-∑_t=1^T f_t(𝐱_t^*)

where 𝔼 is again taken over the sequence of random actions, and the benchmark is now formed via a sequence of best dynamic
solutions {𝐱_t^*} for the instantaneous cost
minimization problem subject to the instantaneous constraint,
namely

    𝐱_t^*∈min_𝐱∈ X  f_t(𝐱)   s. to   𝐠_t(𝐱) ≤0.

Quantitatively, the dynamic regret is always larger
than the static regret, i.e., Reg^ s_T ≤ Reg^ d_T, since 
∑_t=1^Tf_t(𝐱^*) is always no smaller than
∑_t=1^Tf_t(𝐱^*_t) according to the definitions of
𝐱^* and 𝐱^*_t.
Hence, a sub-linear dynamic regret implies a sub-linear static regret, but not vice versa.

Regarding feasibility of decisions generated by a BCO algorithm, the notion of
dynamic fit will be used to measure the
accumulated violation of constraints <cit.>, that is

    Fit^ d_T:=[1/M∑_t=1^T ∑_m=1^M 𝐠_t(𝐱_m,t)]^+.

Note that the dynamic fit is zero if the accumulated
violation 1/M∑_t=1^T ∑_m=1^M 𝐠_t(𝐱_m,t) is entry-wise
less than zero. Hence, enforcing
1/M∑_t=1^T ∑_m=1^M 𝐠_t(𝐱_m,t) ≤0 is
different from restricting 𝐱_t to meet
1/M∑_m=1^M 𝐠_t(𝐱_m,t)≤0 in every slot.
While the latter readily implies the former, the long-term constraint implicitly assumes that the instantaneous constraint violations can be compensated by the later strictly feasible decisions, and thus allows adaptation of online decisions to the unknown dynamics. 


Under this broader BCO setup, an ideal online algorithm is the
one that achieves both sub-linear dynamic regret and sub-linear
dynamic fit. A sub-linear dynamic regret implies “no-regret”
relative to the clairvoyant dynamic solution on the long-term
average; i.e., lim_T→∞ Reg_T^
d/T=0; and a sub-linear dynamic fit indicates that the online
strategy is also feasible on average; i.e., lim_T→∞ Fit_T^ d/T=0. Unfortunately, the sub-linear
dynamic regret is not achievable in general, even when the time-varying constraint in (<ref>)
is absent <cit.>.
Therefore, we aim at designing an online strategy that generates a sequence {𝐱_m,t} ensuring sub-linear dynamic regret and fit, under the suitable conditions on the underlying dynamics.






 §.§ Main results

Before formally analyzing the dynamic regret and fit for BanSaP, we assume that the following conditions are satisfied.


(as1) For every t, the functions 
f_t(𝐱) and 
𝐠_t(𝐱) are convex.



(as2) Function f_t(𝐱) is bounded over the set X, meaning |f_t(𝐱)|≤ F, ∀𝐱∈ X; while f_t(𝐱) and g_t^n(𝐱) have bounded gradients; that is, ∇
f_t(𝐱)≤ G, and max_n∇ g_t^n(𝐱)≤ G.



(as3) For a small constant γ, there exists a constant η>0, and an interior point 𝐱̃∈ (1-γ) X such that 𝐠_t(𝐱̃)≤ -η1, ∀ t.

(as4) With 𝔹:={𝐱∈ℝ^d:𝐱≤ 1} denoting the unit ball, there exist constants 0<r≤ R such that r𝔹⊆ X⊆ R𝔹.




Assumptions (as1)-(as2) are typical in OCO with both full- and partial-information feedback
<cit.>; (as3) is Slater's condition modified for our BCO setting, which guarantees the existence of a bounded Lagrange multiplier <cit.> in the constrained optimization; and, (as4) requires the action set to be bounded within a ball that contains the origin. 
When (as4) appears to be restrictive, it is tantamount to assuming X is compact and has a nonempty interior, because one can always apply an affine transformation (a.k.a. reshaping) on X to satisfy (as4); see <cit.>. 

Under these assumptions, we are on track to first provide upper bounds for the dynamic regret, and the dynamic fit of the BanSaP solver with one-point feedback. 



Suppose that (as1)-(as4) are satisfied, and consider the parameters α, μ, δ, γ defined in (<ref>)-(<ref>), and constants F, G, r, R defined in (as2)-(as4). 
If the dual variable is initialized by λ_1=0, then the BanSaP with one-point feedback in (<ref>)-(<ref>) has dynamic regret bounded by

    Reg^ d_T≤R/αV(𝐱_1:T^*)   +R^2/2α+d^2G^2R^2α T/δ^2+2Gδ T
       +γ GRT(1+λ̅)+2μ G^2R^2T

where λ̅:=max_t λ_t, and the accumulated variation of the per-slot minimizers 𝐱^*_t in (<ref>) is given by

    V(𝐱_1:T^*):=∑_t=1^T 𝐱^*_t-𝐱^*_t-1.

In addition, the dynamic fit defined in (<ref>) is bounded by

    Fit^ d_T≤λ̅/μ+G^2√(N)T/2β   +δ G√(N)T
       +β√(N)T(α^2 d^2F^2 /δ^2+α^2 G^2λ̅^2)

where β>0 is a pre-selected constant. 
Furthermore, if we choose the stepsizes as α=μ= O(T^-3/4), and the parameters δ= O(T^-1/4), β=T^1/4 and γ=δ/r, then the online decisions generated by BanSaP are feasible, i.e., 𝐱_1,t∈ X; and also yield the following dynamic regret and fit
[box=]align
  Reg^d_T= O(V(𝐱_1:T^*)T^3/4)  and  Fit^d_T 
	=O(T^3/4).

	


See Appendix <ref>.	



For BanSaP with one-point feedback, Theorem <ref> asserts that its dynamic regret and fit are upper-bounded by some
constants depending on the those parameters, the time horizon, and the accumulated variation of per-slot minimizers.
Interestingly, the crucial constant δ controlling the perturbation of random actions appears in both the denominator and numerator of (<ref>) and (<ref>), which correspond to the variance and bias of the gradient estimator. 
Therefore, simply setting a small δ will not only reduce the bias, but it will also boost the variance - a clear manifestation of the that is known as bias-variance tradeoff in BCO <cit.>.
Optimally choosing parameters implies that the dynamic fit is sub-linearly growing, and the dynamic regret is sub-linear given that the variation of the per-slot minimizer is slow enough; i.e., V(𝐱_1:T^*)=𝐨(T^1/4). 


Regarding BanSaP with two-point feedback, we can prove the following result that parallels Theorem <ref>.

Consider the assumptions and the definitions of constants in Theorem <ref>. 
If the dual variable is initialized by λ_1=0, then BanSaP with two-point feedback has dynamic regret bounded by

    Reg^ d_T≤R/αV(𝐱_1:T^*)+R^2/2α   +2μ G^2R^2T+α d^2G^2 T
       +γ GRT(1+λ̅)+2δ GT

and has dynamic fit in (<ref>) bounded by

    Fit^ d_T≤λ̅/μ+G^2√(N)T/2β   +δ G√(N)T
       +β√(N)T(α^2 d^2G^2+α^2 G^2λ̅^2).

In this case, if we choose the stepsizes as α=μ= O(T^-1/2), and set the parameters as β=T^1/2,  δ= O(T^-1), and γ=δ/r, then the online decisions generated by BanSaP are feasible, and its dynamic regret and fit are bounded by
[box=]align
 	  Reg^d_T= O(V(𝐱_1:T^*)T^1/2)  and  Fit^d_T 
	=O(T^1/2)

where V(𝐱_1:T^*) is the accumulated
variation of the per-slot minimizers 𝐱^*_t in (<ref>).


See Appendix <ref>.	


Comparing with the bounds in (<ref>) and (<ref>), the perturbation constant δ only appears in the numerator of (<ref>) and (<ref>) because our gradient estimator here replies on two points. 
In this case, the additional function evaluation allows BanSaP to choose an arbitrarily small δ to minimize the bias of stochastic gradient, without increasing its variance. This observation is aligned with those in BCO without long-term constraints <cit.>. 
Furthermore, Theorem <ref> establishes that the dynamic regret and fit are sub-linear if V(𝐱_1:T^*)=𝐨(T^1/2), which markedly improves those in Theorem <ref> under one-point feedback. 


For the case of BanSaP with M>2 points, slightly improved bounds can be proved without changing the order of regret and fit, but they are omitted here for brevity. 
In addition, the bounds in Theorems <ref> and <ref> can be achieved without any knowledge of V(𝐱_1:T^*).
When the order of V(𝐱_1:T^*) is known, or, can be estimated a-priori, tighter regret and fit bounds can be obtained by adjusting stepsizes accordingly.
Formally, we can arrive at the following corollary.

	Under the conditions of Theorems <ref> and <ref>, suppose that there exists a constant ρ∈[0,1) such that the variation satisfies V(𝐱_1:T^*)=𝐨(T^ρ). If the stepsizes of BanSaP with one-point feedback are chosen as α=μ= O(T^3/4(ρ-1)), 



    and the parameters are δ= O(T^1/4(ρ-1)), β=T^3/4(1-ρ),  and γ=δ/r, 
	 then the dynamic regret and fit in (<ref>) become
	
    Reg^ d_T= O(T^1/4(ρ+3))  and   Fit^ d_T= O(T^1/4(ρ+3)).

Likewise, if the stepsizes of BanSaP with two-point feedback are chosen such that α=μ= O(T^1/2(ρ-1)), 



    and the parameters are δ= O(T^1/2(ρ-1)), β=T^1/2(1-ρ),  and γ=δ/r, 
	 then the dynamic regret and fit in (<ref>) become
	
    Reg^ d_T= O(T^1/2(ρ+1))  and   Fit^ d_T= O(T^1/2(ρ+1)).



Apparently, Corollary <ref> implies that sub-linear dynamic regret and fit are both possible, provided that the accumulated variation of the minimizers is growing sub-linearly (ρ<1), and it is available to the learner in advance. It provides valuable insights for choosing optimal stepsizes in dynamic environments.
Specifically, adjusting stepsizes to match the variability of the environment is the key to achieving the optimal dynamic regret and fit. Intuitively, when the variation is fast (large ρ), slowly decaying stepsizes (thus larger stepsizes) can better track the potential changes; and vice versa.


As a special case of Theorems <ref> and <ref>, by confining 𝐱_1^*=⋯=𝐱_T^* so that V(𝐱_1:T^*)=0, the dynamic regret bounds (<ref>) and (<ref>) reduce to the static ones, which correspond to O(T^3/4) in the one-point feedback case, and to O(√(T)) in the two-point case. 
This pair of bounds markedly improves the regret versus fit tradeoff in <cit.>, and matches the order of regret in <cit.>, and <cit.>, which are the best possible ones that can be achieved by efficient algorithms even in the BCO setup without the long-term constraints.




Theorems <ref>, <ref> and Corollary <ref> extend the dynamic regret analysis in <cit.> to the regime of bandit online learning with long-term time-varying constraints.
Interestingly though, in the BCO setting of our interest, sub-linear dynamic regret and fit are possible to achieve when the per-slot minimizer does not vary on average, that is, V(𝐱_1:T^*) is sub-linearly growing with T. 














§ NUMERICAL TESTS


In this section, we demonstrate how the fog computation offloading task can benefit from our novel BanSaP solvers. 




 §.§ BanSaP for fog computation offloading

Recall that the computation offloading problem (<ref>) is in the form of (<ref>). 
Therefore,
the BanSaP solver of Section <ref> can be
customized to solve (<ref>) in an online fashion, with
provable performance and feasibility guarantees. 


Specifically, with
𝐠_t(𝐱_t) as in (<ref>) and f_t(𝐱_t) as in (<ref>),
the primal update (<ref>) boils down to a simple closed-form gradient update amenable to decentralized implementation; the cloud offloading amount at node n is


    ẑ_t+1^n=[ẑ_t^n-α(∇̂ c^n_t(ẑ_t^n)-λ_t^n)]_0^z̅^n

and the offloading amount from node n to node k is given by

    ŷ_t+1^nk=[ŷ_t^nk-α(∇̂ c^nk_t(ŷ_t^nk)-λ_t^n+λ_t^k)]_0^y̅^nk

while the local processing decision at node n is generated by

    ŷ_t+1^nn=[ŷ_t^nn-α(∇̂ h^n_t(ŷ_t^nn)-λ_t^n)]_0^y̅^nn


where α is chosen according to Theorems <ref> and <ref>. 
Using two-point feedback (M=2) as an example, the gradients involved in (<ref>) can be estimated as


    ∇̂^2 c^n_t(ẑ_t^n):=d/2δ(f_t(𝐱̂_t+δ𝐮_t_𝐱_1,t)-f_t(𝐱̂_t-δ𝐮_t_𝐱_2,t))u_t(ẑ^n)

and with respect to the offloading variable, as 

    ∇̂^2 c^nk_t(ŷ_t^nk):=d/2δ(f_t(𝐱̂_t+δ𝐮_t)-f_t(𝐱̂_t-δ𝐮_t))u_t(ŷ^nk)

and with respect to the local processing variable, as

    ∇̂^2 h^n_t(ŷ_t^nn):=d/2δ(f_t(𝐱̂_t+δ𝐮_t)-f_t(𝐱̂_t-δ𝐮_t))u_t(ŷ^nn)


where u_t(ẑ^n), u_t(ŷ^nk), and u_t(ŷ^nn) represent the corresponding entries of the random vector 𝐮_t∈ℝ^| E| at slot t.

The dual update (<ref>) at each node n reduces to
 
    λ_t+1^n=[λ_t^n+μ(b_t^n+∑_k∈ N_n^ inŷ_t+1^kn-∑_k∈ N_n^ outŷ_t+1^nk-ẑ_t+1^n-ŷ_t+1^nn)]^+

where μ is chosen according to Theorems <ref> and <ref>. 
Intuitively, to guarantee completion of the service requests, the dual variable increases (increasing penalty) when there is instantaneous service residual, and decreases when over-serving incurs in  the mobile-edge computing systems.
Following its generic form in Algorithm <ref>, BanSaP for online fog computation offloading tasks, is summarized in Algorithm <ref>.
















 §.§ Numerical experiments

Consider the fog computing task in Section <ref> with N=10 nodes and a cloud center. 
Each fog node has an outgoing link to the cloud, and two outgoing links to two nearby fog nodes for local collaborative computing. 
For a communication link offloading loads from node n to k, the offloading limit is y̅^nk=10, the local computation limit at node n is y̅^nn=50, and the fog-cloud offloading limits {z̅^n} are all set to 100.
The online cost (a.k.a. service latency) in (<ref>) is specified by



    f_t(𝐱_t):=∑_n∈ N(e^p_t^n z_t^n+∑_k∈ N_n^ outl^nky_t^nk+l^nn(y_t^nn)^2)

where p_t^n=0.015sin(π t/96)+0.05, n∈ N\{4,5}, p_t^n=0.045sin(π t/96)+0.15, n∈{4,5}, and the local coefficients are set to l^nk=8/y̅^nk and l^nn=8/y̅^nn. 
Regarding the data arrival rate b_t^n, it is generated according to b_t^n=q^nsin(π t/96)+ν_t^n, with q^n and ν_t^n uniformly distributed over [40,50] and [45,55] for n∈ N\{1,2,3}⋃{4,5}, and q^n∈[32,40],ν_t^n∈[36,44], n∈{1,2,3}, and q^n∈[20,25], ν_t^n∈[22.5,27.5], n∈{4,5}.
Notice that the scales of p_t^n and b_t^n vary between nodes, mimicking heterogeneity of real IoT systems; and the periods of p_t^n and b_t^n correspond to a 24-hour interval with slot duration 7.5 minutes. 
When the parameters of BanSaP need to be slightly adjusted in each test, they are set to γ=0.05, and δ=4 for with M=1, and δ=0.05 for M≥ 2.







Finally, 

BanSaP is benchmarked by: i) the full-information MOSP method in <cit.> that takes gradient-based update for primal-dual variables; ii) the heuristic cloud-only approach that offloads all data requests to the remote cloud; and, iii) the heuristic fog-only approach that processes all data requests locally without collaboration. 
For both cloud-only and fog-only approaches, unoffloaded and unprocessed requests are buffered at the fog nodes for later processing; thus, these amounts are measured by their fit.   
As different stepsizes of BanSaP and MOSP lead to different behaviors, we manually optimized stepsizes in each test so that they have similar fit, and focus on their cost comparison.
All simulated tests were averaged over 500 Monte Carlo realizations.




Effect of complexity and sampling schemes.
In a simplified setting with N=5 nodes, the fit and average cost are compared among the BanSaP variants with M-point feedback under different sampling schemes in Figs. <ref> and <ref>. 

Clearly, for both sampling schemes, the cost and fit of BanSaP solvers decrease as the amount of bandit feedback increases.  
However, such performance gain varnishes when feedback increases; e.g., M≥ 4. 
Regarding the sampling schemes, 
Fig. <ref> demonstrates that when all the BanSaP variants have low dynamic fit, the uniform sampling-based BanSaP with one-point feedback has large initial fit; and Fig. <ref> confirms that  for M=1, the coordinate sampling-based BanSaP outperforms that with uniform sampling; and, for M≥ 2, the BanSaP solvers with uniform sampling incur lower cost.  
Therefore, to optimize empirical performance in the subsequent tests, coordinate sampling is adopted by BanSaP with M=1, while uniform sampling is used in BanSaP with M≥2.






Optimality and feasibility.
With optimized sampling schemes for BanSaP solvers, the dynamic
fit and average cost are then compared among three BanSaP variants, MOSP, and two heuristic schemes in Figs. <ref> and <ref>. 
Without queueing at the fog side, the cloud-only scheme has much lower dynamic fit since all user demands are offloaded to the remote cloud. 
However, it incurs a much higher average cost (service latency) as the network latency between fog and cloud becomes high due to the large offloading amount.   
By increasing the amount of feedback, the BanSaP solver tends to have a lower fit and a lower average cost, both of which are comparable to those of MOSP when M≥ 2.
On the other hand, the BanSaP with only one-point bandit feedback still has a similar fit relative to the fog-only scheme, but enjoys much lower cost. 
Interestingly enough, when the variance (cf. the shaded area in Fig. <ref>) of the one-point BanSaP's cost is high, it markedly varnishes when multiple function values become available, which corroborates our claims in Theorems <ref>-<ref>. 





 






Effect of network size.
The third test evaluates the performance of all schemes under different number of fog nodes (i.e., network size).  
For each algorithm, the fit averaged over all fog nodes and time is presented in Fig. <ref>, and the cost averaged over the time is shown in Fig. <ref>. 
Clearly, the one-point BanSaP has lower average fit than the fog-only approach in most scenarios, and also incurs less average cost in all tested settings.  
Similar to those in Figs. <ref> and <ref>, the average fit of BanSaP with multiple function evaluations is still comparable to that of the full-information MOSP as the network size grows. 
An interesting observation here is that as the number of fog nodes increases, the performance gain of the BanSaP solver with a large M becomes more evident; see e.g., Fig. <ref>. 
This implies that for a larger network, BanSaP benefits from more bandit information to learn and track the network dynamics.






§ CONCLUSIONS AND THE ROAD AHEAD


Bandit convex optimization (BCO) in dynamic environments was studied
in this paper. 
Different from existing works in bandit settings, the focus was on a broader setting where part of the constraints are revealed after taking actions, and are also tolerable to instantaneous violations but have to be satisfied on average.  
The novel BCO setting fits well the emerging fog computing tasks in IoT.
A class of online bandit saddle-point (BanSaP) approaches were proposed, and their online performance was rigorously analyzed. 
It was shown that the resultant regret bounds match those attained in BCO setups without long-term constraints. 
Furthermore, the BanSaP solvers can simultaneously yield sub-linear dynamic regret and fit, if the dynamic solutions vary slowly over time. 

Our algorithmic and theoretical results serve as an exciting first step to innovate
online bandit learning tailored for dynamic network management tasks, emerging from contemporary IoT applications. 
Interesting future directions include designing asynchronous variants of BanSaP, and incorporating predictable dynamic models in online network optimization. 



§ ACKNOWLEDGEMENT

The authors would like to thank Yanning Shen and Qing Ling for
helpful feedback on the early version of this manuscript.


10

url@samestyle








samie2016b
F. Samie, V. Tsoutsouras, S. Xydis, L. Bauer, D. Soudris, and J. Henkel,
  “Distributed QoS management for Internet of Things under resource
  constraints,” in Proc. Intl. Conf. on Hardware/Software Codesign and
  System Synthesis, Pittsburgh, PA, Oct. 2016, pp. 1–10.

chiang2016
M. Chiang and T. Zhang, “Fog and IoT: An overview of research
  opportunities,” IEEE Internet Things J., vol. 3, no. 6, pp. 854–864,
  2016.

lee2017
G. Lee, W. Saad, and M. Bennis, “An online secretary framework for fog network
  formation with minimal latency,” arXiv:1702.05569, Apr. 2017.

samie2016
F. Samie, V. Tsoutsouras, L. Bauer, S. Xydis, D. Soudris, and J. Henkel,
  “Computation offloading and resource allocation for low-power IoT edge
  devices,” in Proc. World Forum Internet Things, Dec. 2016, pp. 7–12.

mach2017
P. Mach and Z. Becvar, “Mobile edge computing: A survey on architecture and
  computation offloading,” IEEE Comm. Surveys & Tutorials, 2017, to
  appear.

wang2017
F. Wang, J. Xu, X. Wang, and S. Cui, “Joint offloading and computing
  optimization in wireless powered mobile-edge computing systems,”
  IEEE Trans. Wireless Commun., Feb. 2017, submitted. [Online].
  Available: <https://arxiv.org/abs/1702.00606>


mao2017
Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “Mobile edge computing:
  Survey and research outlook,” arXiv preprint:1701.01090, Jan. 2017.

zinkevich2003
M. Zinkevich, “Online convex programming and generalized infinitesimal
  gradient ascent,” in Proc. Intl. Conf. on Machine Learning,
  Washington D.C., Aug. 2003.

hazan2007
E. Hazan, A. Agarwal, and S. Kale, “Logarithmic regret algorithms for online
  convex optimization,” Machine Learning, vol. 69, no. 2-3, pp.
  169–192, Dec. 2007.

duchi2011jmlr
J. C. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online
  learning and stochastic optimization,” Journal of Machine Learning
  Research, vol. 12, pp. 2121–2159, Jul. 2011.

jadbabaie2015
A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan, “Online
  optimization: Competing with dynamic comparators,” in Intl. Conf. on
  Artificial Intelligence and Statistics, San Diego, CA, May 2015.

hall2015
E. C. Hall and R. M. Willett, “Online convex optimization in dynamic
  environments,” IEEE J. Sel. Topics Signal Process., vol. 9, no. 4,
  pp. 647–662, Jun. 2015.

chen2017tsp
T. Chen, Q. Ling, and G. B. Giannakis, “An online convex optimization approach
  to proactive network resource allocation,” IEEE Trans. Signal
  Processing, Jan. 2017 (revised), Available:
  https://arxiv.org/abs/1701.03974.

chen2017iot
T. Chen, Y. Shen, Q. Ling, and G. B. Giannakis, “Online learning for
  “thing-adaptive” fog computing in IoT,” in Proc. of Asilomar
  Conf., Pacific Grove, CA, Oct. 2017. [Online]. Available:
  <www.dropbox.com/s/z4qnog6x0gzd2ko/TAOSP.pdf?dl=0>


neely2017
M. J. Neely and H. Yu, “Online convex optimization with time-varying
  constraints,” arXiv preprint:1702.04783, Feb. 2017.

flaxman2005
A. D. Flaxman, A. T. Kalai, and H. B. McMahan, “Online convex optimization in
  the bandit setting: gradient descent without a gradient,” in Proc. of
  ACM SODA, Vancouver, Canada, Jan. 2005, pp. 385–394.

agarwal2010
A. Agarwal, O. Dekel, and L. Xiao, “Optimal algorithms for online convex
  optimization with multi-point bandit feedback.” in Proc. Annual Conf.
  on Learning Theory, Haifa, Israel, 2010, pp. 28–40.

shamir2017
O. Shamir, “An optimal algorithm for bandit and zero-order convex optimization
  with two-point feedback,” Journal of Machine Learning Research,
  vol. 18, no. 52, pp. 1–11, 2017.

bubeck2012
S. Bubeck and N. Cesa-Bianchi, “Regret analysis of stochastic and
  nonstochastic multi-armed bandit problems,” Found. and Trends in Mach.
  Learn., vol. 5, no. 1, pp. 1–122, 2012.

duchi2015
J. C. Duchi, M. I. Jordan, M. J. Wainwright, and A. Wibisono, “Optimal rates
  for zero-order convex optimization: The power of two function evaluations,”
  IEEE Trans. Inform. Theory, vol. 61, no. 5, pp. 2788–2806, May
  2015.

nesterov2017
Y. Nesterov and V. Spokoiny, “Random gradient-free minimization of convex
  functions,” Foundations of Computational Mathematics, vol. 17, no. 2,
  pp. 527–566, Apr. 2017.

mahdavi2012
M. Mahdavi, R. Jin, and T. Yang, “Trading regret for efficiency: Online
  convex optimization with long term constraints,” Journal of Machine
  Learning Research, vol. 13, pp. 2503–2528, Sep 2012.

awerbuch2004
B. Awerbuch and R. D. Kleinberg, “Adaptive routing with end-to-end feedback:
  Distributed learning and geometric approaches,” in Proc. ACM Symp. on
  Theory of Computing, Chicago, IL, Jun. 2004, pp. 45–53.

kao2016
Y.-H. Kao, K. Wright, B. Krishnamachari, and F. Bai, “Online learning for
  wireless distributed computing,” arXiv preprint:1611.02830, Nov.
  2016. [Online]. Available: <https://arxiv.org/abs/1611.02830>


neely2010
M. J. Neely, “Stochastic network optimization with application to
  communication and queueing systems,” Synthesis Lectures on
  Communication Networks, vol. 3, no. 1, pp. 1–211, 2010.

chen2016tsp
T. Chen, A. Mokhtari, X. Wang, A. Ribeiro, and G. B. Giannakis, “Stochastic
  averaging for constrained optimization with application to online resource
  allocation,” IEEE Trans. Signal Processing, vol. 65, no. 12, pp.
  3078–3093, Jun. 2017.

sardellitti2015
S. Sardellitti, G. Scutari, and S. Barbarossa, “Joint optimization of radio
  and computational resources for multicell mobile-edge computing,” IEEE
  Trans. Signal Info. Process. Netw., vol. 1, no. 2, pp. 89–103, Jun. 2015.

chen2016ton
X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation
  offloading for mobile-edge cloud computing,” IEEE/ACM Trans.
  Networking, vol. 24, no. 5, pp. 2795–2808, Oct. 2016.

huang2017
H. Huang, Q. Ling, W. Shi, and J. Wang, “Collaborative resource allocation
  over a hybrid cloud center and edge server network,” Journal of
  Computational Mathematics, 2017, to appear.

besbes2015
O. Besbes, Y. Gur, and A. Zeevi, “Non-stationary stochastic optimization,”
  Operations Research, vol. 63, no. 5, pp. 1227–1244, Sep. 2015.

bertsekas1999
D. P. Bertsekas, Nonlinear Programming.1em plus 0.5em minus
  0.4emBelmont, MA: Athena scientific, 1999.







The proof generalizes the result in <cit.> from static regret with full-information gradient feedback to the dynamic regret with partial-information bandit feedback. 



 §.§ Supporting lemmas

Before proving the main theory, we first establish several key lemmas and propositions.
The following lemma establishes the unbiasedness of one- and two-point estimations <cit.>.



	With 𝐮 drawn uniformly from the surface of the unit ball 𝕊:={𝐮:𝐮=1}⊆ℝ^d, we have for given a constant δ>0 that
	
    𝔼_𝐮[d/δf_t(𝐱+δ𝐮)𝐮]=∇f̌_t(𝐱)

where ∇f̌_t(𝐱) is the gradient of the smoothed function f̌_t(𝐱):=𝔼_𝐯[f_t(𝐱+δ𝐯)] with 𝐯 drawn from a unit ball 𝔹, and d is the dimension of the variable 𝐱.
Likewise, for the two-point case, we have that
	
    𝔼_𝐮[d/2δ(f_t(𝐱+δ𝐮)-f_t(𝐱-δ𝐮))𝐮]=∇f̌_t(𝐱).


Lemma <ref> provides valuable insights for performing gradient-based algorithms in bandit setting. Namely, ∇̂^1 f_t(𝐱̂_t) and ∇̂^2 f_t(𝐱̂_t) are the unbiased gradient estimators of the smoothed function f̌_t(𝐱), which is an approximation of f_t(𝐱). Note that (as1)-(as2) also imply that the smoothed function f̌_t(𝐱) is convex and G-Lipschitz continuous <cit.>, which will be used frequently in the subsequent analysis.

The following lemma establishes the norm (or variance) of one- and two-point gradient estimations <cit.>.


For the gradient ∇̂^1 f_t(𝐱̂_t) in (<ref>), we have that

    ∇̂^1 f_t(𝐱̂_t)≤d/δ F

where F is an upper-bound of the function.  
For the gradient estimator ∇̂^2 f_t(𝐱̂_t) in (<ref>), we have that

    ∇̂^2 f_t(𝐱̂_t)≤ d G

where G is the Lipschitz constant of the loss function.  


	For the gradient ∇̂^1 f_t(𝐱̂_t) in (<ref>), it holds that

    ∇̂^1 f_t(𝐱̂_t)=d/δ|f_t(𝐱̂_t+δ𝐮_t)|𝐮_t≤d/δ F

where F is an upper-bound of the function. Likewise for ∇̂^2 f_t(𝐱̂_t) in (<ref>), we have that

    ∇̂^2 f_t(𝐱̂_t)   =d/2δ(f_t(𝐱̂_t+δ𝐮_t)-f_t(𝐱̂_t-δ𝐮_t))𝐮_t
       =d/2δ|f_t(𝐱̂_t+δ𝐮_t)-f_t(𝐱̂_t-δ𝐮_t)|𝐮_t
       ≤dG/2δ2δ𝐮_t≤ d G

where G is the Lipschitz constant of the loss function and 𝐮_t=1 by design. Thus, the proof is complete. 


Having bounded the norm of stochastic gradients, the next lemma is useful to ensure feasibility of actual online actions.

Consider a constant r>0 so that r𝔹⊆ X, where 𝔹:={𝐯:𝐯≤ 1}⊆ℝ^d is the unit ball. If we choose γ=δ/r, and the iterate satisfies 𝐱̂_t∈(1-γ) X, then 𝐱̂_t+δ𝐮_t∈ X, where 𝐮_t is drawn uniformly from the unit sphere 𝕊:={𝐮:𝐮=1}⊆ℝ^d.


The next lemma is crucial to establish the dynamic fit <cit.>.

	Considering the BanSaP recursion (<ref>), we have the following bound for the cumulative constraint violation

    ∑_t=1^T 𝐠_t(𝐱̂_t)≤λ_T+1/μ+G^2T1/2β+β/2∑_t=1^T𝐱̂_t+1-𝐱̂_t^21

where μ>0 is the stepsize of the dual iteration (<ref>), and β>0 is a pre-defined constant. 



From the n-th entry of λ in (<ref>), we have

    λ_t+1^n   ≥λ_t^n+μ (g_t^n(𝐱̂_t)+∇^⊤ g_t^n(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t))
       (a)≥λ_t^n+μ g_t^n(𝐱̂_t)-μ/2β∇ g_t^n(𝐱̂_t)^2-μβ/2𝐱̂_t+1-𝐱̂_t^2
       (b)≥λ_t^n+μ g_t^n(𝐱̂_t)-μ G^2/2β-μβ/2𝐱̂_t+1-𝐱̂_t^2

where (a) uses the Cauchy-Schwarz inequality, and (b) follows from the bound on the gradients in (as2). The proof is then complete after summing up (<ref>) over t=1,…,T.




	Consider the BanSaP recursions (<ref>) and (<ref>) with a generic gradient ∇̂ f_t(𝐱̂_t), which is estimated from one- or multi-point feedback. The following holds ∀𝐱∈ (1-γ) X

    1/μ𝔼[Δ(λ_t)]≤f̌_t(𝐱)-𝔼[f̌_t(𝐱̂_t)]+𝔼[λ_t^⊤𝐠_t(𝐱)]+2μ G^2R^2
       +1/2α𝔼[𝐱-𝐱̂_t^2]-1/2α𝔼[𝐱-𝐱̂_t+1^2]+α∇̂ f_t(𝐱̂_t)^2

where the constants G, R and F are as in (as2) and (as3).



Taking the norm square in (<ref>), we have	

    λ_t+1^2   ≤λ_t^2+2μλ_t^⊤(𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t))
       +μ^2𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)^2
       ≤λ_t^2+2μλ_t^⊤(𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t))
       +2μ^2𝐠_t(𝐱̂_t)^2+2μ^2∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)^2.


With Δ(λ_t):=1/2(λ_t+1^2-λ_t^2),  (<ref>) implies that

    1/μΔ(λ_t)≤λ_t^⊤(𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t))+2μ G^2R^2

where G and R are the bounds on the gradient and the radius of the feasible set.
	
On the other hand, recall that the primal iterate 𝐱̂_t+1 is
the optimal solution to the following optimization problem

    𝐱̂_t+1=min_𝐱∈(1-γ) X∇̂_𝐱^⊤ L_t(𝐱̂_t,λ_t)(𝐱-𝐱̂_t)+1/2α𝐱-𝐱̂_t^2.

Recalling the definition of ∇̂_𝐱 L_t(𝐱̂_t,λ_t), we thus have that

    𝐱̂_t+1   =min_𝐱∈(1-γ) X∇̂^⊤ f_t(𝐱̂_t)(𝐱-𝐱̂_t)
    
    	+   λ_t^⊤(𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱-𝐱̂_t))+1/2α𝐱-𝐱̂_t^2

where we add λ_t^⊤𝐠_t(𝐱_t) to the RHS of (<ref>). 
Note that it will not change the minimizer of (<ref>), since the added term is constant, and not coupled with the variable 𝐱.

To connect (<ref>) with the bound obtained in (<ref>), adding ∇̂^⊤ f_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)+1/2α𝐱̂_t+1-𝐱̂_t^2 to the RHS of (<ref>), we have that

    1/μΔ(λ_t)+∇̂^⊤ f_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)+1/2α𝐱̂_t+1-𝐱̂_t^2
    ≤    λ_t^⊤(𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t))+1/2α𝐱̂_t+1-𝐱̂_t^2
            + ∇̂^⊤ f_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)+2μ G^2R^2.


Note that 𝐱̂_t+1 is the minimizer of (<ref>), where the objective on the RHS of (<ref>) is strongly-convex, thus we have that

    1/μΔ(λ_t)+∇̂^⊤ f_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)+1/2α𝐱̂_t+1-𝐱̂_t^2
    ≤    λ_t^⊤(𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱-𝐱̂_t))+1/2α𝐱-𝐱̂_t^2+2μ G^2R^2
       +∇̂^⊤ f_t(𝐱̂_t)(𝐱-𝐱̂_t)-1/2α𝐱-𝐱̂_t+1^2
    (a)≤    λ_t^⊤𝐠_t(𝐱)+∇̂^⊤ f_t(𝐱̂_t)(𝐱-𝐱̂_t)+2μ G^2R^2
       +1/2α𝐱-𝐱̂_t^2-1/2α𝐱-𝐱̂_t+1^2, ∀𝐱∈ (1-γ) X

where (a) uses the non-negativity that λ_t≥0, and the convexity such that 𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱-𝐱̂_t)≤𝐠_t(𝐱).

Using the Cauchy-Schwarz inequality, we have that

    -∇̂^⊤ f_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)
    	≤α∇̂ f_t(𝐱̂_t)^2+𝐱̂_t+1-𝐱̂_t^2/4α.


Plugging (<ref>) into (<ref>) and rearranging terms, for ∀𝐱∈ (1-γ) X, we have that 
 
    1/μΔ(λ_t)+1/4α𝐱̂_t+1-𝐱̂_t^2
    ≤    λ_t^⊤𝐠_t(𝐱)+∇̂^⊤ f_t(𝐱̂_t)(𝐱-𝐱̂_t)+2μ G^2R^2
       +1/2α𝐱-𝐱̂_t^2-1/2α𝐱-𝐱̂_t+1^2+α∇̂ f_t(𝐱̂_t)^2.


Taking expectation over 𝐮_t on both side of (<ref>) conditioning on 𝐱̂_t, it follows that
 
    1/μ𝔼[Δ(λ_t)]+1/4α𝔼[𝐱̂_t+1-𝐱̂_t^2]
    ≤    λ_t^⊤𝐠_t(𝐱)+𝔼[∇̂^⊤ f_t(𝐱̂_t)(𝐱-𝐱̂_t)]+2μ G^2R^2
       +1/2α𝐱-𝐱̂_t^2-1/2α𝔼[𝐱-𝐱̂_t+1^2]+α∇̂ f_t(𝐱̂_t)^2
    (c)=    λ_t^⊤𝐠_t(𝐱)+∇^⊤f̌_t(𝐱̂_t)(𝐱-𝐱̂_t)+2μ G^2R^2
       +1/2α𝐱-𝐱̂_t^2-1/2α𝔼[𝐱-𝐱̂_t+1^2]+α∇̂ f_t(𝐱̂_t)^2

where (c) holds since the randomness 𝐮_t in ∇̂ f_t(𝐱̂_t) is independent of 𝐱̂_t, and ∇̂ f_t(𝐱̂_t) is an unbiased estimator of ∇f̌_t(𝐱̂_t).

The convexity of f_t(𝐱) implies that f̌_t(𝐱) is also convex, and thus ∇^⊤f̌_t(𝐱̂_t)(𝐱-𝐱̂_t)≤f̌_t(𝐱)-f̌_t(𝐱̂_t). Plugging into (<ref>) and taking expectation over all possible 𝐱̂_t, it follows that
 
    1/μ𝔼[Δ(λ_t)]+1/4α𝔼[𝐱̂_t+1-𝐱̂_t^2]
    ≤    f̌_t(𝐱)-𝔼[f̌_t(𝐱̂_t)]+𝔼[λ_t^⊤𝐠_t(𝐱)]+2μ G^2R^2
    +   1/2α𝔼[𝐱-𝐱̂_t^2]-1/2α𝔼[𝐱-𝐱̂_t+1^2]+α𝔼[∇̂ f_t(𝐱̂_t)^2]

 which completes the proof by dropping the nonnegative term 𝔼[𝐱̂_t+1-𝐱̂_t^2] in the LHS.
 
 


 §.§ Proof of Theorem <ref>

With γ=δ/r, the feasibility of actions {𝐱_1,t} readily follows from Lemma <ref>, i.e., 𝐱_1,t∈ X, ∀ t. 
To prove the dynamic regret and fit bounds, the following result is needed.
 
	For the BanSaP recursions (<ref>)-(<ref>), if we choose α=μ= O(T^-3/4) and δ= O(T^-1/4), the dual iterates are uniformly bounded by λ_t≤ C= O(1),



with the constant C given by

    C:=max{2GR,(1/η+1)GR+2G^2R^2μ/η+d^2F^2α/ηδ^2+μ R^2/2αη}

where the constants G, R, and η are as in (as2)-(as4).



Plugging the bounded norm of the one-point gradient estimator (<ref>) into (<ref>), it holds that 
 
    1/μ𝔼[Δ(λ_t)]≤    GR+𝔼[λ_t^⊤𝐠_t(𝐱)]+2μ G^2R^2+d^2 F^2α/δ^2
       +1/2α𝔼[𝐱-𝐱̂_t^2]-1/2α𝔼[𝐱-𝐱̂_t+1^2]

 where we used the Lipschitz condition on (<ref>); i.e., 
 
    𝔼[f̌_t(𝐱)-f̌_t(𝐱̂_t)]≤ GR.

 
 Selecting the interior point 𝐱=𝐱̃∈ (1-γ) X so that 𝐠_t(𝐱̃)≤ -η1, it follows from (<ref>) that
  
    1/μ𝔼[Δ(λ_t)]≤    GR-η𝔼[λ_t^⊤1]+2μ G^2R^2+d^2F^2α/δ^2
       +1/2α𝔼[𝐱̃-𝐱̂_t^2]-1/2α𝔼[𝐱̃-𝐱̂_t+1^2].

  
Using -ηλ_t^⊤1=-ηλ_t_1≤ -ηλ_t, we arrive at
  
    1/μ𝔼[Δ(λ_t)]≤    GR-η𝔼[λ_t]+2μ G^2R^2+d^2F^2α/δ^2
       +1/2α𝔼[𝐱̃-𝐱̂_t^2]-1/2α𝔼[𝐱̃-𝐱̂_t+1^2].


Now we are ready to show that the norm of the dual variable is uniformly bounded by a constant C that is independent of time; that is, λ_t≤ C, ∀ t.

For 1≤ t≤1/μ, it follows readily that

    λ_t   ≤λ_t-1+μ𝐠_t(𝐱̂_t)+∇^⊤𝐠_t(𝐱̂_t)(𝐱̂_t+1-𝐱̂_t)
       ≤λ_t-1+2μ GR≤λ_1+2μ tGR≤ C

where the last inequality follows from λ_1=0, t≤1/μ, and the definition of C in (<ref>). 

For 1/μ≤ t≤ T, we will prove the claim by contradiction. Assume T_0 is the first slot for which λ_T_0>C. Therefore, we have λ_T_0>C≥λ_T_0-1/μ, which after recalling (<ref>) and the definition of Δ(λ_t), yields

    1/μ∑_t=T_0-1/μ^T_0-1𝔼[Δ(λ_t)]=1/2μ(𝔼[λ_T_0^2-λ_T_0-1/μ^2])>0.

On the other hand however, summing up (<ref>), we obtain 

    1/μ∑_t=T_0-1/μ^T_0-1𝔼[Δ(λ_t)]≤GR/μ-η∑_t=T_0-1/μ^T_0-1𝔼[λ_t]+2G^2R^2
          +d^2F^2α/μδ^2+1/2α𝔼[𝐱̃-𝐱̂_T_0-1/μ^2]-1/2α𝔼[𝐱̃-𝐱̂_T_0^2]
    (a)≤   GR/μ-η∑_t=T_0-1/μ^T_0-1𝔼[λ_t]+2G^2R^2+d^2F^2α/μδ^2+R^2/2α

where (a) uses again the bound 𝐱̃-𝐱̂_T_0-1/μ≤ R.

Note that since λ_T_0>C and λ_T_0-λ_T_0-1≤ 2μ GR, we have that

    λ_T_0-τ>C-2τμ GR.


Combining (<ref>) with (<ref>), we deduce

    1/μ∑_t=T_0-1/μ^T_0-1𝔼[Δ(λ_t)]≤GR/μ-Cη/μ+η GR/μ+2G^2R^2+d^2F^2α/μδ^2+R^2/2α.


Together with (<ref>), recursion (<ref>) implies that

    C<GR/η+GR+2G^2R^2μ/η+d^2F^2α/ηδ^2+μ R^2/2αη

which contradicts the definition of C in (<ref>). 
Hence, there is no T_0 satisfying λ_t≤ C, which implies that λ_t≤ C, ∀ t.





By choosing the stepsizes α=μ= O(T^-3/4), and the parameter δ= O(T^-1/4), it follows that

    C= O(GR/η+GR+2G^2R^2/η T^3/4+d^2F^2/η T^1/4+R^2/2η)= O(1)
	
which completes the proof of the lemma.


Dynamic regret in Theorem 1:
 Recall that 𝐱_t^* is the minimizer of the following time-varying problem (<ref>), and note that (1-γ)𝐱_t^*∈ (1-γ) X.
Hence, plugging (1-γ)𝐱_t^* into (<ref>), we have 
  
    1/μ𝔼[Δ(λ_t)]≤f̌_t((1-γ)𝐱_t^*)-𝔼[f̌_t(𝐱̂_t)]
    
    +   1/2α𝔼[(1-γ)𝐱_t^*-𝐱̂_t^2]-1/2α𝔼[(1-γ)𝐱_t^*-𝐱̂_t+1^2]
    
    +   𝔼[λ_t^⊤𝐠_t((1-γ)𝐱_t^*)]+α/δ^2d^2F^2+2μ G^2R^2.

 
From the Lipschitz condition, we can bound the inner product in (<ref>) by 

    𝔼[λ_t^⊤𝐠_t((1-γ)𝐱_t^*)]
    ≤   𝔼[λ_t^⊤(𝐠_t(𝐱_t^*)+γ GR·1)](a)≤γ GR 𝔼[λ_t](b)≤γ GRλ̅

where (a) follows from λ_t^⊤𝐠_t(𝐱_t^*)≤ 0 since 𝐠_t(𝐱_t^*)≤0, and λ_t≥0; and (b) uses the upper bound of λ̅:=max_tλ_t.
The two distance terms in (<ref>) can be bounded by
   
    (1-γ)𝐱^*_t   -𝐱̂_t^2-(1-γ)𝐱^*_t-𝐱̂_t+1^2
    
           = (1-γ)𝐱^*_t   -𝐱̂_t^2-(1-γ)𝐱^*_t-1-𝐱̂_t^2
       +(1-γ)𝐱^*_t-1-𝐱̂_t^2-(1-γ)𝐱^*_t-𝐱̂_t+1^2
    
            = (1-γ)𝐱^*_t   -𝐱^*_t-1(1-γ)(𝐱^*_t+𝐱^*_t-1)-2𝐱̂_t
    
            +(1   -γ)𝐱^*_t-1-𝐱̂_t^2-(1-γ)𝐱^*_t-𝐱̂_t+1^2.


   
   Using the triangle inequality, it follows that
   
    (1-γ)(𝐱^*_t+𝐱^*_t-1)-2𝐱̂_t
    ≤   (1-γ)𝐱^*_t-𝐱̂_t+(1-γ)𝐱^*_t-1-𝐱̂_t≤ 2R

which together with (<ref>), implies that
   
    (1-γ)𝐱^*_t   -𝐱̂_t^2-(1-γ)𝐱^*_t-𝐱̂_t+1^2
    ≤2(1 -γ)R   𝐱^*_t-𝐱^*_t-1+(1-γ)𝐱^*_t-1-𝐱̂_t^2
                  -(1-γ)𝐱^*_t-𝐱̂_t+1^2.


      
 Plugging (<ref>) and (<ref>) into (<ref>), and summing up over t=1,…,T, we find
  
    1/2μ(𝔼[λ_T+1^2-λ_1^2])+∑_t=1^T(𝔼[f̌_t(𝐱̂_t)]-f̌_t((1-γ)𝐱^*_t))
    ≤   γ GRλ̅T+∑_t=1^T(1-γ)R/α𝐱^*_t-𝐱^*_t-1+2μ G^2R^2T+α d^2F^2 T/δ^2
    +   1/2α(𝔼[(1-γ)𝐱^*_0-𝐱̂_1^2]-𝔼[(1-γ)𝐱^*_T-𝐱̂_T+1^2])
    (c)≤    γ GRλ̅T+R/αV(𝐱_1:T^*)+2μ G^2R^2T+R^2/2α+α d^2F^2 T/δ^2

 where (c) uses (1-γ)𝐱^*_0-𝐱̂_1≤𝐱^*_0-𝐱̂_1≤ R, and (1-γ)𝐱^*_T-𝐱̂_T+1^2≥ 0, and the accumulated variation of the per-slot minimizers defined as V(𝐱_1:T^*):=∑_t=1^T 𝐱^*_t-𝐱^*_t-1.

Since 𝔼[λ_T+1^2]≥ 0, initializing the dual variable with λ_1=0, and rearranging (<ref>), we have that
 
    ∑_t=1^T(𝔼[f̌_t(𝐱̂_t)]-f̌_t((1-γ)𝐱^*_t))
    ≤   γ GRλ̅T+R/αV(𝐱_1:T^*)+2μ G^2R^2T+R^2/2α+α d^2F^2 T/δ^2.




   
 The iterates {𝐱̂_t} in this bound are not the actual decisions taken by the learner.
   To obtain the regret bound, our next step is to decompose the regret as
    
    ∑_t=1^T(   𝔼[f_t(𝐱_1,t)]-f_t(𝐱_t^*))
        =∑_t=1^T(𝔼[f_t(𝐱_1,t)]-𝔼[f̌_t(𝐱_1,t)]_U_1
       +𝔼[f̌_t(𝐱_1,t)]-𝔼[f̌_t(𝐱̂_t)]_U_2+𝔼[f̌_t(𝐱̂_t)]-f̌_t((1-γ)𝐱_t^*))_U_3
       +f̌_t((1-γ)𝐱_t^*))-f̌_t(𝐱_t^*)_U_4+f̌_t(𝐱_t^*)-f_t(𝐱_t^*)_U_5).

We next bound each under-braced, starting with
  
    U_1=   𝔼[f_t(𝐱_1,t)-𝔼_𝐯[f_t(𝐱_1,t+δ𝐯_t)]]
    (d)≤   𝔼[f_t(𝐱_1,t)-f_t(𝔼_𝐯[𝐱_1,t+δ𝐯_t])](e)=0

 where (d) uses Jensen's inequality, and (e) follows from 𝔼_𝐯[δ𝐯_t]=0 since 𝐯_t is drawn from 𝔹:={𝐯:𝐯≤ 1}.
 
 Regarding the second term, it follows that   





 
    U_2=𝔼[f̌_t(𝐱̂_t+δ𝐮_t)-f̌_t(𝐱̂_t)]
        	(f)≤𝔼[Gδ𝐮_t]=δ G

where (f) uses the Lipschitz condition of f̌_t(𝐱).
The third term U_3 has been already bounded as in (<ref>). 

Using the Lipschitz condition of f̌_t(𝐱), we can further bound the fourth term
   
    U_4=f̌_t((1-γ)𝐱_t^*))-f̌_t(𝐱_t^*)≤γ GR

   and likewise for the last term for which
 
    U_5=𝔼_𝐯[f_t(𝐱_t^*+δ𝐯_t)]-f_t(𝐱_t^*)
     		≤𝔼_𝐯[Gδ𝐯_t]≤δ G.

   
Plugging (<ref>) and (<ref>)-(<ref>) into (<ref>), we arrive that
 
    ∑_t=1^T(𝔼[f_t(𝐱_1,t)]-f_t(𝐱_t^*)) ≤R/αV(𝐱_1:T^*)   +R^2/2α+d^2G^2R^2α T/δ^2
    
      +γ GRT(1+λ̅)+2μ G^2R^2T   +2Gδ T.

Upon choosing α=μ= O(T^-3/4), and δ= O(T^-1/4) along with γ=δ/r, it follows that (cf. Lemma <ref>)
 
    Reg^ d_T= O(RV(𝐱_1:T^*)T^3/4+GRCT^3/4+2G^2R^2T^1/4+d^2G^2R^2T^3/4)

from which the proof is complete.


Dynamic fit in Theorem 1:
To bound the dynamic fit, recall that the constraint violations in (<ref>) depend on the magnitude of the dual variable and the difference of two consecutive primal iterates.
 The distance between iterates 𝐱̂_t and 𝐱̂_t+1 can be bounded as

    𝐱̂_t+1-𝐱̂_t(a)≤α∇̂_𝐱^1 L_t(𝐱̂_t,λ_t)
    (b)≤   d/δ|f_t(𝐱̂_t+δ𝐮_t)|+∇𝐠_t(𝐱̂_t)λ_t(c)≤α dF/δ+α Gλ_t

where (a) uses the non-expansive property of the projection operator, (b) relies on (<ref>) and the Cauchy-Schwarz's inequality; and (c) uses the bounds in (as2).

On the other hand, using the Lipschitz continuity of 𝐠_t(𝐱) and (<ref>), it follows that

    ∑_t=1^T 𝐠_t(𝐱_1,t)≤∑_t=1^T 𝐠_t(𝐱̂_t)+δ GT1
    ≤   λ_T+1/μ+G^2T1/2β+β/2∑_t=1^T𝐱̂_t+1-𝐱̂_t^21+δ GT1
    (d)≤   λ_T+1/μ+G^2T1/2β+β T(α^2 d^2F^2/δ^2+α^2 G^2λ̅^2)1+δ GT1

where (d) uses (<ref>), and the fact that (a+b)^2≤ 2(a^2+b^2). 
Taking [·]^+ and · on both sides of (<ref>), we have (cf. (<ref>))

    Fit^ d_T≤λ̅/μ   +G^2√(N)T/2β+δ G√(N)T
       +β√(N) T(α^2 d^2F^2 /δ^2+α^2 G^2λ̅^2)

which establishes (<ref>).
Upon selecting α= O(T^-3/4), and δ= O(T^-1/4), we find from Lemma <ref> that λ̅≤ C= O(1). Together with μ= O(T^-3/4) and β= O(T^1/4), it holds from (<ref>) that

    Fit^ d_T≤    CT^3/4+G^2√(N)T^3/4/2+G√(N)T^3/4
       +√(N) T^5/4(d^2F^2 T^-1+T^-3/2 G^2C^2)= O(T^3/4)

which completes the proof of (<ref>).



 §.§ Proof of Theorem <ref>

Similar to the proof of Theorem <ref>, feasibility of actions {𝐱_1,t,𝐱_2,t} readily follows from Lemma <ref>; hence, 𝐱_1,t,𝐱_2,t∈ X, ∀ t. 
To prove the dynamic regret and fit bounds in this setup, the following result is needed.
 
	For the BanSaP recursion (<ref>), (<ref>), and (<ref>), selecting α=μ= O(T^-1/2) ensures that the dual iterates are uniformly bounded by λ_t≤ C= O(1), with the constant C given by

    C:=max{2GR,(1/η+1)GR+2G^2R^2μ/η+d^2G^2α/η+μ R^2/2αη}

where the constants G, R, and η are as in (as2)-(as4).



It follows steps similar to those used to prove Lemma <ref>.


Similar to Lemma <ref>, Lemma <ref> asserts that the dual variable in BanSaP with two-point bandit feedback is also uniformly bounded from above. 
Now, we are ready to prove the regret bound in Theorem <ref>.

Dynamic regret in Theorem 2:
   To obtain the regret bound in the case of two-point feedback, our first step is to connect the regret with the optimality loss induced by the sequence of iterates {𝐱̂_t}, given by 
       
    1/2∑_t=1^T(𝔼[f_t(𝐱_1,t)]+𝔼[f_t(𝐱_2,t)])-∑_t=1^Tf_t(𝐱_t^*)
    
        (a)≤   1/2∑_t=1^T(𝔼[f_t(𝐱̂_t)]+δ G+𝔼[f_t(𝐱̂_t)]+δ G)-∑_t=1^Tf_t(𝐱_t^*)
    
        =   ∑_t=1^T(𝔼[f_t(𝐱̂_t)]-f_t(𝐱_t^*))+δ G

     where (a) follows from the Lipschitz condition in (as2).

The LHS of (<ref>) can be further decomposed as
    
    ∑_t=1^T(𝔼[f_t(𝐱̂_t)]-f_t(𝐱_t^*))
    
        =   ∑_t=1^T(𝔼[f_t(𝐱̂_t)]-𝔼[f̌_t(𝐱̂_t)]_U_1+𝔼[f̌_t(𝐱̂_t)]-f̌_t((1-γ)𝐱_t^*))_U_2
            +f̌_t((1-γ)𝐱_t^*))-f̌_t(𝐱_t^*)_U_3+f̌_t(𝐱_t^*)-f_t(𝐱_t^*)_U_4).

    
For the first term, following the steps in (<ref>), we have that
  
    U_1≤   𝔼[f_t(𝐱̂_t)-𝔼_𝐯[f_t(𝐱̂_t+δ𝐯_t)]]
    ≤   𝔼[f_t(𝐱̂_t)-f_t(𝔼_𝐯[𝐱̂+δ𝐯_t])]≤0.

   
Similar to (<ref>), we have for the case of two-point feedback
 
    ∑_t=1^TU_2   =∑_t=1^T(𝔼[f̌_t(𝐱̂_t)]-f̌_t((1-γ)𝐱^*_t))
       ≤γ GRλ̅T+R/αV(𝐱_1:T^*)+2μ G^2R^2T+R^2/2α+α d^2G^2 T.

  
Using the Lipschitz condition of f̌_t(𝐱), we can bound the third term
   
    U_3=f̌_t((1-γ)𝐱_t^*))-f̌_t(𝐱_t^*)≤γ GR

   and likewise for the last term, it follows from the Lipschitz condition of f_t(𝐱) that
 
    U_4=𝔼_𝐯[f_t(𝐱_t^*+δ𝐯_t)]-f_t(𝐱_t^*)≤δ G.


Plugging (<ref>)-(<ref>) into (<ref>), we arrive at
       
    1/2∑_t=1^T(𝔼[f_t(𝐱_1,t)]+𝔼[f_t(𝐱_2,t)])-∑_t=1^Tf_t(𝐱_t^*) ≤R/αV(𝐱_1:T^*)
       +R^2/2α+2μ G^2R^2T+α d^2G^2 T+γ GRT(1+λ̅)+2δ GT.

     
Upon choosing α=μ= O(T^-1/2), and δ= O(T^-1) along with γ=δ/r, it follows that (ignoring constant terms)
 
    Reg^ d_T= O(RV(𝐱_1:T^*)T^1/2+1/2R^2T^1/2+2G^2R^2T^1/2+d^2G^2T^1/2)

where we used the upper bound of dual variables in Lemma <ref>. This completes the proof of (<ref>).

Dynamic fit in Theorem 2:
To derive the bound on dynamic fit, recall that the constraint violations in (<ref>) depend on the magnitude of the dual variable as well as on the difference of two consecutive primal iterates.
 The distance between iterates 𝐱_t and 𝐱̂_t+1 can be bounded by

    𝐱̂_t+1-𝐱̂_t(a)≤α∇̂_𝐱^2 L_t(𝐱̂_t,λ_t)
    (b)≤   ∇̂^2 f_t(𝐱̂_t)+∇𝐠_t(𝐱̂_t)λ_t(c)≤α dG+α G λ̅

where (a) uses the non-expansive property of the projection operator, (b) applies the Cauchy-Schwarz inequality, and (c) relies on the bounds in (as2).

On the other hand, using the Lipschitz continuity of 𝐠_t(𝐱) and (<ref>), we have

    1/2∑_t=1^T (𝐠_t(𝐱_1,t)+𝐠_t(𝐱_2,t))≤∑_t=1^T 𝐠_t(𝐱̂_t)+δ GT1
    ≤   λ_T+1/μ+G^2T1/2β+β/2∑_t=1^T𝐱̂_t+1-𝐱̂_t^21+δ GT1
    (c)≤   λ_T+1/μ+G^2T1/2β+β T(α^2 d^2G^2+α^2 G^2λ̅^2)1+δ GT1

where (c) uses (<ref>), and the fact that (a+b)^2≤ 2(a^2+b^2). 

In this case, if we take [·]^+ and then · on both sides of (<ref>), and further choose α=μ= O(T^-1/2), δ=T^-1, and β= O(T^1/2), we arrive at

    Fit^ d_T≤   λ_T+1/μ+G^2N^1/2T/2β+β N^1/2T(α^2 d^2G^2+α^2 G^2λ̅^2)
    
    =   CT^1/2+N^1/2T^1/2G^2(1/2+d^2+C^2)= O(T^1/2)

where we used the bound on dual variables in Lemma <ref>. This completes also the proof of (<ref>), and also that of Theorem <ref>.



