論文の概要: Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

• arxiv url: http://arxiv.org/abs/2406.05033v1
• Date: Fri, 7 Jun 2024 15:53:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-10 13:22:27.814841
• Title: Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes
• Title（参考訳）: 非分離データと大規模ステップサイズを用いたロジスティック回帰のグラディエントDescent
• Authors: Si Yi Meng, Antonio Orvieto, Daniel Yiming Cao, Christopher De Sa,
• Abstract要約: 我々は,大きく,一定のステップサイズを持つロジスティック回帰問題における降下ダイナミクスについて検討した。 局所収束は臨界ステップサイズより小さい全てのステップサイズに対して保証されるが、大域収束は保証されない。
• 参考スコア（独自算出の注目度）: 38.595892152591595
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size $2/\lambda$, where $\lambda$ is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than $1/\lambda$ suffices for global convergence. However, for all step sizes between $1/\lambda$ and the critical step size $2/\lambda$, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than $1/\lambda$. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.
• Abstract（参考訳）: 我々は,大きく,一定のステップサイズを持つロジスティック回帰問題における勾配降下(GD)ダイナミクスについて検討した。 線形分離可能なデータに対して、GDは最小化器に任意のステップサイズで収束することが知られている。 実際、この振舞いはずっと複雑で、周期二重分岐のシーケンスは、2/\lambda$という重要なステップサイズで始まります。 最小限のステップサイズを使用すると、ソリューションの近くで初期化されると収束が保証される。 一次元では、グローバル収束のために1/\lambda$suffices以下のステップサイズを示す。 しかし、1/\lambda$と2/\lambda$の間のすべてのステップサイズに対して、GDが安定したサイクルに収束するようにデータセットを構築することができる。 より高次元では、ステップサイズが1/\lambda$未満であっても、これは実際に可能だ。 以上の結果から, 局所収束は臨界ステップサイズよりも小さい全てのステップサイズに対して保証されるが, 大域収束は認められず, GD は初期化に応じてサイクルに収束する可能性が示唆された。

関連論文リスト

• Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency [47.8739414267201]
  線形分離可能なデータを用いたロジスティック回帰に一定の段差を持つ勾配降下(GD)を考える。 GD はこの初期振動位相を急速に終了し、$mathcalO(eta)$ steps となり、その後$tildemathcalO (1 / (eta t) )$ convergence rate が得られることを示す。 我々の結果は、予算が$T$ ステップであれば、GD は攻撃的なステップサイズで $tildemathcalO (1/T2)$ の加速損失を達成できることを示している。
  論文  参考訳（メタデータ） (2024-02-24T23:10:28Z)
• 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)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction [19.540926205375857]
  本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。 特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。 さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
  論文  参考訳（メタデータ） (2020-08-17T15:51:32Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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