A study of how scan orders influence Mixing time in Gibbs sampling.

This paper is interested in comparing the mixing rates of Gibbs sampling using either systematic scan or random updates. The basic contributions are two: First, in Section 2, a set of cases where 1) systematic scan is polynomially faster than random updates. Together with a previously known case where it can be slower this contradicts a conjecture that the speeds of systematic and random updates are similar. Secondly, (In Theorem 1) a set of mild conditions under which the mixing times of systematic scan and random updates are not "too" different (roughly within squares of each other).

First, following from a recent paper by Roberts and Rosenthal, the authors construct several examples which do not satisfy the commonly held belief that systematic scan is never more than a constant factor slower and a log factor faster than random scan. The authors then provide a result Theorem 1 which provides weaker bounds, which however they verify at least under some conditions. In fact the Theorem compares random scan to a lazy version of the systematic scan and shows that and obtains bounds in terms of various other quantities, like the minimum probability, or the minimum holding probability.

MCMC is at the heart of many applications of modern machine learning and statistics. It is thus important to understand the computational and theoretical performance under various conditions. The present paper focused on examining systematic Gibbs sampling in comparison to random scan Gibbs. They do so first though the construction of several examples which challenge the dominant intuitions about mixing times, and develop theoretical bounds which are much wider than previously conjectured.

In this paper the authors experiment with 10,000 image classes based on ImageNet. As ImageNet is based on Wordnet, they have a semantic tree of the categories.

It should be noted that this paper is from 2010. Hence before AlexNet. They don't use CNNs in this paper.

## Key findings

* A relationship between visual similarity and semantic similarity exists
* Classification can be improved by exploiting semantic hierarchy
* Computational difficulties with 10,000 classes
* More classes -> lower mean accuracy

## See also

* [What makes ImageNet good for transfer learning?](https://arxiv.org/abs/1608.08614) ([slides](https://www.dropbox.com/s/vfmncjnyh57glkc/NIPS_LSCVS_ImageNet%20Analysis.pdf?dl=0))

Summary from [reddit](https://www.reddit.com/r/MachineLearning/comments/623oq4/r_early_stopping_without_a_validation_set/dfjzwqq/):

We want to minimize the expected risk (loss) but that's a mean over the real distribution of the data, which we don't know. We approximate that by using a finite dataset and try to minimize the empirical risk instead.
The gradients for the empirical risk are an approximation to the gradients for the expected risk.
The idea is that the real gradients contain just information whereas the approximated gradients contain information + noise. The noise results from using a finite dataset to approximate the real distribution of the data.
By computing local statistics about the gradients, the authors are able to determine when the gradients have no information about the expected risk anymore and what's left is just noise. If we keep optimizing we're going to overfit.

#### Summary:
The main point of the paper is to show the automatic tranformation process of a java project to run on AWS lambda. For the transformation process a self developed tool named Podilzer is used to perform the tests. Further a comparison of the execution times and cost factors is made, to show if it's valuable to run Java functions on AWS lambda.

#### Good points:
The pipeline process is well described and good understandable. The developed tool called Podilizer implements this pipeline process and is also as open source project available. The experiments are also available on the openscience platform including scripts and code, this grantees repeatability of the conducted tests. 

#### Major comments:
One of the main problems with FaaS in general is preserving the state of an application. This challenge is described well. I wished to get a bit more insight what other problematic functions exist and what the approach of transforming those would be. 
The java projects which were used to conduct the results are available but not described in the paper. Therefore the transformation times are difficult to assess, before a study of the projects itself. Further  the execution performance of the same applications were compared locally and on different cloud offerings. On AWS Lambda the execution performance is significantly higher then on all the other platforms. Probably the times also include network latency, therefore it would be also interesting to see the actual execution times on Lambda itself. 

#### Minor comments:
Generally good grammar, some minor typos. 

#### Recommendations:
Describe the problems of transforming existing functions in more extend. Include also the “real” execution times of the AWS Lambda functions, to have a better comparison between the run times. 
Finally proofread and publish after corrections have been made

This paper describes common pitfalls when classifiers are compared and recommends McNemars test

## Notes

* t-test is simply the wrong test for such an experimental design


## See also

* Prechelt "A quantitative study of experimental evaluations of neural network algorithms" - most of 200 evaluated paper had flaws
* Wolpert "On the connection between in-sample testing and generalization error" - No classifier is always better than another one.
* Diettrich: [Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms](http://www.shortscience.org/paper?bibtexKey=journals/neco/Dietterich98)
* Demsar: [Statistical Comparisons of Classifiers over Multiple Data Sets](http://www.shortscience.org/paper?bibtexKey=demvsar2006statistical)