Command Palette

Search for a command to run...

5 个月前

经验风险最小化在随机凸优化中的应用: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

经验风险最小化在随机凸优化中的应用:$O(1/n)$ 和 $O(1/n^2)$ 风险界类型

摘要

尽管监督学习中存在大量关于经验风险最小化(ERM)的理论,但对于相关问题——随机凸优化(SCO)的经验风险最小化的当前理论理解仍然有限。在本研究中,我们通过利用平滑性和强凸性条件来改进风险界,从而加强了SCO领域内ERM的研究。首先,当随机函数是非负、凸且平滑时,且期望函数是Lipschitz连续的,我们建立了O~(d/n+F/n)\widetilde{O}(d/n + \sqrt{F_/n})O(d/n+F/n)的风险界,其中ddd是问题的维度,nnn是样本数量,F_是最小风险。因此,当F_较小时,我们得到一个O~(d/n)\widetilde{O}(d/n)O(d/n)的风险界,这类似于监督学习中ERM的O~(1/n)\widetilde{O}(1/n)O(1/n)乐观率。其次,如果目标函数也是λλλ-强凸的,则我们证明了一个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较大且F_较小的情况下,我们得到了一个O(κ/n2)O(κ/n^2)O(κ/n2)的风险界,据我们所知,这是首个关于ERM的O(1/n2)O(1/n^2)O(1/n2)类型的风险界。第三,我们强调上述结果是在统一框架下建立的,该框架允许我们在较弱条件下推导出新的风险界,例如不需要随机函数的凸性和期望函数的Lipschitz连续性。最后,我们展示了为了在监督学习中实现O(1/[λn2]+κF/n)O(1/[λn^2] + κF_*/n)O(1/[λn2]+κF/n)的风险界,对nnn的要求可以从Ω~(κd)\widetildeΩ(κd)Ω(κd)替换为Ω(κ2)Ω(κ^2)Ω(κ2),后者与维度无关。

基准测试

基准方法指标
image-classification-on-colored-mnist-withMLP-ERM
Accuracy : 17.10

用 AI 构建 AI

从想法到上线——通过免费 AI 协同编程、开箱即用的环境和市场最优价格的 GPU 加速您的 AI 开发

AI 协同编程
即用型 GPU
最优价格
立即开始

Hyper Newsletters

订阅我们的最新资讯
我们会在北京时间 每周一的上午九点 向您的邮箱投递本周内的最新更新
邮件发送服务由 MailChimp 提供