論文の概要: Continuum-Armed Bandits: A Function Space Perspective
- arxiv url: http://arxiv.org/abs/2010.08007v4
- Date: Sun, 21 Mar 2021 22:22:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 03:42:37.241947
- Title: Continuum-Armed Bandits: A Function Space Perspective
- Title(参考訳): 連続整列バンド:関数空間の展望
- Authors: Shashank Singh
- Abstract要約: 本稿では, ベソフ平滑化条件下での連続武装バンディットについて検討する。
単純かつ累積的な後悔の下で、最小限の率を導き出す。
以上の結果から, ベソフ空間における目的関数に対する極小最大値は, ベソフ空間が埋め込まれる最小のH"古い空間における目的関数に対する極小最大値と同一であることが示された。
- 参考スコア(独自算出の注目度): 7.84669346764821
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Continuum-armed bandits (a.k.a., black-box or $0^{th}$-order optimization)
involves optimizing an unknown objective function given an oracle that
evaluates the function at a query point, with the goal of using as few query
points as possible. In the most well-studied case, the objective function is
assumed to be Lipschitz continuous and minimax rates of simple and cumulative
regrets are known in both noiseless and noisy settings. This paper studies
continuum-armed bandits under more general smoothness conditions, namely Besov
smoothness conditions, on the objective function. In both noiseless and noisy
conditions, we derive minimax rates under simple and cumulative regrets. Our
results show that minimax rates over objective functions in a Besov space are
identical to minimax rates over objective functions in the smallest H\"older
space into which the Besov space embeds.
- Abstract(参考訳): 連続武装バンディット(英: Continuum-armed bandits、別名 black-box または $0^{th}$-order optimization)は、クエリポイントで関数を評価するオラクルが与えられた未知の目的関数を最適化する。
最もよく研究されたケースでは、目的関数はリプシッツ連続であり、単純で累積な後悔の最小速度は無音と無音の両方で知られている。
本稿では,より汎用的な平滑性条件,すなわちベッソフ平滑性条件下での連続武装バンディットの客観的機能について検討する。
ノイズのない条件とノイズの多い条件の両方において、単純かつ累積的な後悔の下でミニマックスレートを導出する。
以上の結果から, ベソフ空間の目的関数に対するミニマックス速度は, ベソフ空間が埋め込まれる最小のH\"古い空間における目的関数に対するミニマックス速度と同一であることが示された。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Proportional Response: Contextual Bandits for Simple and Cumulative
Regret Minimization [29.579719765255927]
本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。
我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
論文 参考訳(メタデータ) (2023-07-05T08:34:54Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳(メタデータ) (2021-11-01T21:06:35Z) - Stochastic Subgradient Descent on a Generic Definable Function Converges
to a Minimizer [0.0]
この研究の最初の部分において、弱凸性仮定が第三のタイプの点に失敗したとき、鋭く反発的な臨界点が現れることを示す。
この研究の第2部では、列上の密度のような仮定の下で、下降降下(SGD)は確率1の急激な反発臨界点を避けることを示した。
論文 参考訳(メタデータ) (2021-09-06T13:35:56Z) - Direct-Search for a Class of Stochastic Min-Max Problems [0.0]
オラクルを通してのみ対象物にアクセスする導関数探索法について検討する。
この手法の収束性は軽微な仮定で証明する。
私達の分析は設定のminmax目的のための直接調査方法の収束に取り組む最初のものです。
論文 参考訳(メタデータ) (2021-02-22T22:23:58Z) - Off-Policy Interval Estimation with Lipschitz Value Iteration [29.232245317776723]
一般の連続した環境下での政治外評価のための区間境界を求めるための正当な手法を提案する。
リプシッツ値の反復法を導入し、単調に間隔を縮める。
論文 参考訳(メタデータ) (2020-10-29T07:25:56Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳(メタデータ) (2020-09-04T04:10:39Z) - Non-convex Min-Max Optimization: Applications, Challenges, and Recent
Theoretical Advances [58.54078318403909]
min-max問題(英: min-max problem)またはサドル点問題(英: saddle point problem)は、サムゲームにおいても研究されるクラス逆問題である。
論文 参考訳(メタデータ) (2020-06-15T05:33:42Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - On Suboptimality of Least Squares with Application to Estimation of
Convex Bodies [74.39616164169131]
雑音支援関数の測定から得られる凸を次元$dgeq 6$で推定する際、最小広場の最適性に関するオープンな問題を解決した。
Least Squaresは準最適であり、$tildeTheta_d(n-2/(d-1))$であるのに対して、minimaxレートは$Theta_d(n-4/(d+3)$である。
論文 参考訳(メタデータ) (2020-06-07T05:19:00Z) - Optimality and Stability in Non-Convex Smooth Games [39.365235811852365]
興味深い概念は局所ミニマックス点(英語版)として知られているが、これは降下と強く相関している。
勾配アルゴリズムは非退化の場合、局所的/言語的極小点に収束するが、一般的には失敗する。
これは、未知の滑らかなゲームにおいて、新しいアルゴリズムまたはサドル点を超える概念が必要であることを意味する。
論文 参考訳(メタデータ) (2020-02-27T02:16:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。