論文の概要: Efficient Multinomial Logistic Bandit via Frequent Directions
- arxiv url: http://arxiv.org/abs/2606.11968v1
- Date: Wed, 10 Jun 2026 11:47:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-11 16:42:38.435591
- Title: Efficient Multinomial Logistic Bandit via Frequent Directions
- Title（参考訳）: 周波数方向による効率的な多項ロジスティック帯域
- Authors: Linzhe He, Yu-Jie Zhang, Sifan Yang, Lijun Zhang,
- Abstract要約: 代表的な UCB 型アルゴリズムである OFUL-MLogB は $tildemathcalO(KdsqrtT)$ の残差を達成しているが、それでも $mathcalO(K3d3)$ と $mathcalO(K2d2)$ の時間を必要とする。
我々は、OFD-MLogBに頻繁に描画される方向行列を組み込んだEOFD-MLogBを提案する。
- 参考スコア（独自算出の注目度）: 36.600560776380874
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies efficient online algorithms for multinomial logistic bandits (MLogB), where the feedback distribution over $K+1$ outcomes follows a multinomial logistic model of $d$-dimensional action vectors. A representative UCB-type algorithm, OFUL-MLogB, achieves a regret bound of $\tilde{\mathcal{O}}(Kd\sqrt{T})$, but still requires $\mathcal{O}(K^3d^3)$ time and $\mathcal{O}(K^2d^2)$ space per round due to parameter estimation and optimistic reward construction, which is prohibitive in high-dimensional settings. To address this limitation, we propose EOFD-MLogB, which integrates frequent directions matrix sketching into OFUL-MLogB. By maintaining a low-rank SVD sketch of the accumulated Hessian, constrained online Newton updates in parameter estimation and $Kd \times K$ spectral-norm computations in the reward bonus are reduced to one-dimensional root-finding tasks and $K \times K$ eigenvalue computations, respectively. This yields dominant per-round time complexity $\mathcal{O}(Kd(m+K)^2)$ and space complexity $\mathcal{O}(Kd(m+K))$, where $m \ll d$ is the sketch size. We further prove a regret bound of $\tilde{\mathcal{O}}(Δ_T(Kd\lnΔ_T+m)\sqrt{T})$, where the sketching error factor $Δ_T$ is controlled by the $m$-truncated spectral tail of the Hessian. Thus, when the Hessian is approximately low-rank, the regret is close to that of OFUL-MLogB. Experiments validate the computational efficiency and competitive performance.
- Abstract（参考訳）: 本稿では,多項ロジスティック・バンディット(MLogB)の効率的なオンラインアルゴリズムについて検討する。そこでは,$K+1$以上のフィードバック分布が$d$次元アクションベクトルの多項ロジスティックモデルに従う。
代表的 UCB 型アルゴリズム OFUL-MLogB は、$\tilde{\mathcal{O}}(Kd\sqrt{T})$の後悔境界を達成しているが、高次元の設定ではパラメータ推定と楽観的な報酬構成により、時間と$\mathcal{O}(K^3d^3)$の時間と$\mathcal{O}(K^2d^2)$の空間を必要とする。
この制限に対処するため,OFD-MLogBを提案する。
蓄積したHessianの低ランクSVDスケッチを維持することにより、パラメータ推定における制約のあるNewton更新と、報酬ボーナスにおけるスペクトルノルム計算を、それぞれ1次元のルートフィニングタスクと$K \times K$固有値計算に還元する。
これにより、単位時間あたりの複雑性は$\mathcal{O}(Kd(m+K)^2)$、空間複雑性は$\mathcal{O}(Kd(m+K))$となり、$m \ll d$はスケッチサイズである。
さらに、$\tilde{\mathcal{O}}(Δ_T(Kd\lnΔ_T+m)\sqrt{T})$の後悔境界を証明する。
したがって、ヘッセンがほぼ低ランクである場合、後悔はOFUL-MLogBに近い。
実験は計算効率と競争性能を検証する。
関連論文リスト
- Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Enjoying Non-linearity in Multinomial Logistic Bandits [56.28491566735463]
我々は,学習者が期待される報酬を最大化するために行動を選択することで,学習者が環境と相互作用する,多項ロジスティック・バンディット問題を考える。
本稿では,ロジスティックモデルの非線形性の影響を多項集合に拡張し,効率的なアルゴリズムを提案する。
我々のメソッドは、次数 $ smashwidetildemathcalO(R d sqrtKT/kappa_*)$ の問題依存的後悔境界を生じる。
論文 参考訳（メタデータ） (2025-07-07T08:18:25Z) - Displacement-Sparse Neural Optimal Transport [6.968698312185846]
最適輸送(OT)は、コスト関数を最小化しながら、ある確率測度から別の確率測度へ質量を輸送するマップ$T$を見つけることを目的としている。
ニューラルOTソルバは、薬物摂動などの高次元生物学的応用で人気を博している。
直感的で理論的に基礎を成す手法として,ニューラルOTソルバ内におけるエンファスメント・スパースマップの学習手法を提案する。
論文 参考訳（メタデータ） (2025-02-03T23:44:17Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。
逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。
設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
論文 参考訳（メタデータ） (2024-06-10T17:44:11Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Perturbation Analysis of Randomized SVD and its Applications to Statistics [8.731676546744353]
RSVD(英: RSVD)は、大規模データ行列の切り詰められたSVDを計算するための計算効率のよいアルゴリズムのクラスである。
本稿では、$ell$ と $ell_2,infty$ の正則特異ベクトル $widehatmathbfU$ と $widehatmathbfM$ の上限を導出する。
理論結果を、$widehatmathbfM$ が観測されていない信号行列 $mathbfM$ の加法摂動であるような設定に適用する。
論文 参考訳（メタデータ） (2022-03-19T07:26:45Z) - Nonparametric Learning of Two-Layer ReLU Residual Units [22.870658194212744]
本稿では,線形整列ユニット(ReLU)を活性化した2層残基を学習するアルゴリズムについて述べる。
解析最小化器はそのパラメータと非線形性の観点から、正確な地上構造ネットワークを表現できる機能として層ワイドな目的を設計する。
我々は,アルゴリズムの統計的強い一貫性を証明し,実験によるアルゴリズムの堅牢性とサンプル効率を実証する。
論文 参考訳（メタデータ） (2020-08-17T22:11:26Z) - Variational Orthogonal Features [29.636483122130027]
我々は,ある先行して,エビデンスローバウンド(ELBO)のミニバッチ推定を$mathcalO(M3)$コストで計算する機能を定義できることを示す。
我々は,不偏推定器をELBOに,$mathcalO(tildeNT+M2T)$および$mathcalO(tildeNT+MT)$で$T$ Monte Carloサンプルを用いて計算できる固定前カーネルの構成について述べる。
論文 参考訳（メタデータ） (2020-06-23T17:18:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。