論文の概要: Asymptotics of Entropy-Regularized Optimal Transport via Chaos
Decomposition
- arxiv url: http://arxiv.org/abs/2011.08963v1
- Date: Tue, 17 Nov 2020 21:55:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-24 17:24:35.709544
- Title: Asymptotics of Entropy-Regularized Optimal Transport via Chaos
Decomposition
- Title（参考訳）: カオス分解によるエントロピー規則化最適輸送の漸近
- Authors: Zaid Harchaoui, Lang Liu, Soumik Pal
- Abstract要約: この論文は、離散的なシュル「オーディンガー橋」の性質を、N$が無限大の傾向にあるとして論じる。
最初の2つのエラー項は、それぞれ$N-1/2$と$N-1$を導出する。
1階と2階のカオスに対応するカーネルは、シンクホーンアルゴリズムの自然な解釈を持つマルコフ作用素によって与えられる。
- 参考スコア（独自算出の注目度）: 1.7188280334580195
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the problem of estimating the optimal coupling (i.e., matching)
between $N$ i.i.d. data points sampled from two densities $\rho_0$ and $\rho_1$
in $\mathbb{R}^d$. The cost of transport is an arbitrary continuous function
that satisfies suitable growth and integrability assumptions. For both
computational efficiency and smoothness, often a regularization term using
entropy is added to this discrete problem. We introduce a modification of the
commonly used discrete entropic regularization (Cuturi '13) such that the
optimal coupling for the regularized problem can be thought of as the static
Schr\"odinger bridge with $N$ particles. This paper is on the asymptotic
properties of this discrete Schr\"odinger bridge as $N$ tends to infinity. We
show that it converges to the continuum Schr\"odinger bridge and derive the
first two error terms of orders $N^{-1/2}$ and $N^{-1}$, respectively. This
gives us functional CLT, including for the cost of transport, and second order
Gaussian chaos limits when the limiting Gaussian variance is zero, extending
similar recent results derived for finite state spaces and the quadratic cost.
The proofs are based on a novel chaos decomposition of the discrete
Schr\"odinger bridge by polynomial functions of the pair of empirical
distributions as a first and second order Taylor approximations in the space of
measures. This is achieved by extending the Hoeffding decomposition from the
classical theory of U-statistics. The kernels corresponding to the first and
second order chaoses are given by Markov operators which have natural
interpretations in the Sinkhorn algorithm.
- Abstract（参考訳）: 2つの密度$\rho_0$と$\rho_1$ in $\mathbb{R}^d$からサンプリングされた$N$のデータポイント間の最適結合(すなわちマッチング)を推定する問題を考える。
輸送コストは、適切な成長と可積分性仮定を満たす任意の連続関数である。
計算効率と滑らか性の両方において、エントロピーを用いた正規化項がこの離散問題にしばしば加えられる。
一般化された離散エントロピー正則化 (cuturi '13) の修正を導入することにより, 正則化問題に対する最適結合を, $n$ の粒子を持つ静的 schr\"odinger bridge と考えることができる。
この論文は、この離散的なSchr\"odingerブリッジの漸近的性質について、N$が無限大の傾向にあることを示す。
連続体 Schr\"odinger ブリッジに収束し、それぞれ位数 $N^{-1/2}$ と $N^{-1}$ の最初の2つの誤り項を導出することを示す。
これにより、輸送コストを含む関数型 CLT と、ガウス的分散がゼロであるときの2階ガウス的カオス限界が得られ、有限状態空間と二次コストに対して導かれる同様の結果が拡張される。
この証明は、測度空間における一階および二階テイラー近似として経験分布の対の多項式関数による離散schr\"odinger橋の新たなカオス分解に基づいている。
これは、ホーフディング分解を古典的なU統計理論から拡張することで達成される。
1階と2階のカオスに対応するカーネルは、シンクホーンアルゴリズムの自然な解釈を持つマルコフ作用素によって与えられる。
関連論文リスト
- Optimal convergence rates in trace distance and relative entropy for the quantum central limit theorem [2.7855886538423182]
有限第三次モーメントを持つ中心の$m$モード量子状態に対して、$rhoboxplus n$ と $rho_G$ のトレース距離が $mathcalO(n-1/2)$ の最適速度で崩壊することを示す。
有限四階モーメントを持つ状態に対しては、$rhoboxplus n$と$rho_G$の間の相対エントロピーが$mathcalO(n-1)$の最適速度で崩壊することを示す。
論文 参考訳（メタデータ） (2024-10-29T12:35:47Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。
伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
論文 参考訳（メタデータ） (2023-10-09T18:38:56Z) - Purity decay rate in random circuits with different configurations of
gates [0.0]
我々は、様々なジオメトリの作用の下で、純度減衰(二部体の絡み合いの尺度)を$n$の連鎖で研究する。
ほとんどの回路において、純度は2つの段階においてその値に減衰する: 初期の熱力学的に関係した崩壊は$sim lambda_mathrmeffeff$であり、$lambda_mathrmeff$は必ずしも転移行列のスペクトルにあるとは限らない。
論文 参考訳（メタデータ） (2022-11-24T12:32:07Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for
Two-Dimensional Systems [62.997667081978825]
開量子系は、FGKLS(Franke-Gorini-Kossakowski-Lindblad-Sudarshan)方程式に従うことができる。
我々はヒルベルト空間次元が 2$ である場合を徹底的に研究する。
論文 参考訳（メタデータ） (2022-04-16T07:03:54Z) - Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal
Transport [0.483420384410068]
エントロピー半離散的最適輸送の解に対して、ほぼ厳密で非漸近収束境界を導出する。
また, エントロピーと非正規化コストの差を非漸近的かつ厳密に拡大させることも検討した。
論文 参考訳（メタデータ） (2021-10-25T06:52:45Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - Estimating 2-Sinkhorn Divergence between Gaussian Processes from
Finite-Dimensional Marginals [4.416484585765028]
エルフガウス過程 (GP) 間の2-シンクホーンの偏差を有限次元の辺分布を用いて推定する収束性について検討する。
境界値が基底値に従ってサンプリングされた場合, ほぼ確実に発散の収束を示す。
論文 参考訳（メタデータ） (2021-02-05T16:17:55Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。