LipschitzConstantEstimator

Documentation for LipschitzConstantEstimator.

This package provides a function to estimate the lipschitz constant of a function numerically.

Example

using LipschitzConstantEstimator
# suppose we have the following function
f(x) = x[1] - x[1]^3 / 3

# define a domain we wish to evaluate over
domain = IntervalDomain( [-1.0], [1.0])
# defined as IntervalDomain(lower_corner, upper_corner)

# run the estimator
results = estimate_lipschitz_constant(f, domain);

# check the success code (should be true)
results.success

true

# get the estimated Lipschitz constant (should be close to 1)
results.L

0.9999819837268493

# check the optimization status
results.optim_status

 * Status: success

 * Candidate solution
    Final objective value:     -4.341027e+01

 * Found with
    Algorithm:     L-BFGS

 * Convergence measures
    |x - x'|               = 0.00e+00 ≤ 0.0e+00
    |x - x'|/|x'|          = 0.00e+00 ≤ 0.0e+00
    |f(x) - f(x')|         = 0.00e+00 ≤ 0.0e+00
    |f(x) - f(x')|/|f(x')| = 0.00e+00 ≤ 0.0e+00
    |g(x)|                 = 1.26e+05 ≰ 1.0e-08

 * Work counters
    Seconds run:   0  (vs limit Inf)
    Iterations:    2
    f(x) calls:    175
    ∇f(x) calls:   175

# get the fitted weibull distribution
results.fitted_distribution

RevWeibull3P{Float64}(λ=0.9807693791567749, k=0.9526577429196056, μ=0.9999819837268493)

# get the individual samples of lipschitz constants used to fit the weibull
results.samples

200-element Vector{Float64}:
 0.9993631304201175
 0.9973955384752186
 0.9666527212516333
 0.9972537020983081
 0.9999375677838853
 0.9626436651579565
 0.9310831357842745
 0.998122589139947
 0.9888488972047588
 0.9921679418558397
 ⋮
 0.9905632212217769
 0.9990910018131558
 0.979643010786205
 0.997069857366433
 0.9225819582185376
 0.7844635497131467
 0.9991131016904905
 0.994308550166518
 0.9967835045492071

There are a few parameters to choose for the estimate_lipschitz_constant function, see the API below.

Algorithm

The basic algorithm is described in

@article{wood1996estimation,
  title={Estimation of the Lipschitz constant of a function},
  author={Zhang, BP},
  journal={Journal of Global Optimization},
  volume={8},
  pages={91--103},
  year={1996},
  publisher={Springer}
}

The api we have provided allows for $f: \R^d \to \R^p$ where $d, p \geq 1$ can be one or greater. Note, the original paper only analyzes the case where $d = p = 1$.

Public API

LipschitzConstantEstimator.EstimationResult — Type

EstimationResult

A struct to hold the results of the Lipschitz constant estimation.

success: a boolean indicating whether the optimization converged.
L: the estimated Lipschitz constant.
optim_status: the status of the optimization process.
fitted_distribution: the fitted reversed Weibull distribution parameters.
samples: the samples used to estimate the Lipschitz constant.

source

LipschitzConstantEstimator.IntervalDomain — Type

IntervalDomain{DIM, F}

A domain defined by a lower and upper bound for each dimension. The lower and upper bounds are represented as vectors of length DIM. The type parameter F represents the element type of the bounds.

source

LipschitzConstantEstimator.RevWeibull3P — Type

RevWeibull3P

A three-parameter reversed Weibull distribution, parameterized by scale λ, shape k, and location μ. This distribution is defined for x < μ, and it has a maximum at μ.

source

LipschitzConstantEstimator.estimate_lipschitz_constant — Function

estimate_lipschitz_constant(f, domain::AbstractDomain, n=10, m=200, δ=0.05; alg = NelderMead(), kwargs...)

Estimate the Lipschitz constant for a function f over a given domain. The function samples pairs of points from the domain, computes the Lipschitz constant for each pair and fits a reversed Weibull distribution to the estimates.

f: the function for which the Lipschitz constant is to be estimated.
domain: an instance of AbstractDomain defining the bounds for sampling.
n: number of samples to take for each estimate (default is 10).
m: number of estimates to create (default is 200).
δ: the distance within which to sample pairs of points (default is 0.05).
alg: the optimization algorithm to use for fitting the reversed Weibull distribution (default is NelderMead()).
kwargs: additional keyword arguments to pass to the optimization function.

The function returns a tuple containing

a boolean indicating whether the optimization converged
the estimated Lipschitz constant
the result struct from Optim.jl
the fitted reversed Weibull distribution parameters.

The Lipschitz constant is estimated as the location parameter μ of the fitted reversed Weibull distribution.

source

Private API

Distributions.cdf — Method

cdf(d::RevWeibull3P, x::Real)

Compute the cumulative distribution function for the reversed Weibull distribution at x. If x >= μ, it returns 1.0, otherwise it computes the CDF using the formula:

\[\operatorname{cdf}(x) = \begin{cases} \exp\left(-\left(\frac{μ - x}{λ}\right)^k\right) & \text{if } x < μ \\ 1 & \text{if } x \geq μ \end{cases}\]

This is slightly different from the form in Wood's paper, as the scale parameter is inside the exponent.

source

Distributions.logpdf — Method

logpdf(d::RevWeibull3P, x::Real)

Compute the logarithm of the probability density function for the reversed Weibull distribution at x. The distribution is defined for x < μ, and it returns -Inf for x >= μ.

source

Distributions.pdf — Method

pdf(d::RevWeibull3P, x::Real)

Compute the probability density function for the reversed Weibull distribution at x. If x >= μ, it returns 1.0, otherwise it computes the PDF using the logpdf function.

source

LipschitzConstantEstimator.create_lipschitz_estimates — Function

create_lipschitz_estimates(f, domain::AbstractDomain, n=10, m=200, δ=0.05)

Create estimates of the Lipschitz constant for a function f over a given domain. The function samples pairs of points from the domain, computes the Lipschitz constant for each pair and returns a vector of estimates.

f: the function for which the Lipschitz constant is to be estimated.
domain: an instance of AbstractDomain defining the bounds for sampling.
n: number of samples to take for each estimate (default is 10).
m: number of estimates to create (default is 200).
δ: the distance within which to sample pairs of points (default is 0.05).

The function returns a vector of m estimates of the Lipschitz constant.

source

LipschitzConstantEstimator.fit_reversed_weibull — Function

fit_reversed_weibull(data, initial_guess = [1.0, 1.0, 1.01 * maximum(data)]; alg=NelderMead(), kwargs...)

Fit a reversed Weibull distribution to the given data using maximum likelihood estimation. The function uses the negloglik function to compute the negative log-likelihood and optimizes it using the optimize function from the Optim package. The initial_guess parameter specifies the initial values for the parameters [λ, k, μ], where λ is the scale, k is the shape, and μ is the location (maximum). The default initial guess is [1.0, 1.0, 1.01 * maximum(data)], which ensures that μ is greater than the maximum value in the data. The optimization algorithm can be specified using the alg parameter, with NelderMead() as the default. Additional keyword arguments can be passed to the optimize function.

source

LipschitzConstantEstimator.in_domain — Method

in_domain(domain::IntervalDomain{DIM, F}, y::SVector{DIM, F}) where {DIM, F}

Check if a point y is within the bounds defined by the domain. Returns true if y is within the bounds, otherwise returns false.

source

LipschitzConstantEstimator.negloglik — Method

negloglik(params, data)

Compute the negative log-likelihood for the reversed Weibull distribution given parameters params and data data. The parameters are expected to be in the form [λ, k, μ], where λ is the scale, k is the shape, and μ is the location (maximum). The function returns Inf if the parameters are invalid (e.g., if λ <= 0, k <= 0, or μ <= maximum(data)).

source

LipschitzConstantEstimator.sample_pair — Method

sample_pair(domain::IntervalDomain{DIM, F}, δ) where {DIM, F}

Sample a pair of points (x, y) from the domain such that y is within a distance δ from x. The point x is sampled uniformly from the domain, and y is generated by adding a random direction vector scaled by δ to x.

source