論文の概要: 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分類器に対して、勾配日光に基づく手法が暗黙のバイアスを示すことが明らかになっている。
対照的に、ミラー降下や急勾配のような一般的な最適化手法は、代替測度によって定義される最大辺分類器に収束することが示されている。
しかし, 勾配日光に基づくアルゴリズムは, 暗黙的バイアス率を高速に示す一方で, 一般最適化手法の暗黙的バイアス率は比較的遅い。
本稿では,この制限に対処するために,ミラー降下と最急降下アルゴリズムに対する最先端の暗黙的バイアス率について述べる。
我々の主な手法は、汎用最適化アルゴリズムを、正規化双線形ゲームを解くオンライン学習ダイナミクスに変換し、様々な最適化手法の暗黙のバイアスを分析するための統一的なフレームワークを提供する。
この加速レートは、このゲームフレームワークにおけるオンライン学習アルゴリズムの後悔の限界を利用したものである。
関連論文リスト
- 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) - How Does Adaptive Optimization Impact Local Neural Network Geometry? [32.32593743852949]
ニューラルネットワーク最適化の文脈では、この伝統的な視点は不十分である、と我々は主張する。
我々は、アダムのような適応的な手法が、より高速な収束を期待できる領域への軌道に偏っていることを示す。
論文 参考訳(メタデータ) (2022-11-04T04:05:57Z) - Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive
Step Size [29.15132344744801]
本研究では,行列逆変換などの問題に対して,適応的なステップサイズを持つ勾配勾配の局所収束性を確立する。
これらの一階最適化法は線形あるいは線形収束を実現することができることを示す。
論文 参考訳(メタデータ) (2021-12-30T00:50:30Z) - On Constraints in First-Order Optimization: A View from Non-Smooth
Dynamical Systems [99.59934203759754]
本稿では,スムーズな制約付き最適化のための一階法について紹介する。
提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。
結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
論文 参考訳(メタデータ) (2021-07-17T11:45:13Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳(メタデータ) (2021-05-13T04:23:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。