Fugu-MT 論文翻訳(概要): Polynomial-Time Solvers for the Discrete $\infty$-Optimal Transport Problems

論文の概要: Polynomial-Time Solvers for the Discrete $\infty$-Optimal Transport Problems

arxiv url: http://arxiv.org/abs/2304.13467v1
Date: Wed, 26 Apr 2023 14:51:51 GMT
ステータス: 処理完了
システム内更新日: 2023-04-27 14:30:13.240870
Title: Polynomial-Time Solvers for the Discrete $\infty$-Optimal Transport Problems
Title（参考訳）: 離散$\infty$-Optimal Transport問題に対する多項式時間解法
Authors: Meyer Scetbon
Abstract要約: 本稿では、離散的かつ有限な設定において、$infty$-optimal transport問題を解くことを提案する。これらの問題の効率的な数値解法が提案されているのは、私たちの知る限りでは初めてである。
参考スコア（独自算出の注目度）: 16.688727673221297
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this note, we propose polynomial-time algorithms solving the Monge and Kantorovich formulations of the $\infty$-optimal transport problem in the discrete and finite setting. It is the first time, to the best of our knowledge, that efficient numerical methods for these problems have been proposed.
Abstract（参考訳）: 本稿では,離散および有限設定における$\infty$-optimal transport 問題のmonge および kantorovich 定式化を解く多項式時間アルゴリズムを提案する。我々の知る限り、これらの問題の効率的な数値手法が提案されているのは初めてである。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Sinkhorn algorithms and linear programming solvers for optimal partial transport problems [1.8130068086063336]
一般化された最適部分輸送問題について紹介する。次に、これらの問題の二重定式化と関連するシンクホーン解法について議論する。
論文参考訳（メタデータ） (2024-07-09T01:08:21Z)
Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文参考訳（メタデータ） (2023-10-08T23:39:38Z)
Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
多くの学習問題に対するベストサブセット選択は「ゴールドスタンダード」と見なされている。本稿では,$ell$-regularized問題系の二重形式について検討する。主問題構造と双対問題構造に基づく効率的な主対法が開発されている。
論文参考訳（メタデータ） (2022-07-05T14:07:52Z)
Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文参考訳（メタデータ） (2021-11-24T07:14:57Z)
Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。これらの問題に対する新規で簡単な最適化法を開発した。結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文参考訳（メタデータ） (2021-09-23T17:38:24Z)
Power of human-algorithm collaboration in solving combinatorial optimization problems [0.0]
最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
論文参考訳（メタデータ） (2021-07-25T11:21:59Z)
Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time [6.093245378608679]
非相関なガウス報酬を持つ半帯域を考える。本稿では,多くの関心構造に間に合うように,Graves-Lai問題の解を計算するための最初の方法を提案する。
論文参考訳（メタデータ） (2021-02-14T22:14:28Z)
Multi-armed Bandits with Cost Subsidy [1.6631602844999724]
本稿では、インテリジェントSMSルーティング問題と広告オーディエンス最適化問題という2つのアプリケーションを提案する。既存のMABアルゴリズムの素早い一般化は、この問題に対してうまく機能しないことを示す。また,このアルゴリズムに対して,探索定理の簡単な変種を提示し,ほぼ最適な後悔境界を定めている。
論文参考訳（メタデータ） (2020-11-03T05:38:42Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

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