PaperlayerView exact revision on arXiv

Source-linked AI summary

Global optimization of Lipschitz functions

Cédric Malherbe, Nicolas Vayatis

arXiv:1703.02628v3stat.ML

TL;DR

Costly evaluations make sequential optimization of unknown functions important, but convergence guarantees for functions specified only by global smoothness had not been considered. The paper develops LIPO for a known Lipschitz constant and AdaLIPO for estimating it, and reports faster rates and empirical performance against existing methods.

  • Problem

    Because evaluations may require costly simulations or cross-validation, the paper asks how to optimize unknown, potentially nonconvex functions with few sequential evaluations when only global smoothness is specified.

    Source: §1 · pp. 1–2

  • Method

    It establishes generic consistency and minimax results, then develops LIPO for a known Lipschitz constant and AdaLIPO to estimate the constant during optimization.

    Source: §1 · p. 2, §3.1 · p. 5, §4.1 · p. 11

  • Results

    The paper reports faster rates than local-smoothness methods and theoretical and empirical results for AdaLIPO, assessed on synthetic and real problems against state-of-the-art methods.

    Source: §1 · p. 2, §4.2 · p. 14, §6 · p. 18

  • Takeaways & Limitations

    AdaLIPO estimates the Lipschitz constant during optimization, extending the approach to settings where that constant is not known beforehand.

    Source: §4.1 · p. 11, §6 · p. 18

    The integrated minimax bound shows no improvement over PRS and cannot be significantly improved without an additional assumption.

    Source: §3.2 · p. 8

Abstract

from arXiv · show

The goal of the paper is to design sequential strategies which lead to efficient optimization of an unknown function under the only assumption that it has a finite Lipschitz constant. We first identify sufficient conditions for the consistency of generic sequential algorithms and formulate the expected minimax rate for their performance. We introduce and analyze a first algorithm called LIPO which assumes the Lipschitz constant to be known. Consistency, minimax rates for LIPO are proved, as well as fast rates under an additional H\"older like condition. An adaptive version of LIPO is also introduced for the more realistic setup where the Lipschitz constant is unknown and has to be estimated along with the optimization. Similar theoretical guarantees are shown to hold for the adaptive LIPO algorithm and a numerical assessment is provided at the end of the paper to illustrate the potential of this strategy with respect to state-of-the-art methods over typical benchmark problems for global optimization.

1. Introduction

The paper studies sequential optimization of unknown functions when evaluations are costly and only global Lipschitz smoothness is assumed. It asks what performance is achievable and introduces algorithms that exploit this smoothness, reporting faster rates than methods using only local smoothness.

1. Introduction

  • Global optimization seeks to optimize an unknown, potentially nonconvex function with few evaluations, which may be costly and require sequential exploration.Source: §1 · p. 1
  • The paper introduces two global-smoothness-based algorithms and reports faster convergence rates than previously known methods exploiting only local smoothness.It also reports good performance on typical optimization benchmarks.Source: §1 · p. 2
  • The paper asks what limitations and best performance apply to algorithms optimizing the class of Lipschitz functions.Source: §1 · p. 2
  • Convergence properties had been developed for methods under local smoothness, while the paper identifies a gap for functions specified only by global smoothness.Source: §1 · p. 2

2. Setup and preliminary results

The section formalizes sequential optimization of a noiseless, finite-Lipschitz function using few evaluations, then establishes coverage and minimax benchmarks for such algorithms. It previews LIPO with known Lipschitz constant and AdaLIPO without it.

2.1 Setup and notations

  • With a finite Lipschitz constant and noiseless evaluations, the goal is to find a maximum using as few sequential evaluations as possible.Performance is measured by the gap between the true maximum and the best value observed so far.Source: §2.1 · pp. 2–3

