論文の概要: Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing
- arxiv url: http://arxiv.org/abs/2408.11620v1
- Date: Wed, 21 Aug 2024 13:47:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-22 16:47:35.181019
- Title: Annealed Sinkhorn for Optimal Transport: convergence, regularization path and debiasing
- Title（参考訳）: 最適輸送のためのAnnealed Sinkhorn:収束、正規化、偏り
- Authors: Lénaïc Chizat,
- Abstract要約: Sinkhornのアルゴリズムは、大規模な最適輸送(OT)問題を解決する方法である。
コンケーブスケジュールアルゴリズムがOTを解くことは、$beta_tto+infty$と$beta_t-beta_t-1to 0$の場合に限る。
本稿では, 緩和誤差を低減するため, 簡易なアンナーレ・シンクホーンの修正を提案する。
- 参考スコア（独自算出の注目度）: 4.44549269470273
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sinkhorn's algorithm is a method of choice to solve large-scale optimal transport (OT) problems. In this context, it involves an inverse temperature parameter $\beta$ that determines the speed-accuracy trade-off. To improve this trade-off, practitioners often use a variant of this algorithm, Annealed Sinkhorn, that uses an nondecreasing sequence $(\beta_t)_{t\in \mathbb{N}}$ where $t$ is the iteration count. However, besides for the schedule $\beta_t=\Theta(\log t)$ which is impractically slow, it is not known whether this variant is guaranteed to actually solve OT. Our first contribution answers this question: we show that a concave annealing schedule asymptotically solves OT if and only if $\beta_t\to+\infty$ and $\beta_t-\beta_{t-1}\to 0$. The proof is based on an equivalence with Online Mirror Descent and further suggests that the iterates of Annealed Sinkhorn follow the solutions of a sequence of relaxed, entropic OT problems, the regularization path. An analysis of this path reveals that, in addition to the well-known "entropic" error in $\Theta(\beta^{-1}_t)$, the annealing procedure induces a "relaxation" error in $\Theta(\beta_{t}-\beta_{t-1})$. The best error trade-off is achieved with the schedule $\beta_t = \Theta(\sqrt{t})$ which, albeit slow, is a universal limitation of this method. Going beyond this limitation, we propose a simple modification of Annealed Sinkhorn that reduces the relaxation error, and therefore enables faster annealing schedules. In toy experiments, we observe the effectiveness of our Debiased Annealed Sinkhorn's algorithm: a single run of this algorithm spans the whole speed-accuracy Pareto front of the standard Sinkhorn's algorithm.
- Abstract（参考訳）: Sinkhornのアルゴリズムは、大規模な最適輸送(OT)問題を解決する方法である。
この文脈では、速度精度のトレードオフを決定する逆温度パラメータ$\beta$が関係する。
このトレードオフを改善するために、実践者はしばしばこのアルゴリズムの変種であるAnaaled Sinkhornを使う。これは、$t$が反復数であるような非減少シーケンス$(\beta_t)_{t\in \mathbb{N}}$を使用する。
しかし、非常に遅いスケジュールである$\beta_t=\Theta(\log t)$に加えて、この変種が実際にOTを解くことが保証されているかどうかは不明である。
コンケーブアニーリングスケジュールが OT を漸近的に解くことは、$\beta_t\to+\infty$ と $\beta_t-\beta_{t-1}\to 0$ の場合に限る。
この証明はオンラインミラー・ダイアンスと等価性に基づいており、さらに、アナルド・シンクホーンの反復は、緩和されたエントロピーのOT問題の列、正規化経路の解に従うことを示唆している。
この経路の分析によれば、よく知られた$\Theta(\beta^{-1}_t)$の"エントロピー"エラーに加えて、アニーリング手順は$\Theta(\beta_{t}-\beta_{t-1})$の"レラックス"エラーを誘導する。
最良のエラートレードオフは、スケジュール $\beta_t = \Theta(\sqrt{t})$ で達成される。
この制限を超えて、緩和誤差を低減し、より高速なアニーリングスケジュールを可能にする、Annealed Sinkhornの簡単な修正を提案する。
おもちゃの実験では、このアルゴリズムの単一実行は、標準的なシンクホーンのアルゴリズムの前の全速度精度のパレートにまたがる、偏りのあるアナーレド・シンクホーンのアルゴリズムの有効性を観察する。
関連論文リスト
- LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - On Accelerated Perceptrons and Beyond [17.479295705933698]
RosenblattのPerceptronアルゴリズムは、$n$の線形分離可能なデータポイントを正しく分類する線形しきい値関数を見つけるのに使うことができる。
基本的な結果は、Perceptron が $Omega(sqrtlog n/gamma)$ iterations の後に収束するということである。
最近、より洗練されたアルゴリズムでこの速度を2乗係数で$Omega(sqrtlog n/gamma)$に改善する研究がいくつかある。
論文 参考訳（メタデータ） (2022-10-17T19:12:30Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and
1-D Frank-Wolfe [0.0]
非平衡最適輸送(UOT)は、分布を比較するために質量変動を考慮した最適輸送(OT)を拡張する。
これは、OTをMLアプリケーションで成功させることで、データの正規化とアウトレイラに対して堅牢になる。
本研究では、この欠損の原因、すなわち、二元OTポテンシャルの翻訳に等価な、反復体の大域正規化の欠如を同定する。
論文 参考訳（メタデータ） (2022-01-03T16:07:57Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Thresholded Lasso Bandit [70.17389393497125]
Thresholded Lasso banditは、報酬関数を定義するベクトルとスパースサポートを推定するアルゴリズムである。
一般には $mathcalO( log d + sqrtT )$ や $mathcalO( log d + sqrtT )$ としてスケールする非漸近的後悔の上界を確立する。
論文 参考訳（メタデータ） (2020-10-22T19:14:37Z) - On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm [24.09910756628079]
UOT問題に対する$varepsilon$-approximateソリューションを見つけるためのシンクホーンアルゴリズムの複雑さは、ほぼ直線時間である$widetildemathcalO(n2/ varepsilon)$である。
我々の証明手法は、エントロピー正則化 UOT 問題の最適双対解と原始解のいくつかの性質に対するシンクホーン更新の幾何収束に基づいている。
論文 参考訳（メタデータ） (2020-02-09T06:03:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。