論文の概要: Improved Rate of First Order Algorithms for Entropic Optimal Transport
- arxiv url: http://arxiv.org/abs/2301.09675v1
- Date: Mon, 23 Jan 2023 19:13:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-01-25 15:07:16.640940
- Title: Improved Rate of First Order Algorithms for Entropic Optimal Transport
- Title（参考訳）: エントロピー最適輸送のための一階アルゴリズムの高速化
- Authors: Yiling Luo, Yiling Xie, Xiaoming Huo
- Abstract要約: 本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
- 参考スコア（独自算出の注目度）: 2.1485350418225244
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper improves the state-of-the-art rate of a first-order algorithm for
solving entropy regularized optimal transport. The resulting rate for
approximating the optimal transport (OT) has been improved from
$\widetilde{{O}}({n^{2.5}}/{\epsilon})$ to $\widetilde{{O}}({n^2}/{\epsilon})$,
where $n$ is the problem size and $\epsilon$ is the accuracy level. In
particular, we propose an accelerated primal-dual stochastic mirror descent
algorithm with variance reduction. Such special design helps us improve the
rate compared to other accelerated primal-dual algorithms. We further propose a
batch version of our stochastic algorithm, which improves the computational
performance through parallel computing. To compare, we prove that the
computational complexity of the Stochastic Sinkhorn algorithm is
$\widetilde{{O}}({n^2}/{\epsilon^2})$, which is slower than our accelerated
primal-dual stochastic mirror algorithm. Experiments are done using synthetic
and real data, and the results match our theoretical rates. Our algorithm may
inspire more research to develop accelerated primal-dual algorithms that have
rate $\widetilde{{O}}({n^2}/{\epsilon})$ for solving OT.
- Abstract（参考訳）: 本稿では,エントロピー正則化最適輸送を解く一階法アルゴリズムの最先端の速度を改善する。
最適輸送量(ot)を近似するレートは$\widetilde{{o}}({n^{2.5}}/{\epsilon})$から$\widetilde{o}}({n^2}/{\epsilon})$に改善され、ここで$n$は問題サイズ、$\epsilon$は精度レベルである。
特に,分散低減を伴う主元-双対確率的ミラー降下アルゴリズムを提案する。
このような特別な設計は、他の加速された原始双対アルゴリズムと比較して、速度を改善するのに役立ちます。
さらに,並列計算による計算性能を向上させる確率的アルゴリズムのバッチ版を提案する。
比較するために、確率的シンクホーンアルゴリズムの計算複雑性は$\widetilde{{o}}({n^2}/{\epsilon^2})$であることを証明する。
実験は合成データと実データを用いて行われ、結果が理論値に合致する。
我々のアルゴリズムは、OTを解くために$$\widetilde{{O}}({n^2}/{\epsilon})$を持つ加速原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - An Accelerated Stochastic Algorithm for Solving the Optimal Transport
Problem [2.1485350418225244]
線形制約付き最適化問題を解くために,分散低減アルゴリズム (PDASGD) を用いた一次2次元加速勾配降下法を提案する。
PDASGDは最もよく知られた計算複雑性を享受しており、$widetildemathcalO(n2/epsilon)$、$n$は原子の数、$epsilon>0$は精度である。
論文 参考訳（メタデータ） (2022-03-02T01:16:10Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Efficient Optimal Transport Algorithm by Accelerated Gradient descent [20.614477547939845]
本稿では,ネステロフの平滑化手法に基づく効率と精度をさらに向上させる新しいアルゴリズムを提案する。
提案手法は,同じパラメータでより高速な収束と精度を実現する。
論文 参考訳（メタデータ） (2021-04-12T20:23:29Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。