Nonlinearities and Random Projections

Suresh just mentioned the following:

  If you want any hope of understanding the complexity of deep learning, you need to confront threshold circuits (circuits made from threshold gates). These are notoriously hard to deal with, and in many ways represent the limit of what's learnable. Daniel Kane and +Ryan Williams have a new preprint out with lower bounds for depth 2 and depth 3 threshold circuits. 

At about the same time, on twitter, Laurent asked the following:

Do you know other trendy non-linear random signatures, as the random Fourier features of Rahimi and Recht? i.e., combined with a rand proj?

— Laurent Jacques (@jacquesdurden) December 2, 2015

He added: "Rand. Proj. *with* non-linear operation, eg ". I usually list these under the nonlinearCS tag but I am not consistent. Laurent then mentioned the ones he had in mind:

• 1-bit/QCS, 
• random Fourier feature (cosine+RP), 
• universal QCS (modulo+RP) - also here -

I mentioned that

• the ELM papers generally include some sigmoid and tanh nonlinear functions.
• we recently used the modulus of complex random projections
• and then there was also the random quadratic sketch

Petros pointed out to his recent work

• Universal Embeddings, and more general designswith connections w/ Kernels

Nikhil pointed out the

• random maclaurin features of Kar and Karnik for polynomials

 Here is the paper mentioned by Suresh at the beginning of the post:

Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits by Daniel M. Kane, Ryan Williams

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function.
∙ We prove that for all ϵ≫log(n)/n−−−−−−−√, the linear-time computable Andreev's function cannot be computed on a (1/2+ϵ)-fraction of n-bit inputs by depth-two linear threshold circuits of o(ϵ3n3/2/log3n) gates, nor can it be computed with o(ϵ3n5/2/log7/2n) wires. This establishes an average-case ``size hierarchy'' for threshold circuits, as Andreev's function is computable by uniform depth-two circuits of o(n3) linear threshold gates, and by uniform depth-three circuits of O(n) majority gates.
∙ We present a new function in P based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two linear threshold circuits with o(n3/2/log3n) gates, nor with o(n5/2/log7/2n) wires.
∙ We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits.
The key is a new random restriction lemma for linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.

Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Southwest Research Institute
The Mountainous Shoreline of Sputnik Planum
Release Date: December 4, 2015
Keywords: LORRI, Pluto

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.