On Primal and Dual Sparsity of Markov Networks

by Jun Zhu and Eric P. Xing

This paper mainly taks about the relationship of several M3Ns. The primal and dual sparsity are caused by L1 norm penalty and the constraints (according to KKT conditions). Therefore adding L1 norm penalty to M3N will cause both sparsities, which increases generalization capacity and selects important features.

The LapM3N proposed by the authors earlier is a Bayesian version of M3N. The MAP estimator of LapM3N would go as M3N with different penalties, e.g. L2 norm corresponding to a Gaussian prior and L1 norm corresponding to a Laplace prior with parameter going to infinity.

Another relationship of L1 norm is found to sparse Bayesian learning, since adding a prior for each parameter of M3N (think about RVM) would result a sparse solution. The adaptive M3N will yield the same result as the L1-normed M3N.

The authors proposed an EM-like algorithm for training L1-normed M3N. Obviously, it would have connection to variational Bayesian approximation.

Maybe we should write our own structured learning tools.

Large-scale Deep Unsupervised Learning using Graphics Processors

by Rajat Raina, Anand Madhavan and Andrew Ng

This is a paper on implementation of DBN and sparse coding algorithms with GPU. The finer-grain parallelism provided by the modern GPU outperforms CPU architecture. The bottleneck is the IO, from main memory to the memory inside the video adapter. The finer-grain parallelism allows us to deal with data parallelism and the data are divided for each block and the job assigned to each block is further divided into threads' labor.

They said they would provide their code online. I have not found it.

Gradient Descent with Sparsification: An Iterative Algorithm for Sparse Recovery with Restricted Isometry Property

by Rahul Garg and Rohit Khandekar

This paper tells one story about the following optimization problem arising from compressive sampling

\min_x \quad \| x \|_0 \qquad \text{s.t.} \quad \Phi x = y,

which is usually approximated with the following version

\min_x \quad \| x \|_1 \qquad \text{s.t.} \quad \Phi x = y.

We have quite a few algorithms for solving the optimization under different conditions. This paper proposes the following gradient-based algorithm

x \leftarrow H_s \left( x + \frac{1}{\gamma} \cdot \Phi^\top (y - \Phi x)\right)

where H_s take the largest (absolute value) s elements of x and other as 0.

The theoretical result is their small computation cost (K in each iteration), fast convergence rate (2L / \log(\frac{1 - \delta_{2s}}{2\delta_{2s}})) and lenient recovery condition (\delta_{2s} < \frac{1}{3}). I think it might be a good algorithm if we late want to make some lasso experiments.