論文の概要: Improving the Efficiency of Gradient Descent Algorithms Applied to
Optimization Problems with Dynamical Constraints
- arxiv url: http://arxiv.org/abs/2208.12834v1
- Date: Fri, 26 Aug 2022 18:26:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-30 14:40:57.463317
- Title: Improving the Efficiency of Gradient Descent Algorithms Applied to
Optimization Problems with Dynamical Constraints
- Title（参考訳）: 動的制約付き最適化問題に適用した勾配降下アルゴリズムの効率向上
- Authors: Ion Matei, Maksym Zhenirovskyy, Johan de Kleer and John Maxwell
- Abstract要約: 通常の微分方程式を用いて最適化問題を解くための2つのブロック座標降下アルゴリズムを提案する。
このアルゴリズムは損失関数勾配を評価するために直接または随伴感度解析法を実装する必要はない。
- 参考スコア（独自算出の注目度）: 3.3722008527102894
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We introduce two block coordinate descent algorithms for solving optimization
problems with ordinary differential equations (ODEs) as dynamical constraints.
The algorithms do not need to implement direct or adjoint sensitivity analysis
methods to evaluate loss function gradients. They results from reformulation of
the original problem as an equivalent optimization problem with equality
constraints. The algorithms naturally follow from steps aimed at recovering the
gradient-decent algorithm based on ODE solvers that explicitly account for
sensitivity of the ODE solution. In our first proposed algorithm we avoid
explicitly solving the ODE by integrating the ODE solver as a sequence of
implicit constraints. In our second algorithm, we use an ODE solver to reset
the ODE solution, but no direct are adjoint sensitivity analysis methods are
used. Both algorithm accepts mini-batch implementations and show significant
efficiency benefits from GPU-based parallelization. We demonstrate the
performance of the algorithms when applied to learning the parameters of the
Cucker-Smale model. The algorithms are compared with gradient descent
algorithms based on ODE solvers endowed with sensitivity analysis capabilities,
for various number of state size, using Pytorch and Jax implementations. The
experimental results demonstrate that the proposed algorithms are at least 4x
faster than the Pytorch implementations, and at least 16x faster than Jax
implementations. For large versions of the Cucker-Smale model, the Jax
implementation is thousands of times faster than the sensitivity analysis-based
implementation. In addition, our algorithms generate more accurate results both
on training and test data. Such gains in computational efficiency is paramount
for algorithms that implement real time parameter estimations, such as
diagnosis algorithms.
- Abstract（参考訳）: 通常の微分方程式(ODE)を用いた最適化問題を動的制約として解くための2つのブロック座標降下アルゴリズムを導入する。
このアルゴリズムは損失関数勾配を評価するために直接または随伴感度解析法を実装する必要はない。
それらは、等式制約を伴う等価最適化問題として元の問題の再構成から生じる。
アルゴリズムは、ODEソリューションの感度を明示的に考慮したODEソルバに基づく勾配重み付けアルゴリズムの回復を目的としたステップから自然に従う。
最初に提案したアルゴリズムでは, ODEソルバを暗黙の制約列として統合することで, ODEを明示的に解くことを避ける。
第2のアルゴリズムでは、ODEソルバを用いてODE解をリセットするが、直接随伴感度解析法は使用しない。
どちらのアルゴリズムもミニバッチの実装を受け入れ、GPUベースの並列化による大きな効率性を示している。
本稿では,Cucker-Smaleモデルのパラメータ学習に適用したアルゴリズムの性能を示す。
これらのアルゴリズムは、 Pytorch と Jax の実装を用いて、様々な状態サイズに対して感度解析能力を持つODE ソルバに基づく勾配降下アルゴリズムと比較される。
実験の結果,提案アルゴリズムはPytorchの実装よりも少なくとも4倍高速であり,Jaxの実装より少なくとも16倍高速であることがわかった。
Cucker-Smaleモデルの大規模なバージョンでは、Jaxの実装は感度分析ベースの実装よりも数千倍高速である。
さらに、我々のアルゴリズムは、トレーニングデータとテストデータの両方でより正確な結果を生成する。
このような計算効率の向上は、診断アルゴリズムのようなリアルタイムパラメータ推定を実装するアルゴリズムにとって最重要である。
関連論文リスト
- Performance Evaluation of Evolutionary Algorithms for Analog Integrated
Circuit Design Optimisation [0.0]
本稿では,アナログ回路の自動サイズ化手法について述べる。
探索空間を対象とする探索は粒子生成関数と補修バウンド関数を用いて実装されている。
アルゴリズムは、より良い最適解に収束するように調整され、修正される。
論文 参考訳（メタデータ） (2023-10-19T03:26:36Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Hybrid ACO-CI Algorithm for Beam Design problems [0.4397520291340694]
The novel hybrid version of the Ant colony optimization (ACO) method was developed using the sample space reduction technique of the Cohort Intelligence (CI) algorithm。
提案した研究は、工学領域や医療問題を含む現実世界の応用について検討することができる。
論文 参考訳（メタデータ） (2023-03-29T04:37:14Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex
Minimax Machine Learning [12.069630105460766]
AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。
本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-22T04:33:27Z) - An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization [111.24899593052851]
条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。
ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
論文 参考訳（メタデータ） (2021-09-18T07:08:11Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Optimal and Practical Algorithms for Smooth and Strongly Convex
Decentralized Optimization [21.555331273873175]
ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。
本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
論文 参考訳（メタデータ） (2020-06-21T11:23:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。