論文の概要: Improved SVRG for quadratic functions

• arxiv url: http://arxiv.org/abs/2006.01017v2
• Date: Tue, 15 Jun 2021 07:36:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-26 06:40:18.414793
• Title: Improved SVRG for quadratic functions
• Title（参考訳）: 二次関数に対するSVRGの改良
• Authors: Nabil Kahale
• Abstract要約: ヘッセン行列 $H$ がランダム対称 $dtimes d$ 行列の期待値である二次函数を最小化する反復アルゴリズムを解析する。 最小二乗回帰、リッジ回帰、線形判別分析、正規化線形判別分析を含むいくつかのアプリケーションでは、各イテレーションの実行時間は$d$に比例する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyse an iterative algorithm to minimize quadratic functions whose Hessian matrix $H$ is the expectation of a random symmetric $d\times d$ matrix. The algorithm is a variant of the stochastic variance reduced gradient (SVRG). In several applications, including least-squares regressions, ridge regressions, linear discriminant analysis and regularized linear discriminant analysis, the running time of each iteration is proportional to $d$. Under smoothness and convexity conditions, the algorithm has linear convergence. When applied to quadratic functions, our analysis improves the state-of-the-art performance of SVRG up to a logarithmic factor. Furthermore, for well-conditioned quadratic problems, our analysis improves the state-of-the-art running times of accelerated SVRG, and is better than the known matching lower bound, by a logarithmic factor. Our theoretical results are backed with numerical experiments.
• Abstract（参考訳）: ヘッセン行列 $H$ がランダム対称 $d\times d$ 行列の期待値である二次函数を最小化する反復アルゴリズムを解析する。 このアルゴリズムは確率分散還元勾配(SVRG)の変種である。 最小二乗回帰、リッジ回帰、線形判別分析、正規化線形判別分析を含むいくつかのアプリケーションでは、各イテレーションの実行時間は$d$に比例する。 滑らかさと凸性条件下では、アルゴリズムは線形収束を持つ。 二次関数に適用すると、SVRGの最先端性能を対数係数まで改善する。 さらに, 条件の整った二次問題に対しては, 高速化されたSVRGの走行時間を改善するとともに, 対数係数により一致した下界よりも優れている。 我々の理論結果は数値実験で裏付けられている。

関連論文リスト

• Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms [28.046728466038022]
  ベクトル値出力を持つ多種多様な正規化アルゴリズムの理論的特性について検討する。 ベクトル値出力によるリッジ回帰に対するいわゆる飽和効果を厳密に検証する。 有限サンプルリスク一般ベクトル値スペクトルアルゴリズムの上限について述べる。
  論文  参考訳（メタデータ） (2024-05-23T16:45:52Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Convergence analysis of online algorithms for vector-valued kernel regression [0.42970700836450487]
  オンライン学習アルゴリズムを用いて雑音の多いベクトル値データから回帰関数を近似する問題を考察する。 RKHSノルムの期待二乗誤差は$C2 (m+1)-s/(2+s)$でバウンドできることを示し、$m$は現在の処理データの数である。
  論文  参考訳（メタデータ） (2023-09-14T15:10:47Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。 本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
  論文  参考訳（メタデータ） (2020-11-10T11:36:30Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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