HyperAIHyperAI

Command Palette

Search for a command to run...

経験リスク最小化における確率凸最適化: O(1/n)O(1/n)O(1/n) および O(1/n2)O(1/n^2)O(1/n2) 型のリスク境界

Lijun Zhang; Tianbao Yang; Rong Jin

概要

監督学習の経験的リスク最小化(Empirical Risk Minimization: ERM)に関する理論は数多く存在しますが、関連する問題である確率凸最適化(Stochastic Convex Optimization: SCO)におけるERMの理論的理解は限られています。本研究では、SCOに対するERMの領域を強化し、滑らかさと強い凸性の条件を利用することでリスク境界を改善します。まず、ランダム関数が非負かつ凸で滑らかであり、期待値関数がリプシッツ連続である場合に、O~(d/n+F/n)\widetilde{O}(d/n + \sqrt{F_/n})O(d/n+F/n) のリスク境界を確立します。ここで、ddd は問題の次元数、nnn はサンプル数、F_ は最小リスクです。したがって、FF_*F が小さい場合、O~(d/n)\widetilde{O}(d/n)O(d/n) のリスク境界を得ることができます。これは監督学習におけるERMの O~(1/n)\widetilde{O}(1/n)O(1/n) 優れたレートに類似しています。次に、目的関数がさらに λ\lambdaλ-強凸である場合、O~(d/n+κF/n)\widetilde{O}(d/n + κF_/n)O(d/n+κF/n) のリスク境界を証明し、n=Ω~(κd)n = \widetilde{Ω}(κd)n=Ω(κd) のときにはこれを O(1/[λn2]+κF/n)O(1/[λn^2] + κF_/n)O(1/[λn2]+κF/n) に改善します。その結果、nnn が大きく FF_*F が小さい条件下で O(κ/n2)O(κ/n^2)O(κ/n2) のリスク境界を得ることができました。当該研究において知られている限りでは、これがERMの最初の O(1/n2)O(1/n^2)O(1/n2) 型のリスク境界となります。第三に、上記の結果は統一的な枠組みで確立されており、これによりランダム関数の凸性や期待値関数のリプシッツ連続性といったより弱い条件のもとでも新しいリスク境界を導出することが可能になります。最後に、監督学習において O(1/[λn2]+κF/n)O(1/[λn^2] + κF_*/n)O(1/[λn2]+κF/n) のリスク境界を達成するために必要な n=Ω~(κd)n = \widetilde{Ω}(κd)n=Ω(κd) の要件について述べます。この要件は次元数に依存しない Ω(κ2)Ω(κ^2)Ω(κ2) に置き換えることができます。


AIでAIを構築

アイデアからローンチまで — 無料のAIコーディング支援、すぐに使える環境、最高のGPU価格でAI開発を加速。

AI コーディング補助
すぐに使える GPU
最適な料金体系

HyperAI Newsletters

最新情報を購読する
北京時間 毎週月曜日の午前9時 に、その週の最新情報をメールでお届けします
メール配信サービスは MailChimp によって提供されています