論文の概要: Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification

• arxiv url: http://arxiv.org/abs/2608.06250v1
• Date: Thu, 06 Aug 2026 16:41:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-07 17:43:06.806842
• Title: Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification
• Title（参考訳）: ガウス混合分類のための極小最適早期停止勾配
• Abstract要約: トレーニングデータは、基礎となる分布がそうでない場合でも線形分離可能である。 早期停止はこの亜最適性を克服できることを示す。 新しい校正結果は、過剰なロジスティックリスクを過剰なゼロワンリスクに変換する。
• 参考スコア（独自算出の注目度）: 8.717253904965371
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In overparameterised classification, training data can be linearly separable even when the underlying distribution is not. In this setting, gradient descent (GD) on the logistic loss diverges in norm while converging in direction to a max-margin interpolating classifier, whose implicit bias can be statistically suboptimal. In this work, we show that early stopping can overcome this suboptimality: in a Gaussian mixture model with label-flipping noise, GD stopped at an appropriate oracle time achieves minimax-optimal excess zero-one risk for covariance spectra with fast and continuous decay, including polynomial and exponential spectral decays. Our analysis combines a sharp upper bound for the early-stopped iterate with a matching statistical lower bound over arbitrary classifiers, yielding optimal rates that are validated by experiments. A central technical contribution is a new calibration result that converts excess logistic risk into excess zero-one risk; it handles the model misspecification induced by the label-flipping noise, and removes the square-root rate in standard bounds. We also establish a lower bound for linear interpolators, showing that interpolation can require exponentially more samples than early stopping to achieve the same excess risk.
• Abstract（参考訳）: 過度にパラメータ化された分類では、基礎となる分布がそうでない場合でも、トレーニングデータを線形に分離することができる。 この設定では、ロジスティック損失の勾配降下(GD)は、統計的に準最適である最大母数補間分類器に方向収束しながらノルムで分岐する。 ガウス混合モデルにおいて、GDは適切なオラクル時間で停止し、多項式および指数スペクトル崩壊を含む高速かつ連続的な減衰を伴う共分散スペクトルに対する極小極小最適ゼロワンリスクを達成する。 本分析では, 任意の分類器上の統計的下限に一致し, 実験により検証可能な最適値が得られる。 中心となる技術的貢献は、余剰なロジスティックリスクを過剰なゼロワンリスクに変換する新たなキャリブレーション結果であり、ラベルフリップノイズによって引き起こされるモデルの不特定を処理し、標準境界における平方根率を除去する。 また、線形補間器の低境界を確立し、同じ過大なリスクを達成するためには、早期停止よりも指数関数的に多くのサンプルを必要とすることを示す。

関連論文リスト

• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max最適化は、現代の機械学習に応用されているため、注目を集めている。 我々は、勾配降下(SGDA)の包括的理論を提供する。 我々は,Stoc-GDAMとStoc-TRmaxという新たなクリッピングフリーアルゴリズムを開発し,グラディエントクリッピングを使わずに,目標精度への最適依存を実現する。
  論文  参考訳（メタデータ） (2026-09-05T12:49:28Z)
• Connecting Score Matching, Maximum Likelihood, and Expectation-Maximization in Mixed Linear Regression [11.223656960922478]
  混合線形回帰(MLR)における応答の分散保存拡散と未知の混合重みについて検討した。 本分析では,不規則な拡散雑音レベルにおける損失幾何と最適化信号から,スコアマッチングの統計的保証を分離する。
  論文  参考訳（メタデータ） (2026-09-04T19:52:26Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Gradient Normalization Provably Benefits Nonconvex SGD under Heavy-Tailed Noise [60.92029979853314]
  重み付き雑音下でのグラディエントDescence(SGD)の収束を確実にする上での勾配正規化とクリッピングの役割について検討する。 我々の研究は、重尾雑音下でのSGDの勾配正規化の利点を示す最初の理論的証拠を提供する。 我々は、勾配正規化とクリッピングを取り入れた加速SGD変種を導入し、さらに重み付き雑音下での収束率を高めた。
  論文  参考訳（メタデータ） (2024-10-21T22:40:42Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Max-affine regression via first-order methods [7.12511675782289]
  最大アフィンモデルは信号処理と統計学の応用においてユビキタスに現れる。 最大アフィン回帰に対する勾配降下(GD)とミニバッチ勾配降下(SGD)の非漸近収束解析を行った。
  論文  参考訳（メタデータ） (2023-08-15T23:46:44Z)
• Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regression [12.443289202402761]
  最小ノルム過パラメータ線形回帰モデルのレンズによるバッチ分割の利点を示す。 最適なバッチサイズを特徴付け、ノイズレベルに逆比例することを示す。 また,Weiner係数と同等の係数によるバッチ最小ノルム推定器の縮小がさらに安定化し,全ての設定において2次リスクを低くすることを示した。
  論文  参考訳（メタデータ） (2023-06-14T11:02:08Z)
• Compound Batch Normalization for Long-tailed Image Classification [77.42829178064807]
  本稿では,ガウス混合に基づく複合バッチ正規化法を提案する。 機能空間をより包括的にモデル化し、ヘッドクラスの優位性を減らすことができる。 提案手法は,画像分類における既存の手法よりも優れている。
  論文  参考訳（メタデータ） (2022-12-02T07:31:39Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Minimax Supervised Clustering in the Anisotropic Gaussian Mixture Model: A new take on Robust Interpolation [5.98367009147573]
  2成分異方性ガウス混合モデルに基づくクラスタリング問題について検討する。 その結果, 線形判別分析(LDA)分類器は, ミニマックス感において準最適であることが判明した。
  論文  参考訳（メタデータ） (2021-11-13T05:19:37Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime [16.1176305285103]
  2クラス線形分類における最大マージンアルゴリズムの集団リスクに関するバウンダリを証明した。 誤分類ノイズを含むランダムデータに適用したこのアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2020-04-25T00:06:18Z)

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

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