論文の概要: $k$-SVD with Gradient Descent

• arxiv url: http://arxiv.org/abs/2502.00320v1
• Date: Sat, 01 Feb 2025 05:00:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:21:53.645341
• Title: $k$-SVD with Gradient Descent
• Title（参考訳）: $k$-SVD with Gradient Descent
• Authors: Emily Gan, Yassir Jedra, Devavrat Shah,
• Abstract要約: ステップサイズ選択のための単純で普遍的な規則を持つ勾配発振器は、即興で$k$-SVD を求める。
• 参考スコア（独自算出の注目度）: 16.57405742112833
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that a gradient-descent with a simple, universal rule for step-size selection provably finds $k$-SVD, i.e., the $k\geq 1$ largest singular values and corresponding vectors, of any matrix, despite nonconvexity. There has been substantial progress towards this in the past few years where existing results are able to establish such guarantees for the \emph{exact-parameterized} and \emph{over-parameterized} settings, with choice of oracle-provided step size. But guarantees for generic setting with a step size selection that does not require oracle-provided information has remained a challenge. We overcome this challenge and establish that gradient descent with an appealingly simple adaptive step size (akin to preconditioning) and random initialization enjoys global linear convergence for generic setting. Our convergence analysis reveals that the gradient method has an attracting region, and within this attracting region, the method behaves like Heron's method (a.k.a. the Babylonian method). Empirically, we validate the theoretical results. The emergence of modern compute infrastructure for iterative optimization coupled with this work is likely to provide means to solve $k$-SVD for very large matrices.
• Abstract（参考訳）: ステップサイズ選択のための単純で普遍的な規則を持つ勾配線は、非凸性にもかかわらず、任意の行列の$k$-SVD、すなわち、$k\geq 1$最大の特異値と対応するベクトルを証明できることを示す。 過去数年間で、既存の結果が、オラクルが提供するステップサイズを選択することで、 \emph{exact-parameterized} と \emph{over-parameterized} の設定に対してそのような保証を確立することができるという大きな進歩があった。 しかし、オラクルが提供する情報を必要としないステップサイズの選択によるジェネリックセッティングの保証は、依然として課題である。 この課題を克服し、非常に単純な適応的なステップサイズ(プレコンディショニングと同様)とランダムな初期化による勾配降下が、ジェネリックセッティングに対する大域的線形収束を享受できることを確立する。 収束解析により、勾配法は誘引領域を持ち、この誘引領域内では、ヘロン法(バビロニア法)のように振る舞うことが分かる。 理論的結果の実証実験を行った。 反復最適化のための現代的な計算インフラの出現は、非常に大きな行列に対して$k$-SVDを解く手段を提供する可能性が高い。

関連論文リスト

• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
  本研究は、急勾配と条件勾配のアプローチを組み合わせることでノルムクリッピングを一般化するハイブリッド非ユークリッド最適化手法を提案する。 本稿では、ディープラーニングのためのアルゴリズムのインスタンス化について論じ、画像分類と言語モデリングにおけるそれらの特性を実証する。
  論文  参考訳（メタデータ） (2025-06-02T17:34:29Z)
• Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function [14.986031916712108]
  勾配追跡手法の一点推定に基づくゼロ階分散最適化手法を提案する。 我々は,この手法が雑音条件下で数値関数と収束することを証明した。
  論文  参考訳（メタデータ） (2024-10-08T11:45:45Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
  重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。 その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
  論文  参考訳（メタデータ） (2024-08-19T11:07:05Z)
• Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization [48.84672493756553]
  我々は,1ステップあたり$Obig(slogfrac dsbig)$クエリのみを使用する勾配のクエリ効率と精度の高い推定器を提案する。 Indyk-Price-Woodruff (IPW) アルゴリズムを線形測定から非線形関数への圧縮センシングにおいて一般化した。
  論文  参考訳（メタデータ） (2024-05-27T03:52:53Z)
• Implicit Bias and Fast Convergence Rates for Self-attention [26.766649949420746]
  本稿では,変圧器の定義機構である自己注意の基本的な最適化原理について考察する。 線形分類におけるデコーダを用いた自己アテンション層における勾配ベースの暗黙バイアスを解析する。
  論文  参考訳（メタデータ） (2024-02-08T15:15:09Z)
• Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence and Experiments [0.0]
  本稿では,$frac1sqrtttをベースとした変形ステップサイズを改良することにより,勾配降下法(SGD)アルゴリズムの性能向上に新たなアプローチを提案する。 提案されたステップサイズは対数的なステップ項を統合し、最終イテレーションでより小さな値を選択する。 提案手法の有効性について,FashionMNISTとARARを用いて画像分類タスクの数値実験を行った。
  論文  参考訳（メタデータ） (2023-09-03T19:21:59Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization [26.328847475942894]
  我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。 我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
  論文  参考訳（メタデータ） (2023-06-03T23:31:27Z)
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold [16.099883128428054]
  直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。 ODCGMはベクトル空間へのプロジェクションのみを必要とする。 以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
  論文  参考訳（メタデータ） (2023-03-16T12:25:53Z)
• 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)
• Perseus: A Simple and Optimal High-Order Method for Variational Inequalities [81.32967242727152]
  VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。 そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
  論文  参考訳（メタデータ） (2022-05-06T13:29:14Z)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  この楽観的な手法は凸凹点問題の解法として人気が高まっている。 我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
  論文  参考訳（メタデータ） (2022-02-19T20:31:05Z)
• 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)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。 この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。 滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
  論文  参考訳（メタデータ） (2020-10-22T22:54:54Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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