Stochastic Averaging for Constrained Optimization with Application to Online Resource Allocation

Abstract

Existing approaches to resource allocation for nowadays stochastic networks are challenged to meet fast convergence and tolerable delay requirements. The present paper leverages online learning advances to facilitate stochastic resource allocation tasks. By recognizing the central role of Lagrange multipliers, the underlying constrained optimization problem is formulated as a machine learning task involving both training and operational modes, with the goal of learning the sought multipliers in a fast and efficient manner. To this end, an order-optimal offline learning approach is developed first for batch training, and it is then generalized to the online setting with a procedure termed learn-and-adapt. The novel resource allocation protocol permeates benefits of stochastic approximation and statistical learning to obtain low-complexity online updates with learning errors close to the statistical accuracy limits, while still preserving adaptation performance, which in the stochastic network optimization context guarantees queue stability. Analysis and simulated tests demonstrate that the proposed data-driven approach improves the delay and convergence performance of existing resource allocation schemes.

References in corpus (4)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Starting Small -- Learning with Adaptive Sample Sizes
• Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy

Cited by in corpus (8)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation
• Learning in Wireless Control Systems over Non-Stationary Channels
• Delay-Tolerant Constrained OCO with Application to Network Resource Allocation
• Modeling and Analysis of Energy Harvesting and Smart Grid-Powered Wireless Communication Networks: A Contemporary Survey
• Learning and Management for Internet-of-Things: Accounting for Adaptivity and Scalability
• A Novel Cryptography-Based Privacy-Preserving Decentralized Optimization Paradigm