Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
Dominik Csiba Peter Richtárik School of Mathematics, The University of Edinburgh, United Kingdom (e-mail: of Mathematics, The University of Edinburgh, United Kingdom (e-mail:
Abstract
In this work we develop a new algorithm for regularized empirical risk minimization. Our method extends recent techniques of Shalev-Shwartz [02/2015], which enable a dual-free analysis of SDCA, to arbitrary mini-batching schemes. Moreover, our method is able to better utilize the information in the data defining the ERM problem. For convex loss functions, our complexity results match those of QUARTZ, which is a primal-dual method also allowing for arbitrary mini-batching schemes. The advantage of a dual-free analysis comes from the fact that it guarantees convergence even for non-convex loss functions, as long as the average loss is convex. We illustrate through experiments the utility of being able to design arbitrary mini-batching schemes.
中文速览
经验风险最小化（ERM）是机器学习中训练模型的核心框架，但如何高效求解、尤其是在并行计算和非凸损失函数场景下仍有挑战。本文提出了一种新算法，将 Shalev-Shwartz 对 SDCA 的"无对偶"分析技术推广到任意小批量（mini-batch）采样方案，并通过更充分利用数据本身的结构信息获得更紧的收敛界。对于凸损失函数，该算法的收敛速率与目前唯一支持任意小批量方案的原始-对偶方法 QUARTZ 相当；更重要的是，无对偶分析使其在"平均损失为凸"这一较弱条件下也能保证收敛，从而将理论保障延伸至非凸损失函数场景。此外，论文还提出了"分块"（chunking）这一简单的负载均衡采样策略，通过预处理将计算量相近的样本归为一组分配给各处理器，实验表明这能有效减少并行计算中的等待时间，体现了灵活设计采样方案的实际价值。
原文 arXiv:1506.02227;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1506.02227v1