Orbit Regularization

André F. T. Martins∗
Instituto de TelecomunicaçõesInstituto Superior Técnico
1049–001 Lisboa, Portugal
atm@priberam.pt

Renato Negrinho
Instituto de TelecomunicaçõesInstituto Superior Técnico
1049–001 Lisboa, Portugal
renato.negrinho@gmail.com

Abstract
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 andan orbit is fixed; to control complexity, the model parameters are confined to theconvex hull of this orbit (the orbitope). We recover several well-known regularizers as particular cases, and reveal a connection between the hyperoctahedral groupand the recently proposed sorted `1 -norm. We derive the properties a group mustsatisfy 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.

1

Introduction

The main motivation behind current sparse estimation methods and regularized empirical risk minimization is the principle of parsimony, which states that simple explanations should be preferredover complex ones. Traditionally, this has been done by defining a function Ω : V → R that evaluates the complexity of a model w ∈ V and trades off this quantity with a data-dependent term. The
penalty function Ω is often designed to be a convex surrogate of an otherwise non-tractable quantity,
a strategy which has led to important achievements in sparse regression [1], compressed sensing[2], and matrix completion [3], allowing to successfully recover parameters from highly incomplete
information. Prior knowledge about the structure of the variables and the intended sparsity pattern,when available, can be taken into account when designing Ω via sparsity-inducing norms [4]. Performance bounds under different regimes have been established theoretically [5, 6], contributing toa better understanding of the success and failure modes of these techniques.
In this paper, we introduce a new way to characterize the complexity of a model via the conceptof group-induced majorization. Rather than regarding complexity in an absolute manner via Ω, we
define it relative to a prototype model v ∈ V , by requiring that the estimated model w satisfies
w G v,(1)where G is an ordering relation on V induced by a group G. This idea is rooted in majorization
theory, a well-established field [7, 8] which, to the best of our knowledge, has never been applied tomachine learning. We therefore review these concepts in §2, where we show that this formulation
subsumes several well-known regularizers and motivates new ones. Then, in §3, we introduce two
important properties of groups that serve as building blocks for the rest of the paper: the notionsof matching function and region cones. In §4, we apply these tools to the permutation and signed
permutation groups, unveiling connections with the recent sorted `1 -norm [9] as a byproduct. In §5
we turn to algorithmic considerations, pinpointing the group-specific operations that make a groupamenable to optimization with conditional and projected gradient algorithms.
∗

Also at Priberam Labs, Alameda D. Afonso Henriques, 41 - 2◦ , 1000–123, Lisboa, Portugal.

1

Figure 1: Examples of orbitopes for the orthogonal group O(d) (left) and the hyperoctahedralgroup P± (right). Shown are also the corresponding region cones, which in the case of O(d) degenerates into a ray.

A key aspect of our framework is a decoupling in which the group G captures the invariances of
the regularizer, while the data-dependent term is optimized in the group orbitopes. In §6, we buildon this intuition to propose a simple continuation algorithm for orbit exploration. Finally, §7 showssome simulation results, and we conclude in §8.

2

Orbitopes and Majorization

2.1

Vector Spaces and Groups

Let V be a vector space with an inner product h·, ·i. We will be mostly concerned with the case where
V = Rd , i.e., the d-dimensional real Euclidean space, but some of the concepts introduced here
generalize to arbitrary Hilbert spaces. A group is a set G endowed with an operation · : G × G → G
satisfying closure (g · h ∈ G, ∀g, h ∈ G), associativity ((f · g) · h = f · (g · h), ∀f, g, h ∈ G),
existence of identity (∃1G ∈ G such that 1G · g = g · 1G = g, ∀g ∈ G), and existence of inverses(each g ∈ G has an inverse g −1 ∈ G such that g · g −1 = g −1 · g = 1G ). Throughout, we use
boldface letters u, v, w, . . . for vectors, and g, h, . . . for group elements. We also omit the group
operation symbol, writing gh instead of g · h.
2.2Group Actions, Orbits, and Orbitopes

