提出最优鲁棒凸优化算法,无需强假设即可应对数据污染。
Optimal Rates for Robust Stochastic Convex Optimization
- 基于群体光滑性设计新算法,不依赖个体样本平滑性
- 在ε-污染模型下达到极小最大风险(对数因子内最优)
- 适用于未知协方差和非光滑损失,适合高维鲁棒学习
高维机器学习算法极易受少量结构化异常值影响,鲁棒优化至关重要。在ε-污染模型中,对手可替换最多ε比例的样本,当前关键难题是确定鲁棒随机凸优化(SCO)的最优率。本文提出新算法,在ε-污染模型下实现极小最大风险(对数因子内最优)。相比现有方法,本算法不仅更优,且无需要求个体样本函数的Lipschitz连续性和光滑性,仅需损失函数的群体光滑性。算法还可处理协方差未知情形,并通过卷积平滑推广至非光滑损失。我们进一步给出了鲁棒SCO的紧致信息论下界,证明了算法最优性。
原文摘要 · Abstract (English)
Machine learning algorithms in high-dimensional settings are highly susceptible to the influence of even a small fraction of structured outliers, making robust optimization techniques essential. In particular, within the $ε$-contamination model, where an adversary can inspect and replace up to an $ε$-fraction of the samples, a fundamental open problem is determining the optimal rates for robust stochastic convex optimization (SCO) under such contamination. We develop novel algorithms that achieve minimax-optimal excess risk (up to logarithmic factors) under the $ε$-contamination model. Our approach improves over existing algorithms, which are not only suboptimal but also require stringent assumptions, including Lipschitz continuity and smoothness of individual sample functions. By contrast, our optimal algorithms do not require these stringent assumptions, assuming only population-level smoothness of the loss. Moreover, our algorithms can be adapted to handle the case in which the covariance parameter is unknown, and can be extended to nonsmooth population risks via convolutional smoothing. We complement our algorithmic developments with a tight information-theoretic lower bound for robust SCO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。