Distributed Constrained Online Learning

Abstract

In this paper, we consider groups of agents in a network that select actions in order to satisfy a set of constraints that vary arbitrarily over time and minimize a time-varying function of which they have only local observations. The selection of actions, also called a strategy, is causal and decentralized, i.e., the dynamical system that determines the actions of a given agent depends only on the constraints at the current time and on its own actions and those of its neighbors. To determine such a strategy, we propose a decentralized saddle point algorithm and show that the corresponding global fit and regret are bounded by functions of the order of $\sqrt{T}$. Specifically, we define the global fit of a strategy as a vector that integrates over time the global constraint violations as seen by a given node. The fit is a performance loss associated with online operation as opposed to offline clairvoyant operation which can always select an action if one exists, that satisfies the constraints at all times. If this fit grows sublinearly with the time horizon it suggests that the strategy approaches the feasible set of actions. Likewise, we define the regret of a strategy as the difference between its accumulated cost and that of the best fixed action that one could select knowing beforehand the time evolution of the objective function. Numerical examples support the theoretical conclusions.

References in corpus (8)

• Constrained Consensus
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Distributed Robust Multi-Cell Coordinated Beamforming with Imperfect CSI: An ADMM Approach
• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• A Class of Prediction-Correction Methods for Time-Varying Convex Optimization
• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• Adaptive Penalty-Based Distributed Stochastic Convex Optimization
• Decentralized Online Learning with Kernels

Cited by in corpus (4)

• Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints
• Linear Regression with Distributed Learning: A Generalization Error Perspective
• Distributed Online Optimization for Multi-Agent Networks with Coupled Inequality Constraints
• Distributed Online Convex Optimization with Improved Dynamic Regret