論文の概要: The Sample Complexity Of ERMs In Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2311.05398v1
- Date: Thu, 9 Nov 2023 14:29:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-10 15:04:07.079613
- Title: The Sample Complexity Of ERMs In Stochastic Convex Optimization
- Title(参考訳): 確率凸最適化におけるermのサンプル複雑性
- Authors: Daniel Carmon, Roi Livni, Amir Yehudayoff
- Abstract要約: 実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
- 参考スコア(独自算出の注目度): 13.896417716930687
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic convex optimization is one of the most well-studied models for
learning in modern machine learning. Nevertheless, a central fundamental
question in this setup remained unresolved: "How many data points must be
observed so that any empirical risk minimizer (ERM) shows good performance on
the true population?" This question was proposed by Feldman (2016), who proved
that $\Omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ data points are
necessary (where $d$ is the dimension and $\epsilon>0$ is the accuracy
parameter). Proving an $\omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ lower
bound was left as an open problem. In this work we show that in fact
$\tilde{O}(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$ data points are also
sufficient. This settles the question and yields a new separation between ERMs
and uniform convergence. This sample complexity holds for the classical setup
of learning bounded convex Lipschitz functions over the Euclidean unit ball. We
further generalize the result and show that a similar upper bound holds for all
symmetric convex bodies. The general bound is composed of two terms: (i) a term
of the form $\tilde{O}(\frac{d}{\epsilon})$ with an inverse-linear dependence
on the accuracy parameter, and (ii) a term that depends on the statistical
complexity of the class of $\textit{linear}$ functions (captured by the
Rademacher complexity). The proof builds a mechanism for controlling the
behavior of stochastic convex optimization problems.
- Abstract(参考訳): 確率凸最適化は、現代の機械学習における学習のための最もよく研究されたモデルの1つである。
それでも、この設定における根本的な問題は未解決のままであり、「実験的リスク最小化器(ERM)が真の人口に良いパフォーマンスを示すように、何つのデータポイントが観測されなければならないか?
この問題はfeldman (2016) によって提案され、$\omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$データポイントが必要であることを証明した(ここでは$d$は次元であり$\epsilon>0$は精度パラメータである)。
開問題として$\omega(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$下界を証明した。
この研究で、実際に$\tilde{O}(\frac{d}{\epsilon}+\frac{1}{\epsilon^2})$データポイントも十分であることを示す。
この問題は解決し、ERMと一様収束の間に新たな分離をもたらす。
このサンプル複雑性は、ユークリッド単位球上の有界凸リプシッツ函数を学習する古典的なセットアップに当てはまる。
さらにこの結果を一般化し、すべての対称凸体に対して同様の上界が成り立つことを示す。
一般境界は2つの項からなる。
i) 精度パラメータに逆線形依存を持つ$\tilde{O}(\frac{d}{\epsilon})$という形の用語
(ii)$\textit{linear}$関数のクラスの統計的複雑性に依存する用語(ラデマッハ複雑性によって獲得される)。
この証明は確率凸最適化問題の挙動を制御するメカニズムを構築する。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳(メタデータ) (2024-05-10T09:58:47Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳(メタデータ) (2022-10-25T11:37:11Z) - Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization [37.177329562964765]
我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。
この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。
しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
論文 参考訳(メタデータ) (2022-02-27T09:41:43Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳(メタデータ) (2022-02-23T16:10:23Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳(メタデータ) (2022-02-08T12:58:14Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳(メタデータ) (2020-09-18T02:18:44Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。