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

zbMATH Open1497.68582arXiv1604.02218MaRDI QIDQ4969032FDOQ4969032

Authors:

Publication date: 5 October 2020

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(sqrtT)$ 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^{maxheta,1-heta})$ regret and $O(T^{1-heta/2})$ constraint violations where $hetain(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(sqrtT)$ regret bound with $O(1)$ constraint violations.

Full work available at URL: https://arxiv.org/abs/1604.02218

Recommendations

• Trading regret for efficiency: online convex optimization with long term constraints
• Regrets of proximal method of multipliers for online non-convex optimization with long term constraints
• Logarithmic Regret Algorithms for Online Convex Optimization
• Logarithmic regret algorithms for online convex optimization
• Regret bounded by gradual variation for online convex optimization

zbMATH Keywords

regret boundslow complexityonline convex optimizationconstraint violation boundslong-term constraints

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Prediction, Learning, and Games
• Online learning and online convex optimization
• A tutorial on geometric programming
• Title not available (Why is that?)
• Logarithmic Regret Algorithms for Online Convex Optimization
• Stochastic network optimization with application to communication and queueing systems
• Online submodular minimization
• Trading regret for efficiency: online convex optimization with long term constraints
• A simple parallel algorithm with an \(O(1/t)\) convergence rate for general convex programs
• Maximally representative allocations for guaranteed delivery advertising campaigns

Cited In (8)

• Distributed inertial online game algorithm for tracking generalized Nash equilibria
• Online composite optimization with time-varying regularizers
• Regret analysis of an online majorized semi-proximal ADMM for online composite optimization
• Online Learning with Constraints
• Trading regret for efficiency: online convex optimization with long term constraints
• Regrets of proximal method of multipliers for online non-convex optimization with long term constraints
• Dynamic online convex optimization with long-term constraints via virtual queue
• An online convex optimization-based framework for convex bilevel optimization

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)