MATHEMATICS OF

DEEP LEARNING
RAJA GIRYES
TEL AVIV UNIVERSITY

Mathematics of Deep Learning Tutorial

EUSIPCO Conference, Budapest, Hungary
1
August 29, 2016
 AGENDA

• History and introduction to deep learning.

• A sample of existing theory for deep learning.
• Data structure based theory for deep learning
• Neural networks with random Gaussian weights.
• Generalization error of deep neural networks.
• Deep learning as metric learning.
• Solving minimization problems via deep learning.

2
 HISTORY AND
INTRODUCTION TO
DEEP LEARNING

3
 FIRST LEARNING PROGRAM

1956

“field of study that gives computers the ability to learn

without being explicitly programmed”. [Arthur Samuel, 1959]

4
 IMITATING THE BRAIN

Wiesel and Hubel, 1959 5

 HUMAN VISUAL SYSTEM

In the visual cortex there

are two types of neurons:
Simple and complex

6
 IMITATING THE HUMAN BRAIN

Fukushima 1980

7
 CONVOLUTIONAL NEURAL NETWORKS

• Introduction of convolutional neural networks

[LeCun et. al. 1989]
• Training by backpropagation

8
 SCENE PARSING
• Deep Learning usage before 2012:

[Farabet et al., 2012, 2013]

9
 2012 IMAGENET DEEP LEARNING
BREAKTHROUGH
• Imagenet dataset
• 1.4 Million images
• 1000 categories
• 1.2 Million for training
• 150000 for testing
• 50000 for validation

[Krizhevsky, Sutskever
& Hinton, 2012]

Today deep learning achieves 3.5% by 152 layers [He, Zhang, Ren & Sun, 2016]
10
 DEEP NETWORK STRUCTURE

[Krizhevsky, Sutskever & Hinton, 2012]

• What each layer of the network learns?

11
 LAYERS STRUCTURE
• First layers detect simple patterns that
corresponds to simple objects

•
[Zeiler & Fergus, 2014]
12
 LAYERS STRUCTURE
• Deeper layers detects more complex patterns
corresponding to more complex objects.

•
[Zeiler & Fergus, 2014]
13
 LAYERS STRUCTURE

14
[Zeiler & Fergus, 2014]
 WHY THINGS WORK BETTER TODAY?

• More data – larger datasets, more access (internet)

• Better hardware (GPU)
• Better learning regularization (dropout)

• Deep learning impact and success is not unique

only to image classification.
• But it is still unclear why deep neural networks are
so remarkably successful and how they are doing it.
15
DEEP LEARNING FOR SPEECH RECOGNITION

16
 OBJECT DETECTION

17
[Szegedy et al., 2015]
 GAME PLAYING

[Mnih et al., 2013, 2015] 18

 GO GAME
• AlphaGo - First computer program to ever beat a
professional player at the game of go

• Program created by Google DeepMind

• Game strategy was learned using deep learning
[Silver et al., 2016].
19
 CUTTING EDGE PERFORMANCE
IN MANY OTHER APPLICATIONS
• Disease diagnosis [Zhou, Greenspan & Shen, 2016].
• Language translation [Sutskever et al., 2014].
• Video classification [Karpathy et al., 2014].
• Face detection [Schroff et al., 2015].
• Handwriting recognition [Poznanski & Wolf, 2016].
• Sentiment classification [Socher et al., 2013].
• Image denoising [Burger et al., 2012].
• Super-resolution [Kim et al., 2016], [Bruna et al., 2016].
• many other applications… 20
 DEEP NEURAL NETWORKS (DNN)
• One layer of a neural net

𝑉∈ℝ 𝑑 𝑿 𝑉𝑋
𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎
𝑋 is a linear 𝝍 is a non-linear
operation function

• Concatenation of the layers creates the whole net

Φ(𝑋1 , 𝑋 2 , … , 𝑋 𝐾 ) = 𝜓 𝜓 𝜓 𝑉𝑋1 𝑋 2 … 𝑋 𝐾

𝑽∈ ℝ𝒅 𝑿𝟏 𝝍 𝑿𝒊 𝝍 𝑿𝑲 𝝍

21
 CONVOLUTIONAL NEURAL NETWORKS (CNN)

𝒅 𝑉𝑋
𝑽∈ℝ 𝑿 𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎
𝑋 is a linear 𝐹 is a non-linear
operation function

• In many cases, 𝑋 is selected to be a convolution.

• This operator is shift invariant.
• CNN are commonly used with images as they are
typically shift invariant.

22
 THE NON-LINEAR PART
• Usually 𝜓 = 𝑔 ∘ 𝑓. 𝑿 𝝍
• 𝑓 is the (point-wise) activation function
ReLU Sigmoid Hyperbolic
𝑓(x) = max(x, 0) 1 tangent
𝑓 𝑥 =
1 + 𝑒 −𝑥 𝑓 𝑥 = tanh(𝑥)

• 𝑔 is a pooling or an aggregation operator.

𝑉1 𝑉2 𝑉3 𝑉4 … … … … 𝑉𝑟

Max pooling Mean pooling 𝑙𝑝 pooling

𝑝 𝑛
1 𝑛 𝑝
max 𝑉𝑖 𝑉𝑖
𝑖
𝑉𝑖 𝑖=1
𝑛 𝑖=1

23
 A SAMPLE OF
EXISTING THEORY FOR
DEEP LEARNING

24
 WHY DNN WORK?

What is so
special with the
DNN structure? What is the role of
What is the the depth of DNN?
capability of DNN?
How many
training samples
do we need?
What is the role
What is the role of
of pooling?
the activation
function? What happens to the
data throughout the
layers?
25
 REPRESENTATION POWER
• Neural nets serve as a universal approximation for any
measurable Borel functions [Cybenko 1989, Hornik 1991].
• In particular, let the non-linearity 𝜓 be a bounded,
non-constant continuous function, 𝐼𝑑 be the 𝑑-
dimensional hypercube, and 𝐶 𝐼𝑑 be the space of
continuous functions on 𝐼𝑑 . Then for any 𝑓 ∈ 𝐶 𝐼𝑑
and 𝜖 > 0, there exists 𝑚 > 0, and 𝑋 ∈ ℝ𝑑×𝑚 ,
𝐵 ∈ ℝ𝑚 , 𝑊 ∈ ℝ𝑚 such that the neural network
𝐹 𝑉 = 𝜓 𝑉𝑋 + 𝐵 𝑊 𝑇
approximates 𝑓 with a precision 𝜖:
𝐹 𝑉 −𝑓 𝑉 < 𝜖, ∀𝑉 ∈ ℝ𝑑
26
 ESTIMATION ERROR

• The estimation error of a function f by a neural

networks scales as [Barron 1994].
Smoothness of
𝑪𝒇 𝑵𝒅 Input
approximated 𝑶 +𝑶 𝐥𝐨𝐠(𝑳) dimension
function 𝑵 𝑳

Number of Number of
neurons in the training
DNN examples

27
 DEPTH OF THE NETWORK
• DNN allow representing restricted Boltzmann
machines with a number of parameters
exponentially greater than the number of the
network parameters [Montúfar & Morton, 2015]
• Each DNN layer with ReLU divides the space by a
hyper-plane.
• Therefore the depth of the network divides the
space into an exponential number of sets
compared to the number of parameters [Montúfar,
Pascanu, Cho & Bengio, 2014]
28
 DEPTH EFFICIENCY OF CNN
• Function realized by CNN, with ReLU and max-
pooling, of polynomial size requires super-
polynomial size for being approximated by shallow
network [Telgarsky 2016 ,Cohen et al., 2016].
• Standard convolutional network design has
learning bias towards statistics of natural images
[Cohen et al., 2016].

29
 ROLE OF POOLING
• The pooling stage provides shift invariance [Boureau et
al. 2010], [Bruna, LeCun & Szlam, 2013].
• A connection is drawn between the pooling stage and
the phase retrieval methods [Bruna, Szlam & LeCun, 2014].
• This allows calculating Lipchitz constants of each DNN
layer 𝜓(∙ 𝑋) and empirically recovering the input of a
layer from its output.
• However, the Lipchitz constants calculated are very
loose and no theoretical guarantees are given for the
recovery.
30
 SUFFICIENT STATISTIC AND INVARIANCE
