Fugu-MT 論文翻訳(概要): Improved Space Bounds for Learning with Experts

論文の概要: Improved Space Bounds for Learning with Experts

arxiv url: http://arxiv.org/abs/2303.01453v1
Date: Thu, 2 Mar 2023 18:11:39 GMT
ステータス: 翻訳完了
システム内更新日: 2023-03-03 13:05:45.697692
Title: Improved Space Bounds for Learning with Experts
Title（参考訳）: 専門家による学習のための空間境界の改善
Authors: Anders Aamand, Justin Y. Chen, Huy L\^e Nguyen, and Sandeep Silwal
Abstract要約: スペース予算が$ndelta$ for $delta in (0,1)$であるなら、後悔すべき$tildeO(n2 T1/ (1+delta))$を達成するアルゴリズムを提供する。この改善は、我々のアルゴリズムの後悔が $tildeO_n(sqrtT)$ に近づくレシエーション $delta rightarrow 1$ において特に有益である。
参考スコア（独自算出の注目度）: 5.348126792695619
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give improved tradeoffs between space and regret for the online learning with expert advice problem over $T$ days with $n$ experts. Given a space budget of $n^{\delta}$ for $\delta \in (0,1)$, we provide an algorithm achieving regret $\tilde{O}(n^2 T^{1/(1+\delta)})$, improving upon the regret bound $\tilde{O}(n^2 T^{2/(2+\delta)})$ in the recent work of [PZ23]. The improvement is particularly salient in the regime $\delta \rightarrow 1$ where the regret of our algorithm approaches $\tilde{O}_n(\sqrt{T})$, matching the $T$ dependence in the standard online setting without space restrictions.
Abstract（参考訳）: 私たちは空間間のトレードオフを改善し、専門家のアドバイスでオンライン学習に後悔しています。空間予算が$n^{\delta}$ for $\delta \in (0,1)$を与えられた場合、[PZ23] の最近の研究において、後悔すべき$\tilde{O}(n^2 T^{1/(1+\delta)})$に対して、後悔すべき$\tilde{O}(n^2 T^{2/(2+\delta)})$を改善するアルゴリズムを提供する。この改善は、我々のアルゴリズムの後悔が、スペース制限のない標準オンライン設定における$T$依存と一致する$\tilde{O}_n(\sqrt{T})$に近づく体制において特に有益である。

関連論文リスト

High-Dimensional Calibration from Swap Regret [40.9736612423411]
任意の凸集合 $mathcalP 部分集合 mathbbRd$ 上での多次元予測のオンライン校正について検討する。我々は、$O(sqrtrho T)$$$T$ラウンド後の最悪の後悔を保証できるならば、$T = exp(logd/epsilon2) の後、$epsilon$-calibrated 予測を得ることができることを示した。
論文参考訳（メタデータ） (2025-05-27T17:31:47Z)
Sparsity-Based Interpolation of External, Internal and Swap Regret [4.753557469026313]
本稿では,$phi$-regret最小化によるパフォーマンス指標のコンパレータについて検討する。本稿では,インスタンス適応型$phi$-regretバウンダリを実現する単一アルゴリズムを提案する。従来の$phi$-regretの最小化から外部後悔の最小化への削減を前提に、我々は後者をさらにオンライン線形回帰に変換することを目的としている。
論文参考訳（メタデータ） (2025-02-06T22:47:52Z)
Fully Unconstrained Online Learning [45.31874270358511]
G$-Lipschitz convexの損失に対して、後悔する$G|w_star|sqrtTlog(|w_star|GsqrtT) + |w_star|2 + G2$を得るオンライン学習アルゴリズムを提供する。
論文参考訳（メタデータ） (2024-05-30T23:41:01Z)
Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-04-26T21:54:31Z)
On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
論文参考訳（メタデータ） (2023-05-24T17:40:57Z)
Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-02-27T21:19:24Z)
Smooth Non-Stationary Bandits [49.19728527803684]
本研究では、各アームの平均報酬シーケンスを$beta$-H"older関数に埋め込むことができる非定常包帯問題について検討する。スムース(つまり$betage 2$)と非スムース(つまり$beta=1$)との最初の分離は、$tilde O(k4/5 T3/5)$ regret on any $k$-armed, $2-H"older instanceでポリシーを提示することで示します。
論文参考訳（メタデータ） (2023-01-29T06:03:20Z)
Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文参考訳（メタデータ） (2022-10-15T09:22:22Z)
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)
Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文参考訳（メタデータ） (2021-03-25T18:52:17Z)
Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文参考訳（メタデータ） (2021-03-21T11:43:35Z)
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)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)
Adaptive Online Learning with Varying Norms [45.11667443216861]
オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。この結果を用いて新しい「完全行列」型後悔境界を得る。
論文参考訳（メタデータ） (2020-02-10T17:22:08Z)

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