PaperlayerView exact revision on arXiv

Source-linked AI summary

Hyperparameter Optimization: A Spectral Approach

Elad Hazan, Adam Klivans, Yang Yuan

arXiv:1706.00764v4cs.LGcs.AImath.OCstat.ML

TL;DR

Hyperparameter optimization must search a rapidly growing space of settings, and model evaluations can be costly. The paper applies sparse recovery in an orthogonal-polynomial basis to this problem. It gives noiseless and noisy recovery guarantees and applies the noisy result to decision-tree learning.

  • Problem

    As the number of hyperparameters grows, grid search becomes quickly infeasible, while model evaluations such as neural-network training are expensive.

    Source: §1 · p. 2

  • Method

    Harmonica extends sparse recovery to an orthogonal polynomial basis and adds an optimization step.

    Source: §3 · p. 6

  • Results

    Noiseless recovery uses T=˜O(K^2s · d log n) samples, while noisy recovery returns an ε-close function using T=˜O(K^2s^2/ε · d log n) samples.

    Source: §3 · pp. 7–8

  • Takeaways & Limitations

    The noisy recovery result supports learning decision trees by approximating them in the parity basis and recovering a function whose sign agrees with the target with error at most ε.

    Source: §3.1 · p. 10

    Noisy recovery guarantees a hypothesis close to the objective but does not guarantee recovery of its global optimum, since one noisy point can change the optimum.

    Source: §3 · p. 9

Abstract

from arXiv · show

We give a simple, fast algorithm for hyperparameter optimization inspired by techniques from the analysis of Boolean functions. We focus on the high-dimensional regime where the canonical example is training a neural network with a large number of hyperparameters. The algorithm --- an iterative application of compressed sensing techniques for orthogonal polynomials --- requires only uniform sampling of the hyperparameters and is thus easily parallelizable. Experiments for training deep neural networks on Cifar-10 show that compared to state-of-the-art tools (e.g., Hyperband and Spearmint), our algorithm finds significantly improved solutions, in some cases better than what is attainable by hand-tuning. In terms of overall running time (i.e., time required to sample various settings of hyperparameters plus additional computation time), we are at least an order of magnitude faster than Hyperband and Bayesian Optimization. We also outperform Random Search 8x. Additionally, our method comes with provable guarantees and yields the first improvements on the sample complexity of learning decision trees in over two decades. In particular, we obtain the first quasi-polynomial time algorithm for learning noisy decision trees with polynomial sample complexity.

1 Introduction

Hyperparameter tuning becomes infeasible with grid search as the number of parameters grows, while existing approaches exploit either structure or parallelism. The paper introduces Harmonica, a spectral approach with theoretical and learning-theoretic guarantees, and reports improvements in deep-network experiments.

1 Introduction

  • As hyperparameters multiply, grid search becomes exponentially infeasible, motivating automatic tuning for costly model choices such as neural-network architectures and optimization settings.The introduction frames evaluations as expensive and parallel testing as possible, while requiring structure in the objective.Source: §1 · p. 2

1.2 Previous work

  • Prior HPO methods either rely on a prior over the loss structure, as Bayesian optimization does, or exploit parallelism without exploiting objective structure, as random search and bandit methods do.The introduction also notes that grid search is prohibitive as the number of hyperparameters grows.Source: §1 · p. 2, §1.2 · p. 3

1.1 Our contribution

  • Harmonica assumes the objective is approximated by a sparse, low-degree Fourier polynomial, and uses this structure to obtain approximate minimization guarantees with evaluations linear in sparsity.The paper says this structure intuitively corresponds to approximation by a decision tree and that evaluations can be carried out in parallel.Source: §1.1 · pp. 2–3
  • The method improves sample-complexity bounds for learning noisy size-s decision trees under the uniform distribution, with a bound of ˜O(s2/ε · log n) and the best known quasipolynomial running-time bound.The cited prior bound is nO(log(s/ε)); the supplied text describes the new dependence as quadratic in tree size.Source: §1.1 · p. 3
  • The paper reports significant improvements in accuracy, sample complexity, and running time for deep-neural-network training versus Bayesian optimization, bandit methods, and Random Search.Simulations at higher hyperparameter counts show several orders of magnitude of speedup versus Bayesian optimization.Source: §1.1 · p. 3

1.2 Previous work

  • Extending compressed-sensing methods to approximately sparse, approximately low-degree Boolean functions yields a decision-tree learner with polynomial sample complexity under adversarial noise and optimal dependence on ε.The extension builds on Stobbe and Krause.Source: §1.2 · p. 4

2 Setup and definitions

