Bandit Convex Optimization for Scalable and Dynamic IoT Management

I. INTRODUCTION

• Existing offloading methods address static or stochastic settings, while prior dynamic-regret and time-varying-constraint approaches assume known losses or available gradients.These assumptions are difficult in IoT, where user-dissatisfaction losses are hard to model and low-power devices may not support on-the-fly learning tools.Source: §I · p. 1
• BanSaP extends bandit convex optimization to time-varying costs and constraints, with sub-linear dynamic regret and fit when per-slot minimizers vary sub-linearly over time.The framework evaluates performance against the best dynamic benchmark using dynamic regret and fit.Source: §I · p. 2

A. Online learning with constraints under partial feedback

• The proposed setting reveals only queried loss values and makes time-varying constraints available after decisions, so feasibility is required on average rather than at every step.The loss is modeled as inaccessible beyond queried values, while measurable application constraints are revealed after the action.Source: A. Online learning with constraints… · p. 2

B. Motivating setup: mobile fog computing in IoT

• In the fog-computing example, decisions allocate workloads among cloud offloading, neighboring fog nodes, and local processing while minimizing accumulated network delay and serving arrivals over time.Queues buffer workloads not served immediately, matching the long-term constraint setting.Source: B. Motivating setup: mobile fog… · p. 3

A. Online saddle-point approach with gradient feedback

• The full-information saddle-point scheme updates the primal decision using the gradient of the current Lagrangian and projection onto the feasible set.The Lagrangian combines the current loss with the time-varying constraints weighted by their dual variables.Source: A. Online saddle-point approach with… · pp. 3–4
• The dual update uses a first-order approximation of the constraint at the previous primal iterate, a modification identified as critical to later analysis.The update differs from using the constraint value at the current iterate.Source: A. Online saddle-point approach with… · p. 4
• Because the recursion requires loss gradients that may be unknown or costly to obtain, the paper develops BanSaP methods for settings without gradient information.The methods use bandit feedback to extend the online saddle-point approach.Source: A. Online saddle-point approach with… · p. 4

B. BanSaP with one-point partial feedback

• Single-point BanSaP estimates the loss gradient from one randomly perturbed function evaluation and uses that estimate in its primal update.The estimate uses a query at x + δu, where u is sampled from the unit sphere.Source: B. BanSaP with one-point partial… · p. 4
• The one-point action is the perturbed query point, while projection onto a smaller set ensures that this action remains feasible.The learner updates its iterate separately from the point used to evaluate the function.Source: B. BanSaP with one-point partial… · p. 4
• Single-point BanSaP has degraded theoretical and empirical performance relative to the full-information case.Source: C. BanSaP with multipoint partial… · p. 4

C. BanSaP with multipoint partial feedback

• Two-point feedback reduces gradient-estimator variance: its second moment is uniformly bounded, unlike the one-point estimator whose second moment scales inversely with δ.The paper links the one-point estimator's bias-variance tradeoff, absent in the two-point case, to the latter's improved and stable performance.Source: C. BanSaP with multipoint partial… · p. 5
• Multipoint feedback queries the loss around the learning iterate, and simulations are used to validate improved performance at the cost of extra computation.For two-point feedback, the two queries are at opposite perturbations; multiple queries can be collected in mini-slots when losses and constraints remain unchanged.Source: C. BanSaP with multipoint partial… · p. 5

A. Optimality and feasibility metrics

• Dynamic regret benchmarks against per-slot best feasible solutions, while dynamic fit measures accumulated constraint violations.Long-term feasibility allows instantaneous violations to be compensated by later strictly feasible decisions.Source: A. Optimality and feasibility metrics · p. 6
• Sub-linear dynamic regret implies sub-linear static regret, but the converse does not hold.Static regret can use a coarse benchmark whose gap from the best dynamic benchmark is as large as O(T).Source: A. Optimality and feasibility metrics · pp. 5–6

B. Main results

• The analysis assumes convex costs and constraints, bounded costs and gradients, a Slater-type condition, and a bounded action set containing the origin.The paper notes that the bounded-set condition is equivalent to compactness with nonempty interior after an affine transformation.Source: B. Main results · p. 6
• With one-point feedback, BanSaP achieves sub-linear fit and sub-linear dynamic regret when minimizer variation is o(T^1/4).The one-point perturbation parameter δ trades lower estimator bias for higher variance.Source: B. Main results · p. 6
• Two-point feedback permits an arbitrarily small perturbation to reduce estimator bias without increasing variance.The additional function evaluation removes the one-point bias-variance tradeoff described for the gradient estimator.Source: B. Main results · pp. 6–7
• For one-point BanSaP, dynamic fit grows sub-linearly, and dynamic regret is sub-linear when per-slot minimizer variation is sufficiently slow.The text says the result markedly improves Theorem 1 under one-point feedback.Source: B. Main results · pp. 6–7
• For M > 2 feedback points, bounds improve slightly without changing the regret or fit order; the stated bounds do not require prior knowledge of minimizer variation.When its order is known or estimated, stepsizes can be adjusted for tighter bounds; matching stepsizes to faster variation means slower decay.Source: B. Main results · p. 7
• When minimizers are fixed, the static-regret bounds are O(T^3/4) with one-point feedback and O(T^1/2) with two-point feedback.The paper says this improves the regret-versus-fit tradeoff in and matches the best efficient-algorithm regret order in,,.Source: B. Main results · p. 7

