A low complexity algorithm with O(T) regret and O(1) constraint violations for online convex optimization with long term constraints

Authors

Publication date 5 October 2020

Full work available at URL https://arxiv.org/abs/1604.02218, https://jmlr.csail.mit.edu/papers/v21/16-494.html

constraint violation bounds long-term constraints low complexity online convex optimization regret bounds

Online algorithms; streaming algorithms (68W27) Convex programming (90C25)

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 (s q r t 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^{m a x h e t a, 1 - h e t a})

regret and

O (T^{1 - h e t a / 2})

constraint violations where

h e t a i n (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 (s q r t T)

regret bound with

O (1)

constraint violations.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: A low complexity algorithm with \(O(\sqrt{T})\) regret and \(O(1)\) constraint violations for online convex optimization with long term constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4969032)