A (left) group action of G on V [10] is a function ψ : G × V → V satisfying ψ(g, ψ(h, v)) =ψ(g · h, v) and ψ(1G , v) = v for all g, h ∈ G and v ∈ V . When the action is clear from the context,
we omit the letter ψ, writing simply gv for the action of the group element g on v, instead of ψ(g, v).
In this paper, we always assume our actions are linear, i.e., g(c1 v 1 + c2 v 2 ) = c1 gv 1 + c2 gv 2 forscalars c1 and c2 and vectors v 1 and v 2 . In some cases, we also assume they are norm-preserving,i.e., kgvk = kvk for any g ∈ G and v ∈ V . When V = Rd , we may regard the groups underlying
these actions as subgroups of the general linear group GL(d) and of the orthogonal group O(d),respectively. GL(d) is the set of d-by-d invertible matrices, and O(d) the set of d-by-d orthogonal
matrices {U ∈ Rd×d | U > U = U U > = Id }, where Id denotes the d-dimensional identity matrix.
A group action defines an equivalence relation on V , namely w ≡ v iff there is g ∈ G such thatw = gv. The orbit of a vector v ∈ V under the action of G is the set Gv := {gv | g ∈ G}, i.e., thevectors that result from acting on v with some element of G. Its convex hull is called the orbitope:
OG (v) := conv(Gv).
(2)
Fig. 1 (left) illustrates this concept for the orthogonal group in R2 . An important concept associatedwith group actions and orbitopes is that of G-majorization [7]:Definition 1 Let v, w ∈ V . We say that w is G-majorized by v, denoted w G v, if w ∈ OG (v).
Proposition 2 If the group action is linear, then G is reflexive and transitive, i.e., it is a pre-order.
Proof: See supplemental material.
Group majorization plays an important role in the area of multivariate inequalities in statistics [11].
In this paper, we use this concept for representing model complexity, as described next.
2.3

Orbit Regularization

We formulate our learning problem as follows:
minimize L(w) s.t. w G v,(3)
where L : V → R is a loss function, G is a given group, and v ∈ V is a seed vector. This
formulation subsumes several well-known cases, outlined below.
2• `2 -regularization. If G := O(d) is the orthogonal group acting by multiplication, we recover `2regularization. Indeed, we have Gv = {U v ∈ Rd | U ∈ O(d)} = {w ∈ Rd | kwk2 = kvk2 }, forany seed v ∈ Rd . That is, the orbitope OG (v) = conv(Gv) becomes the `2 -ball with radius kvk2 .
The only property of the seed that matters in this case is its `2 -norm.
• Permutahedron. Let P be the symmetric group (also called the permutation group), which canbe represented as the set of d-by-d permutation matrices. Given v ∈ Rd , the orbitope induced by v
under P is the convex hull of all the permutations of v, which can be equivalently described as thevectors that are transformations of v through a doubly stochastic matrix:
OP (v) = conv{P v | P ∈ P} = {M v | M 1 = 1, M > 1 = 1, M ≥ 0}.

(4)This set is called the permutahedron [12]. We will revisit this case in §4.
• Signed permutahedron. Let P± be the hyperoctahedral group (also called the signed permutation group), i.e., the d-by-d matrices with entries in {0, ±1} such that the sum of the absolute values
in each row and column is 1. The action of P± on Rd permutes the entries of vectors and arbitrarily
switches signs. Given v ∈ Rd , the orbitope induced by v under P± is:
OP± (v) = conv{Diag(s)P v | P ∈ P, s ∈ {±1}d },(5)where Diag(s) denotes a diagonal matrix formed by the entries of s. We call this set the signed
permutahedron; it is depicted in Fig. 1 and will also be revisited in §4.
• `1 and `∞ -regularization. As a particular case of the signed permutahedron, we recover `1 and`∞ balls by choosing seeds of the form v = γe1 (a scaled canonical basis vector) and v = γ1 (aconstant vector), respectively, where γ is a scalar. In the first case, we obtain the `1 -ball, OG (v) =γ conv({e1 , . . . , ed }) and in the second case, we get the `∞ -ball OG (v) = γ conv({±1}d ).
• Symmetric matrices with majorized eigenvalues. Let G := O(d) be again the orthogonalgroup, but now acting by conjugation on the vector space of d-by-d symmetric matrices, V = Sd .
Given a seed v ≡ A ∈ Sd , its orbit is Gv = {U AU > | U ∈ O(d)} = {U Diag(λ(A))U > | U ∈O(d)}, where λ(A) denotes a vector containing the eigenvalues of A in decreasing order (so we
may assume without loss of generality that the seed is diagonal). The orbitope OG (v) becomes:
OG (v) := {B ∈ Sd | λ(B) P λ(A)},(6)

