論文の概要: Safe Screening for Unbalanced Optimal Transport
- arxiv url: http://arxiv.org/abs/2307.00247v1
- Date: Sat, 1 Jul 2023 06:22:14 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-05 17:14:29.935090
- Title: Safe Screening for Unbalanced Optimal Transport
- Title(参考訳): 不均衡最適輸送の安全スクリーニング
- Authors: Xun Su, Zhongxi Fang, Hiroyuki Kasai
- Abstract要約: セーフスクリーニングの UOT 問題への適用可能性について,$ell$-penalty と KL-penalty を用いて実証した。
具体的には、新しい近似射影、楕円型安全な領域、および2つの超平面緩和法を提案する。
これらの拡張により、アルゴリズムの複雑さを変えることなく、UOTのスクリーニング効率が大幅に向上した。
- 参考スコア(独自算出の注目度): 17.489075240435348
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces a framework that utilizes the Safe Screening technique
to accelerate the optimization process of the Unbalanced Optimal Transport
(UOT) problem by proactively identifying and eliminating zero elements in the
sparse solutions. We demonstrate the feasibility of applying Safe Screening to
the UOT problem with $\ell_2$-penalty and KL-penalty by conducting an analysis
of the solution's bounds and considering the local strong convexity of the dual
problem. Considering the specific structural characteristics of the UOT in
comparison to general Lasso problems on the index matrix, we specifically
propose a novel approximate projection, an elliptical safe region construction,
and a two-hyperplane relaxation method. These enhancements significantly
improve the screening efficiency for the UOT's without altering the algorithm's
complexity.
- Abstract(参考訳): 本稿では,スパースソリューションにおけるゼロ要素を積極的に識別・排除することにより,セーフスクリーニング技術を用いて不均衡最適輸送(UOT)問題の最適化プロセスを高速化するフレームワークを提案する。
我々は, 解境界の解析を行い, 双対問題の局所的強凸性を考慮することで, $\ell_2$-penalty と kl-penalty の uot 問題に対して安全なスクリーニングを適用する可能性を示す。
指標行列の一般ラッソ問題と比較して, uotの特異な構造特性を考慮に入れ, 新たな近似投影法, 楕円セーフ領域構成法, 2面緩和法を提案する。
これらの拡張はアルゴリズムの複雑さを変えることなく、uotのスクリーニング効率を大幅に向上させた。
関連論文リスト
- Scalable First-order Method for Certifying Optimal k-Sparse GLMs [9.613635592922174]
そこで本研究では,BnBフレームワークの視点緩和を解くために,一階近位勾配アルゴリズムを提案する。
提案手法は双有界計算を著しく高速化し,大規模問題に対する最適性証明の提供に極めて有効であることを示す。
論文 参考訳(メタデータ) (2025-02-13T17:14:18Z) - Spectral-Risk Safe Reinforcement Learning with Convergence Guarantees [13.470544618339506]
本稿では、スペクトルリスク尺度制約付きRLアルゴリズム、スペクトルリスク制約付きポリシー最適化(SRCPO)を提案する。
双レベル最適化構造では、外部問題はリスク測度から導出される双対変数を最適化することであり、内部問題は最適ポリシーを見つけることである。
提案手法は連続制御タスク上で評価され,制約を満たす他のRCRLアルゴリズムの中で最高の性能を示した。
論文 参考訳(メタデータ) (2024-05-29T02:17:25Z) - SCPO: Safe Reinforcement Learning with Safety Critic Policy Optimization [1.3597551064547502]
本研究では,新しい安全強化学習アルゴリズム,セーフティ・クリティカル・ポリシー・オプティマイゼーションを導入する。
本研究では,安全制約に違反して得られる報酬を無効化する機構である安全評論家を定義した。
理論的解析により,提案アルゴリズムは安全制約への付着と報酬の最大化との間のトレードオフを自動的にバランスできることが示された。
論文 参考訳(メタデータ) (2023-11-01T22:12:50Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳(メタデータ) (2023-06-10T08:25:16Z) - Log Barriers for Safe Black-box Optimization with Application to Safe
Reinforcement Learning [72.97229770329214]
本稿では,学習時の安全性維持が不可欠である高次元非線形最適化問題に対する一般的なアプローチを提案する。
LBSGDと呼ばれるアプローチは、慎重に選択されたステップサイズで対数障壁近似を適用することに基づいている。
安全強化学習における政策課題の違反を最小限に抑えるためのアプローチの有効性を実証する。
論文 参考訳(メタデータ) (2022-07-21T11:14:47Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - On the Convergence of Projected Alternating Maximization for Equitable
and Optimal Transport [36.97843660480747]
本稿では,多くの応用例を有する等価・最適輸送(EOT)問題について検討する。
離散分布の場合、EOT問題は線形プログラム(LP)として定式化できる。
このLPは一般解法では禁止的に大きいため、Scetbon etal citescetbonequitable はエントロピー正則化を加えることによって問題を摂動することを示唆している。
彼らは、エントロピー正規化EOTの双対を解くための予測交互化アルゴリズム(PAM)を提案した。
論文 参考訳(メタデータ) (2021-09-29T04:32:06Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Robust Reinforcement Learning with Wasserstein Constraint [49.86490922809473]
最適なロバストなポリシーの存在を示し、摂動に対する感度分析を行い、新しいロバストな学習アルゴリズムを設計する。
提案アルゴリズムの有効性はCart-Pole環境で検証する。
論文 参考訳(メタデータ) (2020-06-01T13:48:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。