Delay-Tolerant Constrained OCO with Application to Network Resource Allocation

• URL: http://arxiv.org/abs/2105.04005v1
• Date: Sun, 9 May 2021 19:32:33 GMT
• Title: Delay-Tolerant Constrained OCO with Application to Network Resource Allocation
• Authors: Juncheng Wang, Ben Liang, Min Dong, Gary Boudreau, and Hatem Abou-zeid
• Abstract summary: We consider online convex optimization (OCO) with multi-slot feedback delay. An agent makes a sequence of online decisions to minimize the accumulation of time-varying convex loss functions. We propose Delay-Tolerant Constrained-OCO, which uses a novel constraint penalty with double regularization to tackle the asynchrony between information feedback and decision updates.
• Score: 44.67787270821051
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online convex optimization (OCO) with multi-slot feedback delay, where an agent makes a sequence of online decisions to minimize the accumulation of time-varying convex loss functions, subject to short-term and long-term constraints that are possibly time-varying. The current convex loss function and the long-term constraint function are revealed to the agent only after the decision is made, and they may be delayed for multiple time slots. Existing work on OCO under this general setting has focused on the static regret, which measures the gap of losses between the online decision sequence and an offline benchmark that is fixed over time. In this work, we consider both the static regret and the more practically meaningful dynamic regret, where the benchmark is a time-varying sequence of per-slot optimizers. We propose an efficient algorithm, termed Delay-Tolerant Constrained-OCO (DTC-OCO), which uses a novel constraint penalty with double regularization to tackle the asynchrony between information feedback and decision updates. We derive upper bounds on its dynamic regret, static regret, and constraint violation, proving them to be sublinear under mild conditions. We further apply DTC-OCO to a general network resource allocation problem, which arises in many systems such as data networks and cloud computing. Simulation results demonstrate substantial performance gain of DTC-OCO over the known best alternative.

Related papers

• Client Orchestration and Cost-Efficient Joint Optimization for NOMA-Enabled Hierarchical Federated Learning [55.49099125128281]
  We propose a non-orthogonal multiple access (NOMA) enabled HFL system under semi-synchronous cloud model aggregation. We show that the proposed scheme outperforms the considered benchmarks regarding HFL performance improvement and total cost reduction.
  arXiv  Detail & Related papers  (2023-11-03T13:34:44Z)
• Learning Spatio-Temporal Aggregations for Large-Scale Capacity Expansion Problems [0.0]
  Capacity Expansion Problems (CEPs) are expensive to solve due to large network sizes, heterogeneous node characteristics, and a large number of operational periods. Here, we propose a novel graph convolutional autoencoder approach for identifytemporal aggregation of a generic CEP with heterogeneous nodes. We show that our approach provides upper bounds that are 33% (resp. 10%) lower those than obtained from benchmark spatial (resp. temporal) aggregation approaches.
  arXiv  Detail & Related papers  (2023-03-16T00:00:52Z)
• Online Convex Optimization with Long Term Constraints for Predictable Sequences [5.964436882344728]
  We study a specific framework of OCO called it OCO with long term constraints. Long term constraints are introduced as an alternative to reduce the complexity of the projection at every update step in online optimization. We show that, with a predictor that can supply the information of the next function in the sequence, our algorithm can achieve an overall regret and constraint violation rate that is strictly less than the rate that is achievable without prediction.
  arXiv  Detail & Related papers  (2022-10-30T03:50:53Z)
• Effective Multi-User Delay-Constrained Scheduling with Deep Recurrent Reinforcement Learning [28.35473469490186]
  Multi-user delay constrained scheduling is important in many real-world applications including wireless communication, live streaming, and cloud computing. We propose a deep reinforcement learning (DRL) algorithm, named Recurrent Softmax Delayed Deep Double Deterministic Policy Gradient ($mathttRSD4$) $mathttRSD4$ guarantees resource and delay constraints by Lagrangian dual and delay-sensitive queues, respectively. It also efficiently tackles partial observability with a memory mechanism enabled by the recurrent neural network (RNN) and introduces user-level decomposition and node-level
  arXiv  Detail & Related papers  (2022-08-30T08:44:15Z)
• Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization [1.662966122370634]
  We consider online convex optimization (OCO) with time-varying loss and constraint functions. We first develop a class of model-based augmented Lagrangian methods (MALM) for time-varying functional constrained OCO. numerical results for several examples of constrained OCO are presented to demonstrate the efficiency of the proposed algorithms.
  arXiv  Detail & Related papers  (2022-05-19T14:03:25Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
  We study the problem of Online Convex Optimization (OCO) with memory, which allows loss functions to depend on past decisions. In this paper, we introduce dynamic policy regret as the performance measure to design algorithms robust to non-stationary environments. We propose a novel algorithm for OCO with memory that provably enjoys an optimal dynamic policy regret in terms of time horizon, non-stationarity measure, and memory length.
  arXiv  Detail & Related papers  (2021-02-07T09:45:15Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• Online Convex Optimization with Binary Constraints [0.04170934882758551]
  We consider online optimization with binary decision variables and convex loss functions. We design a new algorithm, binary online gradient descent (bOGD) and bound its expected dynamic regret. We test the performance of bOGD in several simulations based on demand response.
  arXiv  Detail & Related papers  (2020-05-05T15:09:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.