論文の概要: Linear Bandits on Uniformly Convex Sets

• arxiv url: http://arxiv.org/abs/2103.05907v1
• Date: Wed, 10 Mar 2021 07:33:03 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-11 14:42:14.611336
• Title: Linear Bandits on Uniformly Convex Sets
• Title（参考訳）: 均一凸集合上の線形バンド
• Authors: Thomas Kerdreux, Christophe Roux, Alexandre d'Aspremont, Sebastian Pokutta
• Abstract要約: 線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
• 参考スコア（独自算出の注目度）: 88.3673525964507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear bandit algorithms yield $\tilde{\mathcal{O}}(n\sqrt{T})$ pseudo-regret bounds on compact convex action sets $\mathcal{K}\subset\mathbb{R}^n$ and two types of structural assumptions lead to better pseudo-regret bounds. When $\mathcal{K}$ is the simplex or an $\ell_p$ ball with $p\in]1,2]$, there exist bandits algorithms with $\tilde{\mathcal{O}}(\sqrt{nT})$ pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond $\ell_p$ balls that enjoy pseudo-regret bounds of $\tilde{\mathcal{O}}(\sqrt{nT})$, which answers an open question from [BCB12, \S 5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than $\mathcal{O}(\sqrt{n})$. However, this comes at the expense of asymptotic rates in $T$ varying between $\tilde{\mathcal{O}}(\sqrt{T})$ and $\tilde{\mathcal{O}}(T)$.
• Abstract（参考訳）: 線形バンディットアルゴリズムは、$\tilde{\mathcal{O}}(n\sqrt{T})$ コンパクト凸作用集合上の擬似調整境界 $\mathcal{K}\subset\mathbb{R}^n$ を生成し、構造上の仮定の2つのタイプは、より良い擬似補正境界をもたらす。 $\mathcal{K}$ が単純あるいは $\ell_p$ ball with $p\in]1,2]$ であるとき、$\tilde{\mathcal{O}}(\sqrt{nT})$ pseudo-regret bounds を持つバンディットアルゴリズムが存在する。 ここでは、$\tilde{\mathcal{O}}(\sqrt{nT})$の擬似残界を楽しむ $\ell_p$ 球を超えるいくつかの強凸集合のバンディットアルゴリズムを導出し、[BCB12, \S 5.5.] から開放的な質問に答える。 興味深いことに、作用集合が一様凸であるが必ずしも強凸でないとき、$\mathcal{O}(\sqrt{n})$より小さい次元依存を持つ擬回帰境界を得る。 しかし、これは、$\tilde{\mathcal{O}}(\sqrt{T})$と$\tilde{\mathcal{O}}(T)$の間に異なる$T$の漸近率を犠牲にしている。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
  分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。 我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。 我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• Minimax Regret for Bandit Convex Optimisation of Ridge Functions [34.686687996497525]
  f(x) = g(langle x, thetarangle)$ for convex $g : mathbb R to mathbb R$ and $theta in mathbb Rd$.} という形の函数の演奏に制限される対向的な対向的バンドイ・凸最適化を解析する。 我々は、ミニマックス後悔が少なくとも$O(dsqrtn log(operatornamediammathcal K))$であるという短い情報理論の証明を提供する。
  論文  参考訳（メタデータ） (2021-06-01T12:51:48Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• Optimal Strategies for Graph-Structured Bandits [0.0]
  Bernoulli $!=!(nu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a
  論文  参考訳（メタデータ） (2020-07-07T06:27:51Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)
• Some convergent results for Backtracking Gradient Descent method on Banach spaces [0.0]
  bf Theorem.$X$をバナッハ空間とし、$f:Xrightarrow mathbbR$を$C2$関数とする。 $mathcalC$ を $f$ の臨界点の集合とする。
  論文  参考訳（メタデータ） (2020-01-16T12:49:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。