Venue: ICLR 2017 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The idea of universality that is independent of input distribution and dimension, depending only on the algorithm is an appealing one. However, as an empirical study, this paper comes up somewhat short:

1. Exactly one algorithm is shown for the deep learning example. It would have been more convincing to compare distributions with one or more algorithms. 

2. The definition (1),  and much of the work of Section 2.1 seems to have already been covered in Deift (2014), Section 1.3. In that paper, a number of different algorithms for the solution of linear systems are considered, and then the concept of universality becomes more plausible. I do not see enough of such algorithmic comparisons in this paper (same problem setup, different algorithms).

3.  It seems to me that what practitioners might care about in practice are both the mean and variance in running times; these quantities are buried in (1). So I question how useful the distribution itself might be for algorithm tuning. 

At the least, many more empirical comparisons should be provided to convince me that the universality holds across a broad range of algorithms.
review_title: Hard to see universality yet.

final_score: rating: 2: Strong rejection
review_content: Summary


For several algorithms, previous research has shown that the halting time follows a two-parameter distribution (the so-called universal property investigated by the authors). In this work, the authors extend the investigation to new algorithms (spin-glass, gradient descent in deep learning).

An algorithm is considered to satisfy the universality property when the centered/scaled halting time fluctuations (empirical distribution of halting times) depend on the algorithm but do not depend on the target accuracy epsilon, an intrinsic measure of dimension N, the probability distribution/random ensemble. (This is clear from Eq 1 where on the left the empirical halting time distribution depends on epsilon, N, A, E and on the right, the approximation only depends on the algorithm)

The authors argue that empirically, the universal property is observed when both algorithms (spin glass and deep learning) perform well and that it is not observed when they do not perform well.

A moment-based indicator is introduced to assess whether universality is observed.


Review


This paper presents several problems.



page 2: “[…] for sufficiently large N and eps = eps(N)”

The dependence of epsilon on N is troubling.



page 3: “Universality is a measure of stability in an algorithm […] For example […] halting time for the power method […] has infinite expectation and hence this type of universality is *not* present. One could use this to conclude that the power method is naive. Therefore the presence of universality is a desirable feature of a numerical method”

No. An algorithm is naive if there are better ways to answer the problem. One could not conclude from a halting time with infinite expectation (e.g. solving a problem extremely quickly 99% of the time, and looping forever in 1% of cases) or infinite variance, that the algorithm is naive. 
Moreover the universal property is more restrictive than having a finite halting time expectation. Even if in many specific cases, having a finite halting time expectation is a desirable property, showing that the presence of universality is desirable would require a demonstration that the other more restrictive aspects are also desirable. 
Also, the paragraph only concerns one algorithm. why would the conclusions generalise to all numerical methods ? 
Even if the universality property is arguably desirable (i.e. event if the conclusion of this paragraph is assumed correct), the paragraph does not support the given conclusion.



Comparing Eq 1 and figures 2,3,4,5 
From Eq 1, universality means that the centered/scaled halting time fluctuations (which depend on A, epsilon, N, E) can be approximated by a distribution that only depends on A (not on epsilon, N, E) but in the experiments only E varies (figures 2,3,4,5). The validity of the approximation with varying epsilon or N is never tested



The ensembles/distributions parameter E (on which halting fluctuations should not depend) and the algorithm A (on which halting fluctuations are allowed to depend) are not well defined, especially w.r.t. the common use of the words. In the optimisation setting we are told that the functional form of the landscape function is part of A (in answer to the question of a reviewer) but what is part of the functional form ? what about computations where the landscape has no known functional form (black box) ?



The conclusion claims that the paper “attempts to exhibit cases” where one can answer 5 questions in a robust and quantitative way.

Question 1: “What are the conditions on the ensembles and the model that lead to such universality ?” The only quantitative way would be to use the moments based indicator however there is only one example of universality not being observed which concerns only one algorithm (conjugate gradient) and one type of failure (when M = N). This does not demonstrate robustness of the method.