• Given a certain task at hand:
• Minimal sufficient statistic guarantees that we can
replace raw data with a representation with smallest
complexity and no performance loss.
• Invariance guarantees that the statistic is constant
with respect to uninformative transformations of the
data.
• CNN are shown to have these properties for many
tasks [Soatto & Chiuso, 2016].
• Good structures of deep networks can generate
representations that are good for learning with a small
number of examples [Anselmi et al., 2016].
31
 SCATTERING TRANSFORMS
• Scattering transform - a cascade of wavelet
transform convolutions with nonlinear modulus
and averaging operators.
• Scattering coefficients are stable encodings of
geometry and texture [Bruna & Mallat, 2013]
Original image
with 𝑑 pixels

Recovery from first

scattering moments:
𝑂 log 𝑑 coefficients
Recovery from 1st & 2nd
scattering moments:
𝑂 log 2 𝑑 coefficients
32
Images from slides of Joan Bruna in ICCV 2015 tutorial
 SCATTERING TRANSFORMS AND DNN

• More layers create features that can be made

invariant to increasingly more complex
deformations.
• Deep layers in DNN encode complex, class-specific
geometry.
• Deeper architectures are able to better capture
invariant properties of objects and scenes in
images
[Bruna & Mallat, 2013], [Wiatowski & Bölcskei, 2016]
33
 SCATTERING TRANSFORMS AS A METRIC
• Scattering transforms may be used as a metric.
• Inverse problems can be solved by minimizing
distance at the scattering transform domain.
• Leads to remarkable results in super-resolution
[Bruna, Sprechmann & Lecun, 2016]

34
 SCATTERING SUPER RESOLUTION

Original Best Linear Estimate State-of-the-art Scattering estimate

[Bruna, Sprechmann & Lecun, 2016]
35
Images from slides of Joan Bruna in CVPR 2016 tutorial
 MINIMIZATION
• The local minima in deep networks are not far from
the global minimum.

• saddle points are the

main problem of deep
Learning optimization.
• Deeper networks have [Choromanska et al., 2015]

more local minima but less saddle points.

[Saxe, McClelland & Ganguli, 2014], [Dauphin, Pascanu, Gulcehre,
Cho, Ganguli & Bengio, 2014] [Choromanska, Henaff, Mathieu, Ben
Arous & LeCun, 2015]
36
 GLOBAL OPTIMALITY IN DEEP LEARNING
• Deep learning is a positively homogeneous
factorization problem, i.e., ∃𝑝 ≥ 0 such that
∀𝛼 ≥ 0 DNN obey
Φ 𝛼𝑋1 , 𝛼𝑋 2 , … , 𝛼𝑋 𝐾 = 𝛼 𝑝 Φ 𝑋1 , 𝑋 2 , … , 𝑋 𝐾 .
• With proper regularization, local minima are global.
• If the network is large enough, global minima can
be found by local descent.
Guarantees of proposed
framework

[Haeffele & Vidal, 2015]

37
 DATA STRUCTURE
BASED THEORY FOR
DEEP LEARNING

38
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal Random

of training: Gaussian
Classify the OUTLINE weights are
boundary points good for
between the classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 39
 ASSUMPTIONS – GAUSSIAN WEIGHTS

𝑉 ∈ ℝ𝑑 𝑿𝟏 𝝍 𝑿𝒊 𝝍 𝑿𝑲 𝝍

𝑋 𝑖 , … , 𝑋 𝑖 , …,𝑋 𝐾 are
random Gaussian matrices
• Infusion of random weights reveals internal
properties of a system [Saxe et al.
Phase Deep
2014]
Retrieval Learning
Compressed
Sparse [Choromanska
Sensing [Arora et [Dauphin et
Recovery et al. 2015]
al. 2014] al. 2014]
40
 ASSUMPTIONS – NO POOLING

𝑽 ∈ ℝ𝒅 𝑿𝟏 𝝍 𝑿𝒊 𝝍 𝑿𝑲 𝝍

𝜓 is an element wise max(v, 0) 1

tanh(𝑣)
activation function 1 + 𝑒 −𝑥

• Pooling provides invariance [Boureau et. al. 2010,

Bruna et. al. 2013].
We assume that all equivalent points in the data were
merged together and omit this stage.
Reveals the role of the other components in the DNN.
41
ASSUMPTIONS – LOW DIMENSIONAL DATA

𝑽∈𝜰 𝑋1 𝜓 𝑋𝑖 𝜓 𝑋𝐾 𝜓

Υ is a low dimensional set

Gaussian Low Rank
Mixture Matrices
Models
(GMM)

Low
Signals with
Dimensional
Sparse
Manifolds
Representations

42
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal Gaussian Random

of training: Gaussian
Classify the Mean weights are
boundary points good for
between the Width classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 43
WHAT HAPPENS TO SPARSE DATA IN DNN?
• Let Υ be sparsely represented data
Υ
• Example: Υ = {𝑉 ∈ ℝ3 : 𝑉 0 ≤ 1}

• ΥX is still sparsely represented data Υ𝑋

• Example: ΥX = {𝑉 ∈ ℝ3 : ∃𝑊 ∈ ℝ3 , 𝑉 = 𝑊𝑋, 𝑊 0 ≤ 1}

• 𝜓(ΥX) not sparsely represented 𝜓(Υ𝑋)

• But is still low dimensional

44
 GAUSSIAN MEAN WIDTH
• Gaussian mean width:
𝝎 𝜰 = 𝑬 𝐬𝐮𝐩 𝑽 − 𝑾, 𝒈 , 𝒈~𝑵(𝟎, 𝑰).
𝑽,𝑾∈𝜰

𝒈
The width of
the set 𝜰 in 𝑾
the direction 𝜰
of 𝒈:
𝑽

45
 MEASURE FOR LOW DIMENSIONALITY
• Gaussian mean width:
𝝎 𝜰 = 𝑬 𝐬𝐮𝐩 𝑽 − 𝑾, 𝒈 , 𝒈~𝑵(𝟎, 𝑰).
𝑽,𝑾∈𝜰
• 𝝎𝟐 𝜰 is a measure for the dimensionality of the
data.
• Examples:
If Υ ⊂ 𝔹𝑑 is a Gaussian If Υ ⊂ 𝔹𝑑 is a data
Mixture Model with 𝑘 with 𝑘-sparse
Gaussians then representations then
𝝎𝟐 𝜰 = 𝑶(𝒌) 𝝎𝟐 𝜰 = 𝑶(𝒌 𝐥𝐨𝐠 𝒅)
46
 GAUSSIAN MEAN WIDTH IN DNN

𝑿 𝝍
𝑋 is a linear 𝐹 is a non-linear
𝜰 ⊂ ℝ𝒅 operation
𝜰𝑿 ⊂ ℝ 𝒎 function
𝝍(𝑽𝑿) ∈ ℝ𝒎

𝝎𝟐 𝜰
Theorem 1: small imply 𝝎𝟐 𝜰 ≈ 𝝎𝟐 𝝍(𝑽𝑿)
𝒎

Small 𝝎𝟐 𝜰 Small 𝝎𝟐 𝝍(𝑽𝑿)

It is sufficient to provide proofs only for a single layer

47
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal Random

of training: Gaussian
Classify the Stability weights are
boundary points good for
between the classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 48
 ASSUMPTIONS

𝑽 ∈ 𝕊𝒅 𝑿 𝑉𝑋
𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎

𝑋 is a 𝜓 is an
𝑽∈𝜰 element wise
random
Gaussian activation
matrix function
max(v, 0) 1
tanh(𝑣)
1 + 𝑒 −𝑥

𝑚 = 𝑂 𝛿 −6 𝜔2 Υ

49
 ISOMETRY IN A SINGLE LAYER

𝑽 ∈ 𝕊𝒅 𝑋 𝑉𝑋
𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎

Theorem 2: 𝜓(∙ 𝑋) is a 𝛿-isometry in the Gromov-

Hausdorff sense between the sphere 𝕊𝑑−1 and the
Hamming cube [Plan & Vershynin, 2014, Giryes, Sapiro & Bronstein 2016].
• If two points belong to the same tile
then their distance < 𝜹
• Each layer of the network keeps the
main information of the data

