論文の概要: A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport
- arxiv url: http://arxiv.org/abs/2310.14087v2
- Date: Tue, 30 Jan 2024 20:23:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-01 20:17:41.186476
- Title: A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport
- Title(参考訳): カーネルに基づく最適輸送のためのセミスムースニュートン法
- Authors: Tianyi Lin, Marco Cuturi and Michael I. Jordan
- Abstract要約: カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
- 参考スコア(独自算出の注目度): 92.96250725599958
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Kernel-based optimal transport (OT) estimators offer an alternative,
functional estimation procedure to address OT problems from samples. Recent
works suggest that these estimators are more statistically efficient than
plug-in (linear programming-based) OT estimators when comparing probability
measures in high-dimensions~\citep{Vacher-2021-Dimension}. Unfortunately, that
statistical benefit comes at a very steep computational price: because their
computation relies on the short-step interior-point method (SSIPM), which comes
with a large iteration count in practice, these estimators quickly become
intractable w.r.t. sample size $n$. To scale these estimators to larger $n$, we
propose a nonsmooth fixed-point model for the kernel-based OT problem, and show
that it can be efficiently solved via a specialized semismooth Newton (SSN)
method: We show, exploring the problem's structure, that the per-iteration cost
of performing one SSN step can be significantly reduced in practice. We prove
that our SSN method achieves a global convergence rate of $O(1/\sqrt{k})$, and
a local quadratic convergence rate under standard regularity conditions. We
show substantial speedups over SSIPM on both synthetic and real datasets.
- Abstract(参考訳): カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
近年の研究では、これらの推定器は高次元~\citep{Vacher-2021-Dimension}の確率測度を比較する際に、プラグイン(線形プログラミングに基づく)OT推定器よりも統計的に効率的であることが示唆されている。
残念なことに、この統計的な利点は非常に高い計算コストがかかる: 計算は短い段階のインテリアポイント法 (SSIPM) に依存しており、これは実際は大きな反復数を持つため、これらの推定器はすぐに難解なw.r.t.サンプルサイズ$n$になる。
これらの推定器をより大きな$n$にスケールするために、カーネルベースのot問題の非スムース不動点モデルを提案し、特殊なセミスムースニュートン(ssn)法によって効率的に解くことができることを示した。
我々はSSN法がO(1/\sqrt{k})$の大域収束率と標準正規性条件下での局所二次収束率を達成することを証明した。
合成データと実データの両方でSSIPMよりもかなり高速であることを示す。
関連論文リスト
- Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。
本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
論文 参考訳(メタデータ) (2023-11-15T12:36:45Z) - Online non-parametric likelihood-ratio estimation by Pearson-divergence
functional minimization [55.98760097296213]
iid 観測のペア $(x_t sim p, x'_t sim q)$ が時間の経過とともに観測されるような,オンラインな非パラメトリック LRE (OLRE) のための新しいフレームワークを提案する。
本稿では,OLRE法の性能に関する理論的保証と,合成実験における実証的検証について述べる。
論文 参考訳(メタデータ) (2023-11-03T13:20:11Z) - On Computationally Efficient Learning of Exponential Family
Distributions [33.229944519289795]
我々は、サポートと自然なパラメータが適切にバウンドされている設定に焦点を当てる。
本手法は,ノードワイズ・スパースランダムフィールドに適した場合,$O(sf log(k)/alpha2)$のオーダー最適サンプル複雑性を実現する。
論文 参考訳(メタデータ) (2023-09-12T17:25:32Z) - Statistical Inference with Stochastic Gradient Methods under
$\phi$-mixing Data [9.77185962310918]
データが$phi$-mixingの場合の統計的推測のためのミニバッチSGD推定器を提案する。
信頼区間は、関連するミニバッチSGDプロシージャを用いて構成される。
提案手法はメモリ効率が高く,実装が容易である。
論文 参考訳(メタデータ) (2023-02-24T16:16:43Z) - Robust computation of optimal transport by $\beta$-potential
regularization [79.24513412588745]
最適輸送(OT)は、確率分布間の差を測定する機械学習分野で広く使われているツールである。
我々は、いわゆる$beta$-divergenceに付随するベータポテンシャル項でOTを正規化することを提案する。
提案アルゴリズムで計算した輸送行列は,外乱が存在する場合でも確率分布を頑健に推定するのに役立つことを実験的に実証した。
論文 参考訳(メタデータ) (2022-12-26T18:37:28Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳(メタデータ) (2022-06-05T21:32:33Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳(メタデータ) (2021-11-12T01:51:50Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳(メタデータ) (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。