Dirty Statistical Models
We provide a unified framework for the high-dimensional analysis of "superposition-structured" or "dirty" statistical models: where the model parameters are a superposition of structurally constrained parameters. We allow for any number and types of structures, and any statistical model. We consider the general class of M -estimators that minimize the sum of any loss function, and an instance of what we call a "hybrid" regularization, that is the infimal convolution of weighted regularization functions, one for each structural component. We provide corollaries showcasing our unified framework for varied statistical models such as linear regression, multiple regression and principal component analysis, over varied superposition structures.
This paper provides bounds for the learning of 
      M-estimators minimizing a loss function with superposition-structured 
      regularizers. This type of statistical model features a parameter vector 
      which is a superposition of several vectors, each of them having a 
      specific structure enforced by its own regularizer. Examples of such 
      models have been the subject of very recent results (see in particular the 
      referenced papers from Chandrasekaran et al.). The present work provides 
      bounds for the learning of the parameter vector by extending the framework 
      of decomposable regularizers proposed in (Negahban et al. 2012). While the 
      general result is provided in Theorem 1, the resulting bound involves 
      several unknown constants which are specific to the statistical model. The 
      remaining of the paper studies several examples of such models and derives 
      explicit bounds for each of them. Similarly to (Negahban et al. 2012), the 
      resulting bounds emphasize the good behavior of structured regularizers 
      for high-dimensional problems when the target vector lies in an 
      appropriate structured subspace. Pros: The type of statistical 
      models ("dirty" models) for which bounds are derived has triggered 
      recently considerable interest from the statistical community, elegantly 
      providing convex relaxations to challenging problems. These problems 
      moreover touch areas directly relevant to machine learning (graphical 
      models, regression,...) and have clear potential applications. The 
      paper provides important insights in the factors determining the 
      performance of the superposition structured M-estimator. In particular, 
      the concept of Structural Incoherence is introduced (assumption C4) to 
      account for the interactions between the regularizers associated to each 
      structure. As stated in the paper, the provided bounds seem to 
      represent considerable improvement with respect to the state of the art 
      and are more general. Finally, the authors convincingly illustrate the 
      application of their general methodology in 3 interesting examples of 
      sparse statistical models. Cons: Although the authors claim their 
      result is very general, the assumptions on the model seem in practice 
      quite constraining: in particular, the family of appropriate penalties, 
      that are both norms and decomposable (as a sum of penalties over 
      orthogonal subspaces), seems restricted to immediate generalizations of 
      the l1-norm. It would be useful to discuss the possibility/consequences of 
      including additional regularizers such as the squared Euclidian norm 
      (typically: can this framework deal with elastic net penalties?). One 
      other issue is the applicability of the bounds to practical cases. As far 
      as I understand, the assumptions required to prove these bounds are 
      numerous and involve several unknown parameters. In particular, in the 
      first two presented examples (Proposition 2, Corollary 2, Proposition 3), 
      conditions for which assumptions hold are not established, especially all 
      results assume the C-linearity condition (7) to hold without further 
      justification. Corollary 4 assumes a (simpler) C-linearity condition (12) 
      as well. Moreover, in all examples, bounds depend on \bar{\kappa} or 
      directly on the curvature parameter \kappa_{\mathcal{L}}, for which no 
      range of acceptable values is provided. Is it possible to show for that 
      these assumptions hold with some degree of generality and for some values 
      of the parameters (curvature…), that might depend on the specific model. 
      Although very well written, the paper is also very dense and some 
      definitions/notations are difficult to understand without referring to 
      (Negahban et al. 2012), see the following comments for details. 
      Comments: -line 142: proposition 1 is important, please provide at 
      least references for the concept of infimal convolution. Although the 
      result seems intuitive, please make sure all necessary assumptions are 
      correctly listed. -line 157: please mention that the target parameter 
      is the minimizer of the population risk -line 168: the concept of 
      restricted set is introduced, however without referring to other readings, 
      it is difficult to understand how these sets are defined for each 
      structure and used. Please provide some explanation. -Corollaries 2, 3 
      and 4 do not mention whether the bound is obtained with high probability, 
      please clarify. Typos: -line 230: "subspaces are chosen so 
      that $\prod$...$", I guess the projector on the subspace *orthogonal* to 
      $\mathcal{M}$ should vanish. -line 303: "we are now ready *to* derive"