PaperlayerView exact revision on arXiv

Source-linked AI summary

An Online Convex Optimization Approach to Dynamic Network Resource Allocation

Tianyi Chen, Qing Ling, Georgios B. Giannakis

arXiv:1701.03974v2eess.SYcs.LGmath.OCstat.ML

TL;DR

The paper addresses OCO with adversarial costs and constraints revealed after decisions, where violations are tolerated instantaneously but must be controlled over time. It develops MOSP and proves simultaneous sub-linear dynamic regret and fit under sub-linear variation of minimizers and constraints, then evaluates MOSP for dynamic network resource allocation against stochastic dual gradient methods. Numerical experiments report performance gains for MOSP in the examined scenarios.

  • Problem

    The paper addresses OCO with adversarial, time-varying constraints revealed after actions, using dynamic regret and dynamic fit instead of a solely static benchmark.

  • Method

    MOSP uses modified primal descent and dual ascent for online optimization with time-varying costs and long-term constraints.

  • Results

    MOSP simultaneously achieves sub-linear dynamic regret and fit under sub-linear accumulated variation, and numerical experiments report gains over stochastic dual gradient methods.

  • Takeaways & Limitations

    MOSP provides finite-sample online performance analysis and remains applicable to non-stationary network resource allocation without probabilistic assumptions.

Abstract

from arXiv · show

Existing approaches to online convex optimization (OCO) make sequential one-slot-ahead decisions, which lead to (possibly adversarial) losses that drive subsequent decision iterates. Their performance is evaluated by the so-called regret that measures the difference of losses between the online solution and the best yet fixed overall solution in hindsight. The present paper deals with online convex optimization involving adversarial loss functions and adversarial constraints, where the constraints are revealed after making decisions, and can be tolerable to instantaneous violations but must be satisfied in the long term. Performance of an online algorithm in this setting is assessed by: i) the difference of its losses relative to the best dynamic solution with one-slot-ahead information of the loss function and the constraint (that is here termed dynamic regret); and, ii) the accumulated amount of constraint violations (that is here termed dynamic fit). In this context, a modified online saddle-point (MOSP) scheme is developed, and proved to simultaneously yield sub-linear dynamic regret and fit, provided that the accumulated variations of per-slot minimizers and constraints are sub-linearly growing with time. MOSP is also applied to the dynamic network resource allocation task, and it is compared with the well-known stochastic dual gradient method. Under various scenarios, numerical experiments demonstrate the performance gain of MOSP relative to the state-of-the-art.

I. INTRODUCTION

The paper extends online convex optimization to adversarial, time-varying constraints that are revealed after decisions and need only hold on average. It introduces MOSP, establishes sub-linear dynamic regret and fit under sub-linear variation, and applies the method to dynamic network resource allocation.

  • Motivation: Static regret can be inadequate when the underlying optimum varies over time, motivating dynamic regret against one-slot-ahead per-slot minimizers.Sub-linear dynamic regret is possible when accumulated cost or minimizer variation grows sub-linearly.
  • Problem formulation: The proposed OCO setting reveals adversarial costs and time-varying constraints after each action, while allowing instantaneous violations if constraints hold on average.Performance is measured by dynamic regret and accumulated constraint violations, termed dynamic fit.
  • Method: MOSP combines a modified primal descent step with dual ascent to address time-varying costs and long-term constraints.The current action minimizes a problem formed from the previous primal iterate and current dual iterate.
  • Application and evaluation: In dynamic network resource allocation, MOSP is compared with stochastic dual gradient methods and evaluated under stationary and non-stationary numerical scenarios.The paper emphasizes operation without probabilistic assumptions and finite-sample analysis for non-stochastic sequences.
  • Theoretical guarantees: MOSP simultaneously achieves sub-linear dynamic regret and fit when accumulated variations of per-slot minimizers and constraints grow sub-linearly.These guarantees imply no-regret performance relative to the dynamic benchmark and average feasibility over the long term.

III. MODIFIED ONLINE SADDLE-POINT (MOSP) METHOD