2.2 Preliminary results

  • Sequential algorithms choose each evaluation point from a distribution based on prior points and function values; deterministic methods are included as degenerate distributions.Consistency means asymptotically reaching the maximum over the function class under study.Source: §2.2 · pp. 3–4
  • For Lipschitz functions, consistency requires covering the whole input space, regardless of observed function values.The section presents a necessary-and-sufficient consistency condition and identifies this coverage consequence.Source: §2.2 · p. 4
  • No algorithm has a uniform finite-time loss bound over Lipschitz functions with unrestricted constants; fixing the constant permits minimax bounds.The unrestricted class includes functions with finite but arbitrarily large variations.Source: §2.2 · pp. 4–5
  • The minimax convergence rate is Θ(n^-1/d), and an optimal O(n^-1/d) covering rate suffices to achieve it.The lower-bound construction uses spikes that are almost constant elsewhere, which the paper says have limited practical interest.Source: §2.2 · p. 5
  • The section previews LIPO, which assumes a known Lipschitz constant and achieves minimax efficiency plus exponentially decreasing rates on a large function subset, and AdaLIPO, which does not require that constant and has comparable performance.The comparison for AdaLIPO is to performance when the constant is known.Source: §2.2 · p. 5

3. Optimization with fixed Lipschitz constant

With the Lipschitz constant known, LIPO samples uniformly and evaluates only points whose upper bound could match the best value observed so far. The analysis establishes consistency and minimax performance, with faster rates under an additional condition on decay near the maximum.

3.1 The LIPO Algorithm

  • Given k, LIPO samples uniformly and evaluates a point only when its Lipschitz upper bound can match the best observed value, retaining possible maximizers.Figure 2 illustrates the upper bound and the set of points satisfying this decision rule.Source: §3.1 · pp. 5–6, Figure 2 · p. 7

3.2 Convergence analysis

  • LIPO is consistent for k-Lipschitz functions and stochastically dominates Pure Random Search; its minimax bound does not improve on PRS without additional assumptions.The paper also gives a finite-time upper bound and shows that this minimax rate cannot be significantly improved over the Lipschitz class alone.Source: §3.2 · pp. 7–8
  • Under Condition 1, which describes decay around the maximum, LIPO has fast rates; for Lipschitz functions this local one-sided Hölder condition requires κ ≥ 1.The theorem states the fast-rate result for κ ≥ 1 and cκ > 0.Source: §3.2 · p. 8

3.3 Examples

  • The sphere satisfies Condition 1 with κ = 1 and cκ = 1; LIPO has exponential decay for any k ≥ 1, while nonzero linear weights satisfy Condition 1 with κ = 1.For nonzero linear weights, cκ = mini=1...d |wi|; LIPO with any k ≥ ∥w∥2 provides a decay of order O∗.Source: §3.3 · p. 9

3.4 Comparison with existing works

  • LIPO combines space-filling and exploitation; its bounds match DOO on Fκ and improve uniformly on F′κ for κ > 1, while a smaller local constant can favor DOO when κ = 1.The comparison contrasts LIPO's global smoothness information with DOO's local smoothness assumptions.Source: §3.4 · p. 10

4. Optimization with unknown Lipschitz constant

AdaLIPO extends LIPO to settings with an unknown Lipschitz constant, alternating exploration with exploitation based on an estimate. The analysis establishes consistency and convergence guarantees, then compares its rates with methods using local smoothness.

4.1 The adaptive algorithm

  • AdaLIPO alternates uniform exploration, chosen with probability p, and exploitation by LIPO using the smallest current mesh constant whose candidate functions probably include f.The algorithm starts its Lipschitz-constant estimate at zero and updates it after each evaluation.Source: §4.1 · p. 11

4.2 Convergence analysis

  • The finite-time estimate can recover a small subset of Lipschitz functions containing f; fast rates similar to known-constant LIPO follow after f enters the estimated class.The stated bound’s constant and convergence rate vary inversely with the exploration parameter and the density of the Lipschitz-constant sequence.Source: §4.2 · pp. 12, 14
  • The mesh sequence’s density trades off estimate bias against convergence: smaller α reduces bias but also reduces Γ(f, kᵢ⋆₋₁).Γ measures the ratio of pairs in X × X where f is witnessed to be at least kᵢ⋆₋₁-Lipschitz.Source: §4.2 · p. 13
  • Estimating the Lipschitz constant gets harder with dimension; the stated bound implies at least ΩP(eᶜᵈᵏ/ᵏᵢ⋆₋₁) evaluations to estimate kᵢ⋆ successfully.The result applies to k-Lipschitz functions on [0, 1]^d.Source: §4.2 · p. 13
  • For any p in (0, 1) and any meshgrid sequence of Lipschitz constants, AdaLIPO is consistent over Lipschitz functions..Source: §4.2 · p. 13

