A provable control of sensitivity of neural networks through a direct parameterization of the overall bi-Lipschitzness

Summary

This paper investigates and proposes a novel bi-Lipschitz neural network architecture. This architecture provides a simple, direct and tight control of the Lipschitz and inverse Lipschitz constants through the use of two parameters, the ideal minimum, equipped with theoretical guarantees. To devise their architecture the authors exploit convex neural networks and the Legendre-Fenchel duality. The authors also propose a variant of their bi-Lipschitz architecture that is more scalable by exploiting partially input convex neural networks. Finally, the authors propose a set of experiments to showcase the utility of our model in concrete machine learning applications, namely, uncertainty estimation and monotone problem settings and show that it can improve previous methods.

Strengths

- The paper is well written. After writing a clearly structured related work (with an extensive background and related work proposed in Appendix A), the authors propose their new design and explicitly explain how the forward pass of their network is computed as well as the expressivity and how the backpropagation can be done. - The authors acknowledge that the computational cost of their approach can pose serious limitation and propose to overcome this problem with partially input convex neural networks.

Weaknesses

- It would be interesting of the authors could provide experiments with both their architectures with respect to computational cost, and highlight time of training etc.

Questions

NA.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Lack of experiments wrt to computational cost and maybe an experiment with a more larger dataset than the current ones use in the paper.

Summary

This paper proposes a novel neural network architecture called BLNN (Bi-Lipschitz Neural Network) that allows direct control and parameterization of the overall bi-Lipschitzness of the network. The main contributions include: i) a framework that allows tight control of Lipschitz and inverse Lipschitz constants of networks via using convex neural networks and the Legendre-Fenchel transformation, ii) comprehensive theoretical analysis, iii) empirical evaluation showing the nice performance of BLNN on tasks like function fitting, out-of-distribution detection, and monotone regression.

Strengths

**Originality:** The paper presents a novel approach to constructing bi-Lipschitz neural networks that is distinctly different from existing methods. The use of convex neural networks and Legendre-Fenchel transformation to directly parameterize overall bi-Lipschitzness is quite novel. The extension (e.g. partially bi-Lipschitz networks, etc) is also new. **Quality:** The quality of the paper is good. The authors provide detailed proofs and analyses for their key claims, including the bi-Lipschitz properties of their construction and the expressive power of the resulting networks. The experiments cover various scenarios, from simple function fitting to uncertainty estimation and monotone regression. The results are quite competitive. **Clarity:** The paper is generally well-structured and clearly written. However, given the technical nature and the length of the paper, understanding the paper fully is still a tough task. **Significance:** The paper's contributions are significant in its solid theoretical developments. The significance is further underscored by the improved performance on tasks like out-of-distribution detection and monotone function learning. In conclusion, this paper presents a novel approach to an important problem in deep learning theory and practice.

Weaknesses

1. Computational Complexity: A detailed analysis of time and space complexity compared to traditional networks can be helpful. 2. Scalability and Practical Implications: There's insufficient exploration of how the method scales to very large networks or complex datasets (e.g. TinyImageNet). 3. Hyperparameter Sensitivity: More discussions on this issue will be beneficial. 4. The paper could be more explicit about scenarios where the theoretical guarantees might not hold, and could explore potential extensions to other network architectures beyond feedforward networks.

Questions

1. How does the proposed method perform on larger, more complex datasets like TinyImageNet or ImageNet? 2. Can the authors clarify the computational complexity of their approach? 3. Can the authors provide a more comprehensive study on hyperparameter sensitivity? 4. Can the authors comment on other network structures (e.g. implicit models, DEQs, etc)?

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

It seems that an improved discussion on potential negative societal impacts or broader ethical considerations is still missing.

Summary

This paper proposes to control the bi-Lipschitzness of a neural-network by parameterizing the output by the Legendre-Fenchel-Dual. This involves parameterizing a strongly convex function and computing the minimum of that function in the forward pass. Several benchmarks are studied in simple regression tasks and uncertainty quantification.

Strengths

-The framework is interesting because it parameterizes bi-Lipschitz networks in a way that is not layer-wise and instead takes advantage of the Legendre-Fenchel transform LFT / convex conjugate of parameterized strongly-convex functions (ICNN), which only modifies the output of the output. -Computing the LFT of a given function can be costly, however the paper offers a non-asymptotic bound for the Lipschitz constant and tractable gradient. -The experimental results show a considerable improvement in tightness and regularity over other Lipschitz controlled networks like spectral normalization, AOL and Sandwich layers on small regression tasks. In particular BiLipNet behaves a lot better when the Lipschitz constant is overestimated in existing parameterizations.

Weaknesses

-Computing the LFT seems to be quite expensive, hence why the experiments are only on simple 2d problems and fashion-MNIST. For this reason I'm doubtful that it will be used for any large-scale network training pipelines where tight Lipschitz control and estimation is challenging. -The provable approximation class is limited to alpha-strongly monotone functions and is the derivative of some function almost everywhere. Lipschitz layers like AOL, SLL and Sandwich layer are all solutions to the LipSDP framework which only requires the activations themselves to be alpha-strongly monotone for alpha >= 0 (Fazlyab et al., 2019).

Questions

-Is it also necessary that BLNN is a strongly monotone function? It seems that many of the regression experiments involve monotone target functions (figure 2 and 3), but I'm not sure if that is because BLNN is not capable of representing monotone functions or just not a great representer due to your approximation theorem. If it can represent non-monotone functions, it would be interesting to see a simple regression comparison to SLL, AOL, etc. Answering this question will greatly help my evaluation. -The Lipschitz parameterization of SLL, AOL, and Sandwich layers commonly uses compositions of 1-Lipschitz layers for the application of certified robustness. How would the BLNN parameterization compare to existing 1-Lipschitz layer networks in the certified robustness setting? I’d imagine BLNN might be much more expressive than composed 1-Lipschitz layers which could have a big impact. -Have you considered amortizing the LFT computation as done in this paper? https://arxiv.org/abs/2210.12153 -I'm curious if there is any possibility of extending BLNN to convolutional layers? These settings are interesting for larger image classification problems like CIFAR10 and Imagenet.

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Limitation are adequately addressed.