論文の概要: On algorithmically boosting fixed-point computations
- arxiv url: http://arxiv.org/abs/2304.04665v1
- Date: Tue, 4 Apr 2023 07:26:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-16 22:24:07.760424
- Title: On algorithmically boosting fixed-point computations
- Title(参考訳): アルゴリズムによる不動点計算の高速化について
- Authors: Ioannis Avramopoulos and Nikolaos Vasiloglou
- Abstract要約: 本稿では,反復的不動点計算の収束性を高める方法を提案する。
本稿では,アルゴリズムによる高速化により,収束速度の指数関数的高速化が実現可能であることを示す。
次に、非収束連続流れを収束するツールを提供するアルゴリズムの強化に対する変分的アプローチを検討する。
- 参考スコア(独自算出の注目度): 1.182080439211329
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper is a thought experiment on exponentiating algorithms. One of the
main contributions of this paper is to show that this idea finds material
implementation in exponentiating fixed-point computation algorithms. Various
problems in computer science can be cast as instances of computing a fixed
point of a map. In this paper, we present a general method of boosting the
convergence of iterative fixed-point computations that we call algorithmic
boosting, which is a (slight) generalization of algorithmic exponentiation. We
first define our method in the general setting of nonlinear maps. Secondly, we
restrict attention to convergent linear maps and show that our algorithmic
boosting method can set in motion exponential speedups in the convergence rate.
Thirdly, we show that algorithmic boosting can convert a (weak) non-convergent
iterator to a (strong) convergent one. We then consider a variational approach
to algorithmic boosting providing tools to convert a non-convergent continuous
flow to a convergent one. We, finally, discuss implementations of the
exponential function, an important issue even for the scalar case.
- Abstract(参考訳): 本論文は,指数化アルゴリズムに関する思考実験である。
本稿の主な貢献の1つは、このアイデアが固定点計算アルゴリズムの指数化における物質的実装を見出すことを示すことである。
コンピュータ科学における様々な問題は、地図の不動点を計算する例としてキャストすることができる。
本稿では,アルゴリズム指数の(軽い)一般化であるアルゴリズムブースティングと呼ばれる反復的不動点計算の収束を促進させる一般的な方法を提案する。
まず,非線形写像の一般設定で本手法を定義する。
第2に,収束線形写像への注意を制限し,このアルゴリズムにより収束速度の指数的高速化を実現できることを示す。
第三に、アルゴリズム的ブースティングは(弱)非収束イテレータを(強)収束イテレータに変換することができることを示す。
次に,非収束連続流を収束流に変換するためのアルゴリズム的ブースティングツールに対する変分的アプローチを検討する。
最後に指数関数の実装について論じるが、これはスカラーの場合でさえ重要な問題である。
関連論文リスト
- Convergence of Some Convex Message Passing Algorithms to a Fixed Point [0.0]
グラフィカルモデルにおけるMAP推論問題に対する一般的なアプローチは、双対線型計画法や(ブロック座標)降下によるラグランジュ緩和から得られる上限を最小化することである。
より強い結果(これは以前予想されたが、決して証明されなかった)を証明します。
本研究の主な結果とは対照的に,制約付き最適化問題に適用された座標降下の類似バージョンは収束しないことを示す。
論文 参考訳(メタデータ) (2024-03-07T13:14:21Z) - A fixed-point algorithm for matrix projections with applications in
quantum information [7.988085110283119]
このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。
量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
論文 参考訳(メタデータ) (2023-12-22T11:16:11Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - An Algebraically Converging Stochastic Gradient Descent Algorithm for
Global Optimization [14.336473214524663]
アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。
アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。
アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
論文 参考訳(メタデータ) (2022-04-12T16:27:49Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。
我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。
これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文 参考訳(メタデータ) (2022-04-07T00:11:05Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳(メタデータ) (2020-06-24T07:40:31Z) - Dynamical perturbation theory for eigenvalue problems [0.0]
提案アルゴリズムは,通常のレイリー=シュル・オーディンガー展開を3つの数で上回ることを示す。
また,本手法は汎用固有値ルーチンよりも行列のサイズがよい。
論文 参考訳(メタデータ) (2020-02-28T17:13:22Z) - On the Dual Formulation of Boosting Algorithms [92.74617630106559]
AdaBoost,LogitBoost,Soft-marginBoostのラグランジュ問題は、すべて一般化されたヒンジ損失エントロピーの双対問題であることを示す。
これらのブースティングアルゴリズムの2つの問題を見て、より良いマージン分布を維持するという観点から、ブースティングの成功を理解することができることを示す。
論文 参考訳(メタデータ) (2009-01-23T02:14:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。