論文の概要: Instance-dependent Stochastic Lipschitz bandit

• arxiv url: http://arxiv.org/abs/2605.29748v1
• Date: Thu, 28 May 2026 10:46:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-30 02:45:56.188028
• Title: Instance-dependent Stochastic Lipschitz bandit
• Title（参考訳）: インスタンス依存型確率リプシッツバンドイット
• Authors: Marius Potfer, Vianney Perchet,
• Abstract要約: 学習者が未知のリプシッツ関数をドメイン上で逐次最大化するリプシッツバンドイット問題について検討する。 既存の後悔境界は最悪の場合であり、$tilde left (Td+1/d+2right )$としてスケールするか、ズーム次元$d_z$で適応する。 我々は、そのレベル集合上の$f$の準最適ギャップの積分を通して後悔を特徴づける分析とアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 28.946496440127603
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the Lipschitz bandit problem, where a learner sequentially maximizes an unknown Lipschitz function $f$ over a domain $\mathcal{X} \subset [0,1]^d$ using noisy pointwise evaluations. Existing regret bounds are either worst-case, scaling as $\tildeΘ \left ( T^{d+1/d+2}\right )$, or adaptive via the zooming dimension $d_z$, yielding $\tildeΘ \left ( T^{d_z+1/d_z+2}\right )$. However, such zooming-based guarantees are only partially instance-dependent, as they depend solely on the asymptotic growth of near-optimal level sets and fail to capture finer structural properties of $f$. We provide an analysis and an algorithm that characterizes the regret through integrals of the suboptimality gap of $f$ over its level sets. This yields regret bounds that adapt to the local growth of level sets, rather than only their asymptotic behavior. As a corollary, when the set of maximizers has dimension $d^\star>0$, we obtain improved adaptive rates of order $\tilde{\mathcal{O}} \left ( T^{d_z+1 / \max(d_z,d^\star)+2}\right )$ strictly improving over classical zooming bounds in this regime. Finally, we extend our analysis to the full-information setting (Lipschitz experts) and show how some of the regularity assumptions can be relaxed.
• Abstract（参考訳）: 学習者が未知のリプシッツ関数 $f$ を領域 $\mathcal{X} \subset [0,1]^d$ 上で次々に最大化するリプシッツ帯域問題を研究する。 既存の後悔境界は最悪の場合であり、$\tilde' \left (T^{d+1/d+2}\right )$としてスケールするか、ズーム次元$d_z$で適応し、$\tilde' \left (T^{d_z+1/d_z+2}\right )$となる。 しかし、そのようなズームングベースの保証は部分的にはインスタンス依存であり、それらは近最適準位集合の漸近的成長にのみ依存し、より微細な構造的特性を$f$で取得できないためである。 我々は、そのレベル集合上の$f$の準最適ギャップの積分を通して後悔を特徴づける分析とアルゴリズムを提供する。 このことは、その漸近的な振る舞いだけでなく、レベル集合の局所的な成長に適応する後悔の限界をもたらす。 結果として、最大値の集合が次元$d^\star>0$を持つとき、次数$\tilde{\mathcal{O}} \left (T^{d_z+1 / \max(d_z,d^\star)+2}\right )$ の適応率の改善が得られる。 最後に、分析結果を全情報設定(Lipschitz の専門家)に拡張し、正規性仮定のいくつかを緩和する方法を示す。

関連論文リスト

• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets [35.8717656676532]
  オンライン線形最適化では、損失関数の平均勾配が一定の閾値を超えると、実現可能な集合の曲率を利用することができることが知られている。 本研究では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
  論文  参考訳（メタデータ） (2024-02-20T09:59:33Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Nearly Optimal Algorithms for Level Set Estimation [21.83736847203543]
  線形包帯に対する最近の適応的実験設計手法と関連づけることで, レベルセット推定問題に対する新しいアプローチを提案する。 我々は、我々の境界がほぼ最適であることを示す。すなわち、我々の上限は、しきい値線形帯域に対して既存の下限と一致する。
  論文  参考訳（メタデータ） (2021-11-02T17:45:02Z)
• 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)
• 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)
• Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates [0.0]
  コンパクト部分集合 $mathcal X$ of $mathbb Rd$ 上で定義されるリプシッツ関数 $f$ のゼロ次(ブラックボックス)最適化の問題を研究する。 我々は、任意のリプシッツ関数 $f$ の評価の最適な個数を特徴付け、精度$varepsilon$ で$f$ の近似器を見つけて証明する。
  論文  参考訳（メタデータ） (2021-02-03T09:51:03Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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