Fugu-MT 論文翻訳(概要): Asymptotically optimal strategies for online prediction with history-dependent experts

論文の概要: Asymptotically optimal strategies for online prediction with history-dependent experts

arxiv url: http://arxiv.org/abs/2008.13703v1
Date: Mon, 31 Aug 2020 16:00:42 GMT
ステータス: 処理完了
システム内更新日: 2022-10-23 07:44:06.745309
Title: Asymptotically optimal strategies for online prediction with history-dependent experts
Title（参考訳）: 歴史依存専門家によるオンライン予測のための漸近的最適戦略
Authors: Jeff Calder and Nadejda Drenska
Abstract要約: 我々は,履歴に依存した専門家によるオンライン予測の問題に対して,鋭く最適な戦略を確立する。 De Bruijn グラフ上の最適条件は、グラフポアソン方程式に対応することを示す。
参考スコア（独自算出の注目度）: 1.52292571922932
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We establish sharp asymptotically optimal strategies for the problem of online prediction with history dependent experts. The prediction problem is played (in part) over a discrete graph called the $d$ dimensional de Bruijn graph, where $d$ is the number of days of history used by the experts. Previous work [11] established $O(\varepsilon)$ optimal strategies for $n=2$ experts and $d\leq 4$ days of history, while [10] established $O(\varepsilon^{1/3})$ optimal strategies for all $n\geq 2$ and all $d\geq 1$, where the game is played for $N$ steps and $\varepsilon=N^{-1/2}$. In this paper, we show that the optimality conditions over the de Bruijn graph correspond to a graph Poisson equation, and we establish $O(\varepsilon)$ optimal strategies for all values of $n$ and $d$.
Abstract（参考訳）: 歴史に係わる専門家によるオンライン予測問題に対する鋭利な漸近的最適戦略を確立する。予測問題は、$d$ dimensional de Bruijn graphと呼ばれる離散グラフ上で(部分的には)行われ、$d$は専門家が使う歴史の日数である。以前の作業 [11] では$O(\varepsilon)$Optimical Strategy for $n=2$ experts と $d\leq 4$ days of history, [10] では$O(\varepsilon^{1/3})$Optimical Strategy for all $n\geq 2$ and all $d\geq 1$, ここでゲームは$N$ steps と $\varepsilon=N^{-1/2}$でプレイされる。本稿では, de bruijn グラフ上の最適条件がグラフ poisson 方程式に対応していることを示し,すべての値が $n$ と $d$ に対して $o(\varepsilon)$ の最適戦略を確立する。

関連論文リスト

Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
論文参考訳（メタデータ） (2024-05-06T17:38:20Z)
On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文参考訳（メタデータ） (2023-03-10T00:11:18Z)
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。目標は最小限のコストで予測を行うことだ。最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文参考訳（メタデータ） (2023-03-03T04:39:53Z)
Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
有向フィードバックグラフが帯域幅を持つ拡張について検討する。グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
論文参考訳（メタデータ） (2022-10-09T11:21:08Z)
Efficient and Optimal Fixed-Time Regret with Two Experts [5.650647159993238]
専門家のアドバイスによる予測は、オンライン学習における基礎的な問題である。 T$のラウンドと$n$のエキスパートを持つ場合、古典的な乗法的重み更新法は、$T$が事前に知られているときに、少なくとも$sqrt(T/2)ln n$の後悔を被る。専門家が$n$の数が小さい/固定された場合、より後悔する保証のあるアルゴリズムが存在する。
論文参考訳（メタデータ） (2022-03-15T01:07:09Z)
Mediated Uncoupled Learning: Learning Functions without Direct Input-output Correspondences [80.95776331769899]
ペア化されたデータがない場合、$X$から$Y$を予測するタスクを考えます。単純なアプローチは、$S_X$で$U$から$U$を予測し、$S_Y$で$U$から$Y$を予測することである。我々は$U$を予測しない新しい方法を提案するが、$f(X)$と$S_X$をトレーニングすることで$Y = f(X)$を直接学習し、$h(U)$を予測する。
論文参考訳（メタデータ） (2021-07-16T22:13:29Z)
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)
Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
すべての次数$D ge 2$ of girth $> 5$に対して、QAOA$はQAOA$ on $G$よりも大きなカット率を持つことを示す。任意の定数$p$に対して、すべてのグラフ上でQAOA$_p$と同様に動作する局所古典的MAX-CUTアルゴリズムが存在すると推測する。
論文参考訳（メタデータ） (2021-01-14T09:17:20Z)
Online Prediction With History-Dependent Experts: The General Case [1.52292571922932]
本稿では,オンライン・機械学習の古典的な例である,オンライン・セッティングにおけるエキスパート・アドバイスによるバイナリ・シーケンスの予測問題について検討する。我々は、バイナリシーケンスを株価の価格履歴と解釈し、予測器を投資家とみなし、その問題を株価予測問題に変換する。
論文参考訳（メタデータ） (2020-07-31T19:40:20Z)
Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文参考訳（メタデータ） (2020-03-04T07:36:38Z)

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