論文の概要: Difference of Submodular Minimization via DC Programming

• arxiv url: http://arxiv.org/abs/2305.11046v1
• Date: Thu, 18 May 2023 15:39:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-19 14:29:04.473844
• Title: Difference of Submodular Minimization via DC Programming
• Title（参考訳）: DCプログラミングによる部分モジュラ最小化の差
• Authors: Marwa El Halabi, George Orfanides, Tim Hoheisel
• Abstract要約: 2つのサブモジュール(DS)関数の差を最小化することは、様々な機械学習問題に自然に発生する。 DC問題に対する古典的アルゴリズムはDCアルゴリズム (DCA) と呼ばれる。 DS最小化に対応するDCプログラムに適用したDCAの変種とその完全形(CDCA)を紹介する。
• 参考スコア（独自算出の注目度）: 5.465873146396502
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Minimizing the difference of two submodular (DS) functions is a problem that naturally occurs in various machine learning problems. Although it is well known that a DS problem can be equivalently formulated as the minimization of the difference of two convex (DC) functions, existing algorithms do not fully exploit this connection. A classical algorithm for DC problems is called the DC algorithm (DCA). We introduce variants of DCA and its complete form (CDCA) that we apply to the DC program corresponding to DS minimization. We extend existing convergence properties of DCA, and connect them to convergence properties on the DS problem. Our results on DCA match the theoretical guarantees satisfied by existing DS algorithms, while providing a more complete characterization of convergence properties. In the case of CDCA, we obtain a stronger local minimality guarantee. Our numerical results show that our proposed algorithms outperform existing baselines on two applications: speech corpus selection and feature selection.
• Abstract（参考訳）: 2つの部分モジュラ(DS)関数の違いを最小化することは、様々な機械学習問題に自然に発生する問題である。 DS問題は2つの凸関数(DC)の差の最小化として等価に定式化できることはよく知られているが、既存のアルゴリズムはこの接続を完全に利用していない。 DC問題に対する古典的アルゴリズムはDCアルゴリズム (DCA) と呼ばれる。 DS最小化に対応するDCプログラムに適用したDCAの変種とその完全形(CDCA)を紹介する。 我々は, dca の既存の収束特性を拡張し, ds 問題の収束特性と接続する。 dcaの結果は既存のdsアルゴリズムが満たした理論的な保証と一致し、収束特性のより完全なキャラクタリゼーションを提供する。 CDCAの場合、より強力な局所最小性保証が得られる。 提案アルゴリズムは,音声コーパス選択と特徴選択の2つの応用において,既存のベースラインよりも優れていることを示す。

関連論文リスト

• Distributed Difference of Convex Optimization [1.2661010067882734]
  $-f_i$ と $-f_i$ の $-差分の違いによる各エージェントにおけるn$ エージェントの局所目的関数を含む分散問題のクラスを示す。 DDC-Consensusアルゴリズムは、正規化されていない分散二乗問題を解くために開発された。
  論文  参考訳（メタデータ） (2024-07-23T14:41:32Z)
• Two-Stage ML-Guided Decision Rules for Sequential Decision Making under Uncertainty [55.06411438416805]
  SDMU (Sequential Decision Making Under Uncertainty) は、エネルギー、金融、サプライチェーンといった多くの領域において、ユビキタスである。 いくつかのSDMUは、自然にマルチステージ問題(MSP)としてモデル化されているが、結果として得られる最適化は、計算の観点からは明らかに困難である。 本稿では,2段階の一般決定規則(TS-GDR)を導入し,線形関数を超えて政策空間を一般化する手法を提案する。 TS-GDRの有効性は、TS-LDR(Two-Stage Deep Decision Rules)と呼ばれるディープリカレントニューラルネットワークを用いたインスタンス化によって実証される。
  論文  参考訳（メタデータ） (2024-05-23T18:19:47Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)
• Fixed-Point Automatic Differentiation of Forward--Backward Splitting Algorithms for Partly Smooth Functions [4.389150156866014]
  近位分割アルゴリズムの固定点反復にインプリシット(ID)と自動微分(AD)を適用する。 これらのアルゴリズムによって生成される列のADが解写像の微分に収束することを示す。 FPAD(Fixed-Point Automatic Differentiation)と呼ばれる自動微分の変種については、逆モードADのメモリオーバーヘッド問題を改善する。
  論文  参考訳（メタデータ） (2022-08-05T11:27:55Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Manifold-Aware Deep Clustering: Maximizing Angles between Embedding Vectors Based on Regular Simplex [11.45476110868809]
  多様体対応直流 (M-DC) は, もともとの直流よりも効率よく超空間利用を向上させることができる。 本手法は,正規表現の性質に基づいて,超空間の目標角度を最大化することを目的とした一意な損失関数を導出する。
  論文  参考訳（メタデータ） (2021-06-04T08:27:01Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• A Refined Inertial DCA for DC Programming [0.0]
  目的関数がレベル境界である定常型(dc)プログラミング問題を考える。 古典的なDCアルゴリズム(DCA)は、ある種の問題を解決することで知られており、臨界点を返す。 そこで本研究では,2つの改良型DCA(RInDCA)を提案する。
  論文  参考訳（メタデータ） (2021-04-30T04:21:57Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。 実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
  論文  参考訳（メタデータ） (2020-10-26T01:33:05Z)

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

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