The rows of 𝑋 create a tessellation of the space.

 This stands in line with [Montúfar et. al. 2014]
 This structure can be used for hashing 50
 DNN AND HASHING
• A single layer performs a locally sensitive hashing.
• Deep network with random weights may be
designed to do better [Choromanska et al., 2016].
• It is possible to train DNN for hashing, which
provides cutting-edge results [Masci et al., 2012],
[Lai et al., 2015].

51
 DNN STABLE EMBEDDING

𝑽∈𝕊 𝒅 𝑿 𝑉𝑋
𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎

Theorem 3: There exists an algorithm 𝒜 such that

𝜔 Υ
𝑉 − 𝒜(𝜓(𝑉𝑋)) < 𝑂 = 𝑂 𝛿3
𝑚
[Plan & Vershynin, 2013, Giryes, Sapiro & Bronstein 2016].

After 𝐾 layers we have an error 𝑂 𝐾𝛿 3

Stands in line with [Mahendran and Vedaldi, 2015].
DNN keep the important information of the data
52
RECOVERY FROM DNN OUTPUT

53
[Mahendran and Vedaldi, 2015].
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal DNN with Random

of training: Gaussian
Classify the Gaussian weights are
boundary points good for
between the Weights classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 54
 ASSUMPTIONS

𝑽 ∈ ℝ𝒅 𝑿 𝑉𝑋
𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎

𝑋 is a 𝜓 is the ReLU
𝑉∈Υ
random max(v, 0)

Gaussian
matrix
𝒎 = 𝑶 𝜹−𝟒 𝝎𝟒 𝜰

55
 DISTANCE DISTORTION

𝑽∈𝜰 𝑿 𝑉𝑋 𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎

Theorem 4: for 𝑉, 𝑊 ∈ Υ
𝜓(𝑉𝑋) − 𝜓(𝑊𝑋) 2 − 12 V − W 2

