Command Palette
Search for a command to run...
経験リスク最小化における確率凸最適化: O(1/n) および O(1/n2) 型のリスク境界
経験リスク最小化における確率凸最適化: O(1/n) および 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) のリスク境界を確立します。ここで、d は問題の次元数、n はサンプル数、F_ は最小リスクです。したがって、F∗ が小さい場合、O(d/n) のリスク境界を得ることができます。これは監督学習におけるERMの O(1/n) 優れたレートに類似しています。次に、目的関数がさらに λ-強凸である場合、O(d/n+κF/n) のリスク境界を証明し、n=Ω(κd) のときにはこれを O(1/[λn2]+κF/n) に改善します。その結果、n が大きく F∗ が小さい条件下で O(κ/n2) のリスク境界を得ることができました。当該研究において知られている限りでは、これがERMの最初の O(1/n2) 型のリスク境界となります。第三に、上記の結果は統一的な枠組みで確立されており、これによりランダム関数の凸性や期待値関数のリプシッツ連続性といったより弱い条件のもとでも新しいリスク境界を導出することが可能になります。最後に、監督学習において O(1/[λn2]+κF∗/n) のリスク境界を達成するために必要な n=Ω(κd) の要件について述べます。この要件は次元数に依存しない Ω(κ2) に置き換えることができます。