論文の概要: Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate

• arxiv url: http://arxiv.org/abs/2510.25287v1
• Date: Wed, 29 Oct 2025 08:43:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-30 15:50:45.291286
• Title: Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate
• Title（参考訳）: 半離散最適輸送における確率最適化:収束解析と最小速度
• Authors: Ferdinand Genans, Antoine Godichon-Baggioni, François-Xavier Vialard, Olivier Wintenberger,
• Abstract要約: グラディエント・Descent(SGD)ベースの解法は、最近の機械学習アプリケーションで強い経験的性能を示した。 SGD法は最小収束率$mathcalO (1/sqrtn)$でOTマップを推定できることを示す。 ソース測度がコンパクトにサポートされていなくても、目的の最小値を含む適切な射影集合を同定する。
• 参考スコア（独自算出の注目度）: 33.30496814734325
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the semi-discrete Optimal Transport (OT) problem, where a continuous source measure $\mu$ is transported to a discrete target measure $\nu$, with particular attention to the OT map approximation. In this setting, Stochastic Gradient Descent (SGD) based solvers have demonstrated strong empirical performance in recent machine learning applications, yet their theoretical guarantee to approximate the OT map is an open question. In this work, we answer it positively by providing both computational and statistical convergence guarantees of SGD. Specifically, we show that SGD methods can estimate the OT map with a minimax convergence rate of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the number of samples drawn from $\mu$. To establish this result, we study the averaged projected SGD algorithm, and identify a suitable projection set that contains a minimizer of the objective, even when the source measure is not compactly supported. Our analysis holds under mild assumptions on the source measure and applies to MTW cost functions,whic include $\|\cdot\|^p$ for $p \in (1, \infty)$. We finally provide numerical evidence for our theoretical results.
• Abstract（参考訳）: 本稿では, 半離散最適輸送(OT)問題について検討し, 連続音源測度 $\mu$ を離散目標測度 $\nu$ に輸送し, 特に OT マップ近似に注目した。 この設定では、SGD(Stochastic Gradient Descent)に基づく解法は、最近の機械学習アプリケーションにおいて強力な経験的性能を示してきたが、OTマップを近似する理論的保証はオープンな問題である。 本研究では,SGDの数値収束保証と統計的収束保証の両面から正の回答を得る。 具体的には、SGD法が最小収束率$\mathcal{O}(1/\sqrt{n})$で OT マップを推定できることを示し、$n$ は $\mu$ から引き出されたサンプルの数である。 この結果を確立するために,提案手法の平均予測SGDアルゴリズムについて検討し,ソース測度がコンパクトにサポートされていない場合でも,目標の最小値を含む適切な射影集合を同定する。 我々の解析は、ソース測度について穏やかな仮定を下し、MTWコスト関数に適用するが、whic は $\|\cdot\|^p$ for $p \in (1, \infty)$ を含む。 最終的に、理論結果の数値的な証拠を提供する。

関連論文リスト

• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。 所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
  論文  参考訳（メタデータ） (2024-05-23T11:46:03Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。