期刊
OPERATIONS RESEARCH
卷 63, 期 5, 页码 1227-1244出版社
INFORMS
DOI: 10.1287/opre.2015.1408
关键词
stochastic approximation; non-stationary; minimax regret; online convex optimization
资金
- National Science Foundation [NSF] [0964170]
- U.S.-Israel Binational Science Foundation[BSF] [2010466]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [0964170] Funding Source: National Science Foundation
- Division Of Physics
- Direct For Mathematical & Physical Scien [2010466] Funding Source: National Science Foundation
We consider a non-stationary variant of a sequential stochastic optimization problem, in which the underlying cost functions may change along the horizon. We propose a measure, termed variation budget, that controls the extent of said change, and study how restrictions on this budget impact achievable performance. We identify sharp conditions under which it is possible to achieve long-run average optimality and more refined performance measures such as rate optimality that fully characterize the complexity of such problems. In doing so, we also establish a strong connection between two rather disparate strands of literature: (1) adversarial online convex optimization and (2) the more traditional stochastic approximation paradigm (couched in a non-stationary setting). This connection is the key to deriving well-performing policies in the latter, by leveraging structure of optimal policies in the former. Finally, tight bounds on the minimax regret allow us to quantify the price of non-stationarity, which mathematically captures the added complexity embedded in a temporally changing environment versus a stationary one.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据