Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms
arXiv:1704.07987
Abstract
The -regularized models are widely used for sparse regression or classification tasks. In this paper, we propose the orthant-wise passive descent algorithm (OPDA) for optimizing -regularized models, as an improved substitute of proximal algorithms, which are the standard tools for optimizing the models nowadays. OPDA uses a stochastic variance-reduced gradient (SVRG) to initialize the descent direction, then apply a novel alignment operator to encourage each element keeping the same sign after one iteration of update, so the parameter remains in the same orthant as before. It also explicitly suppresses the magnitude of each element to impose sparsity. The quasi-Newton update can be utilized to incorporate curvature information and accelerate the speed. We prove a linear convergence rate for OPDA on general smooth and strongly-convex loss functions. By conducting experiments on -regularized logistic regression and convolutional neural networks, we show that OPDA outperforms state-of-the-art stochastic proximal algorithms, implying a wide range of applications in training sparse models.
arXiv commentAccepted to The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18). Feb 2018, New Orleans
References in corpus (10)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
- Stochastic Variance Reduction for Nonconvex Optimization
- RES: Regularized Stochastic BFGS Algorithm
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- Variance Reduction for Faster Non-Convex Optimization
- Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
- Action constrained quasi-Newton methods
- A Proximal Stochastic Quasi-Newton Algorithm