論文の概要: 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})$を持つ加速原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
関連論文リスト
- A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - 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) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Optimal and Practical Algorithms for Smooth and Strongly Convex
Decentralized Optimization [21.555331273873175]
ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。
本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
論文 参考訳（メタデータ） (2020-06-21T11:23:20Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。