論文の概要: Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes

• arxiv url: http://arxiv.org/abs/2504.04105v1
• Date: Sat, 05 Apr 2025 08:34:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:14:52.204448
• Title: Minimax Optimal Convergence of Gradient Descent in Logistic Regression via Large and Adaptive Stepsizes
• Title（参考訳）: 大規模・適応的なステップサイズによるロジスティック回帰におけるグラディエントDescentの最小収束
• Authors: Ruiqi Zhang, Jingfeng Wu, Licong Lin, Peter L. Bartlett,
• Abstract要約: 線形分離可能なデータに対して、現在のリスクに適応する段差を持つロジスティック回帰のための$textitgradient descent$(GD)について検討する。 我々は、少なくとも1/gamma2$のバーンインステップの後、$exp(-Theta(eta))$で上限付けられたリスクをGDが達成し、$gamma$がデータセットのマージンであることを示している。
• 参考スコア（独自算出の注目度）: 32.64968378005787
• License:
• Abstract: We study $\textit{gradient descent}$ (GD) for logistic regression on linearly separable data with stepsizes that adapt to the current risk, scaled by a constant hyperparameter $\eta$. We show that after at most $1/\gamma^2$ burn-in steps, GD achieves a risk upper bounded by $\exp(-\Theta(\eta))$, where $\gamma$ is the margin of the dataset. As $\eta$ can be arbitrarily large, GD attains an arbitrarily small risk $\textit{immediately after the burn-in steps}$, though the risk evolution may be $\textit{non-monotonic}$. We further construct hard datasets with margin $\gamma$, where any batch or online first-order method requires $\Omega(1/\gamma^2)$ steps to find a linear separator. Thus, GD with large, adaptive stepsizes is $\textit{minimax optimal}$ among first-order batch methods. Notably, the classical $\textit{Perceptron}$ (Novikoff, 1962), a first-order online method, also achieves a step complexity of $1/\gamma^2$, matching GD even in constants. Finally, our GD analysis extends to a broad class of loss functions and certain two-layer networks.
• Abstract（参考訳）: 我々は、線形分離可能なデータに対するロジスティック回帰を現在のリスクに適応するステップサイズで$\textit{gradient descent}$ (GD) で検討し、定数のハイパーパラメータ$\eta$でスケールする。 我々は、少なくとも1/\gamma^2$のバーンインステップの後、GDは$\exp(-\Theta(\eta))$で上限付けられたリスクを達成し、$\gamma$はデータセットのマージンであることを示した。 $\eta$ は任意に大きいので、GD は任意の小さなリスク $\textit{immediately after the burn-in steps}$ を達成するが、リスクの進化は $\textit{non-monotonic}$ となる。 さらに、マージン$\gamma$でハードデータセットを構築し、任意のバッチまたはオンライン一階法は、線形セパレータを見つけるために$\Omega(1/\gamma^2)$ステップを必要とする。 したがって、大規模で適応的なステップサイズを持つGDは、一階バッチメソッドの中で$\textit{minimax optimal}$である。 特に、古典的な$\textit{Perceptron}$ (Novikoff, 1962)は、1/\gamma^2$のステップ複雑性も達成し、定数でもGDと一致する。 最後に、GD解析は、幅広い損失関数と特定の2層ネットワークにまで拡張する。

関連論文リスト

• 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)
• Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations [51.14495595270775]
  我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。 この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
  論文  参考訳（メタデータ） (2023-10-30T19:52:43Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。 我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
  論文  参考訳（メタデータ） (2022-05-03T12:09:59Z)
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
  このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。 高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。 提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
  論文  参考訳（メタデータ） (2022-02-19T22:12:30Z)
• Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
  本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。 係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。 オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
  論文  参考訳（メタデータ） (2022-01-03T15:10:17Z)
• 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)
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data [8.55881355051688]
  本研究では,高次元空間における重み付きデータを用いたDP-SCOの問題に関する最初の研究を行う。 損失関数が滑らかで、その勾配が第二次モーメントに有界ならば、$epsilon$-DPモデルで$tildeO(fraclog d(nepsilon)frac13)$の(高い確率)誤差境界(過剰な集団リスク)を得ることが可能である。 論文の第2部では,重み付きデータを用いたスパース学習について検討した。
  論文  参考訳（メタデータ） (2021-07-23T11:03:21Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Gradient-Based Empirical Risk Minimization using Local Polynomial Regression [39.29885444997579]
  この論文の主な目標は、勾配降下(GD)や勾配降下(SGD)といった異なるアルゴリズムを比較することである。 損失関数がデータのスムーズな場合、各反復でオラクルを学習し、GDとSGDの両方のオラクル複雑度に打ち勝つことができることを示す。
  論文  参考訳（メタデータ） (2020-11-04T20:10:31Z)

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

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