4.3 Comparison with previous works

  • AdaLIPO attains a faster polynomial rate than SOO on Fκ and an O⋆P(e^-cn) rate when κ = 1, while SOO’s O(e^-c√n) rate applies over the broader {F′κ, κ ≥ 1} class.The comparison contrasts exploiting global smoothness with SOO’s local-smoothness guarantees.Source: §4.3 · p. 15

5. Numerical experiments

AdaLIPO is compared with global-optimization methods on real-data and synthetic problems. It is competitive on most benchmarks, often performs best at 90% and 95% targets, but can slow near the 99% target.

Algorithms

  • Comparators include Bayesian optimization, evolutionary search, local-mutation and multistart methods, DIRECT, and pure random search.The cited descriptions characterize BayesOpt as using a surrogate distribution, CMA-ES as sampling from an evolving normal distribution, and MLSL as multistart local optimization.Source: §5 · p. 16
  • For a fair comparison, tuning parameters use defaults; AdaLIPO uses p = 0.1 and k_i = (1 + 0.01/d)^i.The sequence choice is described as an arbitrary rule of thumb.Source: §5 · p. 16

Data sets

  • The evaluation covers five UCI data sets for kernel ridge-regression tuning and five synthetic benchmarks spanning multimodal, nonlinear, ill-conditioned, and well-shaped functions.The synthetic problems range from 2 to 5 dimensions.Source: §5 · p. 16

Protocol and performance metrics

  • Each method receives 100 runs and a budget of 1,000 evaluations per problem, with stopping times recorded for 90%, 95%, and 99% targets.The reported performance measures are the mean and standard deviation of evaluations needed to reach each target.Source: §5 · pp. 17–18

Results

  • AdaLIPO is competitive on most benchmarks and is best several times at 90% and 95% targets, but may reach 99% more slowly on some problems.The reported slowdown on Concrete and Housing is attributed to instability in the Lipschitz-constant estimate near maxima; a noise parameter is proposed as a possible extension.Source: §5 · p. 18

6. Conclusion

The paper introduces LIPO, which uses a known Lipschitz constant, and AdaLIPO, which estimates it during optimization. It provides theoretical analysis and empirical comparisons of the adaptive method with state-of-the-art global-optimization methods.

Conclusion

  • The paper introduces LIPO with a known Lipschitz constant and AdaLIPO, which estimates that constant during optimization.The conclusion also reports theoretical analysis and empirical results on synthetic and real problems for AdaLIPO against state-of-the-art methods.Source: §6 · p. 18

Appendix A. Preliminary results

The appendix establishes preliminary geometric and probabilistic results used in later computations, including covering results for convex sets and a bound for pure random search.

Covering numbers

  • An ε-cover consists of points in X whose ε-radius balls cover X; the covering number is the minimum size of such a sequence.The definition is stated for compact, convex X.Source: Appendix A · p. 18
  • Corollary 28 extends a covering-number result to bounded, compact, convex subsets of R^d.Its proof places X inside a hypercube, constructs a cover there, and projects centers onto X.Source: Appendix A · p. 20

Geometric results

  • Lemma 29 gives a volume inequality for the intersection of a ball and a compact, convex set with non-empty interior.The result is attributed to Zabinsky and Smith (1992).Source: Appendix A · p. 21

Pure random search

  • Proposition 30 gives a high-probability performance bound for pure random search on a compact, convex domain, assuming a k-Lipschitz objective.The evaluated points are independent uniform samples from X.Source: Appendix A · p. 22

Appendix B. Proofs of Section 3

The appendix proofs establish consistency and minimax results through constructions that hide an optimum from sequential evaluations, alongside covering-based and random-search upper-bound arguments.

