A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints

Abstract

This paper considers online convex optimization over a complicated constraint set, which typically consists of multiple functional constraints and a set constraint. The conventional online projection algorithm (Zinkevich, 2003) can be difficult to implement due to the potentially high computation complexity of the projection operation. In this paper, we relax the functional constraints by allowing them to be violated at each round but still requiring them to be satisfied in the long term. This type of relaxed online convex optimization (with long term constraints) was first considered in Mahdavi et al. (2012). That prior work proposes an algorithm to achieve $O(\sqrt{T})$ regret and $O(T^{3/4})$ constraint violations for general problems and another algorithm to achieve an $O(T^{2/3})$ bound for both regret and constraint violations when the constraint set can be described by a finite number of linear constraints. A recent extension in \citet{Jenatton16ICML} can achieve $O(T^{\max \{\theta ,1-\theta \}})$ regret and $O(T^{1-\theta /2})$ constraint violations where $\theta \in (0,1)$. The current paper proposes a new simple algorithm that yields improved performance in comparison to prior works. The new algorithm achieves an $O(\sqrt{T})$ regret bound with $O(1)$ constraint violations.

This paper is published in JMLR. The title is changed to emphasize that constraint violations attained by our algorithm is independent of the number of rounds $T$. In this version, we also analyze the regret and constraint violations for our algorithm without requiring the Slater condition

References in corpus (1)

• Projection-free Online Learning

Cited by in corpus (10)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Online Convex Optimization with Time-Varying Constraints
• Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization
• Online Convex Optimization with Stochastic Constraints
• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints
• Safe Learning under Uncertain Objectives and Constraints
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints
• Online Distributed Coordinated Precoding for Virtualized MIMO Networks with Delayed CSI
• Online Learning in Weakly Coupled Markov Decision Processes: A Convergence Time Study