論文の概要: From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization

• arxiv url: http://arxiv.org/abs/2405.00065v3
• Date: Thu, 31 Oct 2024 23:57:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-04 14:32:55.153339
• Title: From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
• Title（参考訳）: リニアからリニアへの最適化:定常および非定常DR-サブモジュール最適化への新たなフレームワーク
• Authors: Mohammad Pedramfar, Vaneet Aggarwal,
• Abstract要約: 本稿では,モノトーン非線型やDR-サブモジュラリティなど,様々な環境での凹凸とDR-サブモジュラリティの概念を紹介する。 一般的なメタアルゴリズムは、線形/四進関数を上線形/四進関数を最適化するものに変換する。
• 参考スコア（独自算出の注目度）: 33.38582292895673
• License:
• Abstract: This paper introduces the notion of upper-linearizable/quadratizable functions, a class that extends concavity and DR-submodularity in various settings, including monotone and non-monotone cases over different convex sets. A general meta-algorithm is devised to convert algorithms for linear/quadratic maximization into ones that optimize upper-linearizable/quadratizable functions, offering a unified approach to tackling concave and DR-submodular optimization problems. The paper extends these results to multiple feedback settings, facilitating conversions between semi-bandit/first-order feedback and bandit/zeroth-order feedback, as well as between first/zeroth-order feedback and semi-bandit/bandit feedback. Leveraging this framework, new algorithms are derived using existing results as base algorithms for convex optimization, improving upon state-of-the-art results in various cases. Dynamic and adaptive regret guarantees are obtained for DR-submodular maximization, marking the first algorithms to achieve such guarantees in these settings. Notably, the paper achieves these advancements with fewer assumptions compared to existing state-of-the-art results, underscoring its broad applicability and theoretical contributions to non-convex optimization.
• Abstract（参考訳）: 本稿では,異なる凸集合上の単調および非単調なケースを含む,様々な条件下での凹凸とDR-部分モジュラリティを拡張するクラスである,上線形可乗関数(上線形可乗関数)の概念を紹介する。 一般メタアルゴリズムは、線形/四次最大化のためのアルゴリズムを、上線形可微分/四次可微分関数を最適化するアルゴリズムに変換するために考案され、凹凸問題とDR-部分モジュラー最適化問題に統一的なアプローチを提供する。 本論文は、これらの結果を複数のフィードバック設定に拡張し、半帯域/一階フィードバックと帯域/二階フィードバックの変換を容易にし、一階フィードバックと半帯域/二階フィードバックの変換を容易にする。 このフレームワークを利用すると、既存の結果から凸最適化のベースアルゴリズムとして新たなアルゴリズムが導出され、様々なケースで最先端の結果が改善される。 DR-サブモジュラー最大化のために動的かつ適応的な後悔保証が得られ、これらの設定でそのような保証を達成するための最初のアルゴリズムがマークされる。 特に,本論文は,既存の最先端結果と比較して仮定を少なくして,その広範な適用性と非凸最適化への理論的貢献を裏付けるものである。

関連論文リスト

• Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization [28.598226670015315]
  本稿では,DR-サブモジュラー最適化のための統合プロジェクションフリーのFrank-Wolfe型アルゴリズムを提案する。 非単調な設定で考慮されたすべての問題に対して、提案アルゴリズムは、証明されたサブ線形$alpha$-regret境界を持つ最初のものであるか、あるいは、最先端よりもより優れた$alpha$-regret境界を持つかのいずれかである。
  論文  参考訳（メタデータ） (2024-03-15T07:05:44Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions [9.518010235273785]
  両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。 我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
  論文  参考訳（メタデータ） (2023-06-21T07:32:29Z)
• Online Dynamic Submodular Optimization [0.0]
  オンラインバイナリ最適化のための証明可能な性能を持つ新しいアルゴリズムを提案する。 高速な需要応答とリアルタイム分散ネットワーク再構成という2つのパワーシステムアプリケーションでアルゴリズムを数値的にテストする。
  論文  参考訳（メタデータ） (2023-06-19T10:37:15Z)
• Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods [20.118513136686452]
  一階最適化法は、未決定の訓練目標を最小化する際に、本質的に他よりも特定の解を優先する傾向がある。 本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。 私たちの加速速度は、このゲームフレームワークにおけるオンライン学習アルゴリズムの残念な部分を活用することによって導き出されます。
  論文  参考訳（メタデータ） (2023-05-27T18:16:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Primal-Dual Sequential Subspace Optimization for Saddle-point Problems [3.9582154141918964]
  大規模サドル点問題に対する逐次部分空間最適化手法を提案する。 低次元部分空間における補助的サドル点問題(英語版)を、原始整数双対変数上の一階情報から導かれる方向によって解決する。 実験結果は、一般的な一階法と比較して、かなり良い収束性を示した。
  論文  参考訳（メタデータ） (2020-08-20T18:19:19Z)
• 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)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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