論文の概要: Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical
Solution
- arxiv url: http://arxiv.org/abs/2103.06263v1
- Date: Wed, 10 Mar 2021 18:53:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-11 19:58:58.214631
- Title: Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical
Solution
- Title（参考訳）: 半離散最適輸送:硬さ, 規則化, 数値解
- Authors: Bahar Taskesen, Soroosh Shafieezadeh-Abadeh, Daniel Kuhn
- Abstract要約: 2つの点でサポートされる離散確率測度の間のWasserstein距離の計算が既に#P-hardであることを証明します。
目的関数が最も悪質な外乱分布で滑らかになる分布的に頑健な双対最適輸送問題を導入する。
双対目的関数の平滑化は主目的関数の正則化と等価であることを示す。
- 参考スコア（独自算出の注目度）: 8.465228064780748
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Semi-discrete optimal transport problems, which evaluate the Wasserstein
distance between a discrete and a generic (possibly non-discrete) probability
measure, are believed to be computationally hard. Even though such problems are
ubiquitous in statistics, machine learning and computer vision, however, this
perception has not yet received a theoretical justification. To fill this gap,
we prove that computing the Wasserstein distance between a discrete probability
measure supported on two points and the Lebesgue measure on the standard
hypercube is already #P-hard. This insight prompts us to seek approximate
solutions for semi-discrete optimal transport problems. We thus perturb the
underlying transportation cost with an additive disturbance governed by an
ambiguous probability distribution, and we introduce a distributionally robust
dual optimal transport problem whose objective function is smoothed with the
most adverse disturbance distributions from within a given ambiguity set. We
further show that smoothing the dual objective function is equivalent to
regularizing the primal objective function, and we identify several ambiguity
sets that give rise to several known and new regularization schemes. As a
byproduct, we discover an intimate relation between semi-discrete optimal
transport problems and discrete choice models traditionally studied in
psychology and economics. To solve the regularized optimal transport problems
efficiently, we use a stochastic gradient descent algorithm with imprecise
stochastic gradient oracles. A new convergence analysis reveals that this
algorithm improves the best known convergence guarantee for semi-discrete
optimal transport problems with entropic regularizers.
- Abstract（参考訳）: 離散的(おそらく非離散的)確率測度の間のワッサースタイン距離を評価する半離散的最適輸送問題は計算的に難しいと考えられている。
しかし、そのような問題は統計学、機械学習、コンピュータビジョンにおいて普遍的であるが、この認識は理論的な正当化を受けていない。
このギャップを埋めるために、2つの点で支持される離散確率測度と標準ハイパーキューブ上のルベーグ測度とのワッサーシュタイン距離の計算は既に#Pハードであることを示す。
この知見は,半離散的最適輸送問題に対する近似解を求めるきっかけとなる。
そこで我々は,不明瞭な確率分布に支配される付加的外乱による輸送コストを乱し,対象関数が与えられたあいまいさ集合内から最も悪質な外乱分布で滑らかになるような分布的に頑健な双対輸送問題を導入する。
さらに、双対目的関数の平滑化は主目的関数の正則化と等価であることを示し、いくつかの既知の新しい正則化スキームを生み出す曖昧性集合を同定する。
副産物として, 半離散的最適輸送問題と, 伝統的に心理学や経済学で研究されてきた離散的選択モデルとの関係を見出した。
正規化最適輸送問題を効率的に解くために,不正確な確率的勾配オラクルを用いた確率的勾配降下アルゴリズムを用いる。
新しい収束解析により、このアルゴリズムは、エントロピー正規化器による半離散最適輸送問題に対する既知の収束保証を改善することが明らかになった。
関連論文リスト
- An Inexact Halpern Iteration with Application to Distributionally Robust
Optimization [9.529117276663431]
決定論的および決定論的収束設定におけるスキームの不正確な変種について検討する。
不正確なスキームを適切に選択することにより、(予想される)剰余ノルムの点において$O(k-1)収束率を許容することを示す。
論文 参考訳（メタデータ） (2024-02-08T20:12:47Z) - Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems [3.038642416291856]
クラス確率分布上に定義された複合目的関数を最小化する一般的な最適化問題を考える。
本稿では,正規分布最適化問題の解法として,モロー・吉田変分輸送(MYVT)と呼ばれる新しい手法を提案する。
論文 参考訳（メタデータ） (2023-07-31T01:14:42Z) - New Perspectives on Regularization and Computation in Optimal
Transport-Based Distributionally Robust Optimization [8.564319625930892]
本研究では, 有限の輸送コストで所定の基準分布による不確実な問題パラメータの分布を選択することができるような, 最適輸送に基づく分布安定度最適化問題について検討する。
論文 参考訳（メタデータ） (2023-03-07T13:52:32Z) - A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization [11.034091190797671]
本稿では, 関東ロビッチ輸送コスト, 測定可能な損失関数, および有意な確率分布を抑えるような, 分散的ロバストな最適化のための一般化双対性結果を提案する。
我々は、ある可測射影と弱い可測選択条件が満たされている場合にのみ、交換可能性原理が成立することを示した。
論文 参考訳（メタデータ） (2022-04-30T22:49:01Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal
Transport [0.483420384410068]
エントロピー半離散的最適輸送の解に対して、ほぼ厳密で非漸近収束境界を導出する。
また, エントロピーと非正規化コストの差を非漸近的かつ厳密に拡大させることも検討した。
論文 参考訳（メタデータ） (2021-10-25T06:52:45Z) - Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable
Approach for Continuous Markov Random Fields [53.31927549039624]
断片的な離散化は既存の離散化問題と矛盾しないことを示す。
この理論を2つの画像のマッチング問題に適用する。
論文 参考訳（メタデータ） (2021-07-13T12:31:06Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization [106.70006655990176]
分散最適化問題は機械学習や統計学で広く発生する。
本稿では,変分輸送と呼ばれる粒子に基づく新しいアルゴリズムを提案する。
目的関数がpolyak-Lojasiewicz (PL) (Polyak, 1963) の機能バージョンと滑らかな条件を満たすとき、変分輸送は線形に収束することを示す。
論文 参考訳（メタデータ） (2020-12-21T18:33:13Z) - Continuous Regularized Wasserstein Barycenters [51.620781112674024]
正規化ワッサーシュタイン・バリセンタ問題に対する新しい双対定式化を導入する。
我々は、強い双対性を確立し、対応する主対関係を用いて、正規化された輸送問題の双対ポテンシャルを用いて暗黙的にバリセンターをパラメトリゼーションする。
論文 参考訳（メタデータ） (2020-08-28T08:28:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。