論文の概要: Corruption-Robust Contextual Search through Density Updates
- arxiv url: http://arxiv.org/abs/2206.07528v1
- Date: Wed, 15 Jun 2022 13:18:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-16 15:13:04.980350
- Title: Corruption-Robust Contextual Search through Density Updates
- Title（参考訳）: 密度更新による汚職ロバストコンテクスト検索
- Authors: Renato Paes Leme, Chara Podimata, and Jon Schneider
- Abstract要約: 逆雑音モデルにおける文脈探索の問題について検討する。
d$を問題の次元とし、T$を時間軸とし、C$をシステム内のノイズの総量とする。
- 参考スコア（独自算出の注目度）: 28.474451077732287
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of contextual search in the adversarial noise model. Let
$d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the
total amount of noise in the system. For the $\eps$-ball loss, we give a tight
regret bound of $O(C + d \log(1/\eps))$ improving over the $O(d^3 \log(1/\eps))
\log^2(T) + C \log(T) \log(1/\eps))$ bound of Krishnamurthy et al (STOC21). For
the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$.
Our techniques are a significant departure from prior approaches.
Specifically, we keep track of density functions over the candidate vectors
instead of a knowledge set consisting of the candidate vectors consistent with
the feedback obtained.
- Abstract（参考訳）: 逆雑音モデルにおける文脈探索の問題について検討する。
d$を問題の次元とし、T$を時間軸とし、C$をシステム内のノイズの総量とする。
$\eps$-ball損失に対して、$O(C + d \log(1/\eps))$$O(d^3 \log(1/\eps)) \log^2(T) + C \log(T) \log(1/\eps))$Krishnamurthy et al (STOC21) の厳密な後悔境界を与える。
対称損失に対して、後悔する$O(C+d \log T)$の効率的なアルゴリズムを与える。
私たちの技術は、以前のアプローチから大きく離れています。
具体的には、得られたフィードバックに一致した候補ベクトルからなる知識セットの代わりに、候補ベクトル上の密度関数の追跡を行う。
関連論文リスト
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
論文 参考訳（メタデータ） (2025-02-06T12:03:24Z) - Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
本稿では,非退化関数に対するバッチ帯域学習問題について検討する。
本稿では,非退化関数に対するバッチバンドイット問題をほぼ最適に解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-09T12:50:16Z) - Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳（メタデータ） (2024-03-05T12:28:00Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳（メタデータ） (2023-10-23T04:07:26Z) - Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial
Corruptions [98.75618795470524]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
我々は不確実性に直面した楽観主義の原理に基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-13T17:58:58Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。