Optimal Regularized Online Allocation by Adaptive Re-Solving
研究在线资源分配问题，使用不可分离正则化项促进公平性等目标，提出基于对偶的优化策略，通过自适应更新资源约束和基于历史的重求解实现最优对数遗憾，无需log-log因子。
Online resource allocation is challenging when the decision maker aims to achieve fairness, load balancing, diversity, and so on. In “Optimal Regularized Online Allocation by Adaptive Re-Solving,” Ma, Cao, Tsang, and Xia examine the online allocation problem equipped with a nonseparable regularizer, which is commonly adopted to promote fairness and beyond. Under certain regularity, smoothness, and nondegeneracy assumptions of the dual problem, the authors show that a dual-based optimization strategy with adaptively updated resource constraints and history-based re-solving can achieve optimal logarithmic regret, even without the notorious log-log factor. The authors also demonstrate that an optimal regret upper bound can be achieved using infrequent re-solving and that an even faster algorithm is available if nearly optimal regret performance is acceptable. Their results demonstrate that optimal logarithmic regret is achievable under the max-min fairness or load-balancing constraints.