論文の概要: On Acceleration of Gradient-Based Empirical Risk Minimization using
Local Polynomial Regression
- arxiv url: http://arxiv.org/abs/2204.07702v1
- Date: Sat, 16 Apr 2022 02:39:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-20 12:29:53.693542
- Title: On Acceleration of Gradient-Based Empirical Risk Minimization using
Local Polynomial Regression
- Title（参考訳）: 局所多項式回帰を用いた勾配に基づく経験的リスク最小化の加速について
- Authors: Ekaterina Trimbach, Edward Duc Hien Nguyen, and C\'esar A. Uribe
- Abstract要約: 最近提案された局所多項式補間法(LPIGD)による近似解経験的リスク問題(ERM)の高速化について検討した。
我々は条件数$sigma$と強く凸で滑らかな損失関数にフォーカスする。
LPI-GDに基づく問題を高速化する2つの手法を提案し,その複雑さを$tildeOleft(sqrtsigma md log (1/varepsilon)$とする。
- 参考スコア（独自算出の注目度）: 0.491574468325115
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the acceleration of the Local Polynomial Interpolation-based
Gradient Descent method (LPI-GD) recently proposed for the approximate solution
of empirical risk minimization problems (ERM). We focus on loss functions that
are strongly convex and smooth with condition number $\sigma$. We additionally
assume the loss function is $\eta$-H\"older continuous with respect to the
data. The oracle complexity of LPI-GD is $\tilde{O}\left(\sigma m^d
\log(1/\varepsilon)\right)$ for a desired accuracy $\varepsilon$, where $d$ is
the dimension of the parameter space, and $m$ is the cardinality of an
approximation grid. The factor $m^d$ can be shown to scale as
$O((1/\varepsilon)^{d/2\eta})$. LPI-GD has been shown to have better oracle
complexity than gradient descent (GD) and stochastic gradient descent (SGD) for
certain parameter regimes. We propose two accelerated methods for the ERM
problem based on LPI-GD and show an oracle complexity of
$\tilde{O}\left(\sqrt{\sigma} m^d \log(1/\varepsilon)\right)$. Moreover, we
provide the first empirical study on local polynomial interpolation-based
gradient methods and corroborate that LPI-GD has better performance than GD and
SGD in some scenarios, and the proposed methods achieve acceleration.
- Abstract（参考訳）: 我々は最近, 経験的リスク最小化問題 (ERM) の近似解法として, 局所多項式補間法 (LPI-GD) の高速化について検討した。
我々は、条件番号$\sigma$ の強い凸かつ滑らかな損失関数に焦点を当てる。
さらに、損失関数はデータに関して$\eta$-h\"older連続であると仮定する。
LPI-GD のオラクル複雑性は $\tilde{O}\left(\sigma m^d \log(1/\varepsilon)\right)$ for a desired accuracy $\varepsilon$, where $d$ はパラメータ空間の次元、$m$ は近似格子の濃度である。
因子 $m^d$ は $O((1/\varepsilon)^{d/2\eta})$ とスケールできる。
LPI-GDは,特定のパラメータ状態において,勾配降下 (GD) や確率勾配降下 (SGD) よりもオラクルの複雑さが高いことが示されている。
LPI-GDに基づくERM問題の2つの高速化手法を提案し、$\tilde{O}\left(\sqrt{\sigma} m^d \log(1/\varepsilon)\right)$のオラクル複雑性を示す。
さらに,LPI-GD が GD や SGD よりも優れた性能を持つことを示す,局所多項式補間に基づく勾配法に関する最初の実証的研究を行い,提案手法を加速させる。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Span-Based Optimal Sample Complexity for Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2023-11-22T15:34:44Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization [52.25843977506935]
有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。
そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
論文 参考訳（メタデータ） (2022-11-03T14:41:46Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Gradient Descent for Low-Rank Functions [36.56489593549855]
例えば、深層ニューラルネットワークのトレーニングのような機械学習タスクでは、損失関数は入力のわずか数方向に大きく変化する。
提案した emphLowRank Descent は $mathcalO(plog(1/epsilon))$gd と $mathcalOp/epsilon2)$p/epsilon2)$を識別して $epsilon 勾配関数を求める。
論文 参考訳（メタデータ） (2022-06-16T15:58:05Z) - A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。
高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。
提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
論文 参考訳（メタデータ） (2022-02-19T22:12:30Z) - Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。
SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。
我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
論文 参考訳（メタデータ） (2021-10-25T07:20:05Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳（メタデータ） (2021-10-21T19:22:14Z) - Gradient-Based Empirical Risk Minimization using Local Polynomial
Regression [39.29885444997579]
この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。
損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
論文 参考訳（メタデータ） (2020-11-04T20:10:31Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。