論文の概要: Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret

• arxiv url: http://arxiv.org/abs/2609.10981v1
• Date: Thu, 10 Sep 2026 01:58:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 23:53:35.179577
• Title: Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret
• Title（参考訳）: 非モノトン凸リッジバンドのトンプソンサンプリング:ポリノミアルレジストにはモノトニック性は必要ない
• Abstract要約: 我々は、トンプソンサンプリング (TS) が、凸エンフォモノトン尾根の損失を伴う包帯凸最適化に対してベイズ的後悔$tilde O(d5/2sqrt n)$を持つことを証明した。
• 参考スコア（独自算出の注目度）: 6.657272312990604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bakhtiari, Lattimore and Szepesvári (COLT 2025) proved that Thompson sampling (TS) has Bayesian regret $\tilde O(d^{5/2}\sqrt n)$ for bandit convex optimisation with convex \emph{monotone} ridge losses $f(x)=\ell(\ip{x}θ)$, and asked whether monotonicity of the link is necessary. We give a qualitative negative answer. For every prior on $[0,1]$-valued, $1$-Lipschitz convex ridge losses with an arbitrary convex, possibly non-monotone, link, and for any fixed measurable selection of minimisers, exact-posterior TS has Bayesian regret $O\big((d+1)^4\sqrt{dn}\,\log(e+nd\max\{1,\diam K\})\big)=\tilde O(d^{9/2}\sqrt n)$. The monotone proof relies on a single-removal John-ellipsoid dichotomy; we show by an explicit twelve-point configuration that this dichotomy fails for non-monotone links, and replace it by an $O(d^2)$ cardinality bound for ``uninformative'' configurations. The bound uses a Boolean rounding argument: a $0$-$1$ matrix within $1/(4r)$ in max-norm of a rank-$r$ matrix has rank at most $2r-1$. We construct $d(d+1)$ uninformative losses, showing that the cardinality bound is tight up to constants in the large-diameter-to-gap regime, and give a self-contained information-ratio-to-regret transfer that is uniform over fixed measurable selections. Whether the $d^{5/2}$ dependence of the monotone case can be retained remains open.
• Abstract（参考訳）: Bakhtiari, Lattimore and Szepesvári (COLT 2025) は、トンプソンサンプリング (TS) がベイズ的後悔$\tilde O(d^{5/2}\sqrt n)$ for bandit convex optimization with convex \emph{monotone} ridge loss $f(x)=\ell(\ip{x}θ)$ であることを示した。 我々は質的な否定的な答えを与える。 0,1]$-valued, $1$-Lipschitz convex ridge loss with an arbitrary convex, potentially non-monotone, link, and for any fixed measurable selection of minimisers, exact-posterior TS has Bayesian regret $O\big((d+1)^4\sqrt{dn}\,\log(e+nd\max\{1,\diam K\})\big)=\tilde O(d^{9/2}\sqrt n)$. 単調証明は単調なジョン・エリプソイド二分法に依存しており、この二分法は非単調リンクでは失敗し、 '`uninformative' の構成では$O(d^2)$濃度で置き換える、明示的な12点構成によって示される。 0$-$1$行列が1/(4r)$以内のランク-$r$行列は最高2r-1$である。 我々は$d(d+1)$uninformative lossを構築し、その濃度境界が大径対ギャップ状態の定数に密接であることを示し、固定可測選択に一様である自己完結した情報比対レグレット転送を与える。 単調ケースの$d^{5/2}$依存が維持できるかどうかは未定のままである。

関連論文リスト

• Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression [0.0]
  有限データセットの完全なデータ損失を回復する重み付き例の最小予算は、正確に$n*(d,m)=(m+1)d$であることを示す。 直近の未送付プリプリントで循環する誤ったクレームを補正すると、$m=2$の明示的なデータセットが示され、2d$ポイントの重み付き選択がなければ、最適損失が回復する。
  論文  参考訳（メタデータ） (2026-08-31T05:04:49Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。 すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。 指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
  論文  参考訳（メタデータ） (2026-08-27T01:31:46Z)
• The sharp SAT/UNSAT phase transition in random ellipsoid fitting [5.7652356955571085]
  エンフェレプソイド整合は行列 $S succeq 0$ であり、すべての$i$に対して$x_itop S x_i =d$ となる。 我々は、ソーンダーソン、パリロ、ウィルスキーの予想を証明し、$n,d を infty$ にすると、この半確定実現可能性問題は $n sim d2/4$ で急移行する。
  論文  参考訳（メタデータ） (2026-08-10T19:55:11Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization [4.774251262663345]
  我々は,$widetilde(d5/4sqrt T)$が$dsqrtT$よりも速く成長することを示す。 これは、この問題に対して$dsqrtT$よりも早く成長する最初の非自明な後悔の低い境界を示す。
  論文  参考訳（メタデータ） (2026-07-21T02:44:33Z)
• On the Power of Adaptivity for $\varepsilon$-Best Arm Identification in Linear Bandits [8.86974002494041]
  線形包帯における$varepsilon$-best腕識別のミニマックスサンプル複雑性について検討した。 目標は、$langle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x,rangle ge max_xinmathcalX langle x であるようなarm $widehatxinmathcalX$を出力することである。
  論文  参考訳（メタデータ） (2026-05-15T06:35:31Z)
• Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds [7.787109481104569]
  ランダムシャッフルに基づくサブサンプリングによるDP-SGDのトレードオフ関数の厳密な解析を導出する。 Berry-Esseenの定理によって導かれる我々の具体的な境界は、証明フレームワーク内の定数要素に密着している。
  論文  参考訳（メタデータ） (2026-05-07T13:35:43Z)
• Variance-Dependent Regret Lower Bounds for Contextual Bandits [65.93854043353328]
  これは従来の$tildeO(dsqrtK)$ regret bound to $tildeO(dsqrtsum_k=1Ksigma_k2)$で改善されている。
  論文  参考訳（メタデータ） (2025-03-15T07:09:36Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。 観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-26T21:54:31Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)
• Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
  本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。 Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
  論文  参考訳（メタデータ） (2020-01-25T14:44:53Z)

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

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