論文の概要: An algorithmic view of $\ell_2$ regularization and some path-following
algorithms
- arxiv url: http://arxiv.org/abs/2107.03322v1
- Date: Wed, 7 Jul 2021 16:00:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-08 16:00:43.585078
- Title: An algorithmic view of $\ell_2$ regularization and some path-following
algorithms
- Title（参考訳）: $\ell_2$正規化のアルゴリズムビューと経路追従アルゴリズム
- Authors: Yunzhang Zhu and Renxiong Liu
- Abstract要約: 凸損失関数に対する$ell$-regularized Solution pathと通常の微分方程式(ODE)の解との等価性を確立する。
この等価性は、溶液経路を勾配降下のハイブリッドの流れと見なすことができ、ニュートン法は経験的損失に適用できることを示した。
ホモトピー法と数値ODE解法に基づく新しい経路追従アルゴリズムを提案し,解経路を数値的に近似する。
- 参考スコア（独自算出の注目度）: 7.6146285961466
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish an equivalence between the $\ell_2$-regularized solution path
for a convex loss function, and the solution of an ordinary differentiable
equation (ODE). Importantly, this equivalence reveals that the solution path
can be viewed as the flow of a hybrid of gradient descent and Newton method
applying to the empirical loss, which is similar to a widely used optimization
technique called trust region method. This provides an interesting algorithmic
view of $\ell_2$ regularization, and is in contrast to the conventional view
that the $\ell_2$ regularization solution path is similar to the gradient flow
of the empirical loss.New path-following algorithms based on homotopy methods
and numerical ODE solvers are proposed to numerically approximate the solution
path. In particular, we consider respectively Newton method and gradient
descent method as the basis algorithm for the homotopy method, and establish
their approximation error rates over the solution path. Importantly, our theory
suggests novel schemes to choose grid points that guarantee an arbitrarily
small suboptimality for the solution path. In terms of computational cost, we
prove that in order to achieve an $\epsilon$-suboptimality for the entire
solution path, the number of Newton steps required for the Newton method is
$\mathcal O(\epsilon^{-1/2})$, while the number of gradient steps required for
the gradient descent method is $\mathcal O\left(\epsilon^{-1}
\ln(\epsilon^{-1})\right)$. Finally, we use $\ell_2$-regularized logistic
regression as an illustrating example to demonstrate the effectiveness of the
proposed path-following algorithms.
- Abstract（参考訳）: 凸損失関数に対する$\ell_2$-regularized Solution pathと通常の微分方程式(ODE)の解との等価性を確立する。
この等価性は、解経路を勾配降下のハイブリッドの流れと見なすことができ、ニュートン法は経験的損失に適用でき、これは信頼領域法と呼ばれる広く使われている最適化手法に類似している。
これは$\ell_2$正規化の興味深いアルゴリズム的なビューを提供し、$\ell_2$正規化解パスは経験的損失の勾配流と似ているという従来の見解とは対照的である。
特に,ホモトピー法の基本アルゴリズムとしてニュートン法と勾配降下法をそれぞれ考慮し,解経路上の近似誤差率を定式化する。
重要なことに、この理論は解経路の任意に小さい部分最適性を保証する格子点を選択するための新しいスキームを提案する。
計算コストの観点からは、解経路全体に対して$\epsilon$-suboptimalityを達成するためには、ニュートン法に必要なニュートンのステップの数は$\mathcal o(\epsilon^{-1/2})$であり、勾配降下法に必要な勾配ステップの数は$\mathcal o\left(\epsilon^{-1} \ln(\epsilon^{-1})\right)である。
最後に,提案する経路追従アルゴリズムの有効性を示す例として,$\ell_2$-regularized logistic regressionを用いた。
関連論文リスト
- Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。
これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
論文 参考訳（メタデータ） (2024-12-05T10:38:29Z) - Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods [18.47705532817026]
本研究では,スムーズな関数を持つ$epsilon$firstorder stationary point (FOSP) を求める問題について検討する。
本稿では,このオンライン学習問題を解決するために,新しい楽観的な準勾配近似法を提案する。
論文 参考訳（メタデータ） (2024-12-03T05:20:05Z) - Beyond Discretization: Learning the Optimal Solution Path [3.9675360887122646]
本稿では,解経路を基底関数の集合でパラメータ化し,エンフィングル最適化問題を解く手法を提案する。
我々の手法は、離散化よりも相当に複雑化している。
また、機械学習に共通する特殊なケースに対して、より強力な結果を示す。
論文 参考訳（メタデータ） (2024-10-18T22:23:42Z) - A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning [9.628032156001073]
立方正則化を取り入れた2つのポリシーニュートンアルゴリズムを提案する。
どちらのアルゴリズムも確率比法を用いて値関数の勾配とヘシアンを推定する。
特に、我々のアルゴリズムのサンプル複雑さが$epsilon$-SOSPを見つけるのに$O(epsilon-3.5)$であり、これは最先端のサンプル複雑性の$O(epsilon-4.5)$よりも改善されている。
論文 参考訳（メタデータ） (2023-04-21T13:43:06Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。
理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
論文 参考訳（メタデータ） (2022-07-30T13:05:01Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳（メタデータ） (2020-06-03T04:00:52Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。