QUIC & DIRTY: A Quadratic Approximation Approach for Dirty Statistical Models
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 first-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 efficiently 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 first-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 first algorithm that can extend active subspace ideas to multiple regularizers.
The paper addresses the question of estimating so called dirty models in which the parameter is a sum of "simple parameters", complexities of which are individually regularized. The paper proposes a subspace selection strategy that makes quadratic approximation feasible. The theoretic development builds on the notion of decomposable norms. I have to confess that I have not followed this line of work very closely, so my comments are necessarily those of a generally knowledgeable person in machine learning and model selection.It appears that the work is a neat combination of ideas that have been published before, such as minimizing nuclear norm via active subspace selection (ICML 2014), and using quadratic approximation for sparse inverse covariance estimation (NIPS 2011), but the work is now carried out in a more general setting of decomposable norms. To me, this appears elegant, but some questions remain. The algorithmic achievement of 10-fold speedup does not sound very impressive, such factors are usually easily achieved by optimizing the implementation, thus the question becomes how easy it is to optimize (say parallelize etc.) the most demanding parts of the algorithm. For very practically oriented person the achievement may not appear great.The presentation of the theory is in general rather clear even if somewhat compact possibly due to page limit. The writing is not impeccable - some of the language errors are distracting to the level that hampers comprehension. The use of citations as a part of sentence is generally not encouraged and it creates new grammatical problems: should we write "[7, 5] consider the estimation ..." or "[7, 5] considers the estimation ..."? Sometimes poor punctuation creates problems like in "[14] in turn use a superposition ..." or "we consider instead a proximal ...". At worst the sentences are ungrammatical to the level of being incomprehensible like the sentence: "Overall, our algorithmic ...." on page 2. Writing formulas inside the text creates a set of problems of its own and sometimes the result is awkward - too often do we see a line ending in equal-sign (say 0 = \newline). On page 7, the formula breaches the margin as does the figure 1 and the table 1 on page 8.In general, it is customary to have some kind of conclusion or discussion in the paper. Now there is none. For example, discussion about the future directions would be welcome, since it is not clear to me where to go from here.In the algorithm 1, line 7, the superscript (t) should probably be (r), and updating the sum on line 8 looks strange (one should update variables rather than expressions).