A Relaxation Argument for Optimization in Neural Networks and Non-Convex Compressed Sensing

2020/02/03 by Gerrit Welper, G. Welper, Welper, G. · 1 citation
Chemistry · Computer Science · Engineering · Mathematics · Neuroscience · Psychology · #68T05 #90C26 #94A12 #Analog and Mixed-Signal Circuit Design #Argument (complex analysis) #Artificial intelligence #Artificial neural network #CCD and CMOS Imaging Sensors #Chemistry #Compressed sensing #Computer science #Convex optimization #FOS: Mathematics #Geometry #Mathematical optimization #Mathematics #Neuroscience #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Psychology #Regular polygon #Relaxation (psychology) #Sparse and Compressive Sensing Techniques #cs.NA #math.NA #math.OC #msc:68T05 #msc:90C26 #msc:94A12

paper · pdf · doi:10.48550/arxiv.2002.00516

published in arXiv (Cornell University) (Cornell University)

arxiv created 2020/02/03 · openalex publication_date 2020/02/03 · arxiv updated 2020/02/06 · openalex created_date 2020/02/07 · openalex updated_date 2026/07/28

Abstract

It has been observed in practical applications and in theoretical analysis that over-parametrization helps to find good minima in neural network training. Similarly, in this article we study widening and deepening neural networks by a relaxation argument so that the enlarged networks are rich enough to run r copies of parts of the original network in parallel, without necessarily achieving zero training error as in over-parametrized scenarios. The partial copies can be combined in r^θ possible ways for layer width θ. Therefore, the enlarged networks can potentially achieve the best training error of r^θ random initializations, but it is not immediately clear if this can be realized via gradient descent or similar training methods. The same construction can be applied to other optimization problems by introducing a similar layered structure. We apply this idea to non-convex compressed sensing, where we show that in some scenarios we can realize the r^θ times increased chance to obtain a global optimum by solving a convex optimization problem of dimension rθ.

Citations

• Topics in Optimal Transportation
• Sparse Approximate Solutions to Linear Systems
• Iteratively reweighted least squares minimization for sparse recovery
• Stable signal recovery from incomplete and inaccurate measurements
• Iteratively reweighted algorithms for compressive sensing
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Learning Overparameterized Neural Networks via Stochastic Gradient\n Descent on Structured Data
• Restricted Isometry Property under High Correlations

Related

• Optimization Over Trained Neural Networks: Taking a Relaxing Walk
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• Mollifying Networks
• Why Learning of Large-Scale Neural Networks Behaves Like Convex Optimization
• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time