論文の概要: A Truncated Newton Method for Optimal Transport

• arxiv url: http://arxiv.org/abs/2504.02067v1
• Date: Wed, 02 Apr 2025 19:00:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-12 00:52:56.188636
• Title: A Truncated Newton Method for Optimal Transport
• Title（参考訳）: トランク化ニュートン法による最適輸送
• Authors: Mete Kemertas, Amir-massoud Farahmand, Allan D. Jepson,
• Abstract要約: 本稿では, エントロピック規則化最適輸送(OT)解法のための特殊トランケートニュートンアルゴリズムを提案する。 提案アルゴリズムは実行時性能が極めて良好であり,既存の多くの選択肢よりも高精度な順序を達成できる。 アルゴリズムのスケーラビリティは、非常に大きなOT問題に対して、約106$の$n近似で示され、エントロピー正則化の弱さの下で解決される。
• 参考スコア（独自算出の注目度）: 13.848861021326755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Developing a contemporary optimal transport (OT) solver requires navigating trade-offs among several critical requirements: GPU parallelization, scalability to high-dimensional problems, theoretical convergence guarantees, empirical performance in terms of precision versus runtime, and numerical stability in practice. With these challenges in mind, we introduce a specialized truncated Newton algorithm for entropic-regularized OT. In addition to proving that locally quadratic convergence is possible without assuming a Lipschitz Hessian, we provide strategies to maximally exploit the high rate of local convergence in practice. Our GPU-parallel algorithm exhibits exceptionally favorable runtime performance, achieving high precision orders of magnitude faster than many existing alternatives. This is evidenced by wall-clock time experiments on 24 problem sets (12 datasets $\times$ 2 cost functions). The scalability of the algorithm is showcased on an extremely large OT problem with $n \approx 10^6$, solved approximately under weak entopric regularization.
• Abstract（参考訳）: 現代的な最適トランスポート(OT)解決器の開発には、GPU並列化、高次元問題へのスケーラビリティ、理論的収束保証、精度対実行時の経験的性能、実際の数値安定性など、いくつかの重要な要件のトレードオフをナビゲートする必要がある。 これらの課題を念頭に、エントロピック規則化OTのための特別切り離されたニュートンアルゴリズムを導入する。 リプシッツ・ヘッセンを仮定せずに局所二次収束が可能であることを証明することに加えて、我々は実際に局所収束の高率を最大限に活用するための戦略を提供する。 我々のGPU並列アルゴリズムは、非常に良好な実行時性能を示し、既存の多くの選択肢よりも高精度な順序を達成している。 これは24の問題集合(12データセット$\times$2コスト関数)のウォールクロック時間実験によって証明されている。 アルゴリズムのスケーラビリティは、極端に大きな OT 問題に対して、約$n \approx 10^6$ で示される。

関連論文リスト

• Quantum Hamiltonian Descent for Non-smooth Optimization [7.773836776652785]
  古典的アルゴリズムの限界を克服するために量子力学をどのように活用するかを検討する。 本稿では,非平滑なグローバルコンバージェンス問題に対して,新しい設計によるグローバルコンバージェンス率を提案する。 さらに,新しいLynov関数を用いて離散時間QHDを完全デジタル化する手法を提案する。
  論文  参考訳（メタデータ） (2025-03-20T06:02:33Z)
• Solving quadratic binary optimization problems using quantum SDP methods: Non-asymptotic running time analysis [1.9081120388919084]
  量子コンピュータは、最先端の古典的手法よりも優れたスケールのリソースを用いて、半定値プログラム(SDP)を解くことができる。 本稿では,量子SDPソルバの非漸近的リソース要求の解析を行う。
  論文  参考訳（メタデータ） (2025-02-21T12:54:05Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients [13.848861021326755]
  ミラーDescent Optimal Transport (MDOT) は、離散最適輸送(OT)問題を高精度に解くための新しい方法である。 MDOT は既存の OT ソルバの代表的な集合よりもはるかに高速で高精度で実現可能な解が得られることを示す。
  論文  参考訳（メタデータ） (2023-07-17T14:09:43Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• 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)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)

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

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