Fugu-MT 論文翻訳(概要): Fast Rates in Online Convex Optimization by Exploiting the Curvature of Feasible Sets

論文の概要: Fast Rates in Online Convex Optimization by Exploiting the Curvature of Feasible Sets

arxiv url: http://arxiv.org/abs/2402.12868v1
Date: Tue, 20 Feb 2024 09:59:33 GMT
ステータス: 処理完了
システム内更新日: 2024-02-21 15:54:57.283521
Title: Fast Rates in Online Convex Optimization by Exploiting the Curvature of Feasible Sets
Title（参考訳）: 実現可能集合の曲率を利用したオンライン凸最適化の高速化
Authors: Taira Tsuchiya, Shinji Ito
Abstract要約: オンライン線形最適化では、損失関数の平均勾配が特定の値よりも大きい場合、実現可能な集合の曲率を利用することができる。本稿では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
参考スコア（独自算出の注目度）: 42.37773914630974
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we explore online convex optimization (OCO) and introduce a new analysis that provides fast rates by exploiting the curvature of feasible sets. In online linear optimization, it is known that if the average gradient of loss functions is larger than a certain value, the curvature of feasible sets can be exploited by the follow-the-leader (FTL) algorithm to achieve a logarithmic regret. This paper reveals that algorithms adaptive to the curvature of loss functions can also leverage the curvature of feasible sets. We first prove that if an optimal decision is on the boundary of a feasible set and the gradient of an underlying loss function is non-zero, then the algorithm achieves a regret upper bound of $O(\rho \log T)$ in stochastic environments. Here, $\rho > 0$ is the radius of the smallest sphere that includes the optimal decision and encloses the feasible set. Our approach, unlike existing ones, can work directly with convex loss functions, exploiting the curvature of loss functions simultaneously, and can achieve the logarithmic regret only with a local property of feasible sets. Additionally, it achieves an $O(\sqrt{T})$ regret even in adversarial environments where FTL suffers an $\Omega(T)$ regret, and attains an $O(\rho \log T + \sqrt{C \rho \log T})$ regret bound in corrupted stochastic environments with corruption level $C$. Furthermore, by extending our analysis, we establish a regret upper bound of $O\Big(T^{\frac{q-2}{2(q-1)}} (\log T)^{\frac{q}{2(q-1)}}\Big)$ for $q$-uniformly convex feasible sets, where uniformly convex sets include strongly convex sets and $\ell_p$-balls for $p \in [1,\infty)$. This bound bridges the gap between the $O(\log T)$ regret bound for strongly convex sets ($q=2$) and the $O(\sqrt{T})$ regret bound for non-curved sets ($q\to\infty$).
Abstract（参考訳）: 本稿では,オンライン凸最適化(OCO)について検討し,実現可能な集合の曲率を利用して高速な速度解析を行う。オンライン線形最適化では、損失関数の平均勾配が一定の値よりも大きい場合、その実現可能な集合の曲率をフォロー・ザ・リード(FTL)アルゴリズムで利用し、対数的後悔を達成することが知られている。本稿では,損失関数の曲率に適応したアルゴリズムが実現可能な集合の曲率を活用できることを示す。まず、最適決定が実現可能な集合の境界にあり、基礎となる損失関数の勾配がゼロでないことを証明した場合、アルゴリズムは確率環境において、後悔の上限である$O(\rho \log T)$を達成する。ここで、$\rho > 0$ は最適決定を含む最小球面の半径であり、実現可能な集合を包含する。本手法は既存手法と異なり, 凸損失関数と直接連携し, 損失関数の曲率を同時に活用し, 実行可能集合の局所的性質のみを用いて対数的後悔を実現することができる。さらに、ftlが$\omega(t)$の後悔に苦しむ敵環境においても、$o(\sqrt{t})$後悔を達成し、腐敗レベル$c$の腐敗した確率環境において、$o(\rho \log t + \sqrt{c \rho \log t})$後悔を達成する。さらに、分析を拡張して、$O\Big(T^{\frac{q-2}{2(q-1)}} (\log T)^{\frac{q}{2(q-1)}}\Big)$ for $q$-一様凸可能集合に対して、一様凸集合は強凸集合と$p \in [1,\infty)$に対する$\ell_p$-ballsを含む。この境界は、強い凸集合に対して$O(\log T)$後悔束(q=2$)と非曲線集合に対して$O(\sqrt{T})$後悔束(q\to\infty$)とのギャップを埋める。

論文の概要: Fast Rates in Online Convex Optimization by Exploiting the Curvature of Feasible Sets

関連論文リスト