Proof of Proposition 3

  • The consistency proof finds a region that the algorithm almost never visits, then constructs a Lipschitz function whose maximum lies there.This two-step argument is used to derive a contradiction with consistency.Source: Appendix B · p. 23

Proof of Example 1

  • The proof of Example 1 combines a covering of X with the convex-set covering-number bound.It chooses a scale involving ln(n/δ), dimension d, and the number n of random samples.Source: Appendix B · pp. 24–25

Proof of Proposition 4

  • The lower-bound proof partitions an inscribed hypercube and places a peak in a cell that the algorithm misses with high probability.The constructed function is indistinguishable from the constant function outside that cell.Source: Appendix B · pp. 25–26

Proof of Proposition 5

  • The minimax lower bound reuses a hidden-peak construction, while the upper bound uses pure random search and a change of variables.The upper-bound argument invokes Proposition 30 and the Euler gamma function.Source: Appendix B · pp. 26–27

Appendix C. Proofs of Section 3

Appendix C gives proofs for the listed results from Section 3, including arguments based on potential maximizers, shrinking neighborhoods, and random-search bounds.

Lemma 8

  • Lemma 8 characterizes potential maximizers by whether the observed best value plus the Lipschitz-distance bound can still reach the largest observed value.The proof constructs a function in the admissible class whose maximizers are exactly the points satisfying that condition.Source: Appendix C · p. 27

Proposition 11

  • Proposition 11’s proof uses a positive-measure near-optimal level set and a comparison with uniformly sampled points to obtain its probability bound.The proof invokes Proposition 12 after considering an i.i.d. uniform sequence over the domain.Source: Appendix C · p. 27

Corollary 13

  • Corollary 13 follows by combining Proposition 12 with Proposition 30.Source: Appendix C · p. 27

Proposition 14

  • Proposition 14 constructs a Lipschitz cone supported on a ball around an interior point, with its height determined by the radius and Lipschitz constant.The chosen ball has radius rδ,n, and the function is zero outside it.Source: Appendix C · pp. 27–28

Theorem 15

  • Theorem 15’s proof tracks evaluation counts in successively smaller neighborhoods of an optimum, then bounds the best observed value using random-search comparisons.Stopping times mark when enough points have entered each neighborhood; covering arguments bound visits to the surrounding annuli.Source: Appendix C · pp. 28, 29, 32

Theorem 16

  • Theorem 16’s lower-bound proof places the near-optimal level set inside a ball around the maximizer and uses a concentration result for gamma random variables.The proof refers to Lemmas 37 and 38 of Malherbe and Vayatis (2016) for the concentration step.Source: Appendix C · pp. 33–34

Appendix D. Analysis of AdaLipOpt (proofs of Section 4)

Appendix D proves properties of AdaLipOpt, including positivity of a sampling probability, estimation of the Lipschitz constant, and performance bounds after estimation.

Proposition 19

  • Continuity of a function built from f and the candidate Lipschitz constant implies Γ(f, k_i⋆−1) > 0.Since f is not Lipschitz with constant k_i⋆−1, the function is positive at some pair of points and remains positive in a neighborhood.Source: Appendix D · p. 34

Proposition 23

  • Proposition 23 follows by combining the consistency equivalence of Proposition 3 with the covering-rate upper bound from Example 1.Source: Appendix D · p. 34

Proposition 24

  • After enough exploration samples, Proposition 24’s proof uses those uniformly sampled evaluations to estimate the Lipschitz constant with high probability.The proof first obtains a required number of uniform samples, then applies Proposition 19 to them.Source: Appendix D · p. 35

Adaptive performance bound

  • Once the estimate equals the relevant candidate constant and satisfies the function’s Lipschitz bound, AdaLipOpt is at least as fast as pure random search in the stated probability bound.The proof compares subsequent evaluations with n−N2 i.i.d. uniform samples and also treats n ≤ N2 as a trivial case.Source: Appendix D · p. 35

Proposition 25

  • Proposition 25’s proof combines constant estimation and collected exploitative points with the fast-rate argument used for Theorem 15.The proof allocates exploitative points after its preliminary steps and extends the bound to all n.Source: Appendix D · pp. 35–36
Loading 1703.02628v3…