Fugu-MT 論文翻訳(概要): Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

論文の概要: Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

arxiv url: http://arxiv.org/abs/2606.27917v1
Date: Fri, 26 Jun 2026 10:07:10 GMT
ステータス: 翻訳完了
システム内更新日: 2026-06-29 18:24:25.449122
Title: Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces
Title（参考訳）: 文脈帯域のグラフ次元化:近似平滑性と雑音固有空間の下での構造特異的レグレト境界
Abstract要約: グラフ構造を持つ腕を持つコンテキスト帯は、推薦、引用検索、ソーシャル広告に現れる。グラフの低周波スペクトル部分空間に腕の特徴を投影するGraphDR-LinUCBを提案する。我々はスペクトル射影に基づく文脈的包帯に対して、最初の$wtO(ksqrtT)$ regret boundを証明した。
参考スコア（独自算出の注目度）: 7.100140700856556
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Contextual bandits with graph-structured arms arise in recommendation, citation retrieval, and social advertising, where arms connected on a graph tend to share reward signal. Standard dimensionality reduction ignores this structure, inflating exploration cost by a factor of $d/k$. We propose GraphDR-LinUCB, which projects arm features onto the graph's low-frequency spectral subspace and runs linear UCB in the resulting $k$-dimensional space. We prove the first $\wtO(k\sqrt{T})$ regret bound for spectral-projection-based contextual bandits, reducing dimension dependence from $d$ to $k$; a perturbation argument extends this to noisy graphs, with an explicit penalty for reward-smoothness mismatch and graph-estimation error. Our central theoretical finding is that the high-frequency reward component need not incur a worst-case linear-in-$T$ penalty: its actual cost depends on its realized impact along the played path, not on its total energy. A simple spectral comparison between subspaces ($Γ_k$) predicts which reducer wins on a given dataset, correctly calling five of six real-dataset outcomes without any fitted threshold. Across a synthetic benchmark and six real datasets (MovieLens, Amazon, LastFM, ogbn-arxiv, MIND), GraphDR-LinUCB reduces cumulative regret by $15\times$ over full-dimensional LinUCB and outperforms competing graph-aware methods on five of six; the single failure is precisely where the graph's spectral subspace is misaligned with the reward.
Abstract（参考訳）: グラフ構造を持つ腕を持つコンテキスト帯は、リコメンデーション、引用検索、ソーシャル広告に現れ、グラフに接続された腕は報酬信号を共有する傾向にある。標準次元減少は、この構造を無視し、探索コストを$d/k$で膨らませる。我々は、グラフの低周波スペクトル部分空間にアームを投影し、その結果の$k$次元空間で線形 UCB を実行するGraphDR-LinUCBを提案する。スペクトル射影に基づく文脈包帯に対しての最初の$\wtO(k\sqrt{T})$ regret boundを証明し、次元依存を$d$から$k$に減らした。我々の中心的な理論的な発見は、高周波報酬成分は最悪の場合のリニア・イン・T$ペナルティを発生させる必要がなく、実際のコストは演奏経路に沿った実効的な影響に依存し、総エネルギーに依存しないということである。部分空間の単純なスペクトル比較($)は、与えられたデータセットで還元器が勝つかを予測し、適合しきい値のない6つの実データのうち5つを正しく呼び出す。合成ベンチマークと6つの実際のデータセット(MovieLens、Amazon、LastFM、ogbn-arxiv、MIND)を通じて、GraphDR-LinUCBは、全次元LinUCBよりも15\times$で累積後悔を減らし、競合するグラフ認識メソッドを6つ中5つで上回る。

関連論文リスト

Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文参考訳（メタデータ） (2026-09-07T01:38:41Z)
Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization [1.0762008415887194]
自己教師付き学習はラベルのごく一部から精度を指示するが、その背景にあるラベル付きサンプルの効率は理論的な説明に欠けていた。データ拡張はラベルのないデータに類似性グラフを誘導するので、そのグラフ上の下流での学習はグラフ-ラプラシア正規化学習である。
論文参考訳（メタデータ） (2026-07-08T15:11:21Z)
Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction [7.176258979075087]
Federated Graph Learningのような設定には、ローカライズ、フラグメント、ノイズ、プライバシ学習といったグラフデータが含まれる。標準データセットを3つの戦略と4つのコントロールを使用してフラグメント化されたベンチマークに分解するLoGraBを導入する。本稿では,スペクトルフラグメントのノイズ除去手法であるAFR(Adaptive Fidelity-driven Reconstruction)を提案する。
論文参考訳（メタデータ） (2026-04-22T21:31:32Z)
Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence [6.908972852063454]
主要声楽アンサンブルは、多種多様なほぼ独立した基礎学習者に対して平均化することにより、ばらつきの低減を実現する。固定次元マルコフ集合における離散的な分類のために、この現象のミニマックス的特徴付けを行う。合成マルコフ連鎖、2次元空間格子、128データセットのUCRアーカイブ、アタリDQNアンサンブルに関する実験は、理論的な予測を検証している。
論文参考訳（メタデータ） (2026-04-15T02:32:30Z)
Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
データ・ポーア・システマにおける高次元スパース線形包帯問題について検討する。線形モデルに対するラッソ推定器の新たなオフライン統計的保証を示す。本稿では,最小限のコストで最適空間パラメータ$k$の知識を必要としない相関に基づくメタアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-10-26T01:42:03Z)
Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
論文参考訳（メタデータ） (2023-05-13T17:29:18Z)
Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。グラフの構造は知られており、ノードは$N$である。頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-08-26T16:21:31Z)
Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。三角凸分解はその上部に対応する変換によって保証されることを示す。
論文参考訳（メタデータ） (2021-09-17T17:46:12Z)
Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文参考訳（メタデータ） (2020-12-10T15:40:07Z)
High-Dimensional Sparse Linear Bandits [67.9378546011416]
データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
論文参考訳（メタデータ） (2020-11-08T16:48:11Z)
Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models? [13.572602792770288]
ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
論文参考訳（メタデータ） (2020-06-26T12:06:10Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。