Loading...
Please wait, while we are loading the content...
Similar Documents
O C ] 3 1 M ay 2 01 9 Online Convex Optimization with Perturbed Constraints
| Content Provider | Semantic Scholar |
|---|---|
| Author | Valls, Victor Iosifidis, George Leith, Douglas J. Tassiulas, Leandros |
| Copyright Year | 2019 |
| Abstract | This paper addresses Online Convex Optimization (OCO) problems where the constraints have additive perturbations that (i) vary over time and (ii) are not known at the time to make a decision. Perturbations may not be i.i.d. generated and can be used to model a time-varying budget or commodity in resource allocation problems. The problem is to design a policy that obtains sublinear regret while ensuring that the constraints are satisfied on average. To solve this problem, we present a primal-dual proximal gradient algorithm that has O(T ǫ ∨ T ) regret and O(T ) constraint violation, where ǫ ∈ [0, 1) is a parameter in the learning rate. Our results match the bounds of previous work on OCO with time-varying constraints when ǫ = 1/2; however, we (i) define the regret using a time-varying set of best fixed decisions; (ii) can balance between regret and constraint violation; and (iii) use an adaptive learning rate that allows us to run the algorithm for any time horizon. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://arxiv-export-lb.library.cornell.edu/pdf/1906.00049 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
