論文の概要: On algorithmically boosting fixed-point computations
- arxiv url: http://arxiv.org/abs/2304.04665v2
- Date: Mon, 25 Sep 2023 06:37:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-27 03:22:10.872411
- Title: On algorithmically boosting fixed-point computations
- Title（参考訳）: アルゴリズムによる不動点計算の高速化について
- Authors: Ioannis Avramopoulos and Nikolaos Vasiloglou
- Abstract要約: アルゴリズムブースティング(英: Algorithmic boosting)は、反復写像の(長期の)平均を取ることによって固定点を計算する原理である。
本研究では,アルゴリズムの高速化により,収束速度の指数的高速化が実現可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.9790236766474201
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The main topic of this paper are algorithms for computing Nash equilibria. We
cast our particular methods as instances of a general algorithmic abstraction,
namely, a method we call {\em algorithmic boosting}, which is also relevant to
other fixed-point computation problems. Algorithmic boosting is the principle
of computing fixed points by taking (long-run) averages of iterated maps and it
is a generalization of exponentiation. We first define our method in the
setting of nonlinear maps. Secondly, we restrict attention to convergent linear
maps (for computing dominant eigenvectors, for example, in the PageRank
algorithm) and show that our algorithmic boosting method can set in motion {\em
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 also consider a {\em variational approach} to algorithmic
boosting providing tools to convert a non-convergent continuous flow to a
convergent one. Then, by embedding the construction of averages in the design
of the iterated map, we constructively prove the existence of Nash equilibria
(and, therefore, Brouwer fixed points). We then discuss implementations of
averaging and exponentiation, an important matter even for the scalar case. We
finally discuss a relationship between dominant (PageRank) eigenvectors and
Nash equilibria.
- Abstract（参考訳）: この論文の主なトピックは、ナッシュ平衡の計算アルゴリズムである。
我々は,本手法を一般のアルゴリズム抽象化,すなわち,他の不動点計算問題にも関連する「アルゴリズムブースティング」と呼ぶ手法のインスタンスとしてキャストした。
アルゴリズムブースティングは、反復写像の(長期の)平均を取ることによって固定点を計算する原理であり、指数化の一般化である。
まず, この手法を非線形写像として定義する。
次に、収束線形写像(例えば、ページランクアルゴリズムにおいて支配的固有ベクトルを計算するために)への注意を限定し、アルゴリズム的ブースティング法が収束率の指数的速度アップを運動に設定できることを示す。
第三に、アルゴリズム的ブースティングは(弱)非収束イテレータを(強)収束イテレータに変換することができることを示す。
また,非収束連続流を収束流に変換するためのアルゴリズム的ブースティング支援ツールに対する変分法も検討する。
次に、反復写像の設計に平均の構成を組み込むことで、ナッシュ平衡の存在を構成的に証明する(従ってブラウアー不動点)。
次に、スカラーケースにおいても重要な問題である平均化と指数化の実装について議論する。
最終的に、支配的(PageRank)固有ベクトルとナッシュ平衡の関係について論じる。
関連論文リスト
- Approximating Metric Magnitude of Point Sets [4.522729058300309]
計量等級は、多くの望ましい幾何学的性質を持つ点雲の「大きさ」の尺度である。
様々な数学的文脈に適応しており、最近の研究は機械学習と最適化アルゴリズムを強化することを示唆している。
本稿では, 等級問題について検討し, 効率よく近似する方法を示し, 凸最適化問題として扱うことができるが, 部分モジュラ最適化としては適用できないことを示す。
本稿では,高速に収束し精度の高い反復近似アルゴリズムと,計算をより高速に行うサブセット選択法という,2つの新しいアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2024-09-06T17:15:28Z) - 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) - Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。