Fugu-MT 論文翻訳(概要): Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation

論文の概要: Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation

arxiv url: http://arxiv.org/abs/2006.00475v3
Date: Fri, 25 Sep 2020 13:10:28 GMT
ステータス: 処理完了
システム内更新日: 2022-11-26 12:31:39.922914
Title: Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation
Title（参考訳）: zeroth-order adversarial bandit convex optimization に対する後悔の改善
Authors: Tor Lattimore
Abstract要約: 零次逆凸最適化に対するミニマックス後悔の情報理論上界は、少なくとも$O(d2.5 sqrtn log(n))$であることを示す。これはBubeckらによって$O(d9.5 sqrtn log(n)7.5$で改善される。
参考スコア（独自算出の注目度）: 28.93486346263364
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We prove that the information-theoretic upper bound on the minimax regret for zeroth-order adversarial bandit convex optimisation is at most $O(d^{2.5} \sqrt{n} \log(n))$, where $d$ is the dimension and $n$ is the number of interactions. This improves on $O(d^{9.5} \sqrt{n} \log(n)^{7.5}$ by Bubeck et al. (2017). The proof is based on identifying an improved exploratory distribution for convex functions.
Abstract（参考訳）: 零次対逆帯域凸最適化に対するミニマックス後悔の情報理論上界は、少なくとも$O(d^{2.5} \sqrt{n} \log(n))$であり、$d$は次元であり、$n$は相互作用の数である。これはbubeck et al. (2017) によって $o(d^{9.5} \sqrt{n} \log(n)^{7.5}$ で改善される。この証明は、凸関数の探索分布を改善することに基づいている。

関連論文リスト

A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文参考訳（メタデータ） (2024-06-26T18:19:10Z)
Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
論文参考訳（メタデータ） (2024-06-10T17:44:11Z)
Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文参考訳（メタデータ） (2024-02-14T13:44:16Z)
Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文参考訳（メタデータ） (2023-02-07T02:22:31Z)
Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文参考訳（メタデータ） (2022-02-01T16:06:20Z)
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)
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)
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)
A Tight Bound for Stochastic Submodular Cover [8.668055353339287]
Golovin and Krause の Adaptive Greedy アルゴリズム (2011) は部分モジュラー被覆に対して$(ln (Q/eta)+1) の近似限界を達成することを示す。私たちの境界は、既知の$(lnm + 1)$の近似を古典的な問題に対してグリーディに有界に一般化し、$m$は基底集合のサイズである。
論文参考訳（メタデータ） (2021-02-01T20:37:40Z)
Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文参考訳（メタデータ） (2020-01-25T14:44:53Z)

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