Fugu-MT 論文翻訳(概要): Convergence of batch Greenkhorn for Regularized Multimarginal Optimal Transport

論文の概要: Convergence of batch Greenkhorn for Regularized Multimarginal Optimal Transport

arxiv url: http://arxiv.org/abs/2112.00838v1
Date: Wed, 1 Dec 2021 21:31:26 GMT
ステータス: 処理完了
システム内更新日: 2021-12-04 09:10:36.080029
Title: Convergence of batch Greenkhorn for Regularized Multimarginal Optimal Transport
Title（参考訳）: 正規化マルチマルジナル最適輸送のためのバッチグリーンホーンの収束性
Authors: Vladimir Kostic and Saverio Salzo and Massimilano Pontil
Abstract要約: 欲求制御を伴う反復的ブレグマン射影法(IBP)の特性に基づく完全収束解析を行う。上記のアルゴリズムに特化すると、新たな洞察を与え、既存のものを改善します。
参考スコア（独自算出の注目度）: 6.123324869194195
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this work we propose a batch version of the Greenkhorn algorithm for multimarginal regularized optimal transport problems. Our framework is general enough to cover, as particular cases, some existing algorithms like Sinkhorn and Greenkhorn algorithm for the bi-marginal setting, and (greedy) MultiSinkhorn for multimarginal optimal transport. We provide a complete converge analysis, which is based on the properties of the iterative Bregman projections (IBP) method with greedy control. Global linear rate of convergence and explicit bound on the iteration complexity are obtained. When specialized to above mentioned algorithms, our results give new insights and/or improve existing ones.
Abstract（参考訳）: 本研究では,マルチマージ正規化最適輸送問題に対するGreenkhornアルゴリズムのバッチバージョンを提案する。私たちのフレームワークは、特に、二辺数設定のためのsinkhornアルゴリズムやgreenkhornアルゴリズムや、多辺数最適輸送のための(太い)multisinkhornアルゴリズムなど、既存のアルゴリズムをカバーするのに十分一般的です。欲求制御を伴う反復的ブレグマン射影法(IBP)の特性に基づく完全収束解析を行う。反復複雑性に対する大域的な収束率と明示的な境界を求める。上記のアルゴリズムに特化すれば,新たな洞察や既存アルゴリズムの改善が期待できる。

関連論文リスト

Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文参考訳（メタデータ） (2023-12-13T11:08:25Z)
ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文参考訳（メタデータ） (2023-12-04T19:00:07Z)
An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control [0.0]
このノートは"One-Way Ticket to Las Vegas and the Quantum Adversary"という論文を補完している。私は、Barnum-Saks-Szegedyと同じ視点で、逆境界-普遍アルゴリズムの双対性を異なる形で開発する。
論文参考訳（メタデータ） (2022-11-29T15:25:45Z)
Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm [0.0]
エントロピー正則化は、元の最適輸送問題を一般化する。 Kullback-Leibler の発散を一般の$f$-divergence に置き換えると、自然な一般化につながる。本稿では,正規化された最適輸送コストとその勾配を計算するための実用的なアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-05-29T16:37:31Z)
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence [29.189409618561964]
我々は単調演算子を用いた変分不等式の新しい適応アルゴリズムを開発した。我々のアルゴリズムは未知の問題パラメータに自動的に適応する。我々のアルゴリズムは普遍的であり、同時に最適な収束率を達成することを示す。
論文参考訳（メタデータ） (2020-10-15T14:44:26Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)
Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文参考訳（メタデータ） (2020-06-11T17:43:19Z)
Multi-Scale Zero-Order Optimization of Smooth Functions in an RKHS [19.252319300590653]
ブラックボックス関数 $f:mathcalX mapto mathbbR$ は、$f$がよりスムーズで、与えられたカーネル $K$ に関連する RKHS の有界ノルムを持つという仮定の下で最適化される。本稿では,H の局所多項式 (LP) 推定器を用いて通常の GP 代理モデルを拡張した新しいアルゴリズム (textttLP-GP-UCB) を提案する。
論文参考訳（メタデータ） (2020-05-11T01:55:39Z)
Inference with Aggregate Data: An Optimal Transport Approach [16.274397329511196]
多数の個人が生成した集合データを用いた確率的グラフィカルモデルに対する推論(フィルタリング)問題を考察する。本稿では,木構造グラフの計算複雑性とグローバルコンバージェンス保証を両立する,効率的な信念伝播アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-03-31T03:12:20Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。