論文の概要: On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and
OT Distance Gaps
- arxiv url: http://arxiv.org/abs/2205.13846v1
- Date: Fri, 27 May 2022 09:19:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-30 13:26:39.142271
- Title: On the Convergence of Semi-Relaxed Sinkhorn with Marginal Constraint and
OT Distance Gaps
- Title（参考訳）: 限界制約とot距離ギャップをもつ半相対シンクホーンの収束について
- Authors: Takumi Fukunaga and Hiroyuki Kasai
- Abstract要約: 半緩和シンクホーン(Semi-Relaxed Sinkhorn、SR-Sinkhorn)は、半緩和最適輸送(SROT)問題のアルゴリズムである。
本稿では,SR-シンクホーンの総合収束解析について述べる。
- 参考スコア（独自算出の注目度）: 20.661025590877774
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents consideration of the Semi-Relaxed Sinkhorn (SR-Sinkhorn)
algorithm for the semi-relaxed optimal transport (SROT) problem, which relaxes
one marginal constraint of the standard OT problem. For evaluation of how the
constraint relaxation affects the algorithm behavior and solution, it is
vitally necessary to present the theoretical convergence analysis in terms not
only of the functional value gap, but also of the marginal constraint gap as
well as the OT distance gap. However, no existing work has addressed all
analyses simultaneously. To this end, this paper presents a comprehensive
convergence analysis for SR-Sinkhorn. After presenting the
$\epsilon$-approximation of the functional value gap based on a new proof
strategy and exploiting this proof strategy, we give the upper bound of the
marginal constraint gap. We also provide its convergence to the
$\epsilon$-approximation when two distributions are in the probability simplex.
Furthermore, the convergence analysis of the OT distance gap to the
$\epsilon$-approximation is given as assisted by the obtained marginal
constraint gap. The latter two theoretical results are the first results
presented in the literature related to the SROT problem.
- Abstract（参考訳）: 本稿では,Semi-Relaxed Sinkhorn (SR-Sinkhorn) アルゴリズムを用いて,標準OT問題の限界制約を緩和する半緩和最適輸送(SROT)問題について考察する。
制約緩和がアルゴリズムの挙動や解にどのように影響するかを評価するためには、関数値ギャップだけでなく、限界制約ギャップやOT距離ギャップについても理論収束解析を提示する必要がある。
しかし、すべての分析に同時に対処する作業は行われていない。
本稿では,sr-sinkhornの包括的収束解析について述べる。
新しい証明戦略に基づいて関数値ギャップの$\epsilon$-approximationを提示し、この証明戦略を利用した後、限界制約ギャップの上限を与える。
また、2つの分布が確率単純度にあるときの$\epsilon$-approximationへの収束も提供する。
さらに、OT距離ギャップの$\epsilon$-approximationへの収束解析は、得られた限界制約ギャップの補助として与えられる。
後者の2つの理論的結果は、SROT問題に関する文献で示された最初の結果である。
関連論文リスト
- Taming under isoperimetry [0.0]
本稿では,ログの増大に伴う分布のサンプル化を目的としたLangevinベースのスキームであるmathbfsTULA$を提案する。
非漸近KLを導出し、結果としてLog-Sobolevの不等式を満たす。
論文 参考訳（メタデータ） (2023-11-15T14:44:16Z) - Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine
Constraints [21.38692458445459]
ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。
単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
論文 参考訳（メタデータ） (2023-10-02T08:07:36Z) - Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent
Estimator [0.0]
本稿では,凸問題の文脈における統計的推論のための勾配降下(SGD)の理論的性質について検討する。
多重誤差最小値を含む2つの干渉手順を提案する。
論文 参考訳（メタデータ） (2023-06-03T22:08:10Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T02:19:39Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - A Convergence Theory for Federated Average: Beyond Smoothness [28.074273047592065]
フェデレートラーニングにより、大量のエッジコンピューティングデバイスが、データ共有を併用せずにモデルを学習できるようになる。
この設定における主要なアルゴリズムとして、ローカルデバイス上でGradient Descent(SGD)を並列に実行するFederated Average FedAvgが広く使用されている。
本稿では,フェデレートラーニングに関する理論的収束研究について述べる。
論文 参考訳（メタデータ） (2022-11-03T04:50:49Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - 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) - Low-Rank Sinkhorn Factorization [45.87981728307819]
本稿では,テキストサブカップリング係数の積として,低位結合の明示的な因子化を導入する。
このアルゴリズムの非漸近定常収束を証明し、その効率をベンチマーク実験で示す。
論文 参考訳（メタデータ） (2021-03-08T13:18:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。