論文の概要: Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport
- arxiv url: http://arxiv.org/abs/2510.27340v1
- Date: Fri, 31 Oct 2025 10:22:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-03 17:52:16.065524
- Title: Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport
- Title（参考訳）: 半離散最適輸送のための平均勾配のエントロピー正則化の低減
- Authors: Ferdinand Genans, Antoine Godichon-Baggioni, François-Xavier Vialard, Olivier Wintenberger,
- Abstract要約: 自然解法は、解に近づくにつれて正則化を適応的に減少させる。
正規化の減少が実際に収束を加速することを証明する。
本稿では,DRAGが定型化よりも規則化の低下に寄与することを示す理論的解析を行う。
- 参考スコア（独自算出の注目度）: 33.30496814734325
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Adding entropic regularization to Optimal Transport (OT) problems has become a standard approach for designing efficient and scalable solvers. However, regularization introduces a bias from the true solution. To mitigate this bias while still benefiting from the acceleration provided by regularization, a natural solver would adaptively decrease the regularization as it approaches the solution. Although some algorithms heuristically implement this idea, their theoretical guarantees and the extent of their acceleration compared to using a fixed regularization remain largely open. In the setting of semi-discrete OT, where the source measure is continuous and the target is discrete, we prove that decreasing the regularization can indeed accelerate convergence. To this end, we introduce DRAG: Decreasing (entropic) Regularization Averaged Gradient, a stochastic gradient descent algorithm where the regularization decreases with the number of optimization steps. We provide a theoretical analysis showing that DRAG benefits from decreasing regularization compared to a fixed scheme, achieving an unbiased $\mathcal{O}(1/t)$ sample and iteration complexity for both the OT cost and the potential estimation, and a $\mathcal{O}(1/\sqrt{t})$ rate for the OT map. Our theoretical findings are supported by numerical experiments that validate the effectiveness of DRAG and highlight its practical advantages.
- Abstract（参考訳）: 最適輸送(OT)問題にエントロピー正規化を加えることは、効率的でスケーラブルな解法を設計するための標準的アプローチとなっている。
しかし、正規化は真の解からのバイアスをもたらす。
正規化によって得られる加速度の恩恵を受けながら、このバイアスを軽減するために、自然解法は、解に近づくにつれて正則化を適応的に減少させる。
このアイデアをヒューリスティックに実装するアルゴリズムもあるが、その理論的な保証と、固定正規化を用いた場合と比較して加速の程度は、大半がオープンである。
ソース測度が連続で対象が離散である半離散OTの設定において、正則化の減少が実際に収束を加速することを証明する。
この目的のために、 DRAG: 正規化(エントロピー) 正規化 Averaged Gradient は、最適化ステップの数に応じて正規化が減少する確率勾配降下アルゴリズムである。
DRAGは、固定されたスキームに比べて正規化を減少させ、未バイアスの$\mathcal{O}(1/t)$サンプルとイテレーションの複雑さをOTコストと潜在的推定の両方で達成し、また、OTマップの$\mathcal{O}(1/\sqrt{t})$レートを達成できることを理論的に示す。
本研究は,DRAGの有効性を検証し,実用上の優位性を明らかにする数値実験で裏付けるものである。
関連論文リスト
- On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization [57.179679246370114]
既存の手法の潜在的な制限は、ステップサイズが提案されない限り、ほとんどの摂動推定器に固有のバイアスである。
本稿では, 良好な構成を維持しつつ, バイアスを排除した非バイアス勾配スケーリング推定器のファミリーを提案する。
論文 参考訳（メタデータ） (2025-10-22T18:25:43Z) - Optimal Rates in Continual Linear Regression via Increasing Regularization [39.30412893918111]
本研究では,ランダムなタスク順序付けの下での連続線形回帰について検討する。
この設定では、$k$学習後の最悪の損失は、$Omega (1/k)$の低いバウンドを認める。
明示的等方的$ell$正則化と有限ステップ予算による暗黙的正則化という2つのよく使われる正則化スキームを用いる。
論文 参考訳（メタデータ） (2025-06-06T19:51:14Z) - Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
重み付き雑音下でのグラディエントDescence(SGD)の収束を確実にする上での勾配正規化とクリッピングの役割について検討する。
我々の研究は、重尾雑音下でのSGDの勾配正規化の利点を示す最初の理論的証拠を提供する。
我々は、勾配正規化とクリッピングを取り入れた加速SGD変種を導入し、さらに重み付き雑音下での収束率を高めた。
論文 参考訳（メタデータ） (2024-10-21T22:40:42Z) - 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) - Signal Processing Meets SGD: From Momentum to Filter [6.751292200515355]
ディープラーニングでは、勾配降下(SGD)とその運動量に基づく変種が最適化に広く利用されている。
本稿では,信号処理レンズを用いて勾配挙動を解析し,更新に影響を与える重要な要因を分離する。
本稿では,ワイナーフィルタの原理に基づく新しいSGDF手法を提案する。
論文 参考訳（メタデータ） (2023-11-06T01:41:46Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Variance Regularization for Accelerating Stochastic Optimization [14.545770519120898]
ミニバッチ勾配に隠れた統計情報を利用してランダムな誤りの蓄積を低減する普遍原理を提案する。
これは、ミニバッチのばらつきに応じて学習率を正規化することで達成される。
論文 参考訳（メタデータ） (2020-08-13T15:34:01Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。