Sparsity-inducing regularization problems are ubiquitous in machine learning
applications, ranging from feature selection to model compression. In this
paper, we present a novel stochastic method -- Orthant Based Proximal
Stochastic Gradient Method (OBProx-SG) -- to solve perhaps the most popular
instance, i.e., the l1-regularized problem. The OBProx-SG method contains two
steps: (i) a proximal stochastic gradient step to predict a support cover of
the solution; and (ii) an orthant step to aggressively enhance the sparsity
level via orthant face projection. Compared to the state-of-the-art methods,
e.g., Prox-SG, RDA and Prox-SVRG, the OBProx-SG not only converges to the
global optimal solutions (in convex scenario) or the stationary points (in
non-convex scenario), but also promotes the sparsity of the solutions
substantially. Particularly, on a large number of convex problems, OBProx-SG
outperforms the existing methods comprehensively in the aspect of sparsity
exploration and objective values. Moreover, the experiments on non-convex deep
neural networks, e.g., MobileNetV1 and ResNet18, further demonstrate its
superiority by achieving the solutions of much higher sparsity without
sacrificing generalization accuracy.

介绍了一种新的随机优化算法 - 基于正交面的近端随机梯度方法（OBProx-SG）- 用于解决最流行的稀疏正则化问题，与现有方法相比，在稀疏探索和目标值方面综合表现优异，特别是在凸优化问题上获得了全局最优解，同时在非凸优化问题上获得了稳定点，同时在非凸深度神经网络中获得了更高稀疏度的解而不会牺牲泛化精度。

基于正交坐标轴的惩罚项一正则化优化的近端随机梯度方法

Orthant Based Proximal Stochastic Gradient Method for  $\ell_1$-Regularized Optimization

Variable selection is a fundamental task in statistical data analysis.
Sparsity-inducing regularization methods are a popular class of methods that
simultaneously perform variable selection and model estimation. The central
problem is a quadratic optimization problem with an l0-norm penalty. Exactly
enforcing the l0-norm penalty is computationally intractable for larger scale
problems, so dif- ferent sparsity-inducing penalty functions that approximate
the l0-norm have been introduced. In this paper, we show that viewing the
problem from a convex relaxation perspective offers new insights. In
particular, we show that a popular sparsity-inducing concave penalty function
known as the Minimax Concave Penalty (MCP), and the reverse Huber penalty
derived in a recent work by Pilanci, Wainwright and Ghaoui, can both be derived
as special cases of a lifted convex relaxation called the perspective
relaxation. The optimal perspective relaxation is a related minimax problem
that balances the overall convexity and tightness of approximation to the l0
norm. We show it can be solved by a semidefinite relaxation. Moreover, a
probabilistic interpretation of the semidefinite relaxation reveals connections
with the boolean quadric polytope in combinatorial optimization. Finally by
reformulating the l0-norm pe- nalized problem as a two-level problem, with the
inner level being a Max-Cut problem, our proposed semidefinite relaxation can
be realized by replacing the inner level problem with its semidefinite
relaxation studied by Goemans and Williamson. This interpretation suggests
using the Goemans-Williamson rounding procedure to find approximate solutions
to the l0-norm penalized problem. Numerical experiments demonstrate the
tightness of our proposed semidefinite relaxation, and the effectiveness of
finding approximate solutions by Goemans-Williamson rounding.

本文介绍了如何将一个经典的稀疏正则化模型 with an l0 范数惩罚转化为凸松弛的形式，在此基础上通过引入远离凸性的惩罚函数，如 Minimax Concave Penalty (MCP) 以及 reverse Huber penalty，进一步推导出新的解法，并且可以通过半定松弛方法求解。文章最终通过 Goemans-Williamson 圆整算法来找到近似解。