Return to Answer

That is a very deep question. There was series of papers recently with proof of convergence of gradient descent for overparameterized deep network (for example, Gradient Descent Finds Global Minima of Deep Neural Networks, A Convergence Theory for Deep Learning via Over-Parameterization or Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks). All of them condition proof on random Gaussian distribution of weights. It's importance for proofs depend on two factors:

1. Random weights make ReLU statistically compressive mapping (up to linear transformation)

2. Random weights preserve separation of input for any input distribution - that is if input samples are distinguishable network propagation will not make them indistinguishable

Those properties very difficult to reproduce with deterministic matrices, and even if they are reproducible with deterministic matrices NULL-space (domain of adversarial examples) would likely make method impractical, and more important preservation of those properties during gradient descent would likely make method impractical. But overall it's very difficult but not impossible, and may warrant some research in that direction. In analogous situation, there were some results for Restricted Isometry Property for deterministic matrices in compressed sensing.

That is a very deep question. There was series of papers recently proving the convergence of gradient descent for overparameterized deep networks (for example, Gradient Descent Finds Global Minima of Deep Neural Networks, A Convergence Theory for Deep Learning via Over-Parameterization or Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks). All of the proofs assume that the initial weights are assigned randomly according to a Gaussian distribution. The main reasons this initial distribution is important for the proofs are:

1. Random weights make the ReLU operators in each layer statistically compressive mapping (up to a linear transformation).

2. Random weights preserve separation of input for any input distribution - that is if input samples are distinguishable network propagation will not make them indistinguishable.

Those properties are very difficult to reproduce with deterministically generated initial weight matrices, and even if they are reproducible with deterministic matrices NULL-space (from which we can generate adversarial examples) would likely make the method less useful in practice. More importantly, preservation of those properties during gradient descent would likely make method impractical. But overall it's very difficult but not impossible, and may warrant some research in that direction. In analogous situation, there were some results for Restricted Isometry Property for deterministic matrices in a compressed sensing.

That is a very deep question. There was series of papers recently with proof of convergence of gradient descent for overparameterized deep network (for example, Gradient Descent Finds Global Minima of Deep Neural Networks, A Convergence Theory for Deep Learning via Over-Parameterization or Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks). All of them condition proof on random Gaussian distribution of weights. It's important for proofs to consist of two factors:

1. Random weights make ReLU statistically compressive mapping (up to linear transformation)

2. Random weights preserve separation of input for any input distribution - that is if input samples are distinguishable network propagation will not make them indistinguishable

Those properties very difficult to reproduce with deterministic matrices, and even if they are reproducible with deterministic matrices NULL-space (domain of adversarial examples) would likely make method impractical, and more important preservation of those properties during gradient descent would likely make method impractical. But overall it's very difficult but not impossible, and may warrant some research in that direction. In analogous situation, there were some results for Restricted Isometry Property for deterministic matrices in compressed sensing.

That is a very deep question. There was series of papers recently with proof of convergence of gradient descent for overparameterized deep network (for example, Gradient Descent Finds Global Minima of Deep Neural Networks, A Convergence Theory for Deep Learning via Over-Parameterization or Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks). All of them condition proof on random Gaussian distribution of weights. It's importance for proofs depend on two factors:

1. Random weights make ReLU statistically compressive mapping (up to linear transformation)

2. Random weights preserve separation of input for any input distribution - that is if input samples are distinguishable network propagation will not make them indistinguishable

Those properties very difficult to reproduce with deterministic matrices, and even if they are reproducible with deterministic matrices NULL-space (domain of adversarial examples) would likely make method impractical, and more important preservation of those properties during gradient descent would likely make method impractical. But overall it's very difficult but not impossible, and may warrant some research in that direction. In analogous situation, there were some results for Restricted Isometry Property for deterministic matrices in compressed sensing.

That is a very deep question. There was series of papers recently with proof of convergence of gradient descent for overparameterized deep network ( for example Gradient Descent Finds Global Minima of Deep Neural Networks, A Convergence Theory for Deep Learning via Over-Parameterization, Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks and more) All of them condition proof on random (gaussian) distribution of weights. It's importance for proofs consist of two factors:

1. Random weights make ReLU statistically compressive mapping (up to linear transformation)

2. Random weights preserve separation of input for any input distribution - that is if input samples are distinguishable network propagation will not make them indistinguishable

Those properties very difficult to reproduce with deterministic matrices, and even if they are reproducible with deterministic matrices NULL-space (domain of adversarial examples) would likely make method impractical, and more important preservation of those properties during gradient descent would likely make method impractical. But overall it's very difficult but not impossible, and may warrant some research in that direction. In analogous situation there were some results for Restricted Isometry Property for deterministic matrices in compressed sensing

That is a very deep question. There was series of papers recently with proof of convergence of gradient descent for overparameterized deep network (for example, Gradient Descent Finds Global Minima of Deep Neural Networks, A Convergence Theory for Deep Learning via Over-Parameterization or Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks). All of them condition proof on random Gaussian distribution of weights. It's important for proofs to consist of two factors:

1. Random weights make ReLU statistically compressive mapping (up to linear transformation)

2. Random weights preserve separation of input for any input distribution - that is if input samples are distinguishable network propagation will not make them indistinguishable

Those properties very difficult to reproduce with deterministic matrices, and even if they are reproducible with deterministic matrices NULL-space (domain of adversarial examples) would likely make method impractical, and more important preservation of those properties during gradient descent would likely make method impractical. But overall it's very difficult but not impossible, and may warrant some research in that direction. In analogous situation, there were some results for Restricted Isometry Property for deterministic matrices in compressed sensing.