5  Proximal Toolbox

• Regularization Functions
• Function mexProximalFlat
• Function mexProximalTree
• Function mexProximalGraph
• Function mexProximalPathCoding
• Function mexEvalPathCoding
• Problems Addressed
• Function mexFistaFlat
• Function mexFistaTree
• Function mexFistaGraph
• Function mexFistaPathCoding
• Function solverPoisson
• Function mexIncrementalProx
• Function mexStochasticProx

The previous toolbox we have presented is well adapted for solving a large number of small and medium-scale sparse decomposition problems with the square loss, which is typical from the classical dictionary learning framework. We now present a new software package that is adapted for solving a wide range of possibly large-scale learning problems, with several combinations of losses and regularization terms. The method implements the proximal methods of [1], and includes the proximal solvers for the tree-structured regularization of [15], and the solver of [22] for general structured sparse regularization. The solver for structured sparse regularization norms includes a C++ max-flow implementation of the push-relabel algorithm of [13], with heuristics proposed by [5].

This implementation also provides robust stopping criteria based on duality gaps, which are presented in Appendix A. It can handle intercepts (unregularized variables). The general formulation that our software can solve take the form

where f is a smooth loss function and ψ is a regularization function. When one optimizes a matrix W in ℝ^{p × r} instead of a vector w in ℝ^p, we will write

Note that the software can possibly handle nonnegativity constraints.

We start by presenting the type of regularization implemented in the software

5.1  Regularization Functions

Our software can handle the following regularization functions ψ for vectors w in ℝ^p:

• The Tikhonov regularization: ψ(w) =^▵ 1/2||w||₂².
• The ℓ₁-norm: ψ(w) =^▵ ||w||₁.
• The Elastic-Net: ψ(w) =^▵ ||w||₁+γ||w||₂².
• The Fused-Lasso: ψ(w) =^▵ ||w||₁+γ||w||₂²+γ₂∑_i=1^p−1|w_i+1−w_i|.
• The group Lasso: ψ(w) =^▵ ∑_{g ∈ G} η_g ||w_g||₂, where G are groups of variables.
• The group Lasso with ℓ_∞-norm: ψ(w) =^▵ ∑_{g ∈ G} η_g ||w_g||_∞, where G are groups of variables.
• The sparse group Lasso: same as above but with an additional ℓ₁ term.
• The tree-structured sum of ℓ₂-norms: ψ(w) =^▵ ∑_{g ∈ G} η_g ||w_g||₂, where G is a tree-structured set of groups [15], and the η_g are positive weights.
• The tree-structured sum of ℓ_∞-norms: ψ(w) =^▵ ∑_{g ∈ G} η_g ||w_g||_∞. See [15]
• General sum of ℓ_∞-norms: ψ(w) =^▵ ∑_{g ∈ G} η_g ||w_g||_∞, where no assumption are made on the groups G.
• The path-coding penalties of [24].
• the ℓ₁-constraint.
• a few undocumented ones.

Our software also handles regularization functions ψ on matrices W in ℝ^{p × r} (note that W can be transposed in these formulations). In particular,

• The ℓ₁/ℓ₂-norm: ψ(W) =^▵ ∑_i=1^p ||W_i||₂, where W_i denotes the i-th row of W.
• The ℓ₁/ℓ_∞-norm: ψ(W) =^▵ ∑_i=1^p ||W_i||_∞,
• The ℓ₁/ℓ₂+ℓ₁-norm: ψ(W) =^▵ ∑_i=1^p ||W_i||₂ + λ₂ ∑_i,j|W_ij|.
• The ℓ₁/ℓ_∞+ℓ₁-norm: ψ(W) =^▵ ∑_i=1^p ||W_i||_∞+λ₂ ∑_i,j|W_ij|,
• The ℓ₁/ℓ_∞-norm on rows and columns: ψ(W) =^▵ ∑_i=1^p ||W_i||_∞+λ₂ ∑_j=1^r||W^j||_∞, where W^j denotes the j-th column of W.
• The multi-task tree-structured sum of ℓ_∞-norms:

  ψ(W)

  ▵ =

  r ∑ i=1

  ∑ g ∈ G

  ηg||wgi||∞+ γ

  ∑ g ∈ G

  ηg

  max j ∈ g

  ||Wj||∞,     (25)

  where the first double sums is in fact a sum of independent structured norms on the columns wⁱ of W, and the right term is a tree-structured regularization norm applied to the ℓ_∞-norm of the rows of W, thereby inducing the tree-structured regularization at the row level. G is here a tree-structured set of groups.
