論文の概要: Consistent Submodular Maximization

• arxiv url: http://arxiv.org/abs/2405.19977v1
• Date: Thu, 30 May 2024 11:59:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 14:38:07.754623
• Title: Consistent Submodular Maximization
• Title（参考訳）: Consistent Submodular Maximization
• Authors: Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam,
• Abstract要約: 定性制約下での単調部分モジュラ関数の最大化は、データマイニングや機械学習におけるいくつかの応用において古典的な最適化課題である。 本稿では, 安定解を持ちながら, ストリーミング方式で要素が到着し, 最適解に対する定数近似が維持されるという, 一貫性の制約のある動的環境において, この問題を考察する。 この設定では、一貫性と近似品質のトレードオフが異なるアルゴリズムを提供しています。
• 参考スコア（独自算出の注目度）: 27.266085572522847
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper we study this problem in a dynamic environment with consistency constraints: elements arrive in a streaming fashion and the goal is maintaining a constant approximation to the optimal solution while having a stable solution (i.e., the number of changes between two consecutive solutions is bounded). We provide algorithms in this setting with different trade-offs between consistency and approximation quality. We also complement our theoretical results with an experimental analysis showing the effectiveness of our algorithms in real-world instances.
• Abstract（参考訳）: 濃度制約下での単調部分モジュラ函数の最大化は、データマイニングや機械学習におけるいくつかの応用において古典的な最適化課題である。 本稿では, 安定解(すなわち, 2つの連続解間の変化数は有界)を持ちながら, ストリーミング方式で要素が到着し, 最適解に対する定数近似が維持されることを目標とする動的環境において, この問題を考察する。 この設定では、一貫性と近似品質のトレードオフが異なるアルゴリズムを提供しています。 また、実世界の事例におけるアルゴリズムの有効性を示す実験分析により、理論的結果を補完する。

関連論文リスト

• A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints [4.6796315389639815]
  分散最適化問題は分散制約の存在下では解決できない。 目的関数の勾配と制約写像のヤコビアンを同時に追跡する新しいアルゴリズムを導入する。 合成と実世界の両方のデータセットに数値的な結果を示す。
  論文  参考訳（メタデータ） (2024-09-08T06:57:35Z)
• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。 このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
  論文  参考訳（メタデータ） (2024-07-29T13:54:28Z)
• Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties [12.095075636344536]
  本稿では,制約付き多種多様な問題を捕捉する,確率制約付き部分モジュラー最適化問題について検討する。 所与の最適解に対する定数近似比という,高品質な解を得ることのできるグリーディアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-23T04:48:49Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
  本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。 我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。 その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
  論文  参考訳（メタデータ） (2020-06-22T03:13:07Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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