无需知道时间视界也能做到O(√d)遗憾！在线逆线性优化新算法逼近理论最优下界
Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights
📖 AI 总结
本文研究在线逆向线性优化问题：每轮环境给出一个紧凑动作集，学习器推荐一个动作，环境则返回该集合中最大化固定未知线性效用的动作。在效用向量与动作均位于d维欧氏单位球的设定下，作者提出一种随机算法，其期望遗憾——即相对于最优动作的累计效用损失——对任意时间跨度均为O(√d)，且无需预先知道时间跨度。由于已知在时间跨度T≥d时存在Ω(√d)下界，该结果在常数因子意义下达到了最优维度依赖。算法核心是在几何间隔的多尺度多项式特征空间上维护矩阵乘法权重，通过求解线性规划确定推荐分布，并利用可用动作与反馈动作的比较更新得分矩阵。在有理数预言机输出与反馈动作条件下，相对于线性优化预言机可计算的实现仍保持该遗憾界。论文同时指出，能否在维度、时间跨度和输入长度多项式时间内达到相同速率仍是开放问题。
🔑 关键词速览
| 在线逆线性优化 | 一种在线学习框架，其中学习器通过观察环境的最优动作反馈来推断未知的线性效用函数。 |
| 遗憾 | 衡量学习算法性能的指标，定义为累积效用与最优动作累积效用之间的差距。 |
| 矩阵乘法权重 | 一种用于在线学习的算法技术，通过维护矩阵权重并乘法更新来最小化遗憾。 |
| 多项式特征空间 | 由原始特征的多项式组合构成的高维空间，用于捕捉非线性关系。 |
| 线性优化预言机 | 一个假设的求解器，能够高效地解决线性规划问题，用于算法实现。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