The paper develops a modified online saddle-point method for the proposed time-varying constrained OCO problem and evaluates it using dynamic regret and fit.

  • MOSP is developed to solve the time-varying constrained OCO problem.
  • The method's performance and feasibility are analyzed through dynamic regret and fit.

A. Algorithm development

MOSP combines a modified primal update with a dual ascent update after the learner observes the current cost and constraint.

  • Algorithm development: MOSP forms the online partial Lagrangian using the current cost, time-varying constraint, and dual iterate.
  • Algorithm development: At each slot, the primal decision minimizes a modified optimization problem based on the previous primal iterate and current dual iterate.
  • Algorithm development: The primal update uses the previous objective gradient and a proximal term controlled by positive stepsize α.
  • Algorithm development: After making the decision, the learner observes the current cost and constraint before updating the dual variable.
  • Algorithm development: The dual update ascends using the current constraint violation, with positive stepsize µ and gradient ∇λL_t(x_t, λ_t) = g_t(x_t).
  • Algorithm development: Unlike a classical gradient step for nonlinear constraints, MOSP minimizes the exact constraint violation; for linear constraints, it reduces to earlier approaches.

B. Performance analysis

MOSP’s performance analysis establishes bounds on dynamic fit and dynamic regret under convexity, boundedness, and a Slater-type condition. With suitably chosen stepsizes and sub-linearly growing environmental variation, both metrics grow sub-linearly.

  • The analysis assumes convex costs and constraints, bounded gradients and constraints, a bounded action set, and a common strictly feasible point.The common interior point is the Slater condition used to guarantee bounded Lagrange multipliers.
  • The dynamic-fit bound depends on the dual stepsize and constraint variation, with Fit^d_T of order O(1/µ) for fixed primal stepsize α.A larger dual stepsize improves long-term constraint satisfaction, while smaller constraint variation reduces dynamic fit.
  • The dynamic-regret bound depends on accumulated minimizer and constraint variations together with the primal and dual stepsizes.Theorem 2 makes these dependencies explicit, while the surrounding analysis shows the bound can be small under slowly varying environments.
  • MOSP achieves sub-linear dynamic fit and dynamic regret when accumulated variations of per-slot minimizers and constraints grow sub-linearly.The result is stated under Assumptions 1–4 and zero-initialized dual variables.
  • Choosing α = µ = O(T^-1/3) yields sub-linear dynamic fit and dynamic regret under the stated variation conditions.A later corollary allows stepsizes to be matched to a known environmental variability rate.
  • When environmental variation follows a faster rate, larger and more slowly decaying stepsizes can better track potential changes.This stepsize guidance is presented for settings with a-priori knowledge of temporal variability.

C. Beyond dynamic regret

The paper distinguishes the dynamic benchmark from the offline optimum and analyzes the resulting optimality gap through dual-function variation. This extends performance evaluation beyond dynamic regret while preserving the information distinction between online and offline solutions.

  • The dynamic benchmark uses one-slot-ahead information, whereas the offline optimum requires cost and constraint information over the entire horizon.The offline solution is therefore unavailable to an online learner at decision time.
  • MOSP satisfies long-term constraints on average, while the offline solution exactly satisfies them; offline costs provide a benchmark for evaluating online decisions.The paper presents this offline comparison as an accurate performance measure through OptGap^off_T.
  • The optimality gap decomposes into dynamic regret and the difference between per-slot minimizers and offline optimal solutions.The second term is denoted U2 in the decomposition.
  • The paper bounds the second component through accumulated variation of the dual functions associated with instantaneous problems.Strong duality under Slater’s condition enables this dual-domain representation.
  • Restarting dual variables across sub-horizons can improve the optimality-gap bound when total dual-function variation is known and sub-linear.The resulting two summands are sub-linear when the dynamic-regret condition also holds on each sub-horizon.

IV. APPLICATION TO NETWORK RESOURCE ALLOCATION

