論文の概要: Impossible Tuning Made Possible: A New Expert Algorithm and Its
Applications
- arxiv url: http://arxiv.org/abs/2102.01046v1
- Date: Mon, 1 Feb 2021 18:34:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 10:08:20.186312
- Title: Impossible Tuning Made Possible: A New Expert Algorithm and Its
Applications
- Title（参考訳）: 不可能なチューニングが可能になった:新しいエキスパートアルゴリズムとその応用
- Authors: Liyu Chen, Haipeng Luo, Chen-Yu Wei
- Abstract要約: 我々は、すべてのエキスパート$i$に対して、後悔の$Oleft(sqrt(ln d)sum_t ell_t,i2right)を同時に$T$ラウンド$d$-expert問題で達成できることを示します。
本アルゴリズムは,補正項と重み付きエントロピー正規化器を備えたミラー・ディキストリアル・フレームワークに基づいている。
- 参考スコア（独自算出の注目度）: 37.6975819766632
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We resolve the long-standing "impossible tuning" issue for the classic expert
problem and show that, it is in fact possible to achieve regret
$O\left(\sqrt{(\ln d)\sum_t \ell_{t,i}^2}\right)$ simultaneously for all expert
$i$ in a $T$-round $d$-expert problem where $\ell_{t,i}$ is the loss for expert
$i$ in round $t$. Our algorithm is based on the Mirror Descent framework with a
correction term and a weighted entropy regularizer. While natural, the
algorithm has not been studied before and requires a careful analysis. We also
generalize the bound to $O\left(\sqrt{(\ln d)\sum_t
(\ell_{t,i}-m_{t,i})^2}\right)$ for any prediction vector $m_t$ that the
learner receives, and recover or improve many existing results by choosing
different $m_t$. Furthermore, we use the same framework to create a master
algorithm that combines a set of base algorithms and learns the best one with
little overhead. The new guarantee of our master allows us to derive many new
results for both the expert problem and more generally Online Linear
Optimization.
- Abstract（参考訳）: 我々は、古典的専門家問題の長年にわたる「不可能なチューニング」問題を解決し、実際、後悔の$O\left(\sqrt{(\ln d)\sum_t \ell_{t,i}^2}\right)$と同時に、$T$-round $d$-expert problemにおけるすべてのエキスパート$i$に対して$\ell_{t,i}$は、ラウンド$t$におけるエキスパート$i$の損失であることを示す。
本アルゴリズムは、補正項と重み付きエントロピー正則化器を備えたミラー降下フレームワークに基づいている。
自然だが、アルゴリズムはこれまで研究されておらず、慎重に分析する必要がある。
また、学習者が受信する任意の予測ベクトル $m_t$ に対して $o\left(\sqrt{(\ln d)\sum_t (\ell_{t,i}-m_{t,i})^2}\right)$ を一般化し、異なる $m_t$ を選択して既存の結果を復元または改善する。
さらに,同じフレームワークを使用して,基本アルゴリズムの集合を結合し,オーバーヘッドの少ない最善のアルゴリズムを学習するマスタアルゴリズムを作成する。
マスターの新たな保証により、専門家問題とより一般的なオンライン線形最適化の両方に対して、多くの新しい結果が得られます。
関連論文リスト
- Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - 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) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - 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) - 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) - Adaptive Online Learning with Varying Norms [45.11667443216861]
オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。
この結果を用いて新しい「完全行列」型後悔境界を得る。
論文 参考訳（メタデータ） (2020-02-10T17:22:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。