Command Palette
Search for a command to run...
Lijun Zhang; Tianbao Yang; Rong Jin

摘要
尽管监督学习中存在大量关于经验风险最小化(ERM)的理论,但对于相关问题——随机凸优化(SCO)的经验风险最小化的当前理论理解仍然有限。在本研究中,我们通过利用平滑性和强凸性条件来改进风险界,从而加强了SCO领域内ERM的研究。首先,当随机函数是非负、凸且平滑时,且期望函数是Lipschitz连续的,我们建立了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)类型的风险界。第三,我们强调上述结果是在统一框架下建立的,该框架允许我们在较弱条件下推导出新的风险界,例如不需要随机函数的凸性和期望函数的Lipschitz连续性。最后,我们展示了为了在监督学习中实现O(1/[λn2]+κF∗/n)的风险界,对n的要求可以从Ω(κd)替换为Ω(κ2),后者与维度无关。
基准测试
| 基准 | 方法 | 指标 |
|---|---|---|
| image-classification-on-colored-mnist-with | MLP-ERM | Accuracy : 17.10 |