Orbit Regularization
We propose a general framework for regularization based on group-induced majorization. In this framework, a group is defined to act on the parameter space and an orbit is fixed; to control complexity, the model parameters are confined to the convex hull of this orbit (the orbitope). We recover several well-known regularizers as particular cases, and reveal a connection between the hyperoctahedral group and the recently proposed sorted 1 -norm. We derive the properties a group must satisfy for being amenable to optimization with conditional and projected gradient algorithms. Finally, we suggest a continuation strategy for orbit exploration, presenting simulation results for the symmetric and hyperoctahedral groups.
Summary: The authors re-explain regularization in optimization problems as a constraint of the type "the parameters ${\bf w}$ must belong to the convex set $O$" where the convex set "O" is obtained as the convex hull of all the points of the form $g.v$ where $v$ is some fix vector, $g$ an element from a group and $.$ is a (linear) group action of element $g$ on vector $v$.More concretely, their main contributions are as follows. (A) they explain how several regularizations can be obtained from their framework. For example, the ball associated to the L1 norm can be explained as the convex hull of the points obtained by flipping the sign and permuting the components of the vector $(1,0,0,..,0)$; (B) they show that given a seed $v$ and a group action associated to a group $G$, the notion of "$w$ is a member of the convex set $O_G(v)$" can be seen as "$v$ is smaller than $w$" under a pre-order; (C) they show that if $-v$ belongs to convex set $O$ then $O$ can be seen as the ball of an atomic norm (as defined in Chandra et al.); (D) they show that the L1-sorted norm equals the dual of the norm associated to the signed-pertumation orbitope; (E) they show how to reinterpret the main steps of conditional and projected gradient algorithms in the language of orbitopes and give a procedure to compute projections onto orbitopes. (F) they provide an heuristic algorithm that iteratively morphs the shape of the ball-norm associated to the regularizer, generalizing the idea of regularization paths.Quality: There are no technical mistakes in the paper. The idea of morphing the shape of the regularizer's ball-norm is the most interesting idea in my opinion. In this regard, it would be good if the authors could clarify the following. Homotopy methods build complete regularization paths that, after being computed, are used in combination with, for example, cross-validation to find the right amount of regularization to perform. I do not understand why the continuation algorithm stops "at (the) point regularization is not having any effect". It would also appreciate if the authors could say a few words about how the continuation algorithm would performs when $\epsilon = 0$. In other words, the shape of the ball-norm is changed by its size is kept constant. Does the algorithm converge ?Proposition 10 has a trivial pictorial explanation that might be good to include for the sake of clarity. In particular, taking the dual of the norm associated to singed-permutations corresponds to transforming the edges in the ball-norm of Fig. 1-right to vertices and transforming vertices to edges. This leads immediately to the ball-norm of the sorted L1-norm, that can be seen as the intersection of the ball-norms of all weighted L1-norms obtained by permuting the coefficients $w$.In Prop. 3 the authors show that (under some conditions) orbit regularizers can be seen as atomic norms. It would be good to explain when/how atomic norms can be seen as orbit regularizers. Clarity: The paper is overall very well written and clear. Here are a few minor things that can be improved. In Line 071 there is a parenthesis missing. In line 244-246  subscripts are missing in $m({\bf w},{\bf v})$, having them would be better. The quality of the pictures should be improved. Are pictures vector format? When I print the paper they look blurred. It would be very useful to have numbers in the references, [1], [2], etc. In Fig. 4, what is the scale in the y-axis referring too?Significance: I find the idea of morphing the shape of the regularizer's ball-norm potentially interesting. Unfortunately, the numerical results do not clearly show that the continuation algorithm, as is, leads to significantly better performance. In Fig. 5 only one simple example is analyzed. Also, the results from Fig. 4 seem inconclusive. It would be good to report the number of iterations it takes for the continuation algorithm to converge. Originality: The idea of re-explaining regularization using orbitopes is new. The idea of a continuation algorithm that iteratively morphs the shape of ball-norms in addition to scaling them is, as far as I can tell, new.