random matrix theory

Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis

  • Courtney Paquette
  • Elliot Paquette
  • Bart van Merrienboer
  • Fabian Pedregosa
    • Categories Global Optimization Tags , ,

    Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model. However, we show … Read more

    A dimensionality reduction technique for unconstrained global optimization of functions with low effective dimensionality

  • Coralia Cartis
  • Adilet Otemissov
    • Categories Global Optimization, Stochastic Approaches Tags , , ,

    We investigate the unconstrained global optimization of functions with low effective dimensionality, that are constant along certain (unknown) linear subspaces. Extending the technique of random subspace embeddings in [Wang et al., Bayesian optimization in a billion dimensions via random embeddings. JAIR, 55(1): 361–387, 2016], we study a generic Random Embeddings for Global Optimization (REGO) framework … Read more