which is the set of matrices whose eigenvalues are in the permutahedron OP (λ(A)) (see example
above). This is called the Schur-Horn orbitope in the literature [8].
• Squared matrices with majorized singular values. Let G := O(d) × O(d) act on Rd×d (thespace of squared matrices, not necessarily symmetric) as gU,V A := U AV > . Given a seed v ≡ A,
its orbit is Gv = {U AV > | U, V ∈ O(d)} = {U Diag(σ(A))V > | U, V ∈ O(d)}, where σ(A)contains the singular values of A in decreasing order (so we may assume without loss of generalitythat the seed is diagonal and non-negative). The orbitope OG (v) becomes:
OG (v) := {B ∈ Rd×d | σ(B) P σ(A)},(7)

which is the set of matrices whose singular values are in the permutahedron OP (σ(A)).
• Spectral and nuclear norm regularization. The previous case subsumes spectral and nuclear
norm balls: indeed, for a seed A = γId , the orbitope becomes the convex hull of orthogonal matrices, which is the spectral norm ball {A ∈ Rd×d | kAk2 := σ1 (A) ≤ γ}; while for a seedA = γ Diag(e1 ), the orbitope becomes the convex hull ofPrank-1 matrices with norm bounded byγ, which is the nuclear norm ball {A ∈ Rd×d | kAk∗ := i σi ≤ γ}. This norm has been widelyused for low-rank matrix factorization and matrix completion [3].
Besides these examples, other regularization strategies, such as non-overlapping `2,1 and `∞,1 norms[13, 4] can be obtained by considering products of the groups above. We omit details for space.
2.4

Relation with Atomic Norms

Atomic norms have been recently proposed as a toolbox for structured sparsity [6]. Let A ⊆ V
be a centrally symmetric set of atoms, i.e., v ∈ A iff −v ∈ A. The atomic norm induced by A
is defined as kwkA := inf{t > 0 | w ∈ t conv(A)}. The corresponding atomic ball is the set{w | kwkA ≤ 1} = conv(A). Not surprisingly, orbitopes are often atomic norm balls.
3

Proposition 3 (Atomic norms) If G is a subgroup of the general linear group GL(d) and satisfies−v ∈ Gv, then the set OG (v) is the ball of an atomic norm.
Proof: Under the given assumption, the set Gv is centrally symmetric, i.e., it satisfies w ∈ Gv iff−w ∈ Gv (indeed, the left hand side implies that w = gv for some g ∈ G, and −v ∈ Gv implies
that −v = hv for some h ∈ G, therefore, −w = −gh−1 (−v) = gh−1 v ∈ Gv). As shown by
Chandrasekaran et al. [6], this guarantees that k.kGv satisfies the axioms of a norm.
Corollary 4 For any choice of seed, the signed permutahedron OP± (v) and the orbitope formedby the squared matrices with majorized singular values are both atomic norm balls. If d is even andd/2
v is of the form v = (v + , −v + ), with v + ∈ R+ , then the permutahedron OP (v) and the orbitope
formed by the symmetric matrices with eigenvalues majorized by λ(v) are both atomic norm balls.

3

Matching Function and Region Cones

We now construct a unifying perspective that highlights the role of the group G. Two key concepts
that play a crucial role in our analysis are that of matching function and region cone. In the sequel,these will work as building blocks for important algorithmic and geometric characterizations.
Definition 5 (Matching function) The matching function of G, mG : V × V → R, is defined as:mG (u, v) := sup{hu, wi | w ∈ Gv}.
(8)
Intuitively, mG (u, v) “aligns” the orbits of u and v before taking the inner product. Note also thatmG (u, v) = sup{hu, wi | w ∈ OG (v)}, since we may equivalently maximize the linear objective
over OG (v), which is the convex hull of Gv. We therefore have the following
Proposition 6 (Duality) Fix v ∈ V , and define the indicator function of the orbitope, IOG (v) (w) =0 if w ∈ OG (v), and −∞ otherwise. The Fenchel dual of IOG (v) is mG (., v). As a consequence,letting L? : V → R is the Fenchel dual of the loss L, the dual problem of Eq. 3 is:maximize − L? (−u) − mG (u, v) w.r.t. u ∈ V.
(9)
Note that if k.kGv is a norm (e.g., if the conditions of Prop. 3 are satisfied), then the statement abovemeans that mG (., v) = k.k?Gv is its dual norm. We will revisit this dual formulation in §4.
The following properties have been established in [14, 15].
Proposition 7 For any u, v ∈ V , we have: (i) mG (c1 u, c2 v) = c1 c2 mG (u, v) for c1 , c2 ≥ 0;(ii) mG (g1 u, g2 v) = mG (u, v) for g1 , g2 ∈ G; (iii) mG (u, v) = mG (v, u). Furthermore, thefollowing three statements are equivalent: (i) w G v, (ii) f (w) ≤ f (v) for all G-invariant convex
functions f : V → R, (iii) mG (u, w) ≤ mG (u, v) for all u ∈ V .
In the sequel, we always assume that G is a subgroup of the orthogonal group O(d). This implies
that the orbitope OG (v) is compact for any v ∈ V (and therefore the sup in Eq. 8 can be replaced bya max), and that kgvk = kvk for any v ∈ V . Another important concept is that of the normal coneof a point w ∈ V with respect to the orbitope OG (v), denoted as NGv (w) and defined as follows:
NGv (w) := {u ∈ V | hu, w0 − wi ≤ 0 ∀w0 G v}.
(10)
Normal cones plays an important role in convex analysis [16]. The particular case of the normal
cone at the seed v (illustrated in Fig. 1) is of great importance, as will be seen below.
Definition 8 (Region cone) Given v ∈ V , the region cone at v is KG (v) := NGv (v). It is the setof points that are “maximally aligned” with v in terms of the matching function:
KG (v) = {u ∈ V | mG (u, v) = hu, vi}.
(11)

