論文の概要: Learning Complexity of Simulated Annealing
- arxiv url: http://arxiv.org/abs/2003.02981v2
- Date: Mon, 29 Jun 2020 21:17:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-26 00:34:30.318737
- Title: Learning Complexity of Simulated Annealing
- Title（参考訳）: 模擬アニーリングの学習複雑さ
- Authors: Avrim Blum, Chen Dan, Saeed Seddighin
- Abstract要約: 本研究では,温度変化の基準,すなわち冷却スケジュールについて検討する。
サンプルの複雑さとシミュレーションの複雑さの両面から肯定的な結果が得られる。
本稿では,学習問題に対する証明可能な保証付き時間アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 23.678288517578764
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Simulated annealing is an effective and general means of optimization. It is
in fact inspired by metallurgy, where the temperature of a material determines
its behavior in thermodynamics. Likewise, in simulated annealing, the actions
that the algorithm takes depend entirely on the value of a variable which
captures the notion of temperature. Typically, simulated annealing starts with
a high temperature, which makes the algorithm pretty unpredictable, and
gradually cools the temperature down to become more stable.
A key component that plays a crucial role in the performance of simulated
annealing is the criteria under which the temperature changes namely, the
cooling schedule. Motivated by this, we study the following question in this
work: "Given enough samples to the instances of a specific class of
optimization problems, can we design optimal (or approximately optimal) cooling
schedules that minimize the runtime or maximize the success rate of the
algorithm on average when the underlying problem is drawn uniformly at random
from the same class?"
We provide positive results both in terms of sample complexity and simulation
complexity. For sample complexity, we show that $\tilde O(\sqrt{m})$ samples
suffice to find an approximately optimal cooling schedule of length $m$. We
complement this result by giving a lower bound of $\tilde \Omega(m^{1/3})$ on
the sample complexity of any learning algorithm that provides an almost optimal
cooling schedule. These results are general and rely on no assumption. For
simulation complexity, however, we make additional assumptions to measure the
success rate of an algorithm. To this end, we introduce the monotone stationary
graph that models the performance of simulated annealing. Based on this model,
we present polynomial time algorithms with provable guarantees for the learning
problem.
- Abstract（参考訳）: シミュレーションアニーリングは、効果的で一般的な最適化方法である。
実際には、物質の温度が熱力学の挙動を決定づけるメタロギーにインスパイアされている。
同様に、シミュレート・アニーリングでは、アルゴリズムが行う動作は、温度の概念をキャプチャする変数の値に完全に依存する。
通常、シミュレーションされたアニールは高温から始まり、アルゴリズムはかなり予測不能になり、徐々に温度を下げてより安定になる。
シミュレート・アニーリングの性能において重要な役割を果たす重要な要素は、温度が変化する条件、すなわち冷却スケジュールである。
最適化問題の特定のクラスのインスタンスに十分なサンプルを割り当てることで、サンプルの複雑さとシミュレーションの複雑さの両方において、ランタイムを最小化する最適な(あるいはほぼ最適)冷却スケジュールを設計できるか、または、基礎となる問題を同じクラスからランダムにランダムに描画する場合、平均でアルゴリズムの成功率を最大化できるか?
サンプルの複雑さについて、$\tilde O(\sqrt{m})$サンプルは、長さ$m$のほぼ最適な冷却スケジュールを見つけるのに十分であることを示す。
この結果は、ほぼ最適な冷却スケジュールを提供する学習アルゴリズムのサンプル複雑性に基づいて、$\tilde \omega(m^{1/3})$という下限を与えることによって補完する。
これらの結果は一般的であり、仮定に頼らない。
しかし、シミュレーションの複雑さについては、アルゴリズムの成功率を測定するために追加の仮定を行う。
そこで本研究では,シミュレートアニーリングの性能をモデル化するモノトーン定常グラフを提案する。
このモデルに基づいて,学習問題に対する証明可能な保証付き多項式時間アルゴリズムを提案する。
関連論文リスト
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳（メタデータ） (2024-11-21T10:26:17Z) - Uniform Generalization Bound on Time and Inverse Temperature for
Gradient Descent Algorithm and its Application to Analysis of Simulated
Annealing [0.0]
勾配ランゲヴィン力学の時間と逆温度に縛られる新しい一様一般化を提案する。
応用一般化として、有効性の評価を示す。
論文 参考訳（メタデータ） (2022-05-25T01:21:27Z) - An Algebraically Converging Stochastic Gradient Descent Algorithm for
Global Optimization [14.336473214524663]
アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。
アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。
アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
論文 参考訳（メタデータ） (2022-04-12T16:27:49Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z) - Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。
提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
論文 参考訳（メタデータ） (2020-12-07T14:58:16Z) - A Simulated Annealing Algorithm for Joint Stratification and Sample
Allocation Designs [0.0]
本研究は, 模擬焼鈍とデルタ評価を組み合わせることで, 接合層化および試料配置問題の解法である。
この問題では、原子層は互いに排他的で総括的に全能的な層に分割される。
可能な解のベル数は、適度な数の原子層でさえも巨大であり、各解の評価時間とともに、さらなる複雑さの層が加えられる。
論文 参考訳（メタデータ） (2020-11-25T20:27:49Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - CoolMomentum: A Method for Stochastic Optimization by Langevin Dynamics
with Simulated Annealing [23.87373187143897]
深層学習アプリケーションは、複数の局所ミニマを持つ非目的関数を大域的に最適化する必要がある。
物理シミュレーションでも同様の問題を解くために座標学習アルゴリズムが利用できることを示す。
論文 参考訳（メタデータ） (2020-05-29T14:44:24Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z) - A Near-Optimal Gradient Flow for Learning Neural Energy-Based Models [93.24030378630175]
学習エネルギーベースモデル(EBM)の勾配流を最適化する新しい数値スキームを提案する。
フォッカー・プランク方程式から大域相対エントロピーの2階ワッサーシュタイン勾配流を導出する。
既存のスキームと比較して、ワッサーシュタイン勾配流は実データ密度を近似するより滑らかで近似的な数値スキームである。
論文 参考訳（メタデータ） (2019-10-31T02:26:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。