• The multi-task general sum of ℓ_∞-norms is the same as Eq. (25) except that the groups G are general overlapping groups.
• The trace norm: ψ(W) =^▵ ||W||_*.

Non-convex regularizations are also implemented with the ISTA algorithm (no duality gaps are of course provided in these cases):

• The ℓ₀-pseudo-norm: ψ(w) =^▵ ||w||₀.
• The rank: ψ(W) =^▵ randk(W).
• The tree-structured ℓ₀-pseudo-norm: ψ(w) =^▵ ∑_{g ∈ G} δ_{wg ≠ 0}.

All of these regularization terms for vectors or matrices can be coupled with nonnegativity constraints. It is also possible to add an intercept, which one wishes not to regularize, and we will include this possibility in the next sections. There are also a few hidden undocumented options which are available in the source code.

We now present 3 functions for computing proximal operators associated to the previous regularization functions.

5.2  Function mexProximalFlat

This function computes the proximal operators associated to many regularization functions, for input signals U=[u¹,…,uⁿ] in ℝ^{p × n}, it finds a matrix V=[v¹,…,vⁿ] in ℝ^{p × n} such that:

•  If one chooses a regularization function on vectors, for every column u of U, it computes one column v of V solving

or

or

or

or

or

where T is a tree-structured set of groups (see [16]), and δ^g(v) = 0 if v_g=0 and 1 otherwise. It can also solve

or

or

where G is any kind of set of groups.

This function can also solve the following proximal operators on matrices

where V_i is the i-th row of V, or

or

or

or

where V^j is the j-th column of V.

See details below:

The following piece of code illustrates how to use this function.

5.3  Function mexProximalTree

This function computes the proximal operators associated to tree-structured regularization functions, for input signals U=[u¹,…,uⁿ] in ℝ^{p × n}, and a tree-structured set of groups [15], it computes a matrix V=[v¹,…,vⁿ] in ℝ^{p × n}. When one uses a regularization function on vectors, it computes a column v of V for every column u of U:

or

or

where δ^g(v)=0 if v_g=0 and 1 otherwise (see appendix of [16]).

When the multi-task tree-structured regularization function is used, it solves

which is a formulation presented in [22].

