In many dynamic systems, such as wireless communications, decisions on system operation are updated over time, and the decision maker requires an online learning approach to optimize its strategy in response to the changing environment. When the loss and constraint functions are convex, this belongs to the general family of online convex optimization (OCO). In existing OCO works, the environment is assumed to vary in a time-slotted fashion, while the decisions are updated at each time slot. This model is inadequate for systems that permit only periodic decision updates, i.e., each decision is fixed over multiple time slots, while the environment changes between the decision epochs. In this work, we consider periodic decision updates for OCO. We aim to minimize the accumulation of time-varying convex loss functions, subject to both short-term and long-term constraints. Information about the loss functions within the current update period may be incomplete and is revealed to the decision maker only after the decision is made. We propose an efficient algorithm, termed Periodic Queueing and Gradient Aggregation (PQGA), which employs novel periodic queues together with aggregated gradient descent to update the decisions over time. PQGA is applicable to both constant and time-varying update periods. Most importantly, we show that PQGA yields bounded dynamic regret, static regret, and constraint violation. Furthermore, they are sublinear over time if the accumulated variation of the system states and update periods do not grow too fast. As an example application, we study the performance of PQGA in a large-scale multi-antenna system shared by multiple wireless service providers. Simulation results show that PQGA converges fast and substantially outperforms the known best alternative.?
翻译:在许多动态系统中,如无线通信,关于系统操作的决定会随着时间的变化而更新,而决策者则需要一种在线学习方法来优化其战略,以适应不断变化的环境。当损失和制约功能是 convex 时,这属于在线 convex 优化(OCO) 的一般家庭。在现有的 OCO 工作中,环境假定以时间分布方式变化,而每个时间段的决定都会更新。对于只允许定期更新决定的系统来说,这种模式是不够的,即每个决定都是固定在多个时间档中,而决定间隔之间的环境变化。在这项工作中,我们考虑对 OCO 定期更新决定。我们的目标是尽量减少时间变换的 convex 损失功能的累积,但受短期和长期限制。关于当前更新期内损失功能的信息可能不全,只有在作出决定后才会被披露给决策者。我们建议一种高效的算法,称为定期递增和加固 Agardation(PQGA), 使用新的定期递增时间档, 与不断递增的递增的递增 Q; 最晚递增的递增的递增的系统, 显示我们不断递增的递增的递增的递增的递增的递增。