论文标题
通过通用硬币博彩与附带信息的无参数在线线性优化
Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting
论文作者
论文摘要
提出了一类无参数的在线线性优化算法，该算法通过适应某些侧面信息来利用对抗序列的结构。这些算法结合了Orabona和P {á} L（2016）的还原技术，用于调整硬币投注算法，以在线线性优化与通用压缩技术在信息理论中使用通用压缩技术，以将顺序的侧面信息纳入造成互助。研究了具体的示例，其中侧面信息具有树结构，并由对抗序列的先前符号的量化值组成，包括固定顺序和可变级马尔可夫案例。通过修改Willems，Shtarkov和Tjalkens（1995）的上下文树的加权技术，进一步完善了所提出的算法，以实现与所有自适应算法的最佳性能，并在计算效率的方式中具有给定最大值的树结构的侧面信息。
A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and P{á}l (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner.
