On Lipschitz Regularization of Convolutional Layers using Toeplitz Matrix Theory

Abstract: This paper tackles the problem of Lipschitz regularization of Convolutional Neural Networks. Lipschitz regularity is now established as a key property of modern deep learning with implications in training stability, generalization, robustness against adversarial examples, etc. However, computing the exact value of the Lipschitz constant of a neural network is known to be NP-hard. Recent attempts from the literature introduce upper bounds to approximate this constant that are either efficient but loose or accurate but computationally expensive. In this work, by leveraging the theory of Toeplitz matrices, we introduce a new upper bound for convolutional layers that is both tight and easy to compute. Based on this result we devise an algorithm to train Lipschitz regularized Convolutional Neural Networks.

06/12/2020

On Lipschitz Regularization of Convolutional Layers using Toeplitz Matrix Theory

Alexandre Araujo, Benjamin Negrevergne, Yann Chevaleyre, Jamal Atif

Comments

Similar Papers

Relative gradient optimization of the Jacobian term in unsupervised deep learning

Luigi Gresele, Giancarlo Fissore, Adrián Javaloy and Bernhard Schölkopf, Aapo Hyvarinen

Keywords Abstract Paper

Lipschitz constant estimation of Neural Networks via sparse polynomial optimization

Fabian Latorre, Paul Rolland, Volkan Cevher

Keywords Abstract Paper

robust networks, Lipschitz constant, polynomial optimization

It's Not What Machines Can Learn, It's What We Cannot Teach

Gal Yehuda, Moshe Gabel, Assaf Schuster

Keywords Abstract Paper

Set2Graph: Learning Graphs From Sets

Hadar Serviansky, Nimrod Segol, Jonathan Shlomi and Kyle Cranmer, Eilam Gross, Haggai Maron, Yaron Lipman

Keywords Abstract Paper

How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?

Zixiang Chen, Yuan Cao, Difan Zou, Quanquan Gu

Keywords Abstract Paper

classification, neural tangent kernel, generalization error, (stochastic) gradient descent, deep ReLU networks

Learning Differential Equations that are Easy to Solve

Jacob Kelly, Jesse Bettencourt, Matthew Johnson, David Duvenaud

Keywords Abstract Paper

Semialgebraic Optimization for Lipschitz Constants of ReLU Networks

Tong Chen, Jean Lasserre, Victor Magron, Edouard Pauwels

Keywords Abstract Paper

Opening the Blackbox: Accelerating Neural Differential Equations by Regularizing Internal Solver Heuristics

Avik Pal, Yingbo Ma, Viral Shah, Christopher Rackauckas

Keywords Abstract Paper

EvoGrad: Efficient Gradient-Based Meta-Learning and Hyperparameter Optimization

Ondrej Bohdal, Yongxin Yang, Timothy Hospedales

Keywords Abstract Paper

deep learning, optimization, graph learning, meta learning, few shot learning

Paying more Attention to Snapshots of Iterative Pruning: Improving Model Compression via Ensemble Distillation

Duong Le, Nhan Vo, Nam Thoai

Keywords Abstract Paper

network pruning, knowledge distillation, ensemble learning

Training Quantized Neural Networks to Global Optimality via Semidefinite Programming

Burak Bartan, Mert Pilanci

Keywords Abstract Paper

Optimization, Combinatorial Optimization

Deep Reinforcement Learning with Smooth Policy

Qianli Shen, Yan Li, Haoming Jiang and Zhaoran Wang, Tuo Zhao

Keywords Abstract Paper

Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks

Xin Chen, Lingxi Xie, Jun Wu and Longhui Wei, Yuhui Xu, Qi Tian

Keywords Abstract Paper

The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks

Wei Hu, Lechao Xiao, Ben Adlam, Jeffrey Pennington

Keywords Abstract Paper

Efficient proximal mapping of the path-norm regularizer of shallow networks

Fabian Latorre, Paul Rolland, Shaul Nadav Hallak, Volkan Cevher

Keywords Abstract Paper

Stochastic AUC Maximization with Deep Neural Networks

Mingrui Liu, Zhuoning Yuan, Yiming Ying, Tianbao Yang

Keywords Abstract Paper

Stochastic AUC Maximization, Deep Neural Networks

Neural Pruning via Growing Regularization

Huan Wang, Can Qin, Yulun Zhang, Yun Fu

Keywords Abstract Paper

deep neural network pruning, regularization, Hessian matrix, model compression

Learning Algebraic Multigrid Using Graph Neural Networks

Ilay Luz, Meirav Galun, Haggai Maron and Ronen Basri, Irad Yavneh

Keywords Abstract Paper

From Boltzmann Machines to Neural Networks and Back Again

Surbhi Goel, Adam Klivans, Frederic Koehler

Keywords Abstract Paper

Algorithms -> Nonlinear Dimensionality Reduction and Manifold Learning, Algorithms -> Regression

Optimal Continual Learning has Perfect Memory and is NP-hard

Jeremias Knoblauch, Hisham Husain, Tom Diethe

Keywords Abstract Paper

A Faster Decentralized Algorithm for Nonconvex Minimax Problems

Wenhan Xian, Feihu Huang, Yanfu Zhang, Heng Huang

Keywords Abstract Paper

optimization, machine learning, adversarial robustness and security

Understanding Approximate Fisher Information for Fast Convergence of Natural Gradient Descent in Wide Neural Networks

Ryo Karakida, Kazuki Osawa

Keywords Abstract Paper

Matrix encoding networks for neural combinatorial optimization

Luigi Gresele, Giancarlo Fissore, Adrián Javaloy and
Bernhard Schölkopf, Aapo Hyvarinen

Keywords Paper

Keywords Paper

Keywords Paper

Hadar Serviansky, Nimrod Segol, Jonathan Shlomi and
Kyle Cranmer, Eilam Gross, Haggai Maron, Yaron Lipman

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Qianli Shen, Yan Li, Haoming Jiang and
Zhaoran Wang, Tuo Zhao

Keywords Paper

Xin Chen, Lingxi Xie, Jun Wu and
Longhui Wei, Yuhui Xu, Qi Tian

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Ilay Luz, Meirav Galun, Haggai Maron and
Ronen Basri, Irad Yavneh

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon and
Minah Park, Duwon Park, Youngjune Gwon

Keywords Paper

Kei Ota, Tomoaki Oiki, Devesh Jha and
Toshisada Mariyama, Daniel Nikovski

Keywords Paper

Keywords Paper

Keywords Paper

Emmanuel Abbe, Enric Boix-Adsera, Matthew S Brennan and
Guy Bresler, Dheeraj Nagaraj

Keywords Paper

Keywords Paper

Hadi Daneshmand Daneshmand, Jonas Kohler, Francis Bach and
Thomas Hofmann, Aurelien Lucchi

Keywords Paper

Keywords Paper

Keywords Paper

Keywords Paper

Alexander Camuto, George Deligiannidis, Murat Erdogdu and
Mert Gurbuzbalaban, Umut Simsekli, Lingjiong Zhu

Keywords Paper

Biswajit Paria, Chih-Kuan Yeh, Ian E.H. Yen and
Ning Xu, Pradeep Ravikumar, Barnabás Póczos

Keywords Paper

Keywords Paper

Keywords Paper