論文の概要: Pushing the Limits of the Reactive Affine Shaker Algorithm to Higher Dimensions
- arxiv url: http://arxiv.org/abs/2502.12877v1
- Date: Tue, 18 Feb 2025 14:06:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-19 14:05:22.498413
- Title: Pushing the Limits of the Reactive Affine Shaker Algorithm to Higher Dimensions
- Title(参考訳): 反応性アフィンシェーカーアルゴリズムの限界を高次元にプッシュする
- Authors: Roberto Battiti, Mauro Brunato,
- Abstract要約: 反応アフィンシェーカー (RAS) は、非常に大きな次元空間を探索するための単純なアルゴリズムである。
その単純さとローカル検索のみの利用にもかかわらず、驚くほど結果がBOの最先端の結果と同等であり、それほど遠くない。
- 参考スコア(独自算出の注目度): 0.4143603294943439
- License:
- Abstract: Bayesian Optimization (BO) for the minimization of expensive functions of continuous variables uses all the knowledge acquired from previous samples (${\boldsymbol x}_i$ and $f({\boldsymbol x}_i)$ values) to build a surrogate model based on Gaussian processes. The surrogate is then exploited to define the next point to sample, through a careful balance of exploration and exploitation. Initially intended for low-dimensional spaces, BO has recently been modified and used also for very large-dimensional spaces (up to about one thousand dimensions). In this paper we consider a much simpler algorithm, called "Reactive Affine Shaker" (RAS). The next sample is always generated with a uniform probability distribution inside a parallelepiped (the "box"). At each iteration, the form of the box is adapted during the search through an affine transformation, based only on the point $\boldsymbol x$ position and on the success or failure in improving the function. The function values are therefore not used directly to modify the search area and to generate the next sample. The entire dimensionality is kept (no active subspaces). Despite its extreme simplicity and its use of only stochastic local search, surprisingly the produced results are comparable to and not too far from the state-of-the-art results of high-dimensional versions of BO, although with some more function evaluations. An ablation study and an analysis of probability distribution of directions (improving steps and prevailing box orientation) in very large-dimensional spaces are conducted to understand more about the behavior of RAS and to assess the relative importance of the algorithmic building blocks for the final results.
- Abstract(参考訳): 連続変数の高価な関数の最小化のためのベイズ最適化(BO)は、ガウス過程に基づく代理モデルを構築するために、以前のサンプル({\boldsymbol x}_i$と$f({\boldsymbol x}_i)$ values)から得られた知識を全て利用する。
シュロゲートは次にサンプリングする点を定義するために利用され、探索とエクスプロイトの慎重にバランスを取る。
当初、低次元空間を意図していたBOは、最近、非常に大きな次元空間(最大約1000次元)にも修正され、使用されてきた。
本稿では、より単純なアルゴリズムとして、"Reactive Affine Shaker"(RAS)を提案する。
次のサンプルは、常に並列入力された(ボックス)内の均一な確率分布で生成される。
各イテレーションにおいて、ボックスの形式はアフィン変換を通して検索中に適応され、$\boldsymbol x$ 位置と、関数の改善における成功または失敗に基づいている。
したがって、関数値は、検索領域を変更して次のサンプルを生成するために直接使用されることはない。
全次元性は保たれる(活性部分空間は持たない)。
極端に単純であり、確率的局所探索しか使用していないにもかかわらず、生成した結果がBOの高次元バージョンの最先端の結果と同等であり、それほど遠くないが、より機能的な評価がいくつかある。
超大次元空間における方向の確率分布に関するアブレーション研究と解析を行い、RASの挙動についてより深く理解し、最終結果に対するアルゴリズム的ビルディングブロックの相対的重要性を評価する。
関連論文リスト
- Entangled Mean Estimation in High-Dimensions [36.97113089188035]
信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。
最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
論文 参考訳(メタデータ) (2025-01-09T18:31:35Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence
and Experiments [0.0]
本稿では,$frac1sqrtttをベースとした変形ステップサイズを改良することにより,勾配降下法(SGD)アルゴリズムの性能向上に新たなアプローチを提案する。
提案されたステップサイズは対数的なステップ項を統合し、最終イテレーションでより小さな値を選択する。
提案手法の有効性について,FashionMNISTとARARを用いて画像分類タスクの数値実験を行った。
論文 参考訳(メタデータ) (2023-09-03T19:21:59Z) - Algorithmic Gaussianization through Sketching: Converting Data into
Sub-gaussian Random Designs [22.925108493465363]
平均化によるデータ分布のガウシアン化のためのアルゴリズムフレームワークを提供する。
我々は、ガウス以下のランダムな設計とほとんど区別できないデータスケッチを効率的に構築できることを示す。
論文 参考訳(メタデータ) (2022-06-21T12:16:45Z) - Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap [24.073221004661427]
部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。
広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
論文 参考訳(メタデータ) (2022-05-26T17:47:35Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳(メタデータ) (2021-10-09T21:13:48Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳(メタデータ) (2021-06-15T02:23:07Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳(メタデータ) (2021-03-04T19:01:20Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳(メタデータ) (2020-05-26T17:53:18Z) - Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
多次元回帰を用いた固定設計の基本問題について検討する。
我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。
提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
論文 参考訳(メタデータ) (2020-03-24T19:39:34Z) - Frequentist Regret Bounds for Randomized Least-Squares Value Iteration [94.47472987987805]
有限水平強化学習(RL)における探索・探索ジレンマの検討
本稿では,ランダム化最小二乗値 (RLSVI) の楽観的な変種を紹介する。
マルコフ決定過程が低ランク遷移ダイナミクスを持つという仮定の下で、RSVIの頻繁な後悔は、$widetilde O(d2 H2 sqrtT)$$ d $ が特徴次元であり、$ H $ が地平線であり、$ T $ が総数であることを示す。
論文 参考訳(メタデータ) (2019-11-01T19:48:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。