#### 論文の概要: Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization

• arxiv url: http://arxiv.org/abs/2102.07387v1
• Date: Mon, 15 Feb 2021 08:16:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-16 15:36:57.082640
• Title: Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization
• Title（参考訳）: Pseudo-1d Bandit Convex Optimizationのための最適回帰アルゴリズム
• Authors: Aadirupa Saha, Nagarajan Natarajan, Praneeth Netrapalli, Prateek Jain
• Abstract要約: 我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
• 参考スコア（独自算出の注目度）: 51.23789922123412
• Abstract: We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions $\f_t$ admit a "pseudo-1d" structure, i.e. $\f_t(\w) = \loss_t(\pred_t(\w))$ where the output of $\pred_t$ is one-dimensional. At each round, the learner observes context $\x_t$, plays prediction $\pred_t(\w_t; \x_t)$ (e.g. $\pred_t(\cdot)=\langle \x_t, \cdot\rangle$) for some $\w_t \in \mathbb{R}^d$ and observes loss $\loss_t(\pred_t(\w_t))$ where $\loss_t$ is a convex Lipschitz-continuous function. The goal is to minimize the standard regret metric. This pseudo-1d bandit convex optimization problem (\SBCO) arises frequently in domains such as online decision-making or parameter-tuning in large systems. For this problem, we first show a lower bound of $\min(\sqrt{dT}, T^{3/4})$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm \sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively, guaranteeing the {\em optimal} regret bound mentioned above, up to additional logarithmic factors. In contrast, applying state-of-the-art online convex optimization methods leads to $\tilde{O}\left(\min\left(d^{9.5}\sqrt{T},\sqrt{d}T^{3/4}\right)\right)$ regret, that is significantly suboptimal in $d$.
• Abstract（参考訳）: 我々は,バンディットフィードバックを用いてオンライン学習を学習する。 コスト/リワード関数 $\f_t$ は "pseudo-1d" 構造、すなわち "pseudo-1d" 構造を受け入れる。 $\f_t(\w) = \loss_t(\pred_t(\w))$ ここで$\pred_t$の出力は1次元である。 各ラウンドで、学習者はコンテキスト $\x_t$ を観察し、予測 $\pred_t(\w_t; \x_t)$ を再生する。 $\pred_t(\cdot)=\langle \x_t, \cdot\rangle$) for some $\w_t \in \mathbb{R}^d$ and observes loss $\loss_t(\pred_t(\w_t))$ where $\loss_t$ is a convex Lipschitz-continuous function。 目標は、標準の後悔度を最小化することです。 この擬似1dバンディット凸最適化問題(\SBCO)は、大規模システムにおけるオンライン意思決定やパラメータ調整などの領域で頻繁に発生する。 この問題に対して、まず$T$がラウンド数である任意のアルゴリズムの後悔のために、$\min(\sqrt{dT}, T^{3/4})$の下限を示す。 本稿では,擬似1d構造を効果的に活用するために,ランダム化オンライン勾配降下法とカーネル化指数重み付け法を併用した新しいアルゴリズム \sbcalgを提案する。 対照的に、最先端のオンライン凸最適化手法を適用すると、$\tilde{O}\left(\min\left(\min\left(d^{9.5}\sqrt{T},\sqrt{d}T^{3/4}\right)\right)$ regretとなる。

#### 関連論文リスト

• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。 目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。 論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) • Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221] オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。 そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。 論文 参考訳（メタデータ） (2023-02-27T21:19:24Z) • Logarithmic Regret from Sublinear Hints [76.87432703516942] 自然クエリモデルにより,アルゴリズムが$O(log T)$regretsを$O(sqrtT)$hintsで得ることを示す。 また、$o(sqrtT)$hintsは$Omega(sqrtT)$regretより保証できないことも示しています。 論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) • Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933] 本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。 我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。 論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) • Private Stochastic Convex Optimization: Optimal Rates in$\ell_1$Geometry [69.24618367447101] 対数要因まで$(varepsilon,delta)$-differently private の最適過剰人口損失は$sqrtlog(d)/n + sqrtd/varepsilon n.$です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Adaptive Online Learning with Varying Norms [45.11667443216861]
オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。 この結果を用いて新しい「完全行列」型後悔境界を得る。
論文  参考訳（メタデータ） (2020-02-10T17:22:08Z)