論文の概要: Early-Stopped Mirror Descent for Linear Regression over Convex Bodies

• arxiv url: http://arxiv.org/abs/2503.03426v1
• Date: Wed, 05 Mar 2025 11:59:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-06 15:53:08.051040
• Title: Early-Stopped Mirror Descent for Linear Regression over Convex Bodies
• Title（参考訳）: 凸体上の線形回帰に対する早期停止ミラーダイス
• Authors: Tobias Wegel, Gil Kur, Patrick Rebeschini,
• Abstract要約: 加法的ガウス雑音下での高次元線形回帰の設定について検討する。 その結果,未拘束の早期停止ミラー降下の最悪のリスクは,少なくとも凸体に拘束される最小2乗推定器のリスクであることがわかった。
• 参考スコア（独自算出の注目度）: 14.30754799752932
• License:
• Abstract: Early-stopped iterative optimization methods are widely used as alternatives to explicit regularization, and direct comparisons between early-stopping and explicit regularization have been established for many optimization geometries. However, most analyses depend heavily on the specific properties of the optimization geometry or strong convexity of the empirical objective, and it remains unclear whether early-stopping could ever be less statistically efficient than explicit regularization for some particular shape constraint, especially in the overparameterized regime. To address this question, we study the setting of high-dimensional linear regression under additive Gaussian noise when the ground truth is assumed to lie in a known convex body and the task is to minimize the in-sample mean squared error. Our main result shows that for any convex body and any design matrix, up to an absolute constant factor, the worst-case risk of unconstrained early-stopped mirror descent with an appropriate potential is at most that of the least squares estimator constrained to the convex body. We achieve this by constructing algorithmic regularizers based on the Minkowski functional of the convex body.
• Abstract（参考訳）: 初期停止反復最適化法は明示的正則化の代替として広く用いられ、多くの最適化測地に対して早期停止と明示的正則化の直接比較が確立されている。 しかし、ほとんどの分析は最適化幾何学の特定の性質や経験的目的の強い凸性に大きく依存しており、特に過パラメータ化状態において、初期ストッピングが特定の形状制約に対する明示的な正規化よりも統計的に効率的でないかどうかは不明である。 この問題に対処するために, 既知凸体に基底真理が存在すると仮定した時, 加法ガウス雑音下での高次元線形回帰の設定について検討し, その課題は, サンプル内平均二乗誤差を最小化することである。 本研究の主目的は, 凸体および任意の設計行列において, 絶対定数因子まで, 未拘束の早期停止ミラー降下の最悪のリスクは, 凸体に制約された最小2乗推定器の最大値であることを示す。 我々は、凸体のミンコフスキー関数に基づいてアルゴリズム正規化器を構築することでこれを実現できる。

関連論文リスト

• Mirror Descent Under Generalized Smoothness [23.5387392871236]
  一般ノルムと双対のヘッセン項のノルムを測定する新しい$ell*$-smoothnessの概念を導入する。 我々は、古典的な滑らかさの下でのレートに一致するミラー・ディフレッシュ型アルゴリズムの収束性を確立する。
  論文  参考訳（メタデータ） (2025-02-02T11:23:10Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
  この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。 これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
  論文  参考訳（メタデータ） (2024-02-14T10:48:00Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  この研究は、ディープ線形ネットワークにおけるヘッセン解の最小トレースの帰納バイアスを理解するための第一歩となる。 測定値の標準等尺性(RIP)が1より大きいすべての深さについて、ヘッセンのトレースを最小化することは、対応する終端行列パラメータのシャッテン 1-ノルムを最小化するのとほぼ同値であることを示す。
  論文  参考訳（メタデータ） (2023-06-22T23:14:57Z)
• Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization [16.325663190517773]
  我々は、任意の過パラメータ化を持つ自然な非定式化の下で、非対称な分解問題を考察する。 観測された行列に対して最高の低ランク近似を生成する。
  論文  参考訳（メタデータ） (2022-03-06T00:07:53Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。 2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:48:46Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)
• Iterative regularization for convex regularizers [18.87017835436693]
  線形モデルに対する反復正則化は、バイアスが凸であるが必ずしも凸であるとは限らないときに研究する。 最短ケース決定性雑音の存在下での収束を解析し, 2次元勾配に基づく手法の安定性特性を特徴付ける。
  論文  参考訳（メタデータ） (2020-06-17T13:39:29Z)
• The Statistical Complexity of Early-Stopped Mirror Descent [27.393821783237186]
  早期停止ミラー降下アルゴリズムにより達成される過剰リスクの統計的保証について検討する。 正方形損失の凸性を特徴づける不等式を完遂することにより、オフセットラデマッハ複素数とミラー降下法のポテンシャルベース収束解析との内在的リンクを同定する。
  論文  参考訳（メタデータ） (2020-02-01T11:05:08Z)

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

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