V. NUMERICAL TESTS

• The section examines how BanSaP solvers can benefit fog computation offloading.The passage does not report specific experimental results.Source: §V · p. 7

A. BanSaP for fog computation offloading

• The BanSaP solver is customized for online computation offloading with performance and feasibility guarantees.The offloading problem is identified as a special case of the paper’s general formulation.Source: A. BanSaP for fog computation offloading · p. 7
• Closed-form primal updates generate cloud, fog-to-fog, and local-processing decisions for decentralized implementation.The update is specified for cloud offloading, inter-node offloading, and local processing.Source: A. BanSaP for fog computation offloading · p. 7
• With two-point feedback, random-vector components estimate gradients for the offloading and local-processing variables, while each node updates its dual variable.The dual update is described as responding to service residuals by increasing penalties and to over-serving by decreasing them.Source: A. BanSaP for fog computation offloading · p. 8

B. Numerical experiments

• The tests average 500 Monte Carlo realizations; the main setup uses 10 fog nodes and a cloud center, with later sampling tests using five nodes.BanSaP and MOSP stepsizes were manually optimized for similar fit before comparing cost.Source: B. Numerical experiments · p. 8
• Increasing feedback lowers BanSaP fit and cost, with gains diminishing at M≥4; coordinate sampling costs less at M=1, while uniform sampling costs less at M≥2.Uniform-sampling BanSaP with one-point feedback has large initial fit in the low-fit comparison.Source: Figure 3 · p. 8, Figure 4 · p. 8, B. Numerical experiments · pp. 8–9
• For M≥2, BanSaP’s fit and cost are comparable to MOSP; one-point feedback matches fog-only fit at lower cost, while cloud-only trades lower fit for higher cost.Cloud-only has much lower fit because it offloads all demands, but higher average service-latency cost; BanSaP’s one-point cost variance decreases markedly with multiple evaluations.Source: Figure 5 · p. 9, Figure 6 · p. 9, B. Numerical experiments · p. 9
• As network size grows, multi-point BanSaP fit remains comparable to MOSP, while its performance gain becomes more evident; one-point BanSaP costs less than fog-only in all tested settings.One-point BanSaP also has lower average fit than fog-only in most scenarios.Source: Figure 7 · p. 9, Figure 8 · p. 9, B. Numerical experiments · p. 9

VI. CONCLUSIONS AND THE ROAD AHEAD

• BanSaP can achieve sub-linear dynamic regret and fit simultaneously when dynamic solutions vary slowly over time.The conclusion says the regret bounds match those in BCO setups without long-term constraints.Source: §VI · p. 9
• The authors describe these results as a first step; asynchronous BanSaP and predictable dynamic models are future directions.Source: §VI · p. 10

APPENDIX

• The proof generalizes the result in from static regret with full-information gradient feedback to dynamic regret with partial-information bandit feedback.Source: APPENDIX · p. 10

• The one- and two-point estimators are unbiased for the gradient of the smoothed loss, which is convex and Lipschitz under the stated assumptions.The lemmas also establish norm or variance bounds for these estimators.Source: A. Supporting lemmas · pp. 10–12
• Choosing γ = δ/r keeps the perturbed action ˆxt + δut in X when ˆxt lies in (1 − γ)X and rB ⊆ X.Source: A. Supporting lemmas · p. 11
• A separate lemma bounds cumulative constraint violation under the BanSaP recursion, with the dual stepsize μ and constant β entering its bound.Source: A. Supporting lemmas · p. 11
• The BanSaP recursions yield a comparator inequality for x ∈ (1 − γ)X, used to relate primal updates to loss progress.The proof invokes convexity of the smoothed loss and drops a nonnegative squared-distance term.Source: A. Supporting lemmas · pp. 11–12

• With γ = δ/r, the actions are feasible, and the selected parameters keep the dual iterates uniformly bounded by C = O(1).The passages give α = μ = O(T^-3/4) and δ = O(T^-1/4).Source: B. Proof of Theorem 1 · p. 12

Dynamic regret in Theorem 1

• Dynamic regret is bounded by decomposing it into terms involving the iterates, then bounding those terms using Lipschitz continuity and the accumulated variation of per-slot minimizers.Source: B. Proof of Theorem 1 · pp. 12–13

Dynamic fit in Theorem 1

• The fit proof relates constraint violations to the dual-variable magnitude and consecutive primal-iterate distance, then bounds that distance and applies the selected parameter rates.The proof uses the uniform dual bound and concludes the fit bound in (25).Source: B. Proof of Theorem 1 · pp. 13–14

• For the BanSaP recursion (11), (13), and (12), choosing α = μ = O(T^-1/2) keeps dual iterates uniformly bounded by ||λ_t|| ≤ C = O(1); actions x1,t and x2,t remain in X for all t.Source: C. Proof of Theorem 2 · p. 14

Dynamic regret in Theorem 2

• The dynamic-regret proof connects regret to optimality loss along the iterates and bounds the resulting terms using Lipschitz continuity.It concludes the dynamic-regret bound in (26).Source: C. Proof of Theorem 2 · p. 14

Dynamic fit in Theorem 2

• The fit proof bounds constraint violations through dual-variable magnitude and consecutive primal-iterate distance, then uses the uniform dual bound to conclude (28).Source: C. Proof of Theorem 2 · p. 14