Online convex optimization Sample Clauses

Online convex optimization. ‌ Before introducing online optimization, we first give a general review of static optimization and stochastic optimization, as follows • Static optimization: the core underlying assumption is that the objective and constraint functions remain fixed during the entire running time of the algorithm calculating a solution. • Stochastic optimization: it provides an extension of the framework to prob- lems, where the objective and constraint functions are assumed to follow a stationary stochastic process. However, the above methods rely on strong assumptions regarding the vari- ability of the objective and constraint functions. By contrast, online optimization provides an elegant toolbox which goes beyond the above by allowing for variations in the problem that are completely arbitrary [13]. The author in [142] first introduced the online convex optimization (OCO) model, where an online player iteratively makes a decision, i.e., chooses a sequence of points in Eucildean space, from a fixed feasible set X which is assumed to be bounded, closed and convex. Following [142, 51], we denote the number of iterations by T . At iteration t, the online player first chooses a point xt ∈ X without knowing prior information. After committing to this choice, a convex cost function ft is revealed. Accordingly, the cost incurred to the online player is the value of the cost function at the point xt, i.e., ft(xt). The difference in performance between the online player and a best "static player" who can make an optimal action over the time horizon is usually termed as static regret, as follows T T x∈X Regret = Σ ft(xt) − min Σ ft(x). (2.5) t=1 t=1 The upper bound is considered on the worst case guaranteed regret. Intuitively, an algorithm achieves non-trivial performance if its regret is sub-linear over T , since this implies that the algorithm performs as good as the best fixed solution in the long-term, i.e., limT→∞ Regret/T = 0; see also [97, 50], and reference therein.