4

Permutahedra and Sorted `1 -Norms

In this section, we focus on the permutahedra introduced in §2. Below, given a vector w ∈ Rd , wedenote by w(k) its kth order statistic, i.e., we will “sort” w so that w(1) ≥ w(2) ≥ . . . ≥ w(d) . We
also consider the order statistics of the magnitudes |w|(k) by sorting the absolute values.
44.1

Signed Permutahedron

We start by defining the “sorted `1 -norm,” proposed by Bogdan et al. [9] in their recent SLOPE
method as a means to control the false discovery rate, and studied by Zeng and Figueiredo [17].
Definition 9 (Sorted `1 -norm) Let v, w ∈ Rd , with v1 ≥ v2 ≥ . . . ≥ vd ≥ 0 and v1 > 0. The
Pd
sorted `1 -norm of w (weighted by v) is defined as: kwkSLOPE,v := j=1 vj |w|(j) .
In [9] it is shown that k.kSLOPE,v satisfies the axioms of a norm. The rationale is that larger components of w are penalized more than smaller ones, in a way controlled by the prescribed v. For
v = 1, we recover the standard `1 -norm, while the `∞ -norm corresponds toP
v = e1 . Another special case is the OSCAR regularizer [18, 19], kwkOSCAR,τ1 ,τ2 := τ1 kwk1 + τ2 i<j max{|wi |, |wj |},corresponding to a linearly spaced v, vj = (τ1 + τ2 (d − j)) for j = 1, . . . , d. The next proposition
reveals a connection between SLOPE and the atomic norm induced by the signed permutahedron.
Proposition 10 Let v ∈ Rd+ be as in Def. 9. The sorted `1 -norm weighted by v and the atomic norm
induced by the P ± -orbitope seeded at v are dual to each other: k.k?P± v = k.kSLOPE,v .
Proof: From Prop. 6, we have kwk?P± v = mP± (w, v). Let P be a signed permutation matrix s.t.
w̃ := P w has its components sorted by decreasing magnitude, |w̃|1 ≥ . . . ≥ |w̃|d . From Prop. 7,
we have mP± (w, v) = m(w̃, v) = h|w̃|, vi = kwkSLOPE,v .
The next proposition [7, 14] provides a characterization of the P± -orbitope in terms of inequalities
about the cumulative distribution of the order statistics.
Proposition 11 (Submajorization ordering) The orbitope OP± (v) can be characterized as:noPPOP± (v) = w ∈ Rd
|w|
≤
|v|
,
∀i
=
1,
.
.
.
,
d
.
(12)
(j)
(j)
j≤i
j≤i
Prop. 11 leads to a precise characterization
Pof the atomic
P norm kwkP± v , and therefore of the dual
norm of SLOPE: kwkP± v = maxi=1,...,d j≤i |w|(j) / j≤i |v|(j) .
4.2

Permutahedron

The unsigned counterpart of Prop. 11 goes back to Hardy et al. [20].
Proposition 12 (Majorization ordering) The P-orbitope seeded at v can be characterized as:noPPOP (v) = w ∈ Rd 1> w = 1> v ∧
w
≤
v
,
∀i
=
1,
.
.
.
,
d
−
1
.
(13)
j≤i (j)j≤i (j)As seen in Corollary 4, if d is even and v = (v + , −v + ), with v ≥ 0, then kwkPv qualifies as aPdnorm (we need to confine to the linear subspace V := {w ∈ Rd |w = 0}). From Prop. 12,
Pj=1 j P
we have that this norm can be written as: kwkPv = maxi=1,...,d−1 j≤i w(j) / j≤i v(j) .
Proposition 13 Assume the conditions above hold and that v1 ≥ v2 ≥ . . . ≥ vd/2 ≥ 0 and v1 > 0.
Pd/2
The dual norm of k.kPv is kwk?Pv = j=1 vj (w(j) − w(d−j+1) ).
Proof: Similar to the proof of Prop. 11.

5

Conditional and Projected Gradient Algorithms

Two important classes of algorithms in sparse modeling are the conditional gradient method [21, 22]
and the proximal gradient method [23, 24]. Under Ivanov regularization as in Eq. 3, the latter reduces
to the projected gradient method. In this section, we show that both algorithms are a good fit forsolving Eq. 3 for arbitrary groups, as long as the two building blocks mentioned in §3 are available:(i) a procedure for evaluating the matching function (necessary for conditional gradient methods)
and (ii) a procedure for projecting onto the region cone (necessary for projected gradient).
5

1: Initialize w 1 = 0
2: for t = 1, 2, . . . do
3:
Choose a stepsize ηt4:
a = wt − ηt ∇L(wt )5:
wt+1 = arg minwG v kw − ak
6: end for

1: Initialize w 1 = 0
2: for t = 1, 2, . . . do
3:
ut = arg maxuG v h−∇L(wt ), ui
4:ηt = 2/(t + 2)
5:
wt+1 = (1 − ηt )wt + ηt ut
6: end for

Figure 2: Conditional gradient (left) and projected gradient (right) algorithms.

5.1

Conditional Gradient

The conditional gradient method is shown in Fig. 2 (left). We assume that a procedure is available
for computing the gradient of the loss. The relevant part is the maximization in line 3, whichcorresponds precisely to an evaluation of the matching function m(s, v), with s = −∇L(wt )(cf. Eq. 8). Fortunately, this step is efficient for a variety of cases:
Permutations. If G = P, the matching function can be evaluated in time O(d log d) with a simple sort operation. Without losing generality, we assume the seed v is sorted in descending order(otherwise, pre-sort it before the main loop starts). Then, each time we need to evaluate m(s, v),
we compute a permutation P such that P s is also sorted. The minimizer in line 3 will equal P −1 v.
Signed permutations. If G = P± , a similar procedure with the same O(d log d) runtime also
works, except that now we sort the absolute values, and set the signs of P −1 v to match those of s.
Symmetric matrices with majorized eigenvalues. Let A = UA λ(A)UA> ∈ Sd and B =UB λ(B)UB> ∈ Sd , where the eigenvalues λ(A) and λ(B) are sorted in decreasing order.
In this case, the matching function becomes mG (A, B) = maxV ∈O(d) trace(A> V BV > ) =hλ(A), λ(B)i due to von Neumann’s trace inequality [25], the maximizer being V = UA UB> .
Therefore, we need only to make an eigen-decomposition and set B 0 = UA λ(B)UA> .
Squared matrices with majorized singular values. Let A = UA σ(A)VA> ∈ Rd×d and
B = UB σ(B)VB> ∈ Rd×d , where the singular values are sorted. We have mG (A, B) =maxU,V ∈O(d) trace(A> U BV > ) = hσ(A), σ(B)i also from von Neumann’s inequality [25]. To
evaluate the matching function, we need only to make an SVD and set B 0 = UA σ(B)VA> .
5.2

Projected Gradient

The projected gradient algorithm is illustrated in Fig. 2 (right); the relevant part is line 5, which
involves a projection onto the orbitope OG (v). This projection may be hard to compute directly,
since the orbitope may lack a concise half-space representation. However, we next transform thisproblem into a projection onto the region cone KG (v) (the proof is in the supplemental material).
Proposition 14 Assume G is a subgroup of O(d). Let g ∈ G be such that ha, gvi = mG (a, v).
Then, the solution of the problem in line 5 is w∗ = a − ΠKG (gv) (a − gv).
Thus, all is necessary is computing the arg-max associated with the matching function, and a black
box that projects onto the region cone KG (v). Again, this step is efficient in several cases:
Permutations. If G = P, the region cone of a point v is the set of points w satisfying vi > vj ⇒wi ≥ wj , for all i, j ∈ 1, . . . , d. Projecting onto this cone is a well-studied problem in isotonic
regression [26, 27], with existing O(d) algorithms.
Signed permutations. If G = P± , this problem is precisely the evaluation of the proximity operator of the sorted `1 -norm, also solvable in O(d) runtime with a stack-based algorithm [9].

6Continuation Algorithm

Finally, we present a general continuation procedure for exploring regularization paths when L
is a convex loss function (not necessarily differentiable) and the seed v is not prescribed. The
6

Require: Factor  > 0, interpolation parameter α ∈ [0, 1]
1: Initialize seed v 0 randomly and set kv 0 k = 
2: Set t = 0
3: repeat4:
Solve wt = arg minwG vt L(w)5:
Pick v 0t ∈ Gv t ∩ KG (wt )6:
Set next seed v t+1 = (1 + )(αv 0t + (1 − α)wt )7:t←t+1
8: until kw t kGvt < 1.
b ∈ {w1 , w2 , . . .}9: Use cross-validation to choose the best w
Figure 3: Left: Continuation algorithm. Right: Reachable region WG for the hyperoctahedral group, with areconstruction loss L(w) = kw − ak2 . Only points v s.t. −∇L(v) = a − v ∈ KG (v) belong to this set.
Different initializations of v 0 lead to different paths along WG , all ending in a.

procedure—outlined in Fig. 3—solves instances of Eq. 3 for a sequence of seeds v 1 , v 2 , . . ., using
a simple heuristic for choosing the next seed given the previous one and the current solution.
The basic principle behind this procedure is the same as in other homotopy continuation methods[28, 29, 30, 31]: we start with very strong regularization (using a small norm ball), and then gradually
weaken the regularization (increasing the ball) while “tracking” the solution. The process stops
when the solution is found to be in the interior of the ball (the condition in line 8), which means theregularization constraint is no longer active. The main difference with respect to classical homotopy
methods is that we do not just scale the ball (in our case, the G-orbitope); we also generate newseeds that shape the ball along the way. To do so, we adopt a simple heuristic (line 6) to makethe seed move toward the current solution wt before scaling the orbitope. This procedure depends
on the initialization (see Fig. 3 for an illustration), which drives the search into different regions.
Reasoning in terms of groups, line 4 makes us move inside the orbits, while line 6 is an heuristic
to jump to a nearby orbit. For any choice of  > 0 and α ∈ [0, 1], the algorithm is convergent andproduces a strictly decreasing sequence L(w1 ) > L(w2 ) > · · · before it terminates (a proof isprovided as supplementary material). We expect that, eventually, a seed v will be generated that isb Although it may not be obvious at first sight why would it be desirable
close to the true model w.
b we provide a simple result below (Prop. 15) that sheds some light on this matter, bythat v ≈ w,
characterizing the set of points in V that are “reachable” by optimizing Eq. 3.
From the optimality conditions of convex programming [32, p. 257], we have that w∗ is a solutionof the optimization problem in Eq. 3 if and only if 0 ∈ ∂L(w∗ ) + NGv (w∗ ), where ∂L(w) denotes
the subdifferential of L at w, and NGv (w) is the normal cone to OG (v) at w, defined in §3. For
certain seeds v ∈ V , it may happen that the optimal solution w∗ of Eq. 3 is the seed itself. Let WG
be the set of seeds with this property:
WG := {v ∈ V | L(v) ≤ L(w), ∀w G v} = {v ∈ V | 0 ∈ ∂L(v) + KG (v)},(14)

where KG (v) is the region cone and the right hand side follows from the optimality conditions. We
next show that this set is all we need to care about.
cG :=Proposition
15 Consider the set of points that are solutions of Eq. 3 for some seed v ∈ V , W ∗∗cw ∈ V ∃v ∈ V : w ∈ arg minwG v L(w) . We have WG = WG .
cG . For the reverse direction, suppose that w∗ ∈ W
cG ,Proof: Obviously, v ∈ WG ⇒ v ∈ W∗∗
in which case there is some v ∈ V such that w G v and L(w ) ≤ L(w) for any w G v.
Since G is a pre-order, it must hold in particular that L(w∗ ) ≤ L(w) for any w G w∗ G v.
Therefore, we also have that w∗ ∈ arg minwG w∗ L(w), i.e., w∗ ∈ WG .

7

Simulation Results

We describe the results of numerical experiments when regularizing with the permutahedron (symmetric group) and the signed permutahedron (hyperoctahedral group). All problems were solvedb ∈ Rdusing the conditional gradient algorithm, as described in §5. We generated the true model w
7

Figure 4: Learning curves for the permutahedron and signed permutahedron regularizers with a perfect seed.
Shown are averages and standard deviations over 10 trials. The baselines are `1 (three leftmost plots, resp. withk = 150, 250, 400), and `2 (last plot, with k = 500).

Figure 5: Mean squared errors in the training set (left) and the test set (right) along the regularization path.
For the permutahedra regularizers, this path was traced with the continuation algorithm. The baseline is `1
regularization. The horizontal lines in the right plot show the solutions found with validation in a held-out set.

by sampling the entries from a uniform distribution in [0, 1] and subtracted the mean, keeping k ≤ db was normalized to have unit `2 -norm. Then, we sampled a random nnonzeros; after which w
by-d matrix X with i.i.d. Gaussian entries and variance σ 2 = 1/d, and simulated measurementsb + n, where n ∼ N (0, σn2 ) is Gaussian noise. We set d = 500 and σn = 0.3σ.
y = Xw
For the first set of experiments (Fig. 4), we set k ∈ {150, 250, 400, 500} and varied the numberof measurements n. To assess the advantage of knowing the true parameters up to a group transb up to a constantformation, we used for the orbitope regularizers a seed in the orbit of the true w,
factor (this constant, and the regularization constants for `1 and `2 , were all chosen with validation in a held-out set). As expected, this information was beneficial, and no significant difference
was observed between the permutahedron and the signed permutahedron. For the second set ofexperiments (Fig. 5), where the aim is to assess the performance of the continuation method, no
information about the true model was given. Here, we fixed n = 250 and k = 300 and ran thecontinuation algorithm with  = 0.1 and α = 0.0, for 5 different initializations of v 0 . We observethat this procedure was effective at exploring the orbits, eventually finding a slightly better model
than the one found with `1 and `2 regularizers.

8

Conclusions and Future WorkIn this paper, we proposed a group-based regularization scheme using the notion of orbitopes. Simple choices of groups recover commonly used regularizers such as `1 , `2 , `∞ , spectral and nuclear
matrix norms; as well as some new ones, such as the permutahedron and signed permutahedron.
As a byproduct, we revealed a connection between the permutahedra and the recently proposed
sorted `1 -norm. We derived procedures for learning with these orbit regularizers via conditional andprojected gradient algorithms, and a continuation strategy for orbit exploration.
There are several avenues for future research. For example, certain classes of groups, such as reflection groups [33], have additional properties that may be exploited algorithmically. Our work should
be regarded as a first step toward group-based regularization—we believe that the regularizers studied here are just the tip of the iceberg. Groups and their representations are well studied in otherdisciplines [10], and chances are high that this framework can lead to new regularizers that are agood fit to specific machine learning problems.
Acknowledgments
We thank all reviewers for their valuable comments. This work was partially supported by FCT
grants PTDC/EEI-SII/2312/2012 and PEst-OE/EEI/LA0008/2011, and by the EU/FEDER programme, QREN/POR Lisboa (Portugal), under the Intelligo project (contract 2012/24803).
8References[1] R. Tibshirani. Regression Shrinkage and Selection via the Lasso. Journal of the Royal Statistical Society
B., pages 267–288, 1996.
[2] D. Donoho. Compressed Sensing. IEEE Transactions on Information Theory, 52(4):1289–1306, 2006.
[3] E. Candès and B. Recht. Exact Matrix Completion via Convex Optimization. Foundations of Computational Mathematics, 9(6):717–772, 2009.
[4] F. Bach, R. Jenatton, J. Mairal, and G. Obozinski. Convex optimization with sparsity-inducing norms. In
Optimization for Machine Learning. MIT Press, 2011.
[5] S. Negahban, P. Ravikumar, M. Wainwright, and B. Yu. A Unified Framework for High-Dimensional
Analysis of M-estimators with Decomposable Regularizers. In Neural Information Processing Systems,
pages 1348–1356, 2009.
[6] V. Chandrasekaran, B. Recht, P. Parrilo, and A. Willsky. The Convex Geometry of Linear Inverse Problems. Foundations of Computational Mathematics, 12(6):805–849, 2012.
[7] A. Marshall, I. Olkin, and B. Arnold. Inequalities: Theory of Majorization and Its Applications. Springer,
2010.
[8] R. Sanyal, F. Sottile, and B. Sturmfels. Orbitopes. Technical report, arXiv:0911.5436, 2009.
[9] M. Bogdan, E. Berg, W. Su, and E. Candès. Statistical estimation and testing via the ordered `1 norm.
Technical report, arXiv:1310.1969, 2013.
[10] J. Serre and L. Scott. Linear Representations of Finite Groups, volume 42. Springer, 1977.
[11] Y. Tong. Probability Inequalities in Multivariate Distributions, volume 5. Academic Press New York,1980.
[12] G. Ziegler. Lectures on Polytopes, volume 152. Springer, 1995.
[13] M. Yuan and Y. Lin. Model selection and estimation in regression with grouped variables. Journal of theRoyal Statistical Society Series B (Statistical Methodology), 68(1):49, 2006.
[14] M. Eaton. On group induced orderings, monotone functions, and convolution theorems. Lecture NotesMonograph Series, pages 13–25, 1984.
[15] A. Giovagnoli and H. Wynn. G-Majorization with Applications to Matrix Orderings. Linear algebra andits applications, 67:111–135, 1985.
[16] R.T. Rockafellar. Convex Analysis. Princeton University Press, 1970.
[17] X. Zeng and M. A. T. Figueiredo. Decreasing weighted sorted `1 regularization. Technical report,
arXiv:1404.3184, 2014.
[18] H. Bondell and B. Reich. Simultaneous Regression Shrinkage, Variable Selection, and Supervised Clustering of Predictors with OSCAR. Biometrics, 64(1):115–123, 2008.
[19] L. Zhong and J. Kwok. Efficient Sparse Modeling with Automatic Feature Grouping. IEEE Transactions
on Neural Networks and Learning Systems, 23(9):1436–1447, 2012.
[20] G. Hardy, J. Littlewood, and G. Pólya. Inequalities. Cambridge University Press, 1952.
[21] M. Frank and P. Wolfe. An Algorithm for Quadratic Programming. Naval research logistics quarterly, 3(1-2):95–110, 1956.
[22] M. Jaggi. Revisiting Frank-Wolfe: Projection-free Sparse Convex Optimization. In Proc. of the International Conference on Machine Learning, pages 427–435, 2013.
[23] S.J. Wright, R. Nowak, and M. A. T. Figueiredo. Sparse reconstruction by separable approximation. IEEE
Transactions on Signal Processing, 57(7):2479–2493, 2009.
[24] A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems.
SIAM Journal on Imaging Sciences, 2(1):183–202, 2009.
[25] L. Mirsky. A trace inequality of john von neumann. Monatshefte für Mathematik, 79(4):303–306, 1975.
[26] P. Pardalos and G. Xue. Algorithms for a Class of Isotonic Regression Problems. Algorithmica, 23(3):211–222, 1999.
[27] R. Luss, S. Rosset, and M. Shahar. Decomposing Isotonic Regression for Efficiently Solving Large
Problems. In Neural Information Processing Systems, pages 1513–1521, 2010.
[28] M.R. Osborne, B. Presnell, and B.A. Turlach. A new approach to variable selection in least squares
problems. IMA Journal of Numerical Analysis, 20:389–403, 2000.
[29] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. The Annals of statistics, 32:
407–499, 2004.
[30] M. A. T. Figueiredo, R. Nowak, and S. Wright. Gradient projection for sparse reconstruction: Application
to compressed sensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing,
1(4):586–597, 2007.
[31] E. Hale, W. Yin, and Y. Zhang. Fixed-point continuation for l1-minimization: Methodology and convergence. SIAM Journal on Optimization, 19:1107–1130, 2008.
[32] D.P. Bertsekas, A. Nedic, and A.E. Ozdaglar. Convex analysis and optimization. Athena Scientific, 2003.
[33] A. Steerneman. g-majorization, group-induced cone orderings, and reflection groups. Linear Algebra andits Applications, 127:107–119, 1990.
[34] J.J. Moreau. Fonctions convexes duales et points proximaux dans un espace hilbertien. CR de l’Académie
des Sciences de Paris Série A Mathematics, 255:2897–2899, 1962.

9