論文の概要: Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods

• arxiv url: http://arxiv.org/abs/2305.17544v2
• Date: Sun, 7 Apr 2024 18:45:20 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-10 05:17:18.057244
• Title: Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods
• Title（参考訳）: ジェネリックおよび逆ロバスト最適化法におけるより高速なマージン最大化率
• Authors: Guanghui Wang, Zihao Hu, Claudio Gentile, Vidya Muthukumar, Jacob Abernethy,
• Abstract要約: 一階最適化法は、未決定の訓練目標を最小化する際に、本質的に他よりも特定の解を優先する傾向がある。 本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。 私たちの加速速度は、このゲームフレームワークにおけるオンライン学習アルゴリズムの残念な部分を活用することによって導き出されます。
• 参考スコア（独自算出の注目度）: 20.118513136686452
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: First-order optimization methods tend to inherently favor certain solutions over others when minimizing an underdetermined training objective that has multiple global optima. This phenomenon, known as implicit bias, plays a critical role in understanding the generalization capabilities of optimization algorithms. Recent research has revealed that in separable binary classification tasks gradient-descent-based methods exhibit an implicit bias for the $\ell_2$-maximal margin classifier. Similarly, generic optimization methods, such as mirror descent and steepest descent, have been shown to converge to maximal margin classifiers defined by alternative geometries. While gradient-descent-based algorithms provably achieve fast implicit bias rates, corresponding rates in the literature for generic optimization methods are relatively slow. To address this limitation, we present a series of state-of-the-art implicit bias rates for mirror descent and steepest descent algorithms. Our primary technique involves transforming a generic optimization algorithm into an online optimization dynamic that solves a regularized bilinear game, providing a unified framework for analyzing the implicit bias of various optimization methods. Our accelerated rates are derived by leveraging the regret bounds of online learning algorithms within this game framework. We then show the flexibility of this framework by analyzing the implicit bias in adversarial training, and again obtain significantly improved convergence rates.
• Abstract（参考訳）: 一階最適化法は、複数の大域的最適性を持つ未決定の訓練目標を最小化する際に、本質的に他よりも特定の解を優先する傾向がある。 この現象は暗黙バイアスと呼ばれ、最適化アルゴリズムの一般化能力を理解する上で重要な役割を果たしている。 近年の研究では、分離可能な二項分類タスクにおいて勾配差に基づく手法は、$\ell_2$-maximal margin classificationifierに対して暗黙のバイアスを示すことが明らかになっている。 同様に、ミラー降下や急勾配のような一般的な最適化手法は、代替測度によって定義される最大辺分類器に収束することが示されている。 勾配差に基づくアルゴリズムは高速な暗黙バイアス率を確実に達成するが、汎用最適化手法の文献における対応する速度は比較的遅い。 この制限に対処するために、ミラー降下と最も急勾配のアルゴリズムに対して、最先端の暗黙バイアス率を示す。 我々の主要な手法は、汎用最適化アルゴリズムを正規化された双線形ゲームを解決するオンライン最適化ダイナミックに変換することであり、様々な最適化手法の暗黙バイアスを解析するための統一的なフレームワークを提供する。 私たちの加速速度は、このゲームフレームワークにおけるオンライン学習アルゴリズムの残念な部分を活用することによって導き出されます。 次に, 対人訓練における暗黙のバイアスを解析することにより, この枠組みの柔軟性を示し, また, コンバージェンス率を大幅に改善した。

関連論文リスト

• Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
  本稿では,従来の手法よりもはるかに高速な収束を実現する2段階最適化手法を提案する。 提案アルゴリズムは,様々な条件下で特徴付けられ,オンラインサンプルベース手法に特化していることを示す。
  論文  参考訳（メタデータ） (2024-05-15T19:03:08Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  このアルゴリズムは指数勾配と$p$-normアルゴリズムの組み合わせと解釈できる。 彼らはシーケンス依存の後悔の上界を達成し、スパース目標決定変数の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-08-08T11:29:55Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• Meta-Regularization: An Approach to Adaptive Choice of the Learning Rate in Gradient Descent [20.47598828422897]
  第一次下降法における学習率の適応的選択のための新しいアプローチであるtextit-Meta-Regularizationを提案する。 本手法は,正規化項を追加して目的関数を修正し,共同処理パラメータをキャストする。
  論文  参考訳（メタデータ） (2021-04-12T13:13:34Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• 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)
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems [12.010310883787911]
  我々は、弱凸(おそらく非滑らかな)最適化問題の重要なクラスを解くための、適応的な段階的な新しい手法の族を解析する。 実験結果から,提案アルゴリズムが0次勾配降下と設計変動を経験的に上回ることを示す。
  論文  参考訳（メタデータ） (2020-05-19T07:44:52Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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