Codes for NeurIPS 2021 paper "On the Equivalence between Neural Network and Support Vector Machine".

Overview

On the Equivalence between Neural Network and Support Vector Machine

Codes for NeurIPS 2021 paper "On the Equivalence between Neural Network and Support Vector Machine".

Cite our paper

Yilan Chen, Wei Huang, Lam M. Nguyen, Tsui-Wei Weng, "On the Equivalence between Neural Network and Support Vector Machine", NeurIPS 2021.

@inproceedings{chen2021equiv,
  title={On the equivalence between neural network and support vector machine},
  author={Yilan Chen and Wei Huang and Lam M. Nguyen and Tsui-Wei Weng},
  booktitle={Advances in Neural Information Processing Systems},
  year={2021}
}

Overview

In this paper, we prove the equivalence between neural network (NN) and support vector machine (SVM), specifically, the infinitely wide NN trained by soft margin loss and the standard soft margin SVM with NTK trained by subgradient descent. Our main theoretical results include establishing the equivalence between NN and a broad family of L2 regularized kernel machines (KMs) with finite-width bounds, which cannot be handled by prior work, and showing that every finite-width NN trained by such regularized loss functions is approximately a KM.

Furthermore, we demonstrate our theory can enable three practical applications, including

  • non-vacuous generalization bound of NN via the corresponding KM;
  • non-trivial robustness certificate for the infinite-width NN (while existing robustness verification methods (e.g. IBP, Fast-Lin, CROWN) would provide vacuous bounds);
  • intrinsically more robust infinite-width NNs than those from previous kernel regression.

See our paper and slides for details.

Equivalence between infinite-width NNs and a family of KMs

Code overview

  • train_sgd.py: train the NN and SVM with NTK with stochastic subgradient descent. Plot the results to verify the equivalence.

  • generalization.py: compute non-vacuous generalization bound of NN via the corresponding KM.

  • regression.py: kernel ridge regression with NTK.

  • robust_svm.py:

    • test(): evaluate the robustness of NN using IBP or SVM with our method in the paper.
    • test_regressions(): evaluate the robustness of kernel ridge regression models using our method.
    • bound_ntk():calculate the lower and upper bound for NTK of two-layer fully-connected NN.
  • ibp.py: functions to calculate IBP bounds. Specified for NTK parameterization.

  • models/model.py: codes for constructing fully-connected neural networks with NTK parameterization.

  • config/:

    • svm_sgd.yaml: configurations and hyper-parameters to train NN and SVM.
    • svm_gene.yaml: configurations and hyper-parameters to calculate generalization bound.

Required environments:

This code is tested on the below environments:

python==3.8.8
torch==1.8.1
neural-tangents==0.3.6

Other required packages can be installed using Conda as follows,

conda create -n equiv-nn-svm python=3.8
conda activate equiv-nn-svm
conda install numpy tqdm matplotlib seaborn pyyaml

For the installation of PyTorch, please reference the instructions from https://pytorch.org/get-started/locally/. For the installation and usage of neural-tangents, please reference the instructions at https://github.com/google/neural-tangents.

Experiments

Train NN and SVM to verify the equivalence

python train_sgd.py

Example of the SGD results

SGD results

Example of the GD results

GD results

Computing non-vacuous generalization bound of NN via the corresponding KM

python generalization.py

Example of the generalization bound results

Generalization bound results

Robustness verification of NN

Add your paths to your NN models in the code and separate by the width. Specify the width of the models you want to verify. Then run the test() function in robust_svm.py.

python -c "import robust_svm; robust_svm.test('nn')"

Robustness verification of SVM

Add your paths to your SVM models in the code. Then run the test() function in robust_svm.py.

python -c "import robust_svm; robust_svm.test('svm')"

robustness verification results

Train kernel ridge regression with NTK models

python regression.py

Robustness verification of kernel ridge regression models

Run test_regressions() function in robust_svm.py.

python -c "import robust_svm; robust_svm.test_regressions()"

robustness verification results

Owner
Leslie
Leslie
Hierarchical Time Series Forecasting with a familiar API

scikit-hts Hierarchical Time Series with a familiar API. This is the result from not having found any good implementations of HTS on-line, and my work

Carlo Mazzaferro 204 Dec 17, 2022
Code of TVT: Transferable Vision Transformer for Unsupervised Domain Adaptation

TVT Code of TVT: Transferable Vision Transformer for Unsupervised Domain Adaptation Datasets: Digit: MNIST, SVHN, USPS Object: Office, Office-Home, Vi

37 Dec 15, 2022
simple demo codes for Learning to Teach with Dynamic Loss Functions

Learning to Teach with Dynamic Loss Functions This repo contains the simple demo for the NeurIPS-18 paper: Learning to Teach with Dynamic Loss Functio