The paper applies the OCO framework and MOSP solver to dynamic network resource allocation, using numerical experiments to demonstrate the solver’s merits.

  • MOSP is applied to the network resource allocation problem within the OCO framework and evaluated numerically.

A. Online network resource allocation

The network application models routing and data-center service over a cloud graph with time-varying workloads and costs. Queue dynamics are relaxed into long-term flow constraints so MOSP can operate online and in decentralized form.

  • The cloud network is represented by a directed graph containing mapping nodes and data centers connected by allocation links.The allocation vector includes link bandwidths and data-center service amounts.
  • Each slot combines exogenous workload arrivals with routed workload, producing queue updates that enforce nonnegative buffered workloads.The queue recursion is qt+1 = [qt + Axt + bt]+.
  • Bandwidth and data-center capability limits define the convex action set X := {0 ≤ x ≤ x̄}.The vector x̄ collects link bandwidth and data-center resource capacities.
  • The time-varying instantaneous cost aggregates data-center power costs and link bandwidth costs while incorporating changing network parameters.The cost is written as ft(xt) := f(xt; θt).
  • The original optimization is time-coupled because serving all workloads requires queue evolution and terminal clearing, making future arrivals and costs necessary for offline solution.The paper reformulates this problem because it is challenging to solve without future information.
  • Relaxing queue recursion yields long-term flow conservation, Axt + bt ≤ 0, allowing MOSP to provide online performance and feasibility guarantees.The primal update uses projection onto X, while the dual update tracks the relaxed constraint dynamics.
  • Distributed MOSP lets each mapping node or data center update outgoing allocations and exchange multipliers only with one-hop neighbors.The distributed procedure is summarized in Algorithm 2.

B. Revisiting stochastic dual (sub)gradient

The stochastic dual gradient (SDG) method addresses stationary expected-cost resource allocation by observing each realization before acting, whereas the OCO setting makes decisions without current cost and constraint information.

  • Stochastic formulation: Stochastic resource allocation minimizes limiting average expected cost subject to a stability constraint, unlike OCO’s observed-cost objective.The stochastic formulation couples decisions and queues over an infinite horizon, making it generally intractable.
  • Stochastic formulation: Prior work uses a stationary relaxation that replaces time-coupling constraints with a limiting average constraint, but unknown distributions make the expectations challenging to evaluate.Even with a joint distribution, computing expectations may not scale with the dimensionality of the random vector.
  • SDG method: SDG observes ξ_t, updates dual variables by stochastic dual gradients, and obtains each primal allocation by solving one convex subproblem per slot.Its dual update uses stepsize µ, while the primal subproblem determines x_t.
  • SDG guarantees: O(µ)-optimality is paired with queue lengths O(1/µ), creating a cost-delay trade-off as the stepsize changes.Reducing the optimality gap increases the average network delay.
  • Comparison with MOSP: SDG’s stochastic optimality relies on stationarity, while MOSP makes decisions without current ξ_t and supports finite-sample analysis under non-stochastic, potentially adversarial costs and constraints.MOSP uses projected primal gradient descent and dual gradient ascent, whereas SDG generally solves a convex program each slot.

C. Numerical experiments

The experiments evaluate MOSP and online dual gradient (ODG) in dynamic network resource allocation under stationary and non-stationary scenarios. MOSP generally achieves lower cost and regret, with competitive dynamic fit.

  • Setup: The experiments use a network with J = 10 mapping nodes and K = 10 data centers, comparing MOSP, ODG, per-slot minimizers, and an offline optimum.The horizon is T = 500, with specified α and µ stepsizes; ODG uses prior-slot prices and demands for online fairness.
  • Case 1: Case 1 uses independently drawn time-varying prices and demands, representing i.i.d. costs and constraints.Prices are uniformly distributed over, while workload arrivals are uniformly distributed over [50, 150].
  • Case 1: In Case 1, MOSP converges to lower time-average cost and grows dynamic regret much more slowly than ODG.MOSP’s cost is slightly higher than both the per-slot and offline optimal solutions.
  • Case 1: In Case 1, ODG with µ_ODG = 1 has smaller dynamic fit than µ_ODG = 0.5 and fit similar to MOSP, while increasing µ_ODG improves fit but degrades dynamic regret.MOSP is favorable because its regret is much smaller at comparable fit to ODG with µ_ODG = 1.
  • Case 2: In Case 2, MOSP has lower time-average cost than both ODG and the per-slot optimum, and its dynamic regret is similarly lower.The difference between per-slot-minimizer and offline costs is no longer small under non-stationarity.
  • Case 2: In Case 2, both ODG and MOSP have finite dynamic fits, with MOSP’s fit smaller than ODG with µ_ODG = 0.5 and comparable to ODG with µ_ODG = 1.The reported results therefore show MOSP outperforming ODG in both dynamic regret and fit in the non-stationary case.

