Abstract: In this paper, we develop a family of algorithms for optimizing “superpositionstructured” or “dirty” statistical estimators for high-dimensional problems involving the minimization of the sum of a smooth loss function with a hybrid regularization. Most of the current approaches are ﬁrst-order methods, including proximal gradient or Alternating Direction Method of Multipliers (ADMM). We propose a new family of second-order methods where we approximate the loss function using quadratic approximation. The superposition structured regularizer then leads to a subproblem that can be efﬁciently solved by alternating minimization. We propose a general active subspace selection approach to speed up the solver by utilizing the low-dimensional structure given by the regularizers, and provide convergence guarantees for our algorithm. Empirically, we show that our approach is more than 10 times faster than state-of-the-art ﬁrst-order approaches for the latent variable graphical model selection problems and multi-task learning problems when there is more than one regularizer. For these problems, our approach appears to be the ﬁrst algorithm that can extend active subspace ideas to multiple regularizers.
- QUIC & DIRTY: A Quadratic Approximation Approach for Dirty Statistical Models (pdf)
C. Hsieh, I. Dhillon, P. Ravikumar, S. Becker, P. Olsen.
In Neural Information Processing Systems (NIPS), pp. 2006–2014, December 2014.