k-Sparse Autoencoders
Authors: Alireza Makhzani, Brendan Frey
ICLR 2014

Abstract: Recently, it has been observed that when representations are learnt in a way that encourages sparsity, improved performance is obtained on classification tasks. These methods involve combinations of activation functions, sampling steps and different kinds of penalties. To investigate the effectiveness of sparsity by itself, we propose the k-sparse autoencoder, which is a linear model, but where in hidden layers only the k highest activities are kept. When applied to the MNIST and NORB datasets, we find that this method achieves better classification results than denoising autoencoders, networks trained with dropout, and restricted Boltzmann machines. k-sparse autoencoders are simple to train and the encoding stage is very fast, making them well-suited to large problem sizes, where conventional sparse coding algorithms cannot be applied.


Peer review:
[Review]:
In this paper, the authors propose a new sparse autoencoder. At training time, the input vector is projected onto a set of filters to produce code values. These code values are sorted and only the top k values are retained, the rest is set to 0 to achieve an exact k-sparse code. Then, the code is used to reconstruct the input by multiplying this code by the transpose of the encoding matrix. The parameters are learned via backpropagation of the squared reconstruction error. The authors relate this algorithm to sparse coding and demonstrate its effectiveness in terms of classification accuracy on the MNIST and NORB datasets.

The paper is fairly incremental in its novelty. There are several other papers that used similar ideas. Examples of the most recent ones:
- R. K. Srivastava, J. Masci, S. Kazerounian, F. Gomez, J. Schmidhuber. Compete to Compute. In Proc. Neural Information Processing Systems (NIPS) 2013, Lake Tahoe.
- Smooth Sparse Coding via Marginal Regression for Learning Sparse Representations  K Balasubramanian, K Yu, G Lebanon
Proceedings of the 30th International Conference on Machine Learning 2013

The theoretical analysis is good but straightforward.
What worries me the most is that a very important detail of the method (how to prevent 'dead' units) is only slightly mentioned. The problem is that the algorithm guarantees to find k-sparse codes for every input but not to use different codes for different inputs. As the code becomes more and more overcomplete (and filters more and more correlated), there will be more and more units that are not used making the algorithm rather inefficient.
The authors propose to have a schedule on 'k' but that seems rather hacky to me. What happens if the authors use twice as many codes? what happens if they use 4 times as many codes? My guess is that it will break down easily. 
My intuition is that this is a very simple and effective method when the code has about the same dimensionality of the input but it is less effective in overcomplete settings. This is an issue that can be rather important in practical applications and that should be discussed and better addressed.

Pros:
- simplicity
- clearly written paper

Cons:
- lack of novelty (see comments above)
- lack of comparison
  - I would add a comparison to A. Coates method and to K. Gregor's LISTA (or K. Kavukcuoglu's PSD) (software for these methods is publicly available). These are the most direct competitors of the proposed method because they also try to compute a good and fast approximation to sparse codes.
- the method is a bit flawed because it does not control sparsity across samples (yielding to possibly many dead units). It would be very helpful to add experiments with a few different values of code dimensionality. For instance on MNIST, it would be interesting to try: 1000, 2000 and 5000.

Overall, this is a nicely written paper proposing a simple method that seems to work fairly well. I have concerns about the novelty of this method and its robustness to highly overcomplete settings.