Question 2: “What constitutes a good set of hyper parameters for a given algorithm ?”
The proposed way to choose would be to test whether universality is observed. If it is then the hyper parameters are good, if not the hyper parameters are bad. The correspondance between bad hyper-parameters and observing no universality concerns only one algorithm and one type of failure. Other algorithms may fail in the universal regime or perform well in the non universal regime. The paper does not show how to answer this question in a robust way.

Question 3: "How can we go beyond inspection when tuning a system ? "
The question is too vague and general and there is probably no robust and quantitative way to answer it at all.

Question 4: "How can we infer if an algorithm is a good match to the system at hand ? "
The paper fails to demonstrate convincingly that universality is either a good or robust way to approach the very few studied algorithms. The suggested generalisation to all systems and algorithms is extremely far fetched.

Question 5: "What is the connection between the universal regime and the structure of the landscape ?"
 Same as before, the question is extremely vague and cannot be answered in a robust or quantitative way at all. The fact that what corresponds to A and what corresponds to E is not clear does not help.


In the conclusion it is written that the paper validates the claim that universality is present in all or nearly all sensible computation. It does not. The paper does not properly test whether universality is present (only 1 parameter in 3 that should not vary is tested). The paper does not properly test whether universality is lost when the computation is no longer sensible (only one failure case tested). Finally the experiments do not apply to all or nearly all computations but only to very few  specific algorithms.

review_title: Unusual research. Unsound methodology. conclusions are not supported by the content.

final_score: rating: null
review_content: In Figure 1, what does the x-axis represent? The term "search time fluctuations" is a little confusing. 
review_title: Figure 1

final_score: rating: null
review_content: What you do in the paper is quite clear however i do not fully understand your motivations. In a spirit of fairness, I prefer to candidly ask difficult questions now that you have the time to answer them.

Why should I care about the distribution halting time and the universal property ? How does this relate (in a useful way) to deep networks, learning representations ?

In the conclusion you write:

"What constitutes a good set of hyperparameters for a given algorithm? [...] How can we infer if an algorithm is a good match to the system at hand? [NDR: two questions I relate to]
You then write:
"This research attempts to exhibit cases where one can extract answers to these questions in a robust and quantitative way"
However I do not find where this paper answers (or attempts to answer) these questions. Could you point me to the right pages/paragraphs ?
review_title: Why

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors explore whether the halting time distributions for various algorithms in various settings exhibit "universality", i.e. after rescaling to zero mean and unit variance, the distribution does not depend on stopping parameter, dimensionality and ensemble.

The idea of the described universality is very interesting. However I see several shortcomings in the paper:

In order to be of practical relevance, the actual stopping time might be more relevant than the scaled one. The discussion of exponential tailed halting time distributions is a good start, but I am not sure how often this might be actually helpful. Still, the findings in the paper might be interesting from a theoretical point of view.

Especially for ICLR, I think it would have been more interesting to look into comparisons between stochastic gradient descent, momentum, ADAM etc on different deep learning architectures. Over which of those parameters does universality hold?. How can different initializations influence the halting time distribution? I would expect a sensible initialization to cut of part of the right tail of the distribution.

Additionally, I found the paper quite hard to read. Here are some clarity issues:

- abstract: "even when the input is changed drastically": From the abstract I'm not sure what "input" refers to, here
- I. Introduction: "where the stopping condition is, essentially, the time to find the minimum": this doesn't seem to make sense, a condition is not a time. I guess the authors wanted to say that the stopping condition is that the minimum has been reached?
- I.1 the notions of dimension N, epsilon and ensemble E are introduced without any clarification what they are. From the later parts of the paper I got some ideas and examples, but here it is very hard to understand what these parameters should be (just some examples would be already helpful)
- I.3 "We use x^\ell for \ell \in Z=\{1, \dots, S\} where Z is a random sample from of training samples" This formulation doesn't make sense. Either Z is a random sample, or Z={1, ..., S}.
- II.1 it took me a long time to find the meaning of M. As this parameter seems to be crucial for universality in this case, it would be very helpful to point out more explicitly what it refers to.

review_title: interesting idea, shortcomings in evaluation and clarity

Meta-review: My overall conclusion is that the paper needs more work to be sufficiently convincing. I think the reviews are sufficiently careful. My recommendation is based on the fact that none of the reviewers supports acceptance.
Decision: Reject