The setup treats hyperparameter optimization as minimizing a costly discrete objective, with parallel evaluations available. It introduces Fourier representations and approximate sparsity, then relates recovery in that basis to compressed sensing.

2 Setup and definitions

  • Hyperparameter optimization is modeled as minimizing a discrete real-valued function, with evaluations costly because they involve training but parallelizable across settings.The function is defined over {−1, 1}^n for simplicity, though arbitrary inputs can be handled.Source: §2 · p. 4

2.1 Basics of Fourier analysis

  • The paper uses the parity functions as its Fourier basis under the uniform distribution, while noting that the results extend to other orthogonal polynomial families and product measures.Hermite polynomials with a multivariate spherical Gaussian measure are given as an example for continuous hyperparameters.Source: §2.1 · p. 5
  • The setup defines approximate sparsity through bounded L1 norm and low-degree concentration; bounded-L1 classes include functions beyond exactly sparse ones.For example, the Boolean AND function has L1 norm at most 1 but is not sparse.Source: §2.1 · p. 5

2.2 Compressed sensing and sparse recovery

  • Compressed sensing recovers sparse coefficients from measurements, and the paper uses the extension for measurements drawn from a random orthonormal family.The cited recovery result gives a sample bound of m ≥ CK^2 log K · s log^3 s · log^2 N · log(1/δ).Source: §2.2 · p. 6

3 Basic Algorithm and Main Theoretical Results

Harmonica extends sparse recovery to orthogonal polynomial bases and adds an optimization step. Its guarantees cover noisy function approximation and decision-tree learning, while exact recovery supports finding a minimizer under stricter conditions.

3 Basic Algorithm and Main Theoretical Results

  • Harmonica extends sparse recovery to orthogonal polynomial bases and combines it with an optimization step.The paper also develops a noisy recovery procedure used in the later algorithm and decision-tree result.Source: §3 · pp. 6, 8
  • For approximately sparse, low-degree functions, noisy recovery achieves error ε in time O(n^d) with sample complexity ˜O(K^2s^2/ε · d log n).The guarantee assumes a K-bounded orthonormal polynomial basis and an (ε/4, d, s)-bounded target.Source: §3 · p. 8
  • Exact recovery of a sparse polynomial lets the algorithm find its minimizer, but noisy recovery alone does not guarantee recovery of the global optimum.Even one noisy point can change the optimum.Source: §3 · p. 9

3.1 Application: Learning Decision Trees in Quasi-polynomial Time and Polynomial Sample Complexity

  • Decision trees of size s are learnable under the uniform distribution in time nO(log(s/ε)) with sample complexity ˜O(s^2/ε · log n), including tolerance to bounded arbitrary noise.For noise vector v with ∥v∥2 ≤ √(γm), the output squared error is at most ε + O(γ).Source: §3.1 · p. 10
  • For real-valued size-s decision trees bounded by B, Harmonica uses ˜O(B^2s^2/ε · log n) samples and tolerates noise, versus ˜O(B^4s^2/ε^2 · log n) for the low-degree algorithm without noise tolerance.The passage attributes the improvement in ε-dependence to the random orthonormal family’s RIP property.Source: §3.1 · p. 10

4 Harmonica: The Full Algorithm

The full Harmonica algorithm repeatedly estimates influential hyperparameters and their preferred values, then switches to a base optimizer when the search space is small. Its stated attributes include sparse-function scalability, feature ranking, and fast computation.

4 Harmonica: The Full Algorithm

  • Harmonica iteratively applies polynomial sparse recovery to estimate influential hyperparameters and their optimal values, then uses a base optimizer once the search space is small enough.The described base optimizer is Successive Halving or Random Search.Source: §4 · p. 10
  • Averaging several strong minimizers at each stage addresses the fact that a multivariate polynomial’s minimizing assignments may form a highly non-convex set with many distinct points.The restriction size t serves as a tie-breaking rule for selecting minimizers.Source: §4 · pp. 10–11

4.1 Algorithm attributes and heuristics

  • If the hidden function is s-sparse, Harmonica uses ˜O(s log s) samples; if it is approximable by an s-sparse function at each of q stages, it uses ˜O(qs log s).The authors describe stagewise approximate sparsity as an empirically reasonable assumption for deep-neural-network hyperparameter tuning.Source: §4.1 · p. 11
  • Each stage solves a well-studied convex Lasso problem with fast implementations, whereas Bayesian optimization’s running time is cubic in the number of evaluations.Harmonica’s randomly chosen evaluations can also be run in parallel, like Hyperband, Successive Halving, and Random Search.Source: §4.1 · p. 11
  • Harmonica extracts influential features with weights at each stage, automatically sorting features by importance.The passage points to Appendix A.2 for details.Source: §4.1 · p. 12

