論文の概要: Minimax Regret for Bandit Convex Optimisation of Ridge Functions

• arxiv url: http://arxiv.org/abs/2106.00444v1
• Date: Tue, 1 Jun 2021 12:51:48 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-02 14:05:53.667217
• Title: Minimax Regret for Bandit Convex Optimisation of Ridge Functions
• Title（参考訳）: リッジ関数の帯域凸最適化のためのミニマックスレグレット
• Authors: Tor Lattimore
• Abstract要約: f(x) = g(langle x, thetarangle)$ for convex $g : mathbb R to mathbb R$ and $theta in mathbb Rd$.} という形の函数の演奏に制限される対向的な対向的バンドイ・凸最適化を解析する。 我々は、ミニマックス後悔が少なくとも$O(dsqrtn log(operatornamediammathcal K))$であるという短い情報理論の証明を提供する。
• 参考スコア（独自算出の注目度）: 34.686687996497525
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyse adversarial bandit convex optimisation with an adversary that is restricted to playing functions of the form $f(x) = g(\langle x, \theta\rangle)$ for convex $g : \mathbb R \to \mathbb R$ and $\theta \in \mathbb R^d$. We provide a short information-theoretic proof that the minimax regret is at most $O(d\sqrt{n} \log(\operatorname{diam}\mathcal K))$ where $n$ is the number of interactions, $d$ the dimension and $\operatorname{diam}(\mathcal K)$ is the diameter of the constraint set. Hence, this class of functions is at most logarithmically harder than the linear case.
• Abstract（参考訳）: 逆向きのバンドイット凸最適化を、f(x) = g(\langle x, \theta\rangle)$ for convex $g : \mathbb r \to \mathbb r$ と $\theta \in \mathbb r^d$ という形式の関数に制限された逆数で解析する。 ミニマックスの後悔は最大で$o(d\sqrt{n} \log(\operatorname{diam}\mathcal k))$であり、ここで$n$は相互作用の数、$d$は次元、$\operatorname{diam}(\mathcal k)$は制約集合の直径である。 したがって、この函数の類は線形の場合よりも対数的に難しい。

関連論文リスト

• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Families of costs with zero and nonnegative MTW tensor in optimal transport [0.0]
  我々は、$mathsfc$のコスト関数を持つ$mathbbRn$上の最適輸送問題に対するMTWテンソルを明示的に計算する。 我々は$sinh$-typeの双曲的コストを分析し、$mathsfc$-type関数と発散の例を提供する。
  論文  参考訳（メタデータ） (2024-01-01T20:33:27Z)
• Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded Geometric Penalties [21.141544548229774]
  我々は$min_x max_y f(x, y) という形式で、$mathcalN$ は Hadamard である。 我々は、勾配収束定数を減少させることにより、グローバルな関心が加速されることを示す。
  論文  参考訳（メタデータ） (2023-05-25T15:43:07Z)
• An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
  既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。 我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
  論文  参考訳（メタデータ） (2022-12-29T19:26:12Z)
• Local approximation of operators [0.0]
  距離空間 $mathfrakX$ と $mathfrakY$ の間の非線形作用素の近似の度合いを決定する問題について検討する。 例えば、$mathbbSd$ の近似に関係する定数は $mathcalO(d1/6)$ である。
  論文  参考訳（メタデータ） (2022-02-13T19:28:34Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• 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)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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