Iteratively Re-Weighted Method for Sparsity-Inducing Norms

Among a big body of recently developed algorithms for machine learning and data mining, a class of models using non-convex/non-smooth sparsity-inducing norms achieves promising results on many challenging tasks. An important problem faced with such models is to find an effective solution for the objective function with one or multiple intractable terms. Although a large number of optimization approaches have been developed, most of them are tailored to a specific model. Besides, these approaches generally introduce some additional parameters and no longer guarantee convergence. In this work, we first revisit some representative non-convex/non-smooth machine learning models, and then unity them into a generic formulation. Theoretically, we develop a simple yet efficient optimization framework, namely Iteratively Re-Weighted method (IRW), to solve such a class of models and provide the corresponding convergence analysis. Particularly, we validate our proposed method on two challenging machine learning tasks: multi-task regression and feature selection. Source codes are available at: https://github.com/KDD-Code/Sparse.git.