論文の概要: Genetic column generation: Fast computation of high-dimensional
multi-marginal optimal transport problems
- arxiv url: http://arxiv.org/abs/2103.12624v1
- Date: Tue, 23 Mar 2021 15:24:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-24 19:52:54.945259
- Title: Genetic column generation: Fast computation of high-dimensional
multi-marginal optimal transport problems
- Title（参考訳）: 遺伝的列生成:多次元最適輸送問題の高速計算
- Authors: Gero Friesecke, Andreas S. Schulz, and Daniela V\"ogler
- Abstract要約: CG内の二重状態が「逆」の役割を果たすMMOT用に作られた遺伝的学習法を使用します。
最大120のグリッドポイントと最大30のマージンを持つベンチマーク問題に対して,本手法は常に精度を見出した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We introduce a simple, accurate, and extremely efficient method for
numerically solving the multi-marginal optimal transport (MMOT) problems
arising in density functional theory. The method relies on (i) the sparsity of
optimal plans [for $N$ marginals discretized by $\ell$ gridpoints each, general
Kantorovich plans require $\ell^N$ gridpoints but the support of optimizers is
of size $O(\ell\cdot N)$ [FV18]], (ii) the method of column generation (CG)
from discrete optimization which to our knowledge has not hitherto been used in
MMOT, and (iii) ideas from machine learning. The well-known bottleneck in CG
consists in generating new candidate columns efficiently; we prove that in our
context, finding the best new column is an NP-complete problem. To overcome
this bottleneck we use a genetic learning method tailormade for MMOT in which
the dual state within CG plays the role of an "adversary", in loose similarity
to Wasserstein GANs. On a sequence of benchmark problems with up to 120
gridpoints and up to 30 marginals, our method always found the exact
optimizers. Moreover, empirically the number of computational steps needed to
find them appears to scale only polynomially when both $N$ and $\ell$ are
simultaneously increased (while keeping their ratio fixed to mimic a
thermodynamic limit of the particle system).
- Abstract（参考訳）: 本稿では, 密度汎関数理論によるMMOT(Multi-marginal optimal transport)問題を数値的に解くための, 単純, 正確, 極めて効率的な手法を提案する。
この方法は、(i)最適計画のスパース性(それぞれ$\ell$ gridpoints で区別された$n$ marginals に対して、一般のカントロヴィチ計画では $\ell^n$ gridpoints を必要とするが、オプティマイザのサポートは $o(\ell\cdot n)$ [fv18]]、(ii)我々の知識が mmot で使われていない離散最適化によるカラム生成(cg)の方法、(iii)機械学習からのアイデアに依存する。
CGにおけるよく知られたボトルネックは、新しい候補列を効率的に生成することであり、我々の文脈では、最良の新しい列を見つけることはNP完全問題であることを示す。
このボトルネックを克服するために、我々は、CG内の二重状態がWasserstein GANsと緩やかな類似性において「逆境」の役割を果たすMMOT用に作られた遺伝的学習法を用いている。
最大120のグリッドポイントと最大30のマージンを持つベンチマーク問題に対して,本手法は常に最適化器を見出した。
さらに、それらを見つけるのに必要な計算ステップの数は、N$と$\ell$が同時に増加するときのみ多項式的にスケールするように見える(粒子系の熱力学限界を模倣するためにそれらの比率を固定している)。
関連論文リスト
- Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
3ドルの登録アプローチでは、1000万ドル(107ドル)以上のポイントペアを、99%以上のランダムなアウトレイアで処理することができる。
我々はこの手法をTEARと呼び、Trncated Entry-wise Absolute Residualsを演算するoutlier-robust損失を最小限にする。
論文 参考訳（メタデータ） (2024-04-01T04:43:39Z) - Towards Efficient Pareto-optimal Utility-Fairness between Groups in
Repeated Rankings [7.6275971668447005]
消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。
本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。
さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
論文 参考訳（メタデータ） (2024-02-22T05:48:54Z) - Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold [16.099883128428054]
直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。
ODCGMはベクトル空間へのプロジェクションのみを必要とする。
以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
論文 参考訳（メタデータ） (2023-03-16T12:25:53Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Functional Constrained Optimization for Risk Aversion and Sparsity
Control [7.561780884831967]
リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。
本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。
提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
論文 参考訳（メタデータ） (2022-10-11T02:51:51Z) - Enhancing Column Generation by a Machine-Learning-Based Pricing
Heuristic for Graph Coloring [5.278929511653199]
カラム生成(CG)は,大規模最適化問題の解決に有効な手法である。
本稿では,高品質な列を効率的に生成できる機械学習価格ヒューリスティックを提案する。
論文 参考訳（メタデータ） (2021-12-08T03:58:25Z) - On the complexity of the optimal transport problem with graph-structured
cost [9.24979291231758]
マルチマージ最適輸送(Multi-marginal optimal transport、MOT)は、複数の辺縁への最適輸送の一般化である。
MOTの使用は、その計算複雑性によって大きく妨げられ、限界数で指数関数的にスケールする。
論文 参考訳（メタデータ） (2021-10-01T19:29:59Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。