Benefits of depth in neural networks

Matus Telgarsky

Benefits of depth in neural networks

Matus Telgarsky

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

For any positive integer k, there exist neural networks with Θ(k³) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which can not be approximated by networks with O(k) layers unless they are exponentially large - they must possess Ω(2^k) nodes. This result is proved here for a class of nodes termed semi-algebraic gates which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: Ω(2^k³) total tree nodes are required).

Original language	English (US)
Pages (from-to)	1517-1539
Number of pages	23
Journal	Journal of Machine Learning Research
Volume	49
Issue number	June
State	Published - Jun 6 2016
Event	29th Conference on Learning Theory, COLT 2016 - New York, United States Duration: Jun 23 2016 → Jun 26 2016

Keywords

Approximation
Depth hierarchy
Neural networks
Representation

ASJC Scopus subject areas

Control and Systems Engineering
Software
Statistics and Probability
Artificial Intelligence

Cite this

@article{0374cae83a974e25be7c9734ec628710,

title = "Benefits of depth in neural networks",

abstract = "For any positive integer k, there exist neural networks with Θ(k3) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which can not be approximated by networks with O(k) layers unless they are exponentially large - they must possess Ω(2k) nodes. This result is proved here for a class of nodes termed semi-algebraic gates which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: Ω(2k3) total tree nodes are required).",

keywords = "Approximation, Depth hierarchy, Neural networks, Representation",

author = "Matus Telgarsky",

note = "Publisher Copyright: {\textcopyright} 2016 M. Telgarsky.; 29th Conference on Learning Theory, COLT 2016 ; Conference date: 23-06-2016 Through 26-06-2016",

year = "2016",

month = jun,

day = "6",

language = "English (US)",

volume = "49",

pages = "1517--1539",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

number = "June",

}

TY - JOUR

T1 - Benefits of depth in neural networks

AU - Telgarsky, Matus

PY - 2016/6/6

Y1 - 2016/6/6

N2 - For any positive integer k, there exist neural networks with Θ(k3) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which can not be approximated by networks with O(k) layers unless they are exponentially large - they must possess Ω(2k) nodes. This result is proved here for a class of nodes termed semi-algebraic gates which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: Ω(2k3) total tree nodes are required).

AB - For any positive integer k, there exist neural networks with Θ(k3) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which can not be approximated by networks with O(k) layers unless they are exponentially large - they must possess Ω(2k) nodes. This result is proved here for a class of nodes termed semi-algebraic gates which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: Ω(2k3) total tree nodes are required).

KW - Approximation

KW - Depth hierarchy

KW - Neural networks

KW - Representation

UR - http://www.scopus.com/inward/record.url?scp=85072247791&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85072247791&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85072247791

SN - 1532-4435

VL - 49

SP - 1517

EP - 1539

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

IS - June

T2 - 29th Conference on Learning Theory, COLT 2016

Y2 - 23 June 2016 through 26 June 2016

ER -

Benefits of depth in neural networks

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this