論文の概要: Generalization Error of First-Order Methods for Statistical Learning
with Generic Oracles
- arxiv url: http://arxiv.org/abs/2307.04679v2
- Date: Tue, 11 Jul 2023 10:12:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-12 17:42:43.368039
- Title: Generalization Error of First-Order Methods for Statistical Learning
with Generic Oracles
- Title(参考訳): 一般オラクルを用いた統計的学習のための一階法一般化誤差
- Authors: Kevin Scaman, Mathieu Even and Laurent Massouli\'e
- Abstract要約: 統計的学習のための一階最適化アルゴリズムの一般化誤差の解析のためのフレームワークを提供する。
標準的な教師付き学習では、バッチサイズの増加とウォームスタートによるミニバッチ勾配降下が、乗算係数に最適な一般化誤差に達することが示されている。
- 参考スコア(独自算出の注目度): 15.710088225806299
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we provide a novel framework for the analysis of
generalization error of first-order optimization algorithms for statistical
learning when the gradient can only be accessed through partial observations
given by an oracle. Our analysis relies on the regularity of the gradient
w.r.t. the data samples, and allows to derive near matching upper and lower
bounds for the generalization error of multiple learning problems, including
supervised learning, transfer learning, robust learning, distributed learning
and communication efficient learning using gradient quantization. These results
hold for smooth and strongly-convex optimization problems, as well as smooth
non-convex optimization problems verifying a Polyak-Lojasiewicz assumption. In
particular, our upper and lower bounds depend on a novel quantity that extends
the notion of conditional standard deviation, and is a measure of the extent to
which the gradient can be approximated by having access to the oracle. As a
consequence, our analysis provides a precise meaning to the intuition that
optimization of the statistical learning objective is as hard as the estimation
of its gradient. Finally, we show that, in the case of standard supervised
learning, mini-batch gradient descent with increasing batch sizes and a warm
start can reach a generalization error that is optimal up to a multiplicative
factor, thus motivating the use of this optimization scheme in practical
applications.
- Abstract(参考訳): 本稿では,oracle が与える部分的観測によってのみグラデーションにアクセス可能な場合,統計学習のための一階最適化アルゴリズムの一般化誤差解析のための新しい枠組みを提案する。
本分析は,データサンプルの勾配 w.r.t. の正則性に依存し,教師付き学習,転送学習,ロバスト学習,分散学習,勾配量子化を用いたコミュニケーション効率の良い学習など,複数の学習問題の一般化誤差の上限付近を導出する。
これらの結果は、滑らかで強凸な最適化問題と、Polyak-Lojasiewicz仮定を検証する滑らかな非凸最適化問題に成り立つ。
特に、我々の上界と下界は条件付き標準偏差の概念を拡張する新しい量に依存しており、オラクルへのアクセスによって勾配が近似できる範囲の尺度である。
その結果,統計的学習目標の最適化は,その勾配の推定と同等に難しいという直観への正確な意味が得られた。
最後に、標準的な教師付き学習の場合、バッチサイズの増加とウォームスタートを伴うミニバッチ勾配勾配は、乗算係数に最適化された一般化誤差に到達し、この最適化手法を実用的な応用に活用する動機となることを示す。
関連論文リスト
- Scalable Bayesian Meta-Learning through Generalized Implicit Gradients [64.21628447579772]
Inlicit Bayesian Meta-learning (iBaML) 法は、学習可能な事前のスコープを広げるだけでなく、関連する不確実性も定量化する。
解析誤差境界は、明示的よりも一般化された暗黙的勾配の精度と効率を示すために確立される。
論文 参考訳(メタデータ) (2023-03-31T02:10:30Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。
既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
論文 参考訳(メタデータ) (2022-09-01T11:05:26Z) - Stability vs Implicit Bias of Gradient Methods on Separable Data and
Beyond [33.593203156666746]
分離線形分類に適用された非正規化勾配に基づく学習手順の一般化特性に着目する。
この一般化についてさらに統一的な説明をし、実現可能性と自己有界性(self-boundedness)と呼ぶ。
これらのケースのいくつかでは、文献における既存の一般化誤差境界に対して、我々の境界は著しく改善される。
論文 参考訳(メタデータ) (2022-02-27T19:56:36Z) - From inexact optimization to learning via gradient concentration [22.152317081922437]
本稿では,滑らかな損失関数を持つ線形モデルの文脈における現象について検討する。
本稿では、不正確な最適化と確率論、特に勾配集中のアイデアを組み合わせた証明手法を提案する。
論文 参考訳(メタデータ) (2021-06-09T21:23:29Z) - Deep learning: a statistical viewpoint [120.94133818355645]
ディープラーニングは、理論的観点からいくつかの大きな驚きを明らかにしました。
特に、簡単な勾配法は、最適でないトレーニング問題に対するほぼ完全な解決策を簡単に見つけます。
我々はこれらの現象を具体的原理で補うと推測する。
論文 参考訳(メタデータ) (2021-03-16T16:26:36Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Towards Optimal Problem Dependent Generalization Error Bounds in
Statistical Learning Theory [11.840747467007963]
我々は,「ベスト勾配仮説」で評価された分散,有効損失誤差,ノルムとほぼ最適にスケールする問題依存率について検討する。
一様局所収束(uniform localized convergence)と呼ばれる原理的枠組みを導入する。
我々は,既存の一様収束と局所化解析のアプローチの基本的制約を,我々のフレームワークが解決していることを示す。
論文 参考訳(メタデータ) (2020-11-12T04:07:29Z) - Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
半教師付き学習における簡単なメタ学習アルゴリズムを提案する。
その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
論文 参考訳(メタデータ) (2020-07-08T08:48:56Z) - On the Convergence Rate of Projected Gradient Descent for a
Back-Projection based Objective [58.33065918353532]
我々は、最小二乗(LS)の代替として、バックプロジェクションに基づく忠実度項を考える。
LS項ではなくBP項を用いることで最適化アルゴリズムの繰り返しを少なくすることを示す。
論文 参考訳(メタデータ) (2020-05-03T00:58:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。