Regularized bundle methods for convex and non-convex risks
Regularized bundle methods for convex and non-convex risks
复制标题
DOI：
10.5555/2503308.2503355
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
T. Do;T. Artières
中科院分区：
文献类型：
--
作者：
T. Do;T. Artières
机器学习通常被视为一个优化问题。理想情况下，人们期望凸目标函数依赖于有效的凸优化器，并具有良好的保证，例如没有局部最优值。然而，非凸性在实践中是非常常见的，它有时可能是不适当的，以任何代价寻找凸性。可替代地，可以决定不先验地将建模表达性限制到其学习可以通过凸优化来解决并且依赖于非凸优化算法的模型。这项工作的主要动机是为非凸优化提供有效的和可扩展的算法。我们专注于正则化无约束优化问题，其中涵盖了大量的现代机器学习问题，如逻辑回归，条件随机场，大边缘估计等，我们提出了一种新的算法，用于最小化正则化目标，能够处理凸和非凸，光滑和非光滑的风险。该算法是基于切割平面技术和开发的思想，在目标函数的正则化项。它可以被认为是凸正则化束方法的有限记忆扩展，用于处理凸和非凸风险。在风险是凸的情况下，证明了该算法收敛到一个平稳解，精度为e，收敛速度为O（1/λe），其中λ是目标函数的正则化参数，假设风险是Lipschitz经验风险.在风险不是凸的情况下，得到这样的证明是更困难的，需要更强和更有争议的假设。然而，我们提供了人工测试问题的实验结果，以及五个标准和困难的机器学习问题，这些问题被转换为凸和非凸优化问题，这些问题表明我们的算法在实践中与最先进的优化算法相比如何。
Machine learning is most often cast as an optimization problem. Ideally, one expects a convex objective function to rely on efficient convex optimizers with nice guarantees such as no local optima. Yet, non-convexity is very frequent in practice and it may sometimes be inappropriate to look for convexity at any price. Alternatively one can decide not to limit a priori the modeling expressivity to models whose learning may be solved by convex optimization and rely on non-convex optimization algorithms. The main motivation of this work is to provide efficient and scalable algorithms for non-convex optimization. We focus on regularized unconstrained optimization problems which cover a large number of modern machine learning problems such as logistic regression, conditional random fields, large margin estimation, etc. We propose a novel algorithm for minimizing a regularized objective that is able to handle convex and non-convex, smooth and non-smooth risks. The algorithm is based on the cutting plane technique and on the idea of exploiting the regularization term in the objective function. It may be thought as a limited memory extension of convex regularized bundle methods for dealing with convex and non convex risks. In case the risk is convex the algorithm is proved to converge to a stationary solution with accuracy e with a rate O(1/λe) where λ is the regularization parameter of the objective function under the assumption of a Lipschitz empirical risk. In case the risk is not convex getting such a proof is more difficult and requires a stronger and more disputable assumption. Yet we provide experimental results on artificial test problems, and on five standard and difficult machine learning problems that are cast as convex and non-convex optimization problems that show how our algorithm compares well in practice with state of the art optimization algorithms.