論文の概要: From Random Search to Bandit Learning in Metric Measure Spaces
- arxiv url: http://arxiv.org/abs/2305.11509v1
- Date: Fri, 19 May 2023 08:18:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 15:37:59.536143
- Title: From Random Search to Bandit Learning in Metric Measure Spaces
- Title（参考訳）: 距離測度空間におけるランダム探索からバンディット学習へ
- Authors: Chuying Han, Yasong Feng, Tianyu Wang
- Abstract要約: 本稿ではランダム探索に関する理論的考察を行う。
基礎となる関数の風景を記述したエンフスキャッタリング次元の概念を導入する。
BLiN-MOSと呼ばれるアルゴリズムを導入し、ボレル測度を具現化した距離空間を2倍にする。
- 参考スコア（独自算出の注目度）: 5.195426298007092
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random Search is one of the most widely-used method for Hyperparameter
Optimization, and is critical to the success of deep learning models. Despite
its astonishing performance, little non-heuristic theory has been developed to
describe the underlying working mechanism. This paper gives a theoretical
accounting of Random Search. We introduce the concept of \emph{scattering
dimension} that describes the landscape of the underlying function, and
quantifies the performance of random search. We show that, when the environment
is noise-free, the output of random search converges to the optimal value in
probability at rate $ \widetilde{\mathcal{O}} \left( \left( \frac{1}{T}
\right)^{ \frac{1}{d_s} } \right) $, where $ d_s \ge 0 $ is the scattering
dimension of the underlying function. When the observed function values are
corrupted by bounded $iid$ noise, the output of random search converges to the
optimal value in probability at rate $ \widetilde{\mathcal{O}} \left( \left(
\frac{1}{T} \right)^{ \frac{1}{d_s + 1} } \right) $. In addition, based on the
principles of random search, we introduce an algorithm, called BLiN-MOS, for
Lipschitz bandits in doubling metric spaces that are also emdowed with a Borel
measure, and show that BLiN-MOS achieves a regret rate of order $
\widetilde{\mathcal{O}} \left( T^{ \frac{d_z}{d_z + 1} } \right) $, where $d_z$
is the zooming dimension of the problem instance. Our results show that in
metric spaces with a Borel measure, the classic theory of Lipschitz bandits can
be improved. This result suggests an intrinsic axiomatic gap between metric
spaces and metric measure spaces from an algorithmic perspective, since the
upper bound in a metric measure space breaks the known information-theoretical
lower bounds for Lipschitz bandits in a metric space with no measure structure.
- Abstract（参考訳）: ランダム検索はハイパーパラメータ最適化の最も広く使われている手法の1つであり、ディープラーニングモデルの成功に不可欠である。
驚くべき性能にもかかわらず、基礎となる作用機構を記述するために非ヒューリスティック理論はほとんど開発されていない。
本稿ではランダム探索に関する理論的考察を行う。
本稿では,基礎となる関数のランドスケープを記述する「emph{scattering dimension}」の概念を導入し,ランダム探索の性能を定量化する。
環境がノイズのない場合、ランダム探索の出力はレート $ \widetilde{\mathcal{o}} \left( \left( \frac{1}{t} \right)^{ \frac{1}{d_s} } \right) $ の確率において最適値に収束する。
観測された関数値が有界な$iid$ノイズによって破損した場合、ランダム探索の出力は、$ \widetilde{\mathcal{O}} \left( \left( \frac{1}{T} \right)^{ \frac{1}{d_s + 1} } \right)$で確率の最適値に収束する。
さらに、ランダム探索の原理に基づき、ボレル測度を具現化した計量空間におけるリプシッツの帯域幅を2倍にするアルゴリズム「BLiN-MOS」を導入し、BLiN-MOSが次数$ \widetilde{\mathcal{O}} \left(T^{ \frac{d_z}{d_z + 1} } \right)$であることを示す。
この結果は、ボレル測度を持つ距離空間において、リプシッツバンドイットの古典的な理論が改善可能であることを示している。
この結果は、測度空間における上界が測度構造を持たない計量空間におけるリプシッツ包帯の既知の情報理論的下界を破るので、アルゴリズムの観点から距離空間と計量測度空間の間の固有の公理的ギャップが示唆される。
関連論文リスト
- Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
この論文は、一般的なマルコフ的な設定でステップサイズの選択を再考する。
大きな結論は、$rho =0$ または $rho1/2$ の選択は、選択した設定でのみ正当化されるということである。
論文 参考訳（メタデータ） (2024-05-28T05:11:05Z) - Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - High Probability Guarantees for Random Reshuffling [5.663909018247509]
非行列最適化問題に対処するために、ランダムリシャッフル(mathsfRR$)の勾配法を検討する。
本研究ではまず,$mathsfRR$sサンプリング手順におけるニューラルネットワークの複雑さについて検討する。
そこで我々は,乱数化摂動手順の定常点を含むランダムリシャッフル法(mathsfp$mathsfRR$)を設計する。
論文 参考訳（メタデータ） (2023-11-20T15:17:20Z) - Optimal Exploration is no harder than Thompson Sampling [14.726673043806391]
a pure exploration linear bandit problem to return $argmax_zin mathcalZ ztoptheta_ast with $xtoptheta_ast with $xin mathcalXsubset mathbbRd$。
この複雑さは、後続サンプリングとargmaxオラクルへのアクセスを必要とするだけであり、$mathcalZ$を列挙する必要がない、後悔の最小化のために人気で単純なトンプソンサンプリングと矛盾する。
論文 参考訳（メタデータ） (2023-10-09T18:21:39Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Randomized Exploration is Near-Optimal for Tabular MDP [45.16374124699648]
強化学習におけるThompson Sampling(TS)ライクアルゴリズムにおけるランダム化値関数を用いた探索について検討する。
1)1つのランダムシードを各エピソードで使用し、2)ベルンシュタイン型のノイズの大きさを算出すると、最悪の$widetildeOleft(HsqrtSATright)$リコールがエピソード時間非均質決定プロセスにバインドされることを示します。
論文 参考訳（メタデータ） (2021-02-19T01:42:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。