Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper looks at the problem of optimizing hyperparameters under the assumption that the unknown function can be approximated by a sparse and low degree polynomial in the Fourier basis. The main result is that the approximate minimization can be performed over the boolean hypercube where the number of evaluations is linear in the sparsity parameter. 

In the presented experiments, the new spectral method outperforms the tool based on the Bayesian optimization, technique based on MAB and random search. Their result also has an application in learning decision trees where it significantly improves the sample complexity bound.

The main theoretical result, i.e., the improvement in the sample complexity when learning decision trees, looks very strong. However, I find this result to be out of the context with the main theme of the paper. 

I find it highly unlikely that a person interested in using Harmonica to find the right hyperparamters for her deep network would also be interested in provable learning of decision trees in quasi-polynomial time along with a polynomial sample complexity. Also the theoretical results are developed for Harmonica-1 while Harmonica-q is the main method used in the experiments.

When it comes to the experiments only one real-world experiment is present. It is hard to conclude which method is better based on a single real-world experiment. Moreover, the plots are not very intuitive, i.e., one would expect that Random Search takes the smallest amount of time. I guess the authors are plotting the running time that also includes the time needed to evaluate different configurations. If this is the case, some configurations could easily require more time to evaluate than the others. It would be useful to plot the total number of function evaluations for each of the methods next to the presented plots.

It is not clear what is the stopping criterion for each of the methods used in the experiments. One weakness of Harmonica is that it has 6 hyperparameters itself to be tuned. It would be great to see how Harmonica compares with some of the High-dimensional Bayesian optimization methods. 

Few more questions:

Which problem does Harmonica-q solves that is present in Harmonica-1, and what is the intuition behind the fact that it achieves better empirical results?

How do you find best t minimizers of g_i in line 4 of Algorithm 3?

review_title: The paper contains a strong theoretical result that is a bit out of context with the main theme of the paper. The algorithm presented shows promising results for optimizing hyperparameters when the number of hyperparameters > 6. 

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: The paper is about hyperparameter optimization, which is an important problem in deep learning due to the large number of hyperparameters in contemporary model architectures and optimization algorithms.

At a high-level, hyperparameter optimization (for the challenging case of discrete variables) can be seen as a black-box optimization problem where we have only access to a function evaluation oracle (but no gradients etc.). In the entirely unstructured case, there are strong lower bounds with an exponential dependence on the number of hyperparameters. In order to sidestep these impossibility results, the current paper assumes structure in the unknown function mapping hyperparameters to classification accuracy. In particular, the authors assume that the function admits a representation as a sparse and low-degree polynomial. While the authors do not empirically validate whether this is a good model of the unknown function, it appears to be a reasonable assumption (the authors *do* empirically validate their overall approach).

Based on the sparse and low-degree assumption, the paper introduces a new algorithm (called Harmonica) for hyperparameter optimization. The main idea is to leverage results from compressed sensing in order to recover the sparse and low-degree function from a small number of measurements (i.e., function evaluations). The authors derive relevant sample complexity results for their approach. Moreover, the method also yields new algorithms for learning decision trees.

In addition to the theoretical results , the authors conduct a detailed study of their algorithm on CIFAR10. They compare to relevant recent work in hyperparameter optimization (Bayesian optimization, random search, bandit algorithms) and find that their method significantly improves over prior work. The best parameters found by Harmonica improve over the hand-tuned results for their "base architecture" (ResNets).

Overall, I find the main idea of the paper very interesting and well executed, both on the theoretical and empirical side. Hence I strongly recommend accepting this paper.


Small comments and questions:

1. It would be interesting to see how close the hyperparameter function is to a low-degree and sparse polynomial (e.g., MSE of the best fit).

2. A comparison without dummy parameters would be interesting to investigate the performance differences between the algorithms in a lower-dimensional problem.

3. The current paper does not mention the related work on hyperparameter optimization using reinforcement learning techniques (e.g., Zoph & Le, ICLR 2017). While it might be hard to compare to this approach directly in experiments, it would still be good to mention this work and discuss how it relates to the current paper.

4. Did the authors tune the hyperparameters directly using the CIFAR10 test accuracy? Would it make sense to use a slightly smaller training set and to hold out say 5k images for hyperparameter evaluation before making the final accuracy evaluation on the test set? The current approach could be prone to overfitting.

5. While random search does not explicitly exploit any structure in the unknown function, it can still implicitly utilize smoothness or other benign properties of the hyperparameter space. It might be worth adding this in the discussion of the related work.

6. Algorithm 1: Why is the argmin for g_i  (what does the index i refer to)?

7. Why does PSR truncate the indices in alpha? At least in "standard" compressed sensing, the Lasso also has recovery guarantees without truncation (and empirically works sometimes better without).

9. Definition 3: Should C be a class of functions mapping {-1, 1}^n to R?  (Note the superscript.)

10. On Page 3 we assume that K = 1, but Theorem 6 still maintains a dependence on K. It might be cleaner to either treat the general K case throughout, or state the theorem for K = 1.

11. On CIFAR10, the best hyperparameters do not improve over the state of the art with other models (e.g., a wide ResNet). It could be interesting to run Harmonica in the regime where it might improve over the best known models for CIFAR10.

12. Similarly, it would be interesting to see whether the hyperparameters identified by Harmonica carry over to give better performance on ImageNet. The authors claim in C.3 that the hyperparameters identified by Harmonica generalize from small networks to large networks. Testing whether the hyperparameters also generalize from a smaller to a larger dataset would be relevant as well.
review_title: Good paper on hyperparameter optimization using techniques from compressed sensing

final_score: rating: 6: Marginally above acceptance threshold
review_content: - algorithm 1 has a lot of problem specific hyperparametes that may be difficult to get right. Not clear how important they are
- they analyze the simpler (analytically and likely computationally) Boolean hyperparameter case (each hyperparameter is binary). Not a realistic setting. In their experiments they use these binary parameter spaces so I'm not sure how much I buy that it is straightforward to use continuous valued polynomials. 
- interesting idea but I think it's more theoretical than practical. Feels like a hammer in need of a nail. 
review_title: Interesting theoretical ideas, but unclear how practical the proposed approach really is

Meta-review: This paper introduces an algorithm for optimization of discrete hyperparameters based on compressed sensing, and compares against standard gradient-free optimization approaches.

As the reviewers point out, the provable guarantees (as is usually the case) don't quite make it to the main results section, but are still refreshing to see in hyperparameter optimization.

The method itself is relatively simple compared to full-featured Bayesopt (spearmint), although not as widely applicable.

Decision: Accept (Poster)