V. CONCLUDING REMARKS

The paper extends OCO to adversarial costs and constraints revealed after action selection, allowing instantaneous violations while requiring long-term feasibility. MOSP achieves sub-linear dynamic regret and fit under sub-linear environmental variation and outperforms alternatives numerically.

  • Concluding remarks: The framework evaluates online decisions against a one-slot-ahead dynamic benchmark using dynamic regret and accumulated dynamic fit.Constraints may be violated instantaneously but must be satisfied on average.
  • Concluding remarks: MOSP simultaneously achieves sub-linear dynamic regret and fit when accumulated variations of per-slot minimizers and adversarial constraints grow sub-linearly.This guarantee applies under the paper’s standard assumptions.
  • Concluding remarks: The framework broadens OCO applicability to dynamic network resource allocation and online demand response in smart grids.Numerical tests report that MOSP outperforms state-of-the-art alternatives under different scenarios.

APPENDIX

The appendix establishes bounds needed for MOSP’s theoretical analysis, including dual-variable control and inequalities based on projection, bounded gradients, and constraint variation.

  • Dual-drift analysis: The proof begins by bounding the variation of the dual variable for the MOSP recursion through a per-slot dual-drift lemma.The drift is analyzed by squaring the dual update and rearranging terms.
  • Regret analysis: The dynamic-regret proof generalizes an earlier static-regret argument to time-varying constraints and a dynamic benchmark.It uses the primal iterate defined as the optimizer of MOSP’s per-slot update problem.
  • Regret analysis: The analysis bounds primal-update terms using projection non-expansiveness, an interior feasible point, and bounded gradients and iterates.The cited steps invoke Cauchy-Schwarz and the diameter and gradient bounds from the assumptions.
  • Constraint variation: Constraint-norm bounds and the maximum variation of the constraints control additional terms in the dual-drift inequality.These bounds feed into the lemma used by the main theorems.
  • Dual-variable bound: A contradiction argument proves a uniform upper bound on the dual iterates, starting from λ_1 = 0 and using negative drift beyond the proposed bound.The resulting bound is then used to control cumulative constraint violations.

B. Proof of Theorem 2

The proof derives a per-slot primal–dual inequality for the MOSP updates and sums it over time to bound dynamic regret. Strong convexity, convexity, feasibility, gradient bounds, dual drift, compactness, and constraint variation control the resulting terms.

  • Primal update: The primal iterate x_t+1 is defined as the minimizer of the per-slot optimization problem in (8).
  • Per-slot bound: Strong convexity and convexity establish the key per-slot inequalities used to relate MOSP updates to the per-slot optimal solution.
  • Parameter choice: Choosing η = 1/α cancels the η/2 − 1/(2α) term in the bound.
  • Dual terms: Dual drift, nonnegative multipliers, bounded gradients, and constraint variation bound the accumulated dual terms.
  • Accumulation: Summing the per-slot inequality and applying the definitions of dynamic regret and accumulated variations yields the theorem’s dynamic-regret bound.
  • Boundary terms: Compactness of X and nonnegative squared dual norms complete the remaining boundary-term estimates, including the initialization λ1 = 0.
Loading 1701.03974v2…