論文の概要: 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に,収束線形写像への注意を制限し,このアルゴリズムにより収束速度の指数的高速化を実現できることを示す。 第三に、アルゴリズム的ブースティングは(弱)非収束イテレータを(強)収束イテレータに変換することができることを示す。 次に,非収束連続流を収束流に変換するためのアルゴリズム的ブースティングツールに対する変分的アプローチを検討する。 最後に指数関数の実装について論じるが、これはスカラーの場合でさえ重要な問題である。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。