Recent advances on distributed online optimization

摘要:

Abstract:

Online optimization has received numerous attention in recent two decades, mostly inspired by its potential applications to auctions, smart grids, portfolio management, dictionary learning, neural networks, and so on. Generally, online optimization is a sequence of decision making processes, where a sequence of time-varying loss functions are gradually revealed in a dynamic environment which may be adversarial. At each time instant, the loss function information at current time is revealed to the decision maker only after her/his decision is made. The objective of online optimization is to choose the best decision at each time step as far as possible, but unfortunately, this goal is generally diffcult or impossible to achieve. As such, to measure the performance for an algorithm, two metrics are usually exploited, i.e., regret and competitive ratio, for which the former one is leveraged more frequently in the literature. Moreover, two kinds of regrets, i.e., static and dynamic regrets, are usually considered by researchers, where the static regret is to compare the performance with a cumulative loss with respect to the same best decision through all the time horizons, while the dynamic regret is with respect to the best decision at each time instant. More recently, another regret, called adaptive regret , has been proposed and investigated as a suitable metric for changing environments, as dynamic regret does. Historically, centralized online optimization is first addressed, that is, there is a centralized decision maker who can access all the information on the revealed loss function at each time. Along this line, a wide range of results have thus far been reported in the literature. For example, online optimization was studied subject to feasible set constraints, where it has been shown that the optimal bound is O( √ T) for static regret....