5 Experiments with training deep networks

The experiments evaluate Harmonica on deep-network hyperparameter tuning and synthetic functions, comparing algorithm variants and examining feature selection and parameter stability. The deep-network study uses a residual network on Cifar-10 with 39 binary hyperparameters and 21 dummy variables.

5.1 Performance

  • Harmonica-1 uses less than 1/7 the time of Hyperband and 1/8 the time of Random Search while getting better results; Harmonica-2 finds better results comparable with Spearmint at 4.5× running time.The comparison reports distributions of best results and running time.Source: Figure 2 · p. 13, §5.1 · p. 13
  • Harmonica-3 obtains 6.58% test error versus the best hand-tuning rate of 6.97% reported in.It uses 6.1 GPU days, under half a day in the authors’ 20-GPU environment.Source: §5.1 · p. 13
  • Harmonica-1’s noiseless and noisy recovery guarantees are validated experimentally.Source: §5.1 · p. 13

5.3 Hyperparameters for Harmonica

  • The general HPO search is reduced to six Harmonica hyperparameters, and the algorithm is reported robust to their settings, including some left untuned.Source: §5.3 · pp. 13–14
  • Most tested Harmonica variants outperform SH while using less running time; longer runs yield more stable test-error solutions with less variance.The variants vary the number of stages, base optimizer, and SH run time.Source: Figure 3 · p. 14, §5.3 · p. 14
  • Within stable Lasso regularization and sample-count ranges, the top five features and weight signs remain unchanged; degree 3 finds no important higher-degree features, and Lasso takes under five minutes.Source: §5.3 · p. 14

5.2 Average Test Error For Each Stage

  • After stage 1 selects five features, average test error over 300 samples falls from 60.16 to 33.3; improvements become less significant by stage 3.The measurements use an 8-layer network with 30 training epochs after each stage.Source: §5.2 · p. 13, Figure 4 · p. 15

5.4 Experiments with Synthetic functions

  • On a synthetic hierarchically bounded function, Harmonica’s estimation error is proportional to noise level and it is several magnitudes faster than Spearmint.The experiment uses 100 samples, five features per stage, three stages, and degree-3 features; Spearmint is plotted only for n = 60, where 500 samples take over one day.Source: Figure 6 · p. 15, Figure 5 · p. 15, §5.4 · p. 15

A.1 Options

Table 2 lists the 60 options used in Section 5 and describes binary encodings for parameters with more than two choices.

A.1 Options

  • The 60-option table covers the hyperparameter choices used in Section 5; parameters with k choices use log k binary variables, including four initialization choices.Source: Table 2 · p. 20, §A.1 · p. 21

A.2 Importance features

Harmonica ranks hyperparameter features by importance, identifies options that match common practice, and excludes dummy or irrelevant variables.

A.2 Importance features

  • Its selected options include Batch Norm, ReLU, Adam, and momentum, and most choices match what people do in practice.The ranked options also cover learning rate, ResBlock activations, weight decay, and batch-normalization tuning.Source: §A.2 · p. 21
  • Harmonica ranks Batch Norm first and ReLU second; Dropout contributes little when Batch Norm is present, matching observations in.The selected options also include Adam, momentum, and conditional weight-decay choices.Source: §A.2 · p. 21
  • Harmonica never selects any of the 21/60 dummy variables or irrelevant variables such as cudnn, backend, and nthreads.The cited passage says these irrelevant variables do not affect test error.Source: §A.2 · p. 21

A.3 Generalizing from small networks to big networks

Harmonica extracts important features on a small network and uses them to fine-tune a larger one; the section contrasts this transfer with other search methods.

A.3 Generalizing from small networks to big networks

  • Harmonica first extracts important features on a small network, then uses them to fine-tune a larger network.The supplied passage ends mid-sentence after this workflow description.Source: §A.3 · p. 21
  • Spearmint cannot use small-network information to update its prior for a large network without modification because their optimization spaces differ.The passage describes the limitation for Bayesian optimization techniques.Source: §A.3 · p. 22
  • Important features found by Harmonica seem to generalize from small to large networks, unlike good random-search configurations; this appears to be a distinctive feature of Harmonica.The comparison with random search is based on simulation.Source: §A.3 · pp. 22–23
  • 11.1% was the best test error after 27 GPU days evaluating 100 configurations transferred from an 8-layer to a 56-layer Cifar-10 network, worse than purely random search.The 100 configurations comprised 10 top configurations from random sampling and 90 local perturbations.Source: §A.3 · p. 22
Loading 1706.00764v4…