Marek Karpinski, Angus Macintyre

We introduce a new method for proving explicit upper bounds on the VC

Dimension of general functional basis networks, and prove as an

application, for the first time, the VC Dimension of analog neural

networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$

to ...
more >>>

It is shown that high order feedforward neural nets of constant depth with piecewise

polynomial activation functions and arbitrary real weights can be simulated for boolean

inputs and outputs by neural nets of a somewhat larger size and depth with heaviside

gates and weights ...
more >>>

It has been known for quite a while that the Vapnik-Chervonenkis dimension

(VC-dimension) of a feedforward neural net with linear threshold gates is at

most O(w log w), where w is the total number of weights in the neural net.

We show in this paper that this bound is in ...
more >>>

Marek Karpinski, Angus Macintyre

We introduce a new method for proving explicit upper bounds

on the VC Dimension of general functional basis networks,

and prove as an application, for the first time, that the

VC Dimension of analog neural networks with the sigmoidal

activation function $\sigma(y)=1/1+e^{-y}$ ...
more >>>

Berthold Ruf

Recently one has started to investigate the

computational power of spiking neurons (also called ``integrate and

fire neurons''). These are neuron models that are substantially

more realistic from the biological point of view than the

ones which are traditionally employed in artificial neural nets.

It has turned out that the ...
more >>>

Michael Schmitt

Spiking neurons are models for the computational units in

biological neural systems where information is considered to be encoded

mainly in the temporal pattern of their activity. In a network of

spiking neurons a new set of parameters becomes relevant which has no

counterpart in traditional ...
more >>>

Pekka Orponen

We introduce a model for analog computation with discrete

time in the presence of analog noise

that is flexible enough to cover the most important concrete

cases, such as noisy analog neural nets and networks of spiking neurons.

This model subsumes the classical ...
more >>>

Eduardo D. Sontag

We consider recurrent analog neural nets where the output of each

gate is subject to Gaussian noise, or any other common noise

distribution that is nonzero on a large set.

We show that many regular languages cannot be recognized by

networks of this type, and

more >>>

Michael Schmitt

A neural network is said to be nonoverlapping if there is at most one

edge outgoing from each node. We investigate the number of examples

that a learning algorithm needs when using nonoverlapping neural

networks as hypotheses. We derive bounds for this sample complexity

in terms of the Vapnik-Chervonenkis dimension. ...
more >>>

A simple extension of standard neural network models is introduced that

provides a model for neural computations that involve both firing rates and

firing correlations. Such extension appears to be useful since it has been

shown that firing correlations play a significant computational role in

many biological neural systems. Standard ...
more >>>

Michael Schmitt

In a great variety of neuron models neural inputs are

combined using the summing operation. We introduce the concept of

multiplicative neural networks which contain units that multiply

their inputs instead of summing them and, thus, allow inputs to

interact nonlinearly. The class of multiplicative networks

comprises such widely known ...
more >>>

Robert Albin Legenstein

One of the most basic pattern recognition problems is whether a

certain local feature occurs in some linear array to the left of

some other local feature. We construct in this article circuits that

solve this problem with an asymptotically optimal number of

threshold gates. Furthermore it is shown that ...
more >>>

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give the first-ever polynomial time (in the size of data) algorithm to train to global optimality a ReLU DNN with one hidden layer, assuming the input dimension and number ... more >>>

Anirbit Mukherjee, Amitabh Basu

Motivated by the resurgence of neural networks in being able to solve complex learning tasks we undertake a study of high depth networks using ReLU gates which implement the function $x \mapsto \max\{0,x\}$. We try to understand the role of depth in such neural networks by showing size lowerbounds against ... more >>>

Gal Vardi, Ohad Shamir

In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths $2$ and $3$, and achieving results for higher depths has been ... more >>>

Songhua He, Periklis Papakonstantinou

Deep neural networks are the dominant machine learning model. We show that this model is missing a crucial complexity parameter. Today, the standard neural network (NN) model is a circuit whose gates (neurons) are ReLU units. The complexity of a NN is quantified by the depth (number of layers) and ... more >>>