論文の概要: Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

• arxiv url: http://arxiv.org/abs/2604.03419v1
• Date: Fri, 03 Apr 2026 19:32:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-07 15:49:18.563667
• Title: Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization
• Title（参考訳）: 拡張性サブモジュール最適化のためのアダプティブ閾値駆動型連続グリード法
• Authors: Mohammadreza Rostami, Solmaz S. Kia,
• Abstract要約: マットロイド制約の下でのサブモジュールは、センシング、データマージ、アクティブラーニング、リソース割り当てなどの応用において、最適化の基本的な問題である。 textitATCG(underlineAdaptive underlineThresholded underlineThresholded underlineThresholded underlineGreedy)を提案する。 CIFAR-10動物データセットを用いたクラスバランス型プロトタイプ選択問題の実験
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular maximization under matroid constraints is a fundamental problem in combinatorial optimization with applications in sensing, data summarization, active learning, and resource allocation. While the Sequential Greedy (SG) algorithm achieves only a $\frac{1}{2}$-approximation due to irrevocable selections, Continuous Greedy (CG) attains the optimal $\bigl(1-\frac{1}{e}\bigr)$-approximation via the multilinear relaxation, at the cost of a progressively dense decision vector that forces agents to exchange feature embeddings for nearly every ground-set element. We propose \textit{ATCG} (\underline{A}daptive \underline{T}hresholded \underline{C}ontinuous \underline{G}reedy), which gates gradient evaluations behind a per-partition progress ratio $η_i$, expanding each agent's active set only when current candidates fail to capture sufficient marginal gain, thereby directly bounding which feature embeddings are ever transmitted. Theoretical analysis establishes a curvature-aware approximation guarantee with effective factor $τ_{\mathrm{eff}}=\max\{τ,1-c\}$, interpolating between the threshold-based guarantee and the low-curvature regime where \textit{ATCG} recovers the performance of CG. Experiments on a class-balanced prototype selection problem over a subset of the CIFAR-10 animal dataset show that \textit{ATCG} achieves objective values comparable to those of the full CG method while substantially reducing communication overhead through adaptive active-set expansion.
• Abstract（参考訳）: マトロイド制約の下でのサブモジュラー最大化は、センシング、データ要約、アクティブラーニング、リソース割り当ての応用と組み合わせ最適化の基本的な問題である。 逐次グリーディ(SG)アルゴリズムは、取り消し不能な選択による$\frac{1}{2}$-approximationしか達成しないが、連続グリーディ(CG)は、ほとんどすべての接地要素に対して機能埋め込みを交換する漸進的な決定ベクトルのコストで、多重線型緩和による$-approximationを最適な$\bigl(1-\frac{1}{e}\bigr)$-approximationに達する。 我々は,各エージェントのアクティブなセットを,現在の候補が十分な限界ゲインを達成できなかった場合にのみ拡張し,どの機能埋め込みが送信されるかを直接的に境界付けることを目的として,その勾配評価を分割プログレス比$η_i$でゲートする, \textit{ATCG} (\underline{A}daptive \underline{T}hresholded \underline{C}ontinuous \underline{G}reedy)を提案する。 理論的解析により、有効係数 $τ_{\mathrm{eff}}=\max\{τ,1-c\}$ で曲率を考慮した近似を保証する。 CIFAR-10動物データセットのサブセット上でのクラスバランスのプロトタイプ選択問題に対する実験により, <textit{ATCG} は完全なCG法に匹敵する客観的な値を達成し, 適応能動集合展開による通信オーバーヘッドを大幅に低減することを示した。

関連論文リスト

• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。 また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-03-23T02:30:01Z)
• DRAFTO: Decoupled Reduced-space and Adaptive Feasibility-repair Trajectory Optimization for Robotic Manipulators [4.0407133618465005]
  本稿では、トラジェクトリ最適化のための新しいアルゴリズム、Decoupled Reduced-spaceとAdaptive Feasibility-Repair Trajectory Optimization (DRAFTO)を提案する。 連立限界実現性を扱いながら繰り返し制約された最適化の回数を減らすため、最適化を低空間ガウスニュートン(Gass-Newton, GN)降下に分離する。 CHOMP, TrajOpt, GPMP2, FACTOなどの最適化型プランナに対するベンチマークテストの結果, 様々なシナリオやタスクにおいて高い効率性と信頼性が検証された。
  論文  参考訳（メタデータ） (2026-03-10T20:24:42Z)
• An Accelerated Alternating Partial Bregman Algorithm for ReLU-based Matrix Decomposition [0.0]
  本稿では,非負行列上に補正されたスパース低ランク特性について検討する。 本稿では,クラスタリングと圧縮タスクに有用な構造を取り入れた新しい正規化項を提案する。 我々は、任意の$Lge 1$に対して常に持つ$L$-smoothプロパティを維持しながら、対応する閉形式解を導出する。
  論文  参考訳（メタデータ） (2025-03-04T08:20:34Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Implicit Bias and Fast Convergence Rates for Self-attention [26.766649949420746]
  本稿では,変圧器の定義機構である自己注意の基本的な最適化原理について考察する。 線形分類におけるデコーダを用いた自己アテンション層における勾配ベースの暗黙バイアスを解析する。
  論文  参考訳（メタデータ） (2024-02-08T15:15:09Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)

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

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