論文の概要: Faster Margin Maximization Rates for Generic Optimization Methods
- arxiv url: http://arxiv.org/abs/2305.17544v1
- Date: Sat, 27 May 2023 18:16:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 18:26:31.175545
- Title: Faster Margin Maximization Rates for Generic Optimization Methods
- Title(参考訳): 汎用最適化法におけるマージン最大化速度の高速化
- Authors: Guanghui Wang, Zihao Hu, Vidya Muthukumar, Jacob Abernethy
- Abstract要約: 1次最適化法は、与えられたトレーニング目標を複数の局所最適化で最小化する場合、他の方法よりも特定の解を好む傾向にある。
近年の研究では、勾配差に基づく手法は、$ell$-maximal margin classifierに対して暗黙の偏見を示すことが示されている。
本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。
- 参考スコア(独自算出の注目度): 23.185655992407742
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: First-order optimization methods tend to inherently favor certain solutions
over others when minimizing a given training objective with multiple local
optima. This phenomenon, known as implicit bias, plays a critical role in
understanding the generalization capabilities of optimization algorithms.
Recent research has revealed that gradient-descent-based methods exhibit an
implicit bias for the $\ell_2$-maximal margin classifier in the context of
separable binary classification. In contrast, generic optimization methods,
such as mirror descent and steepest descent, have been shown to converge to
maximal margin classifiers defined by alternative geometries. However, while
gradient-descent-based algorithms demonstrate fast implicit bias rates, the
implicit bias rates of generic optimization methods have been relatively slow.
To address this limitation, in this paper, 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 learning dynamic that solves a regularized bilinear
game, providing a unified framework for analyzing the implicit bias of various
optimization methods. The accelerated rates are derived leveraging the regret
bounds of online learning algorithms within this game framework.
- Abstract(参考訳): 一階最適化法は、与えられた訓練目標を複数の局所最適度で最小化する場合、本質的に他よりも特定の解を好む傾向にある。
この現象は暗黙バイアスと呼ばれ、最適化アルゴリズムの一般化能力を理解する上で重要な役割を果たしている。
近年の研究では、分別可能な二分分類の文脈で$\ell_2$-maximal margin分類器に対して、勾配日光に基づく手法が暗黙のバイアスを示すことが明らかになっている。
対照的に、ミラー降下や急勾配のような一般的な最適化手法は、代替測度によって定義される最大辺分類器に収束することが示されている。
しかし, 勾配日光に基づくアルゴリズムは, 暗黙的バイアス率を高速に示す一方で, 一般最適化手法の暗黙的バイアス率は比較的遅い。
本稿では,この制限に対処するために,ミラー降下と最急降下アルゴリズムに対する最先端の暗黙的バイアス率について述べる。
我々の主な手法は、汎用最適化アルゴリズムを、正規化双線形ゲームを解くオンライン学習ダイナミクスに変換し、様々な最適化手法の暗黙のバイアスを分析するための統一的なフレームワークを提供する。
この加速レートは、このゲームフレームワークにおけるオンライン学習アルゴリズムの後悔の限界を利用したものである。
関連論文リスト
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳(メタデータ) (2024-08-17T02:22:08Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。