論文の概要: Efficient Discretizations of Optimal Transport
- arxiv url: http://arxiv.org/abs/2102.07956v1
- Date: Tue, 16 Feb 2021 04:31:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-17 14:51:17.688377
- Title: Efficient Discretizations of Optimal Transport
- Title(参考訳): 最適輸送の効率的な判別
- Authors: Junqi Wang, Pei Wang, Patrick Shafto
- Abstract要約: 境界分布に対して与えられた点数で離散化を計算するアルゴリズムを提案する。
我々は近似の限界を証明し、幅広い問題について性能を実証する。
- 参考スコア(独自算出の注目度): 16.996068297291057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Obtaining solutions to Optimal Transportation (OT) problems is typically
intractable when the marginal spaces are continuous. Recent research has
focused on approximating continuous solutions with discretization methods based
on i.i.d. sampling, and has proven convergence as the sample size increases.
However, obtaining OT solutions with large sample sizes requires intensive
computation effort, that can be prohibitive in practice. In this paper, we
propose an algorithm for calculating discretizations with a given number of
points for marginal distributions, by minimizing the (entropy-regularized)
Wasserstein distance, and result in plans that are comparable to those obtained
with much larger numbers of i.i.d. samples. Moreover, a local version of such
discretizations which is parallelizable for large scale applications is
proposed. We prove bounds for our approximation and demonstrate performance on
a wide range of problems.
- Abstract(参考訳): 最適輸送(OT)問題に対する解決策を得ることは、通常、限界空間が連続している場合は困難です。
近年,i.i.d.に基づく離散化法を用いて連続解を近似する研究が行われている。
サンプルのサイズが大きくなるにつれて 収束が証明されました
しかし、サンプルサイズが大きいotソリューションを得るには集中的な計算労力が必要であり、これは実際に禁止される。
本稿では,(エントロピー正則化)ワッサーシュタイン距離を最小化することにより,余剰分布の点数で離散化を計算するアルゴリズムを提案する。
サンプル
さらに, 大規模アプリケーション向けに並列化可能な, 局所的な離散化方式を提案する。
我々は近似の限界を証明し、幅広い問題について性能を実証する。
関連論文リスト
- Generative Modeling of Time-Dependent Densities via Optimal Transport
and Projection Pursuit [0.0]
本稿では,時間的モデリングのための一般的なディープラーニングアルゴリズムの代替として,安価に提案する。
我々の手法は最先端の解法と比較して非常に競争力がある。
論文 参考訳(メタデータ) (2023-04-19T13:50:13Z) - Efficient distributed representations beyond negative sampling [7.005458308454873]
本稿では,分散表現を効率よく学習する手法について述べる。
我々は,sotfmax正規化定数を線形時間で推定でき,効率的な最適化戦略を設計できることを示した。
論文 参考訳(メタデータ) (2023-03-30T15:48:26Z) - On Large-Scale Multiple Testing Over Networks: An Asymptotic Approach [19.786769414376323]
提案手法は,分散設定に合わせて,比例マッチングとgreedyアグリゲーションという2つの手法を提案する。
比例マッチング法は、グローバルなBH性能を達成するが、真のヌル仮説の(推定)比率と各ノードにおけるp値の数との1ショットの通信しか必要としない。
最適解の明示的な特徴づけを提供することにより、最適解に焦点をあてることで、BH法を超越する。
これにより、各ノードの最適拒絶領域を効果的に近似するグリーディ集約法が導かれる一方、計算効率はグリーディ型アプローチから自然に得られる。
論文 参考訳(メタデータ) (2022-11-29T10:10:39Z) - Stochastic Constrained DRO with a Complexity Independent of Sample Size [32.90168784074699]
クルバック分散制約DRO問題の解法として,非凸損失と凸損失の両方に適用可能なアルゴリズムを提案し,解析する。
非損失に対する$$$ilon定常解を見つけるのにほぼ最適な複雑さを確立し、広いアプリケーションに最適な解を求めるのに最適なバッチの複雑さを確立します。
論文 参考訳(メタデータ) (2022-10-11T19:11:19Z) - Statistical Inference with Stochastic Gradient Algorithms [18.93569692490218]
勾配アルゴリズムは大規模学習問題や推論問題において最適化とサンプリングの両方に広く用いられている。
実際、これらのアルゴリズムのチューニングは通常、厳密で一般化可能な理論ではなく、試行錯誤を用いて行われる。
一定のステップサイズで適切に調整されたアルゴリズムは、点推定や後部的なサンプルを得るための計算効率が高く統計的に堅牢なアプローチを提供することを示す。
論文 参考訳(メタデータ) (2022-07-25T17:58:09Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳(メタデータ) (2022-03-18T05:49:13Z) - Near-optimal estimation of smooth transport maps with kernel
sums-of-squares [81.02564078640275]
滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。
生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。
そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-03T13:45:36Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。
我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。
また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
論文 参考訳(メタデータ) (2020-02-16T09:01:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。