论文标题
在线自信和相对平滑的最小化，并应用于在线投资组合选择和学习量子状态
Online Self-Concordant and Relatively Smooth Minimization, With Applications to Online Portfolio Selection and Learning Quantum States
论文作者
论文摘要
考虑一个在线凸优化问题，其中损失功能是自我符合的障碍，相对于凸功能$ h $，甚至可能是非lipschitz。我们用$ h $分析了在线镜下降的遗憾。然后，根据结果，我们以统一的方式证明了以下内容。用$ t $ The Time Horizon表示，参数维度为$ D $。 1。对于在线投资组合选择，$ \ widetilde {\ text {eg}} $的遗憾是由于Helmbold等人而导致的渐变梯度的变体，是$ \ tilde {o}（t^{2/3}这对原始$ \ tilde {o}（t^{3/4} d^{1/2}）$遗憾以$ \ wideTilde {\ text {eg}} $绑定。 2。对于在线投资组合选择，对数屏障的在线镜像下降的遗憾是$ \ tilde {o}（\ sqrt {t d}）$。遗憾的界限与因Orseau等人的软贝尔斯的束缚相同。达到对数术语。 3。对于以对数损失的在线学习量子状态，在线镜像下降的遗憾带有log-determinant函数也是$ \ tilde {o}（\ sqrt {t d d}）$。它的触及时间比我们知道的所有现有算法要短。
Consider an online convex optimization problem where the loss functions are self-concordant barriers, smooth relative to a convex function $h$, and possibly non-Lipschitz. We analyze the regret of online mirror descent with $h$. Then, based on the result, we prove the following in a unified manner. Denote by $T$ the time horizon and $d$ the parameter dimension. 1. For online portfolio selection, the regret of $\widetilde{\text{EG}}$, a variant of exponentiated gradient due to Helmbold et al., is $\tilde{O} ( T^{2/3} d^{1/3} )$ when $T > 4 d / \log d$. This improves on the original $\tilde{O} ( T^{3/4} d^{1/2} )$ regret bound for $\widetilde{\text{EG}}$. 2. For online portfolio selection, the regret of online mirror descent with the logarithmic barrier is $\tilde{O}(\sqrt{T d})$. The regret bound is the same as that of Soft-Bayes due to Orseau et al. up to logarithmic terms. 3. For online learning quantum states with the logarithmic loss, the regret of online mirror descent with the log-determinant function is also $\tilde{O} ( \sqrt{T d} )$. Its per-iteration time is shorter than all existing algorithms we know.
