論文の概要: Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications

• arxiv url: http://arxiv.org/abs/2005.02578v4
• Date: Fri, 12 Jun 2020 01:07:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-06 06:16:31.823977
• Title: Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications
• Title（参考訳）: 微分可能なグレディ部分モジュラー最大化:保証、勾配推定器および応用
• Authors: Shinsaku Sakaue
• Abstract要約: 我々は,単調部分関数のグリーディアルゴリズムを微分可能とする理論的に保証された多元性フレームワークを確立する。 乱数化によってグリーディアルゴリズムを滑らかにし、濃度や$kappa$-extensible(拡張可能なシステム制約)の場合に期待する元の近似保証をほぼ回復することを示した。
• 参考スコア（独自算出の注目度）: 15.191184049312467
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by, e.g., sensitivity analysis and end-to-end learning, the demand for differentiable optimization algorithms has been significantly increasing. In this paper, we establish a theoretically guaranteed versatile framework that makes the greedy algorithm for monotone submodular function maximization differentiable. We smooth the greedy algorithm via randomization, and prove that it almost recovers original approximation guarantees in expectation for the cases of cardinality and $\kappa$-extensible system constrains. We also show how to efficiently compute unbiased gradient estimators of any expected output-dependent quantities. We demonstrate the usefulness of our framework by instantiating it for various applications.
• Abstract（参考訳）: 感度分析やエンドツーエンド学習などの動機付けにより、微分可能最適化アルゴリズムの需要は大幅に増加した。 本稿では,単調部分モジュラー関数の最大化を微分可能とする欲望アルゴリズムを理論的に保証した多機能フレームワークを提案する。 ランダム化によってグリーディアルゴリズムを滑らかにし、濃度や$\kappa$-extensibleシステム制約の場合に期待する元の近似保証をほぼ回復することを示した。 また、予測出力依存量の非バイアス勾配推定器を効率的に計算する方法を示す。 各種アプリケーション向けにインスタンス化することで,フレームワークの有用性を示す。

関連論文リスト

• An Accelerated Block Proximal Framework with Adaptive Momentum for Nonconvex and Nonsmooth Optimization [2.323238724742687]
  非平滑および非平滑最適化のための適応モーメント(ABPL$+$)を有する加速ブロック近位線形フレームワークを提案する。 いくつかのアルゴリズムでは外挿ステップの潜在的な原因を解析し、比較プロセスの強化によってこの問題を解消する。 我々はアルゴリズムを勾配ステップと線形補間ステップの更新を含む任意のシナリオに拡張する。
  論文  参考訳（メタデータ） (2023-08-23T13:32:31Z)
• One-step differentiation of iterative algorithms [7.9495796547433395]
  本稿では, 自動微分法としての一段階微分法, あるいはジャコビアンフリーバックプロパゲーションについて検討する。 両レベル最適化の結果とともに, 具体例を用いた完全理論的近似解析を行う。
  論文  参考訳（メタデータ） (2023-05-23T07:32:37Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• A Unified Convergence Theorem for Stochastic Optimization Methods [4.94128206910124]
  一連の統一最適化手法に対する収束結果の導出に使用される基本的な統一収束定理を提供する。 直接応用として、一般的な設定下での収束結果をほぼ確実に回復する。
  論文  参考訳（メタデータ） (2022-06-08T14:01:42Z)
• Robust Subset Selection by Greedy and Evolutionary Pareto Optimization [23.0838604893412]
  サブセット選択は、ある目的関数を最大化するために、グラウンドセットからサブセットを選択することを目的としている。 グリーディアルゴリズムは1-e-betagamma$の近似比を得ることができ、$beta$と$gamma$は対象関数の相関と部分モジュラリティ比である。
  論文  参考訳（メタデータ） (2022-05-03T11:00:54Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• A theoretical and empirical study of new adaptive algorithms with additional momentum steps and shifted updates for stochastic non-convex optimization [0.0]
  適応最適化アルゴリズムは学習分野の鍵となる柱を表現していると考えられる。 本稿では,異なる非滑らかな目的問題に対する適応運動量法を提案する。
  論文  参考訳（メタデータ） (2021-10-16T09:47:57Z)
• SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients [99.13839450032408]
  一般的な問題を解決するための適応アルゴリズムのための普遍的な枠組みを設計することが望まれる。 特に,本フレームワークは,非収束的設定支援の下で適応的手法を提供する。
  論文  参考訳（メタデータ） (2021-06-15T15:16:28Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Efficient and Modular Implicit Differentiation [68.74748174316989]
  最適化問題の暗黙的な微分のための統一的で効率的かつモジュール化されたアプローチを提案する。 一見単純な原理は、最近提案された多くの暗黙の微分法を復元し、新しいものを簡単に作成できることを示している。
  論文  参考訳（メタデータ） (2021-05-31T17:45:58Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)

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

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