Tighter guarantees for the compressive multi-layer perceptron

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

Abstract

We are interested in theoretical guarantees for classic 2- layer feed-forward neural networks with sigmoidal activation functions, having inputs linearly compressed by random projection. Due to the speedy increase of the dimensionality of modern data sets, and the development of novel data acquisition devices in compressed sensing, a proper understanding of are the guarantees obtainable is of much practical importance. We start by analysing previous work that attempted to derive a lower bound on the target dimension to ensure low distortion of the outputs under random projection, and we find a disagreement with empirically observed behaviour. We then give a new lower bound on the target dimension that, in contrast with previous work, does not depend on the number of hidden neurons, but only depends on the Frobenius norm of the first layer weights, and in addition it holds for a much larger class of random projections. Numerical experiments agree with our finding. Furthermore, we are able to bound the generalisation error of the compressive network in terms of the error and the expected distortion of the optimal network in the original uncompressed class. These results mean that one can provably learn networks with arbitrarily large number of hidden units from randomly compressed data, as long as there is sufficient regularity in the original learning problem, which our analysis rigorously quantifies.

Details

Original languageEnglish
Title of host publicationTheory and Practice of Natural Computing
Subtitle of host publication7th International Conference, TPNC 2018 Dublin, Ireland, December 12–14, 2018 Proceedings
EditorsDavid Fagan, Carlos Martín-Vide, Michael O’Neill, Miguel A. Vega-Rodríguez
Publication statusE-pub ahead of print - 22 Nov 2018
Event7th International Conference on the Theory and Practice of Natural Computing (TPNC 2018) - Dublin, Ireland
Duration: 12 Dec 201814 Dec 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Conference on the Theory and Practice of Natural Computing (TPNC 2018)
CountryIreland
CityDublin
Period12/12/1814/12/18

Keywords

  • Error analysis, Random projection, Multi-layer perceptron