Analysis of different norms and corresponding Lipschitz constants for global optimization

By Remigijus Paulavičius, Julius Zilinskas. 2006

49 citations recorded by the source corpus.

Abstract The paper discusses how the used norm and corresponding Lipschitz constant influence the speed of algorithms for global optimization. For this reason Lipschitz constants corresponding to different norms were estimated. Different test functions for global optimization were solved using branch‐and‐bound algorithm for Lipschitz optimization with different norms. Experiments have shown that the best results are achieved when combination of extreme (infinite and first) and sometimes Euclidean norms is used.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Huan Zhang
2. Tsui-Wei Weng
3. Pin-Yu Chen
4. Matt Jordan
5. Cho-Jui Hsieh
6. Dong Su
7. Jinfeng Yi
8. A. Dimakis

Citations in the corpus

• Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach (2018, methodology): “Specifically, our analysis obtains a lower bound of Lemma 3.1 (Lipschitz continuity and its relationship with gradient norm (Paulaviˇcius & ˇ Zilinskas, 2006)) .”
• Towards Practical Differentially Private Convex Optimization (2019, methodology): “As the private Frank-Wolfe algorithm requires the loss to have a relaxed L1-Lipschitz constant L, it suffices (using Theorem 1 from [41]) to bound the L∞-norm of each sample (xi, yi) by L.”
• On Mean Absolute Error for Deep Neural Network Based Vector-to-Vector Regression (2020, methodology): “Proof: To prove Theorem 1, we first introduce Lemma 3, which is achieved by the modification of Theorem 1 in [35].”
• Exactly Computing the Local Lipschitz Constant of ReLU Networks (2020, background): “Previous work has demonstrated the relationship between these two quantities for functions that are scalar-valued and continuously differentiable (Latorre et al., 2019; Paulaviˇcius & ˇZilinskas, 2006).”
• Distribution Matching for Crowd Counting (2020, background): “Before proving the proposed theorems in the main paper, we state the following two theorems, introduced in [7, 9].”