This function can also be used for computing the proximal operators addressed by mexProximalFlat (it will just not take into account the tree structure). The way the tree is incoded is presented below, (and examples are given in the file test_ProximalTree.m, with more usage details:

The following piece of code illustrates how to use this function.

5.4  Function mexProximalGraph

This function computes the proximal operators associated to structured sparse regularization, for input signals U=[u¹,…,uⁿ] in ℝ^{p × n}, and a set of groups [22], it returns a matrix V=[v¹,…,vⁿ] in ℝ^{p × n}. When one uses a regularization function on vectors, it computes a column v of V for every column u of U:

or with a regularization function on matrices, it computes V solving

This function can also be used for computing the proximal operators addressed by mexProximalFlat. The way the graph is incoded is presented below (and also in the example file test_ProximalGraph.m, with more usage details:

The following piece of code illustrates how to use this function.

5.5  Function mexProximalPathCoding

This function computes the proximal operators associated to the path coding penalties of [24].

The following piece of code illustrates how to use this function.

This function is associated to a function to evaluate the penalties:

5.6  Function mexEvalPathCoding

The following piece of code illustrates how to use this function.

After having presented the regularization terms which our software can handle, we present the various formulations that we address

5.7  Problems Addressed

We present here regression or classification formulations and their multi-task variants.

5.7.1  Regression Problems with the Square Loss

Given a training set {xⁱ,y_i}_i=1ⁿ, with xⁱ ∈ ℝ^p and y_i ∈ ℝ for all i in [ 1;n ], we address

where b is an optional variable acting as an “intercept”, which is not regularized, and ψ can be any of the regularization functions presented above. Let us consider the vector y in ℝⁿ that carries the entries y_i. The problem without the intercept takes the following form, which we have already encountered in the previous toolbox, but with different notations:

where the X=[xⁱ,…,xⁿ]^T (the xⁱ’s are here the rows of X).

5.7.2  Classification Problems with the Logistic Loss

The next formulation that our software can solve is the regularized logistic regression formulation. We are again given a training set {xⁱ,y_i}_i=1ⁿ, with xⁱ ∈ ℝ^p, but the variables y_i are now in {−1,+1} for all i in [ 1;n ]. The optimization problem we address is

with again ψ taken to be one of the regularization function presented above, and b is an optional intercept.

5.7.3  Multi-class Classification Problems with the Softmax Loss

We have also implemented a multi-class logistic classifier (or softmax). For a classification problem with r classes, we are given a training set {xⁱ,y_i}_i=1ⁿ, where the variables xⁱ are still vectors in ℝ^p, but the y_i’s have integer values in {1,2,…,r}. The formulation we address is the following multi-class learning problem

where W = [w¹,…,w^r] and the optional vector b in ℝ^r carries intercepts for each class.

5.7.4  Multi-task Regression Problems with the Square Loss

We are now considering a problem with r tasks, and a training set {xⁱ,yⁱ}_i=1ⁿ, where the variables xⁱ are still vectors in ℝ^p, and yⁱ is a vector in ℝ^r. We are looking for r regression vectors w^j, for j∈ [ 1;r ], or equivalently for a matrix W=[w¹,…,w^r] in ℝ^{p × r}. The formulation we address is the following multi-task regression problem

where ψ is any of the regularization function on matrices we have presented in the previous section. Note that by introducing the appropriate variables Y, the problem without intercept could be equivalently rewritten

5.7.5  Multi-task Classification Problems with the Logistic Loss

The multi-task version of the logistic regression follows the same principle. We consider r tasks, and a training set {xⁱ,yⁱ}_i=1ⁿ, with the xⁱ’s in ℝ^p, and the yⁱ’s are vectors in {−1,+1}^r. We look for a matrix W=[w¹,…,w^r] in ℝ^{p × r}. The formulation is the following multi-task regression problem

5.7.6  Multi-task and Multi-class Classification Problems with the Softmax Loss

The multi-task/multi-class version directly follows from the formulation of Eq. (46), but associates with each class a task, and as a consequence, regularizes the matrix W in a particular way:

How duality gaps are computed for any of these formulations is presented in Appendix A. We now present the main functions for solving these problems

5.8  Function mexFistaFlat

Given a matrix X=[x¹,…,x^p]^T in ℝ^{m × p}, and a matrix Y=[y¹,…,yⁿ], it solves the optimization problems presented in the previous section, with the same regularization functions as mexProximalFlat. see usage details below:

The following piece of code illustrates how to use this function.

5.9  Function mexFistaTree

Given a matrix X=[x¹,…,x^p]^T in ℝ^{m × p}, and a matrix Y=[y¹,…,yⁿ], it solves the optimization problems presented in the previous section, with the same regularization functions as mexProximalTree. see usage details below:

The following piece of code illustrates how to use this function.

5.10  Function mexFistaGraph

Given a matrix X=[x¹,…,x^p]^T in ℝ^{m × p}, and a matrix Y=[y¹,…,yⁿ], it solves the optimization problems presented in the previous section, with the same regularization functions as mexProximalGraph. see usage details below:

The following piece of code illustrates how to use this function.

5.11  Function mexFistaPathCoding

Similarly, the toolbox handles the penalties of [24] with the following function

The following piece of code illustrates how to use this function.

5.12  Function solverPoisson

The following problem is addressed here

The following piece of code illustrates how to use this function.

5.13  Function mexIncrementalProx

This implements the incremental solver MISO [25].

The following piece of code illustrates how to use this function.

5.14  Function mexStochasticProx

This implements the stochastic proximal gradient solver [26].

The following piece of code illustrates how to use this function.