Online convex optimization for cumulative constraints

Jianjun Yuan, Andrew Lamperski

Research output: Contribution to journalConference articlepeer-review

28 Scopus citations

Abstract

We propose the algorithms for online convex optimization which lead to cumulative squared constraint violations of the form ΣT t=1 ([g(xt)]+)2 = O(T1−β), where β ∈ (0, 1) . Previous literature has focused on long-term constraints of the form TΣt=1 g(xt). There, strictly feasible solutions can cancel out the effects of violated t=1 constraints. In contrast, the new form heavily penalizes large constraint violations and cancellation effects cannot occur. Furthermore, useful bounds on the single step constraint violation [g(xt)]+ are derived. For convex objectives, our regret bounds generalize existing bounds, and for strongly convex objectives we give improved regret bounds. In numerical experiments, we show that our algorithm closely follows the constraint boundary leading to low cumulative violation.

Original languageEnglish (US)
Pages (from-to)6137-6146
Number of pages10
JournalAdvances in Neural Information Processing Systems
Volume2018-December
StatePublished - Jan 1 2018
Event32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada
Duration: Dec 2 2018Dec 8 2018

Fingerprint

Dive into the research topics of 'Online convex optimization for cumulative constraints'. Together they form a unique fingerprint.

Cite this