V W
− (sin ∠ V, W
𝜋

The smaller ∠ V, W the

smaller the distance we get
∠ V, W
between the points
56
 ANGLE DISTORTION

𝑽∈𝜰 𝑋 𝑉𝑋 𝝍 𝝍(𝑽𝑿) ∈ ℝ𝒎

Theorem 5: for 𝑉, 𝑊 ∈ Υ Behavior of ∠ 𝜓(𝑉𝑋), 𝜓(𝑊𝑋)

cos ∠ 𝜓(𝑉𝑋), 𝜓(W𝑋) − cos ∠ V, W

1
− (sin ∠ V, 𝑊
𝜋

57
 DISTANCE AND ANGLES DISTORTION

𝑋 𝜓
Class I Class I Class II
Class II

Points with small angles between them become

closer than points with larger angles between them
58
 POOLING AND CONVOLUTIONS

• We test empirically this behavior on convolutional

neural networks (CNN) with random weights and
the MNIST, CIFAR-10 and ImageNet datasets.
• The behavior predicted in the theorems remains
also in the presence of pooling and convolutions.

59
 TRAINING DATA SIZE

• Stability in the network implies that close points in the

input are close also at the output
• Having a good network for an 𝜀-net of the input set Υ
guarantees a good network for all the points in Υ.
• Using Sudakov minoration the number of data points
is
exp(𝜔2 Υ /𝜀 2 ) .
• Though this is not a tight bound, it introduces the
Gaussian mean width 𝜔 Υ as a measure for the
complexity of the input data and the required number
of training samples.
60
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal Random

of training: Role of Gaussian
Classify the weights are
boundary points
Training good for
between the classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 61
 ROLE OF TRAINING

• Having a theory for Gaussian weights we test the

behavior of DNN after training.
• We looked at the MNIST, CIFAR-10 and ImageNet
datasets.
• We will present here only the ImageNet results.
• We use a state-of-the-art pre-trained network for
ImageNet [Simonyan & Zisserman, 2014].
• We compute inter and intra class distances.
62
INTER BOUNDARY POINTS DISTANCE RATIO
𝑋1 𝜓 𝑋𝑖 𝜓 𝑋𝐾 𝜓

Class I
𝑾−𝑽 Class II Class I 𝑽−𝒁 Class II
𝑽 𝑾 𝑽 𝒁

𝑉 is a random point and 𝑉 is the output of 𝑉 and 𝑍 the closest

𝑊 its closest point from point to 𝑉 at the output from a
a different class. different class.

𝑽−𝒁
Compute the distance ratio:
𝑾−𝑽

63
INTRA BOUNDARY POINTS DISTANCE RATIO
𝑋1 𝜓 𝑋𝑖 𝜓 𝑋𝐾 𝜓
𝑽
𝑾−𝑽 𝑽
Class I 𝑽−𝒁
Class II Class I Class II

𝑾
𝒁

Let 𝑉 be a point and 𝑊 Let 𝑉 be the output of 𝑉 and 𝑍 the

its farthest point from farthest point from 𝑉 at the output
the same class. from the same class

𝑽−𝒁
Compute the distance ratio:
𝑾−𝑽

64
 BOUNDARY DISTANCE RATIO

Inter-class Intra-class

𝑉−𝑍 𝑉−𝑍
𝑊−𝑉 𝑊−𝑉 65
 AVERAGE POINTS DISTANCE RATIO
𝑋1 𝜓 𝑋𝑖 𝜓 𝑋𝐾 𝜓
𝑽 𝑽−𝒁
𝑽−𝒁 Class II
𝒁 Class I 𝑽
𝑽−𝑾 Class II 𝑽−𝑾 𝒁
𝑾
Class I 𝑊

𝑉, 𝑊 and 𝑍 are three 𝑉, 𝑊 and 𝑍 are the outputs of 𝑉, 𝑊

random points and 𝑍 respectively.

𝑽−𝑾 𝑽−𝒁
Compute the distance ratios: ,
𝑽−𝑾 𝑽−𝒁

66
AVERAGE DISTANCE RATIO

Inter-class Intra-class

𝑉−𝑍 𝑉−𝑊
𝑉−𝑍 𝑉−𝑊 67
 ROLE OF TRAINING

• On average distances are preserved in the trained

and random networks.
• The difference is with respect to the boundary
points.
• The inter distances become larger.
• The intra distances shrink.

68
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal Generali- Random

of training: Gaussian
Classify the zation weights are
boundary points good for
between the Error classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 69
 ASSUMPTIONS
𝑿𝟏 𝝍 𝑿𝒊 𝝍 𝑿𝑲 𝝍

softmax/
𝐓𝐰𝐨
∈ 𝜰 general non-linearity linear 𝑾
𝐂𝐥𝐚𝐬𝐬𝐞𝐬 (ReLU, pooling,…) classifier

𝒘𝑻 𝜱 𝑿𝟏 , 𝑿𝟐 , … , 𝑿𝑲 = 𝟎

Input Space Feature Space

70
 CLASSIFIER TYPES

• Denote the output of the DNN by 𝑍.

• Linear classifier 𝑊 𝑇 is ofClass
the1
form
𝑍𝑊 𝑇 ≷ 𝑏,
Class 2
where b is a certain threshold.
• Softmax classifier predicts the probability of class i:
𝑒 𝑍𝑖
𝜎 𝑍 𝑖= 𝑍
𝑒 1 + 𝑒 𝑍2

71
 CLASSIFICATION OBJETIVES

• Denote the output of the DNN by 𝑍.

• Denote by 𝑡𝑖 the expected output of 𝑍𝑖
• Categorical cross entropy:
∑ log 𝑍𝑖 𝑡𝑖 .
• Hinge loss:
max 0,1 − 𝑍𝑖 𝑡𝑖
• Weight decay: penalty on the weight matrices,
∑ 𝑋𝑖

72
 GENERALIZATION ERROR (GE)
• In training, we reduce the classification error
ℓtraining of the training data as the number of
training examples 𝐿 increases.
• However, we are interested to reduce the error
ℓtest of the (unknown) testing data as 𝐿 increases.
• The difference between the two is the
generalization error
GE = ℓtraining − ℓtest
• It is important to understand the GE of DNN
73
 REGULARIZATION TECHNIQUES
• Weight decay – penalizing DNN weights [Krogh & Hertz, 1992].
• Dropout - randomly drop units (along with their connections)
from the neural network during training [Hinton et al., 2012],
[Baldi & Sadowski, 2013], Srivastava et al., 2014].
• DropConnect – dropout extension [Wan et al., 2013]
• Batch normalization [Ioffe & Szegedy, 2015].
• Stochastic gradient descent (SGD) [Hardt, Recht & Singer,
2016].
• Path-SGD [Neyshabur et al., 2015].
• And more [Rifai et al., 2011], [Salimans & Kingma, 2016], [Sun et
al, 2016].
74
 A SAMPLE OF GE BOUNDS
• Using the VC dimension it can be shown that

log 𝐿
GE ≤ 𝑂 DNN params ∙
𝐿

[Shalev-Shwartz and Ben-David, 2014].

• The GE was bounded also by the DNN weights
1 𝐾
GE ≤ 2 𝑤 2 𝑋 𝑖 2,2
𝐿 𝑖
[Neyshabur et al., 2015].
•
75
 A SAMPLE OF GE BOUNDS
• Using the VC dimension it can be shown that

log 𝐿
GE ≤ 𝑂 DNN params ∙
𝐿

[Shalev-Shwartz and Ben-David, 2014].

• The GE was bounded also by the DNN weights
1 𝐾
GE ≤ 2 𝑤 2 𝑋 𝑖 2,2
𝐿 𝑖
[Neyshabur et al., 2015].
• Note that in both cases the GE grows with the depth

76
 DNN INPUT MARGIN
• Theorem 6: If for every input margin 𝛾𝑖𝑛 𝑉 𝑖 > 𝛾
then 𝐺𝐸 ≤ 𝑁𝛾/2 (Υ) 𝐿 [Sokolic, Giryes, Sapiro,
Rodrigues, 2016]
• 𝑁𝛾/2 (Υ) is the covering number of the data Υ.
• 𝑁𝛾/2 (Υ) gets smaller as 𝛾 gets larger.
• Bound is independent of depth.
• Our theory relies on the 𝑉𝑖

𝑉𝑖
robustness framework
[Xu & Mannor, 2012].
77
 INPUT MARGIN BOUND
• Maximizing the input margin directly is hard
• Our strategy: relate the input margin to the output
margin 𝛾𝑜𝑢𝑡 𝑉 𝑖 and other DNN properties
• Theorem 7:
𝛾𝑜𝑢𝑡 𝑉 𝑖
𝛾𝑖𝑛 𝑉 𝑖 ≥ 𝑉
sup 𝐽 𝑉
𝑉∈Υ 𝑉 2 2
𝛾𝑜𝑢𝑡 𝑉 𝑖
≥ 𝑖
1≤𝑖≤𝐾 𝑋 2

𝛾𝑜𝑢𝑡 𝑉 𝑖
≥ 𝑉𝑖
1≤𝑖≤𝐾 𝑋𝑖 𝐹 Φ(𝑉 𝑖 )
[Sokolic, Giryes, Sapiro,
78
Rodrigues, 2016]
 OUTPUT MARGIN
𝛾𝑜𝑢𝑡 𝑉 𝑖
• Theorem 7: 𝛾𝑖𝑛 𝑉 𝑖 ≥ 𝑉
sup 𝐽 𝑉
𝑉∈Υ 𝑉 2 2
𝛾𝑜𝑢𝑡 𝑉 𝑖 𝛾𝑜𝑢𝑡 𝑉𝑖
≥ ≥
1≤𝑖≤𝐾 𝑋𝑖 2 1≤𝑖≤𝐾 𝑋 𝑖
𝐹

• Output margin is easier to

maximize – SVM problem
• Maximized by many cost
functions, e.g., hinge loss.
𝑉𝑖
Φ(𝑉 𝑖 )

79
 GE AND WEIGHT DECAY
𝛾𝑜𝑢𝑡 𝑉 𝑖
• Theorem 7: 𝛾𝑖𝑛 𝑉 𝑖 ≥ 𝑉
≥
sup 𝐽 𝑉
𝑉∈Υ 𝑉 2 2
𝛾𝑜𝑢𝑡 𝑉𝑖 𝛾𝑜𝑢𝑡 𝑉𝑖
≥
1≤𝑖≤𝐾 𝑋𝑖 2 1≤𝑖≤𝐾 𝑋 𝑖
𝐹

• Bounding the weights

increases the input margin
• Weight decay regularization
decreases the GE
• Related to regularization used 𝑉𝑖
by [Haeffele & Vidal, 2015] Φ(𝑉 𝑖 )

80
 JACOBIAN BASED REGULARIZATION
𝛾𝑜𝑢𝑡 𝑉 𝑖
• Theorem 7: 𝛾𝑖𝑛 𝑉 𝑖 ≥ 𝑉
≥
sup 𝐽 𝑉
𝑉∈Υ 𝑉 2 2
𝛾𝑜𝑢𝑡 𝑉𝑖 𝛾𝑜𝑢𝑡 𝑉𝑖
≥
1≤𝑖≤𝐾 𝑋𝑖 2 1≤𝑖≤𝐾 𝑋 𝑖
𝐹

• 𝐽 𝑉 is the Jacobian of the

DNN at point 𝑉.
• 𝐽 ∙ is piecewise constant.
• Using the Jacobian of the
DNN leads to a better bound.
• New regularization technique.
81
 RESULTS
• Better performance with less training samples

MNIST
Dataset

• CCE: the categorical cross entropy. [Sokolic, Giryes, Sapiro,

Rodrigues, 2016]
• WD: weight decay regularization.
• LM: Jacobian based regularization for large margin.
• Note that hinge loss generalizes better than CCE and
that LM is better than WD as predicted by our theory.
82
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal DNN as Random

of training: Gaussian
Classify the Metric weights are
boundary points good for
between the Learning classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 83
 ASSUMPTIONS

𝑽 ∈ ℝ𝒅 𝑿𝟏 𝝍 𝑿𝟐 𝝍 𝑽

𝑋 is fully 𝝍 is the
connected hyperbolic tan
and trained

84
 METRIC LEARNING BASED TRAINING

𝑽𝒊 ∈ ℝ 𝒅
𝑿 𝟏 𝑉𝑋 𝝍 𝑿𝟐 𝝍 𝑽𝒊

• Cosine Objective:
2
𝑇
𝑉𝑖 𝑉𝑗
min
1 2
− 𝜗𝑖,𝑗
𝑋 ,𝑋 𝑉𝑖 𝑉𝑗
𝑖,𝑗∈𝑇𝑟𝑎𝑖𝑛𝑖𝑛𝑔 𝑆𝑒𝑡
Classification Metric
term preservation term

𝑉𝑖 𝑇 𝑉𝑗
𝜆 + (1 − 𝜆) 𝑖, 𝑗 ∈ 𝑠𝑎𝑚𝑒 𝑐𝑙𝑎𝑠𝑠
𝜗𝑖,𝑗 = 𝑉𝑖 𝑉𝑗
−1 𝑖, 𝑗 ∈ 𝑑𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑡 𝑐𝑙𝑎𝑠
85
 METRIC LEARNING BASED TRAINING

𝑽𝒊 ∈ ℝ 𝒅 𝑿 𝟏 𝑉𝑋 𝝍 𝑿𝟐 𝝍 𝑽𝒊
𝒔𝒂𝒎𝒆 𝒂𝒗𝒆𝒓𝒂𝒈𝒆 𝒊𝒏𝒕𝒓𝒂 𝒔𝒂𝒎𝒆
𝟏 𝒊, 𝒋 ∈ 𝒊, 𝒋 ∈
𝒄𝒍𝒂𝒔𝒔
𝒍𝒊𝒋 =
𝒄𝒍𝒂𝒔𝒔 𝒍𝒊𝒋 = 𝒄𝒍𝒂𝒔𝒔 𝒅𝒊𝒔𝒕𝒂𝒏𝒄𝒆
𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒕 𝒂𝒗𝒆𝒓𝒂𝒈𝒆 𝒊𝒏𝒕𝒆𝒓 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒕
−𝟏 𝒊, 𝒋 ∈ 𝒊, 𝒋 ∈
𝒄𝒍𝒂𝒔𝒔 𝒄𝒍𝒂𝒔𝒔 𝒅𝒊𝒔𝒕𝒂𝒏𝒄𝒆 𝒄𝒍𝒂𝒔𝒔

• Euclidean Objective:
𝜆
𝑇𝑟𝑎𝑖𝑛𝑖𝑛𝑔
𝒍𝒊𝒋 𝑉𝑖 − 𝑉𝑗 − 𝒕𝒊𝒋
+
𝑆𝑒𝑡 𝑖,𝑗∈𝑇𝑟𝑎𝑖𝑛𝑖𝑛𝑔 Classification term
𝑆𝑒𝑡
min
1 2
𝑋 ,𝑋 1−𝜆
+ 𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟𝑠 𝑉𝑖 − 𝑉𝑗 − 𝑉𝑖 − 𝑉𝑗
𝑉𝑖 ,𝑉𝑗 𝑎𝑟𝑒 Metric learning term
𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑢𝑟𝑠
86
 ROBUSTNESS OF THIS NETWORK
• Metric learning objectives impose stability
• Similar to what we have in the random case
• Close points at the input are close at the output
• Using the theory of 𝑇, 𝜖 -robustness [Xu & Mannor,
2012], the generalization error scales as
𝑇
𝐿
• 𝑇 is the covering number and 𝐿 = Training set .
• Also here, the number of training samples scales as
exp(𝜔2 Υ /𝜀 2 ) .
87
 RESULTS
• Better performance with less training samples
#Training/class 30 50 70 100
original pixels 81.91% 86.18% 86.86% 88.49%
MNIST
LeNet 87.51% 89.89% 91.24% 92.75%
Dataset
Proposed 1 92.32% 94.45% 95.67% 96.19%
Proposed 2 94.14% 95.20% 96.05% 96.21%

[Huang, Qiu, Sapiro,

Calderbank, 2015]
Faces in
the wild
ROC curve

88
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal Minimiza Random

of training: Gaussian
Classify the tion by weights are
boundary points good for
between the DNN classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 89
 ASSUMPTIONS
Linear
operators 𝑺

𝑽 ∈ ℝ𝒅 𝑿 + 𝝍 𝒁

𝑽 = 𝒁𝑨 + 𝑬
𝜓 is a An estimate
linear noise
𝒁∈𝜰 operator projection of 𝑍
onto 𝛶
90
 ℓ0 -MINIMIZATION
Iterative hard
𝑻 𝜇 is the
thresholding 𝑰 − 𝝁𝑨𝑨
step size
algorithm (IHT)

𝑽 ∈ ℝ𝒅 𝝁𝑨𝑻 + 𝝍 𝒁

𝑉 = 𝑍𝐴 + 𝐸 A k-sparse
𝜓 is the hard estimate of 𝑍.
𝒁 is a thresholding Aim at solving
k−sparse operation: keeps min 𝑉 − 𝑍𝐴
vecotr the largest 𝑍

k entries 𝑠. 𝑡 𝑍 0
≤k
91
[Blumensath & Davies, 2009]
 ℓ1 -MINIMIZATION
Projected
gradient descent 𝑰 − 𝝁𝑨𝑨 𝑻 𝜇 is the
algorithm for ℓ1 step size
minimization
𝑽 ∈ ℝ𝒅 𝝁𝑨𝑻 + 𝝍 𝒁

𝑽 = 𝒁𝑨 + 𝑬 𝜓 projects onto Estimate of 𝑍.

the ℓ1 ball Aim at solving
𝒁 𝟏 ≤𝑹 𝑹 min 𝑉 − 𝑍𝐴
−𝑹 𝑹 𝑍
𝑠. 𝑡 𝑍 1
≤𝑅
−𝑹 92
 UNCONSTRAINED ℓ1 -MINIMIZATION
Iterative soft
𝑻 𝜇 is the
thresholding 𝑰 − 𝝁𝑨𝑨
step size
algorithm (ISTA)

𝑽 ∈ ℝ𝒅 𝝁𝑨𝑻 + 𝝍 𝒁
Soft
Step size 𝜇 obeys thresholding
1
𝜇
≥ 𝐴 operation
- 𝝀𝝁 𝝀𝝁
Minimizer of
𝒎𝒊𝒏 𝑽 − 𝒁𝑨 + 𝝀 𝒁 𝟏
𝑽 = 𝒁𝑨 + 𝑬 𝒁
[Daubechies, Defrise & Mol, 2004],
93
[Beck & Teboulle, 2009]
 ISTA CONVERGENCE
• Reconstruction mean squared error (MSE) as a
function of the number of iterations
𝑬 𝒁 − 𝒁𝒕

𝒕 94
 LEARNED ISTA (LISTA)
Learned
linear 𝑺
operators

𝑽 ∈ ℝ𝒅 𝑿 + 𝝍 𝒁

Soft
𝑽 = 𝒁𝑨 + 𝑬
thresholding An estimate
operation of 𝒁
𝒁∈𝜰 -𝝀 𝝀
[Gregor & LeCun, 2010]

95
 LISTA CONVERGENCE
• Replacing 𝐼 − 𝜇𝐴𝐴𝑇 and 𝜇𝐴𝑇 in ISTA with the learned
𝑋 and 𝑆 improves convergence [Gregor & LeCun, 2010]
𝐸 𝑍 − 𝑍𝑡

𝑬 𝒁 − 𝒁𝒕

100
20
20 50
𝒕
• Extensions to other models [Sprechmann, Bronstein & Sapiro, 2015],
[Remez, Litani & Bronstein, 2015], [Tompson, Schlachter, Sprechmann & Perlin, 2016].
96
 PROJECTED GRADIENT DESCENT (PGD)
𝑻 𝜇 is the
𝑰 − 𝝁𝑨𝑨
step size

𝑽 ∈ ℝ𝒅 𝝁𝑨𝑻 + 𝝍 𝒁

𝑽 = 𝒁𝑨 + 𝑬 𝝍 projects onto Estimate of 𝒁.

the set 𝜰 Aim at solving
𝒇(𝒁) ≤ 𝑹
𝒎𝒊𝒏 𝑽 − 𝒁𝑨
𝒇(𝒁) ≤ 𝑹 𝒁
𝒔. 𝒕. 𝒇(𝒁) ≤ 𝑹
97
 THEORY FOR PGD
• Theorem 8: Let 𝑍 ∈ ℝ𝑑 , 𝑓: ℝ𝑑 → ℝ a proper
function, 𝑓 𝑍 ≤ 𝑅, 𝐶𝑓 (𝑥) the tangent cone of 𝑓
at point 𝑥, 𝐴 ∈ ℝ𝑑×𝑚 a random Gaussian matrix
and 𝑉 = 𝑍𝐴 + 𝐸. Then the estimate of PGD at
iteration 𝑡, 𝑍 𝑡 , obeys
𝑡 𝑡
𝑍 − 𝑍 ≤ 𝜅𝑓 𝜌 𝑍 ,
where 𝜌 = sup 𝑈 𝐼 − 𝜇𝐴𝐴𝑇 𝑊 𝑇
𝑈,𝑊∈𝐶𝑓 𝑥 ∩ℬ𝑑
and 𝜅𝑓 = 1 if 𝑓 is convex and 𝜅𝑓 = 2 otherwise.
[Oymak, Recht & Soltanolkotabi, 2016].
98
 PGD CONVERGENCE RATE
• 𝜌= sup 𝑈 𝐼 − 𝜇𝐴𝐴𝑇 𝑊 𝑇 is the
𝑈,𝑊∈𝐶𝑓 𝑥 ∩ℬ𝑑
convergence rate of PGD.
• Let 𝜔 be the Gaussian mean width of 𝐶𝑓 𝑥 ∩ ℬ 𝑑 .
1 1 𝑚−𝜔
• If 𝜇 = 2 ≃ then 𝜌 = 1 − 𝑂 .
𝑚+ 𝑑 𝑑 𝑚+𝑑
1 𝜔
• If 𝜇 = then 𝜌 = 𝑂 .
𝑚 𝑚
• For the 𝑘-sparse model 𝜔2 = 𝑂 𝑘log d
• For GMM with 𝑘 Gaussians 𝜔2 = 𝑂 𝑘 .
• How may we cause 𝜔 to become smaller for having a
better convergence rate?
99
 INACCURATE PROJECTION
• PGD iterations projects onto Υ = 𝑍: 𝑓 𝑍 ≤ 𝑅 .
• Smaller Υ ⇒ Smaller 𝜔. 𝜰
⇒Faster convergence as 𝒇(𝒁) ≤ 𝑹
𝑚−𝜔 𝜔
𝜌=1−𝑂 or 𝑂
𝑚+𝑑 𝑚
• Let us assume that our signal belongs to a smaller set
Υ = 𝑍: 𝑓 𝑍 ≤ 𝑅 with 𝜔 ≪ 𝜔. 𝜰
• Ideally, we would like to project 𝒇(𝒁) ≤ 𝑹
onto Υ instead of Υ.
• This will lead to faster convergence.
• What if such a projection is not feasible?
100
 INACCURATE PROJECTION

• We will estimate the projection onto Υ by

• A linear projection 𝑃
• Followed by a projection onto Υ
• Assumptions: 𝒇(𝒁) ≤ 𝑹

• 𝑃(𝑍)−𝑍 ≤ ϵ
• ℘𝐶𝑓(𝑍) (𝑈)−℘𝐶𝑓(𝑍𝑃) (𝑈𝑃) ≤ ϵ, ∀𝑈 ∈ ℝ𝑑

Projection of 𝑈 onto the Projection of 𝑈𝑃 onto the

tangent cone of 𝑓 at point 𝑍 tangent cone of 𝑓 at point 𝑍𝑃
101
 INACCURATE PGD (IPGD)
𝑻 𝜇 is the
𝑰 − 𝝁𝑨𝑨 𝑷
step size

𝑽 ∈ ℝ𝒅 𝝁𝑨𝑻 𝑷 + 𝝍 𝒁

𝑽 = 𝒁𝑨 + 𝑬 𝝍 projects onto Estimate of 𝑍.

𝜰 the set Υ Aim at solving
𝒇(𝒁) ≤ 𝑹 𝒎𝒊𝒏 𝑽 − 𝒁𝑨
𝒇(𝒁) ≤ 𝑹 𝒁
𝒔. 𝒕. 𝒇(𝒁) ≤ 𝑹
102
 THEORY FOR IPGD
• Theorem 9: Let 𝑍 ∈ ℝ𝑑 , 𝑓: ℝ𝑑 → ℝ a proper function,
𝑓 𝑍 ≤ 𝑅, 𝐶𝑓 (𝑥) the tangent cone of 𝑓 at point 𝑥, 𝐴
∈ ℝ𝑑×𝑚 a random Gaussian matrix and 𝑉 = 𝑍𝐴 + 𝐸.
Then the estimate of IPGD at iteration 𝑡, 𝑍 𝑡 , obeys
𝑍𝑡 − 𝑍
𝑡
𝑡 1 − 𝜅𝑓 𝜌 + 𝜖𝛾
≤ 𝜅𝑓 𝜌 + 𝜖𝛾 + 𝜖 𝑍 ,
1 − 𝜅𝑓 𝜌 + 𝜖𝛾
where 𝜌 = sup 𝑈 𝐼 − 𝜇𝐴𝐴𝑇 𝑊 𝑇
𝑈,𝑊∈𝐶𝑓 𝑥 ∩ℬ𝑑
𝛾= 𝐼− 𝜇𝐴𝐴𝑇 and 𝜅𝑓 as in Theorem 8.
[Giryes, Eldar, Bronstein & Sapiro, 2016] 103
 CONVERGENCE RATE COMPARISON
• PGD convergence:
𝑡
𝜅𝑓 𝜌
• IPGD convergence:
𝑡
𝑡 1 − 𝜅𝑓 𝜌 + 𝜖𝛾
𝜅𝑓 𝜌 + 𝜖𝛾 + 𝜖
1 − 𝜅𝑓 𝜌 + 𝜖𝛾
(𝑎) (𝑏)
𝑡
≃ 𝜅𝑓 𝜌 + 𝜖 ≪ 𝜅𝑓 𝜌 𝑡
(a) assuming that 𝜖 is negligible compared to 𝜌.
(b) For small values of 𝑡 (early iterations).
• Faster convergence since 𝜌 ≪ 𝜌 (because 𝜔 ≪ 𝜔).
104
 MODEL BASED COMPRESSED SENSING
• Υ is the set of sparse vectors with sparsity patterns
that obey a tree structure.
• Projecting onto Υ improves convergence 1

rate compared to projecting onto the set

of sparse vectors Υ [Baraniuk et al., 2010]. 0.5 0.5

• The projection onto Υ is more

demanding than onto Υ. 0.25 0.25 0.25 0.25

• Note that the probability of selecting atoms from

lower tree levels is smaller than upper ones.
• 𝑃 will be a projection onto certain tree levels – zeroing
the values at lower levels.
105
MODEL BASED COMPRESSED SENSING
Non-zeros picked
entries has zero mean
random Gaussian
distribution with
variance:
- 1 at first two levels
- 0.12 at the third level
- 0.012 at the rest of
the levels

106
 SPECTRAL COMPRESSED SENSING

• Υ is the set of vectors with sparse representation

in a 4-times redundant DCT dictionary such that:
• The active atoms are selected uniformly at random such that
minimum distance between neighboring atoms is 5.
• The value of each representation coefficient ~𝑁(0,1) i.i.d.
• We set the neighboring coefficients at distance 1 and 2 of each
active atom to be ~𝑁(0,0.12 ) and ~𝑁(0,0.012 ) , respectively
• We set 𝑃 to be a pooling-like operation that keeps
in each window of size 5 only the largest value.
107
SPECTRAL COMPRESSED SENSING

108
 LEARNING THE PROJECTION
• If we have no explicit information about Υ it might
be desirable to learn the projection.
• Instead of learning 𝑃, it is possible to replace
𝐼 − 𝜇𝐴𝐴𝑇 𝑃 and 𝜇𝐴𝑇 𝑃 with two learned matrices
𝑆 and 𝑋 respectively.
• This leads to a very similar scheme to the one of
LISTA and provides a theoretical foundation for the
success of LISTA.

109
 LEARNED IPGD
Learned
linear 𝜇 is the
𝑺
operators step size

𝑽 ∈ ℝ𝒅 𝑿 + 𝝍 𝒁

𝝍 projects onto Estimate of 𝒁.

𝑽 = 𝒁𝑨 + 𝑬
the set 𝜰 Aim at solving
𝜰
𝒇(𝒁) ≤ 𝑹
𝒎𝒊𝒏 𝑽 − 𝒁𝑨
𝒇(𝒁) ≤ 𝑹 𝒁
𝒔. 𝒕. 𝒇(𝒁) ≤ 𝑹
110
 LISTA
Learned
linear 𝜇 is the
𝑺
operators step size

𝑽 ∈ ℝ𝒅 𝑿 + 𝝍 𝒁

𝜓 is a proximal
𝑽 = 𝒁𝑨 + 𝑬 mapping. Estimate of 𝒁.
Aim at solving
𝜰 𝝍 𝑼 =
𝒇(𝒁) ≤ 𝑹
𝒎𝒊𝒏 𝑽 − 𝒁𝑨
𝐚𝐫𝐠𝐦𝐢𝐧 𝑼 − 𝒁 𝒁
𝒁∈ℝ𝒅 +𝝀𝒇(𝒁)
+𝝀𝒇(𝒁) 111
 LISTA MIXTURE MODEL
• Approximation of the projection onto Υ
Υ
with one linear projection may not
be accurate enough.
• This requires more LISTA layers/iterations.
• Instead, one may use several LISTA networks,
where each approximates a different part of Υ
• Training 18 LISTA networks, each with Υ
3 layers, provides the same accuracy
like 1 LISTA network with 10 layers.
112
 RELATED WORKS
• In [Bruna et al. 2016] a different route it taken to
explain the faster convergence of LISTA. It is shown
that a learning may give a gain due to better
preconditioning of A.

113
 DNN keep Gaussian mean
the width is a good
important measure for the
information complexity of
of the data. the data.

Important goal Take Random

of training: Gaussian
Classify the Home weights are
boundary points good for
between the Message classifying the
different classes average points
in the data. in the data.

DNN may Generalization

solve Deep learning error depends
optimization can be viewed on the DNN
problems as a metric input margin
learning. 114
 ACKNOWLEDGEMENTS

Yonina C. Eldar Guillermo Sapiro Robert Calderbank René Vidal Miguel Rodrigues
Technion Duke University Duke University Johns Hopkins UCL

Alex M. Bronstein Joan Bruna Qiang Qiu Jiaji Huang Jure Sokolic
Technion NYU Duke University Baidu SVAIL UCL
115
QUESTIONS?

[Link]/~RAJA

116
 FULL REFERENCES 1
• A. L. Samuel, “Some studies in machine learning using the game of checkers,” IBM Journal, vol. 3, no. 3, pp.
535–554, 1959.
• D. H. Hubel & T. N. Wiesel, “Receptive fields of single neurones in the cat's striate cortex”, J Physiol., vol. 148,
no. 3, pp. 574-591, 1959.
• D. H. Hubel & T. N. Wiesel, “Receptive fields, binocular interaction and functional architecture in the cat's
visual cortex”, J Physiol., vol. 160, no. 1, pp. 106-154, 1962.
• K. Fukushima, “Neocognitron: A self-organizing neural network model for a mechanism of pattern
recognition unaffected by shift in position”, Biological Cybernetics, vol. 36, no. 4, pp. 93-202, 1980.
• Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard & L. D. Jackel, “Backpropagation
Applied to Handwritten Zip Code Recognition”, Neural Computation, vol. 1, no. 4, pp. 541-551, 1989.
• [Link], L. Bottou, Y. Bengio & P. Haffner, “Gradient Based Learning Applied to Document Recognition”,
Proceedings of IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
• C. Farabet, C. Couprie, L. Najman & Y. LeCun, “Learning Hierarchical Features for Scene Labeling,” IEEE
Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 35, no. 8, pp. 1915-1929, Aug. 2013.
• O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A.
C. Berg, L. Fei-Fei, “ImageNet Large Scale Visual Recognition Challenge”, International Journal of Computer
Vision, vol. 115, no. 3, pp. 211-252, 2015
• A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet classification with deep convolutional neural
networks”, NIPS, 2012.
• K. He, X. Zhang, S. Ren, and J. Sun. “Deep residual learning for image recognition”, CVPR, 2016.

117
 FULL REFERENCES 2
• M.D. Zeiler, R. Fergus, “Visualizing and Understanding Convolutional Networks”, ECCV, 2014.
• D. Yu and L. Deng, “Automatic Speech Recognition: A Deep Learning Approach”, Springer, 2014.
• J. Bellegarda & C. Monz, “State of the art in statistical methods for language and speech processing,”
Computer Speech and Language, vol. 35, pp. 163–184, Jan. 2016.
• C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, “Going
Deeper with Convolutions”, CVPR, 2015.
• V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra & M. Riedmiller, “Playing Atari with
Deep Reinforcement Learning”, NIPS deep learning workshop, 2013.
• V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K.
Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S.
Legg & D. Hassabis, “Human-level control through deep reinforcement learning”, Nature vol. 518, pp. 529–
533, Feb. 2015.
• D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V.
Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M.
Leach, K. Kavukcuoglu, T. Graepel & D. Hassabis, “Mastering the Game of Go with Deep Neural Networks and
Tree Search”, Nature, vol. 529, pp. 484–489, 2016.
• S. K. Zhou, H. Greenspan, D. Shen, “Deep Learning for Medical Image Analysis”, Academic Press, 2017.
• I. Sutskever, O. Vinyals & Q. Le, “Sequence to Sequence Learning with Neural Networks”, NIPS 2014.
• A. Karpathy, G. Toderici, S. Shetty, T. Leung, R. Sukthankar, L. Fei-Fei, “Large-scale Video Classification with
Convolutional Neural Networks”, CVPR, 2014.

118
 FULL REFERENCES 3
• F. Schroff, D. Kalenichenko & J. Philbin, “FaceNet: A Unified Embedding for Face Recognition and Clustering”,
CVPR, 2015.
• A. Poznanski & L. Wolf, “CNN-N-Gram for Handwriting Word Recognition”, CVPR, 2016.
• R. Socher, A. Perelygin, J. Wu, J. Chuang, C. Manning, A. Ng & C. Potts, “Recursive Deep Models for Semantic
Compositionality Over a Sentiment Treebank, EMNLP, 2013.
• H. C. Burger, C. J. Schuler & S. Harmeling, Image denoising: Can plain Neural Networks compete with BM3D?,
CVPR, 2012.
• J. Kim, J. K. Lee, K. M. Lee, “Accurate Image Super-Resolution Using Very Deep Convolutional Networks”,
CVPR, 2016.
• J, Bruna, P. Sprechmann, and Y. LeCun, “Super-Resolution with Deep Convolutional Sufficient Statistics”, ICLR,
2016.
• V. Nair and G. E. Hinton, “Rectified linear units improve restricted Boltzmann machines”, ICML, 2010.
• L. Deng & D. Yu, “Deep Learning: Methods and Applications”, Foundations and Trends in Signal Processing,
vol. 7 no. 3-4, pp. 197–387, 2014.
• Bengio, Yoshua, “Learning Deep Architectures for AI”, Foundations and Trends in Machine Learning, vol. 2,
no. 1, pp. 1–127, 2009.
• Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. Nature, vol. 521, no. 7553, pp. 436–444, 2015.
• J. Schmidhuber, “Deep learning in neural networks: An overview”, Neural Networks, vol. 61, pp. 85–117, Jan.
2015.
• I. Goodfellow, Y. Bengio & A. Courville, “Deep learning”, Book in preparation for MIT Press, 2016.

119
 FULL REFERENCES 4
• G. Cybenko, “Approximation by superpositions of a sigmoidal function,” Math. Control Signals Systems, vol. 2,
pp. 303–314, 1989.
• K. Hornik, “Approximation capabilities of multilayer feedforward networks,” Neural Netw., vol. 4, no. 2, pp.
251–257, 1991.
• A. R. Barron, Approximation and estimation bounds for artificial neural networks, Machine Learning, vol. 14,
no. 1, pp. 115–133, Jan. 1994.
• G. F. Montu ́faar & J. Morton, “When does a mixture of products contain a product of mixtures”, SIAM Journal
on Discrete Mathematics (SIDMA), vol. 29, no. 1, pp. 321-347, 2015.
• G. F. Montu ́faar, R. Pascanu, K. Cho, & Y. Bengio, “On the number of linear regions of deep neural networks,”
NIPS, 2014.
• N. Cohen, O. Sharir & A. Shashua, “Deep SimNets,” CVPR, 2016.
• N. Cohen, O. Sharir & A. Shashua, “On the Expressive Power of Deep Learning: A Tensor Analysis,” COLT, 2016.
• N. Cohen & A. Shashua, “Convolutional Rectifier Networks as Generalized Tensor Decompositions,” ICML, 2016
• M. Telgarsky, “Benefits of depth in neural networks,” COLT, 2016.
• N. Cohen and A. Shashua, “Inductive Bias of Deep Convolutional Networks through Pooling Geometry,” arXiv
abs/ 1605.06743, 2016.
• J. Bruna, Y. LeCun, & A. Szlam, “Learning stable group invariant representations with convolutional networks,”
ICLR, 2013.
• Y-L. Boureau, J. Ponce, Y. LeCun, Theoretical Analysis of Feature Pooling in Visual Recognition, ICML, 2010.

120
 FULL REFERENCES 5
• J. Bruna, A. Szlam, & Y. LeCun, “Signal recovery from lp pooling representations”, ICML, 2014.
• S. Soatto & A. Chiuso, “Visual Representations: Defining properties and deep approximation”, ICLR 2016.
• F. Anselmi, J. Z. Leibo, L. Rosasco, J. Mutch, A. Tacchetti, and T. Poggio, “Unsupervised learning of invariant
representations in hierarchical architectures,” Theoretical Computer Science, vol. 663, no. C, pp. 112-121,
Jun. 2016.
• J. Bruna and S. Mallat, “Invariant scattering convolution networks,” IEEE Trans. Pattern Analysis and Machine
Intelligence (PAMI), vol. 35, no. 8, pp. 1872–1886, Aug 2013.
• T. Wiatowski and H. Bölcskei, “A Mathematical Theory of Deep Convolutional Neural Networks for Feature
Extraction,” arXiv abs/1512.06293, 2016
• A. Saxe, J. McClelland, and S. Ganguli, “Exact solutions to the nonlinear dynamics of learning in deep linear
neural network”, ICLR, 2014.
• Y. Dauphin, R. Pascanu, C. Gulcehre, K. Cho, S. Ganguli, and Y. Bengio, “Identifying and attacking the saddle
point problem in high dimensional non-convex optimization,” NIPS, 2014.
• A. Choromanska, M. B. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun, “The loss surfaces of multilayer
networks,” in International Conference on Artificial Intelligence and Statistics (AISTATS), 2015.
• B. D. Haeffele and R. Vidal. Global Optimality in Tensor Factorization, Deep Learning, and Beyond. arXiv,
abs/1506.07540, 2015.
• S. Arora, A. Bhaskara, R. Ge, and T. Ma, “Provable bounds for learning some deep representations,” in Int.
Conf. on Machine Learning (ICML), 2014, pp. 584–592.

121
 FULL REFERENCES 6
• A. M. Bruckstein, D. L. Donoho, & M. Elad, “From sparse solutions ofa systems ofa equations to sparse
modeling ofa signals and images”, SIAM Review, vol. 51, no. 1, pp. 34–81, 2009.
• G. Yu, G. Sapiro & S. Mallat, “Solving inverse problems with piecewise linear estimators: From Gaussian
mixture models to structured sparsity”, IEEE Trans. on Image Processing, vol. 21, no. 5, pp. 2481 –2499, May
2012.
• N. Srebro & A. Shraibman, “Rank, trace-norm and max-norm,” COLT, 2005.
• E. Cand`es & B. Recht, “Exact matrix completion via convex optimization,” Foundations ofa Computational
mathematics, vol. 9, no. 6, pp. 717– 772, 2009.
• R. G. Baraniuk, V. Cevher & M. B. Wakin, "Low-Dimensional Models for Dimensionality Reduction and Signal
Recovery: A Geometric Perspective," Proceedings of the IEEE, vol. 98, no. 6, pp. 959-971, 2010.
• Y. Plan and R. Vershynin, “Dimension reduction by random hyperplane tessellations,” Discrete and
Computational Geometry, vol. 51, no. 2, pp. 438–461, 2014.
• Y. Plan and R. Vershynin, “Robust 1-bit compressed sensing and sparse logistic regression: A convex
programming approach,” IEEE Trans. Infa. Theory, vol. 59, no. 1, pp. 482–494, Jan. 2013.
• R. Giryes, G. Sapiro and A.M. Bronstein, “Deep Neural Networks with Random Gaussian Weights: A Universal
Classifaication Strategy? “, IEEE Transactions onSignal Processing, vol. 64, no. 13, pp. 3444-3457, Jul. 2016.
• A. Choromanska, K. Choromanski, M. Bojarski, T. Jebara, S. Kumar, Y. LeCun, “Binary embeddings with
structured hashed projections”, ICML, 2016.
• J. Masci, M. M. Bronstein, A. M. Bronstein and J. Schmidhuber, “Multimodal Similarity-Preserving Hashing”,
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol. 36, no. 4, pp. 824-830, April 2014.

122
 FULL REFERENCES 7
• H. Lai, Y. Pan, Y. Liu & S. Yan, “Simultaneous Feature Learning and Hash Coding With Deep Neural Networks”,
CVPR, 2015.
• A. Mahendran & A. Vedaldi, “Understanding deep image representations by inverting them,” CVPR, 2015.
• K. Simonyan & A. Zisserman, “Very deep convolutional networks for large-scale image recognition”, ICLR, 2015
• A. Krogh & J. A. Hertz, “A Simple Weight Decay Can Improve Generalization”, NIPS, 1992.
• P. Baldi & P. Sadowski, “Understanding dropout”, NIPS, 2013.
• N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, & R. Salakhutdinov, “Dropout: A simple way to prevent
neural networks from overfitting,” Journal of Machine Learning Research, vol. 15, no. 1, pp. 1929–1958, 2014.
• L. Wan, M. Zeiler, S. Zhang, Y. LeCun & R. Fergus, “Regularization of Neural Networks using DropConnect”,
ICML, 2013.
• S. Ioffe & C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate
shift,” ICML, 2015.
• M. Hardt, B. Recht & Y. Singer, “Train faster, generalize better: Stability of stochastic gradient descent”, arXiv,
abs/1509.01240, 2016.
• B. Neyshabur, R. Salakhutdinov & N. Srebro, “Path-SGD: Path-normalized optimization in deep neural
networks,” NIPS, 2015.
• S. Rifai, P. Vincent, X. Muller, X. Glorot, & Y. Bengio. “Contractive auto-encoders: explicit invariance during
feature extraction,” ICML, 2011.

123
 FULL REFERENCES 8
• T. Salimans & D. Kingma, “Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep
Neural Networks”, arXiv abs/1602.07868, 2016.
• S. Sun, W. Chen, L. Wang, & T.-Y. Liu, “Large margin deep neural networks: theory and algorithms”, AAAI,
2016.
• S. Shalev-Shwartz & S. Ben-David. “Understanding machine learning: from theory to algorithms”, Cambridge
University Press, 2014.
• P. L. Bartlett & S. Mendelson, “Rademacher and Gaussian complexities: risk bounds and structural results”.
The Journal of Machine Learning Research (JMLR), vol 3, pp. 463–482, 2002.
• B. Neyshabur, R. Tomioka, and N. Srebro, “Norm-based capacity control in neural networks,” COLT, 2015.
• J. Sokolic, R. Giryes, G. Sapiro, M. R. D. Rodrigues, “Margin Preservation of Deep Neural Networks”, arXiv,
abs/1605.08254, 2016.
• H. Xu and S. Mannor. “Robustness and generalization,” JMLR, vol. 86, no. 3, pp. 391–423, 2012.
• J. Huang, Q. Qiu, G. Sapiro, R. Calderbank, “Discriminative Geometry-Aware Deep Transform”, ICCV 2015
• J. Huang, Q. Qiu, G. Sapiro, R. Calderbank, “Discriminative Robust Transformation Learning”, NIPS 2016.
• T. Blumensath & M.E. Davies, “Iterative hard thresholding for compressed sensing”, Appl. Comput. Harmon.
Anal, vol. 27, no. 3, pp. 265 – 274, 2009.
• I. Daubechies, M. Defrise, and C. De Mol, “An iterative thresholding algorithm for linear inverse problems
with a sparsity constraint”, Communicationson Pure and Applied Mathematics, vol. 57, no. 11, pp. 1413–
1457, 2004.

124
 FULL REFERENCES 9
• A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM
J. Img. Sci., 2(1):183–202, Mar. 2009.
• K. Gregor & Y. LeCun, “Learning fast approximations of sparse coding”, ICML, 2010.
• P. Sprechmann, A. M. Bronstein & G. Sapiro, “Learning efficient sparse and low rank models”, IEEE Trans.
Pattern Analysis and Machine Intelligence, vol. 37, no. 9, pp. 1821–1833, Sept. 2015.
• T. Remez, O. Litany, & A. M. Bronstein, “A picture is worth a billion bits: Real-time image reconstruction from
dense binary pixels”, ICCP, 2015.
• J. Tompson, K. Schlachter, P. Sprechmann & K. Perlin, “Accelerating Eulerian Fluid Simulation With
Convolutional Networks”, arXiv, abs/1607.03597, 2016.
• S. Oymak, B. Recht, & M. Soltanolkotabi, “Sharp time–data tradeoffs for linear inverse problems”,
arXiv, abs/1507.04793, 2016.
• R. Giryes, Y. C. Eldar, A. M. Bronstein, G. Sapiro, “Tradeoffs between Convergence Speed and
Reconstruction Accuracy in Inverse Problems”, arXiv, abs/1605.09232, 2016.
• R.G. Baraniuk, V. Cevher, M.F. Duarte & C. Hegde, “Model-based compressive sensing”, IEEE Trans. Inf.
Theory, vol. 56, no. 4, pp. 1982–2001, Apr. 2010.
• M. F. Duarte & R. G. Baraniuk, “Spectral compressive sensing”, Appl. Comput. Harmon. Anal., vol. 35, no. 1,
pp. 111 – 129, 2013.
• J. Bruna & T. Moreau, Adaptive Acceleration of Sparse Coding via Matrix Factorization, arXiv
abs/1609.00285, 2016.

125