Lijun Wu 15 Dec 30, 2021
Quick program made to generate alpha and delta tables for Hidden Markov Models

HMM_Calc Functions for generating Alpha and Delta tables from a Hidden Markov Model. Parameters: a: Matrix of transition probabilities. a[i][j] = a_{i

Adem Odza 1 Dec 04, 2021
ParmeSan: Sanitizer-guided Greybox Fuzzing

ParmeSan: Sanitizer-guided Greybox Fuzzing ParmeSan is a sanitizer-guided greybox fuzzer based on Angora. Published Work USENIX Security 2020: ParmeSa

VUSec 158 Dec 31, 2022
Dilated Convolution with Learnable Spacings PyTorch

Dilated-Convolution-with-Learnable-Spacings-PyTorch Ismail Khalfaoui Hassani Dilated Convolution with Learnable Spacings (abbreviated to DCLS) is a no

15 Dec 09, 2022
A stable algorithm for GAN training

DRAGAN (Deep Regret Analytic Generative Adversarial Networks) Link to our paper - https://arxiv.org/abs/1705.07215 Pytorch implementation (thanks!) -

195 Oct 10, 2022
A highly modular PyTorch framework with a focus on Neural Architecture Search (NAS).

UniNAS A highly modular PyTorch framework with a focus on Neural Architecture Search (NAS). under development (which happens mostly on our internal Gi

Cognitive Systems Research Group 19 Nov 23, 2022
Simplified interface for TensorFlow (mimicking Scikit Learn) for Deep Learning

SkFlow has been moved to Tensorflow. SkFlow has been moved to http://github.com/tensorflow/tensorflow into contrib folder specifically located here. T

3.2k Dec 29, 2022
Api's bulid in Flask perfom to manage Todo Task.

Citymall-task Api's bulid in Flask perfom to manage Todo Task. Installation Requrements : Python: 3.10.0 MongoDB create .env file with variables DB_UR

Aisha Tayyaba 1 Dec 17, 2021
Python Environment for Bayesian Learning

Pebl is a python library and command line application for learning the structure of a Bayesian network given prior knowledge and observations. Pebl in

Abhik Shah 103 Jul 14, 2022
zeus is a Python implementation of the Ensemble Slice Sampling method.

zeus is a Python implementation of the Ensemble Slice Sampling method. Fast & Robust Bayesian Inference, Efficient Markov Chain Monte Carlo (MCMC), Bl

Minas Karamanis 197 Dec 04, 2022
TorchOk - The toolkit for fast Deep Learning experiments in Computer Vision

TorchOk - The toolkit for fast Deep Learning experiments in Computer Vision

52 Dec 23, 2022
This is the official PyTorch implementation of the CVPR 2020 paper "TransMoMo: Invariance-Driven Unsupervised Video Motion Retargeting".

TransMoMo: Invariance-Driven Unsupervised Video Motion Retargeting Project Page | YouTube | Paper This is the official PyTorch implementation of the C

Zhuoqian Yang 330 Dec 11, 2022
Neural network-based build time estimation for additive manufacturing

Neural network-based build time estimation for additive manufacturing Oh, Y., Sharp, M., Sprock, T., & Kwon, S. (2021). Neural network-based build tim

Yosep 1 Nov 15, 2021
Robotic Process Automation in Windows and Linux by using Driagrams.net BPMN diagrams.

BPMN_RPA Robotic Process Automation in Windows and Linux by using BPMN diagrams. With this Framework you can draw Business Process Model Notation base

23 Dec 14, 2022
Official repository of IMPROVING DEEP IMAGE MATTING VIA LOCAL SMOOTHNESS ASSUMPTION.

IMPROVING DEEP IMAGE MATTING VIA LOCAL SMOOTHNESS ASSUMPTION This is the official repository of IMPROVING DEEP IMAGE MATTING VIA LOCAL SMOOTHNESS ASSU

电线杆 14 Dec 15, 2022
AdamW optimizer for bfloat16 models in pytorch.

Image source AdamW optimizer for bfloat16 models in pytorch. Bfloat16 is currently an optimal tradeoff between range and relative error for deep netwo

Alex Rogozhnikov 8 Nov 20, 2022
Differentiable molecular simulation of proteins with a coarse-grained potential

Differentiable molecular simulation of proteins with a coarse-grained potential This repository contains the learned potential, simulation scripts and

UCL Bioinformatics Group 44 Dec 10, 2022
ML-Decoder: Scalable and Versatile Classification Head

ML-Decoder: Scalable and Versatile Classification Head Paper Official PyTorch Implementation Tal Ridnik, Gilad Sharir, Avi Ben-Cohen, Emanuel Ben-Baru

189 Jan 04, 2023