論文の概要: Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers

• arxiv url: http://arxiv.org/abs/2209.08951v1
• Date: Mon, 19 Sep 2022 12:11:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-20 16:32:09.924577
• Title: Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers
• Title（参考訳）: 局所化 $\varepsilon$-Covers による確率勾配Descent の一般化境界
• Authors: Sejun Park, Umut \c{S}im\c{s}ekli, Murat A. Erdogdu
• Abstract要約: 本稿では,SGDの軌道に局在する新しい被覆手法を提案する。 このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。 これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
• 参考スコア（独自算出の注目度）: 16.618918548497223
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific complexity measured by the covering number, which can have dimension-independent cardinality in contrast to standard uniform covering arguments that result in exponential dimension dependency. Based on this localized construction, we show that if the objective function is a finite perturbation of a piecewise strongly convex and smooth function with $P$ pieces, i.e. non-convex and non-smooth in general, the generalization error can be upper bounded by $O(\sqrt{(\log n\log(nP))/n})$, where $n$ is the number of data samples. In particular, this rate is independent of dimension and does not require early stopping and decaying step size. Finally, we employ these results in various contexts and derive generalization bounds for multi-index linear models, multi-class support vector machines, and $K$-means clustering for both hard and soft label setups, improving the known state-of-the-art rates.
• Abstract（参考訳）: 本稿では,sgdの軌跡を局所化する新しい被覆手法を提案する。 このローカライゼーションは、指数的次元依存性をもたらす標準的な一様被覆議論とは対照的に、被覆数によって測定されるアルゴリズム固有の複雑性をもたらす。 この局所的な構成に基づき、目的関数が片方向の強い凸と滑らかな関数の有限摂動で$P$ピース、すなわち一般には非凸と非滑らかな関数である場合、一般化誤差は$O(\sqrt{(\log n\log(nP))/n})$で上界し、$n$はデータサンプルの数である。 特に、この速度は次元とは独立であり、早期に停止および崩壊するステップサイズを必要としない。 最後に、これらの結果を様々な文脈で利用し、マルチインデックス線形モデル、マルチクラスサポートベクターマシン、およびハードとソフトのラベル設定のための$K$-meansクラスタリングの一般化バウンダリを導出し、既知の最先端化率を改善した。

関連論文リスト

• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• 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)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap [24.073221004661427]
  部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。 広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
  論文  参考訳（メタデータ） (2022-05-26T17:47:35Z)
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent [69.47594803719333]
  幾何学的中央値 (textGm) は、未破損データのロバストな推定を達成するための統計学における古典的な方法である。 本稿では,テキストscGmを一度に選択した座標ブロックにのみ適用することにより,スムーズな非テキスト問題に対して0.5の分解点を保持することができることを示す。
  論文  参考訳（メタデータ） (2021-06-16T15:55:50Z)
• 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)
• Multiscale regression on unknown manifolds [13.752772802705978]
  マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。 本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。 私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
  論文  参考訳（メタデータ） (2021-01-13T15:14:31Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。 特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2020-06-15T08:25:50Z)

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

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