論文の概要: Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

• arxiv url: http://arxiv.org/abs/2501.18183v1
• Date: Thu, 30 Jan 2025 07:28:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-31 15:12:26.913583
• Title: Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
• Title（参考訳）: 分散プロジェクションフリーオンライン上言語最適化とDR-サブモジュラー最適化への応用
• Authors: Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal,
• Abstract要約: 分散プロジェクションフリー最適化のための新しいフレームワークを提案する。 我々は、高次線形化可能な関数フレームワークの柔軟性で分散最適化手法を活用する。
• 参考スコア（独自算出の注目度）: 29.705337940879705
• License:
• Abstract: We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of $O(T^{1-\theta/2})$ with communication complexity of $O(T^{\theta})$ and number of linear optimization oracle calls of $O(T^{2\theta})$ for decentralized upper-linearizable function optimization, for any $0\le \theta \le 1$. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.
• Abstract（参考訳）: 本稿では、分散化されたプロジェクションフリー最適化のための新しいフレームワークを導入し、プロジェクションフリーな手法をより広範な上線形可微分関数のクラスに拡張する。 提案手法は,従来のDR-サブモジュラー関数最適化を効果的に一般化する上で,高線形化可能な関数フレームワークの柔軟性を活かした分散最適化手法を利用する。 我々は、$O(T^{1-\theta/2})$の通信複雑性と$O(T^{\theta})$の線形最適化オラクルコール数で、任意の$0\le \theta \le 1$に対して、分散化上線形可微分関数最適化に対して、$O(T^{2\theta})$の後悔を得る。 このアプローチにより、一般凸制約付き単調アップ・コンケーブ最適化と一般凸制約付き非単調アップ・コンケーブ最適化の最初の結果が得られる。 さらに、上記の一階フィードバックの結果を、ゼロ階フィードバック、半帯域フィードバック、および帯域フィードバックに拡張する。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
  双レベル最適化は階層型機械学習問題に対処するための基本的な数学的枠組みとなっている。 従来の勾配に基づく二段階最適化アルゴリズムは、大規模アプリケーションの要求を満たすには不適である。 両レベル最適化のためのメタ勾配の偏りのない近似を実現するための$(textFG)2textU$を導入する。
  論文  参考訳（メタデータ） (2024-06-20T08:21:52Z)
• From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization [33.38582292895673]
  本稿では,モノトーン非線型やDR-サブモジュラリティなど,様々な環境での凹凸とDR-サブモジュラリティの概念を紹介する。 一般的なメタアルゴリズムは、線形/四進関数を上線形/四進関数を最適化するものに変換する。
  論文  参考訳（メタデータ） (2024-04-27T06:19:30Z)
• Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization [28.598226670015315]
  本稿では,DR-サブモジュラー最適化のための統合プロジェクションフリーのFrank-Wolfe型アルゴリズムを提案する。 非単調な設定で考慮されたすべての問題に対して、提案アルゴリズムは、証明されたサブ線形$alpha$-regret境界を持つ最初のものであるか、あるいは、最先端よりもより優れた$alpha$-regret境界を持つかのいずれかである。
  論文  参考訳（メタデータ） (2024-03-15T07:05:44Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.1044138971639734]
  強い凸関数制約を受ける凸関数を最小化するために,高速化された原始双対アルゴリズムを導入する。 特にGoogleのパーソナライズされたPageRank問題では、スパシティ誘導最適化におけるメソッドのパフォーマンスが優れています。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Stochastic Coordinate Minimization with Progressive Precision for Stochastic Convex Optimization [16.0251555430107]
  凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。 最適精度制御と結果の順序-最適後悔性能を確立する。 提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
  論文  参考訳（メタデータ） (2020-03-11T18:42:40Z)

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

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