Estimation of Lipschitz constant Sample Clauses

Estimation of Lipschitz constant. D Assume the data set is noisy, and the Lipschitz constant M is unknown. We estimate the value of M using sample splitting and cross-validation. Sample splitting In sample splitting method, we randomly subdivide D into nonintersecting subsets D1 and D2 (parameter ratio controls the ratio of data allocated to 1). The data set 1 is used to approximate the values form 2 using (2.3) and (2.4) ( (2.5) for monotone functions). We try different values of M , in order to minimize the norm of the difference between the predicted and observed values from the set D2. We solve a bi-level optimization problem min 1 Σ max(yˆk(M ) − Mdki) + min(yˆk(M ) + Mdik) − 2yi , (2.8) M≥0 4 i∈7 k∈71 k∈71 where dkj = ||(xk − xj)V+||. The values yˆk(M ) = yk + rk(M ) are found D as a solution to problem (2.7), which now includes only the data from 1. To minimize wrt M we use the golden section algorithm combined with Fibonacci search. Once the optimal value of M is found, we smoothen the whole data set D by solving (2.7). Method ComputeLipschitzSplit() implements this technique. Cross-validation − D In cross-validation, we repeatedly remove one datum from the set , and approximate it using the rest N 1 data and a fixed value of M . We repeat this process for all N data, and minimize the norm of the difference between the predicted and observed values to obtain an optimal M . We solve a bi- level optimization problem N Σ 1 ki ki i min max(yˆ (M ) − Mdki) + min(yˆ (M ) + Mdik) − 2y