Optimization methods for regularized convex formulations in machine learning.

摘要

We develop efficient numerical optimization algorithms for regularized convex formulations that appear in a variety of areas such as machine learning, statistics, and signal processing. Their objective functions consist of a loss term and a regularization term, where the latter controls the complexity of prediction models or induces a certain structure to the solution encoding our prior knowledge. The formulations become difficult to solve when we consider a large amount of data, or when we employ nonsmooth functions in the objective.;We study algorithms in two different learning environments, online and batch learning. In online learning, we consider subgradient algorithms closely aligned to stochastic approximation. Each step of these algorithms requires low computation and thus appealing for large-scale applications, despite their slow asymptotic convergence. We study properties of a stochastic subgradient algorithm for regularized problems, revealing that the manifold embracing a solution can be identified in finite iterations with high probability. This allows us developing a new algorithmic strategy that switches to another type of optimization on the near-optimal manifold. We also present a sub-gradient algorithm customized for the nonlinear support vector machines (SVMs), where kernels are approximated with low-dimensional surrogate mappings.;On the other hand, in batch learning, we typically have full access to the objective. For moderate-sized learning tasks, batch approaches often find solutions much faster than online counterparts. In this setting we discuss algorithms based on decomposition and cutting-plane techniques, exploiting the structure of SVMs for efficiency.