mlsanityData to 14 Oct 2026

RedEx: Beyond Fixed Representation Methods via Convex Optimization

arXiv 2401.07606 ↗First posted 15 Jan 2024cs.LG math.OC stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

Optimizing Neural networks is a difficult task which is still not well understood. On the other hand, fixed representation methods such as kernels and random features have provable optimization guarantees but inferior performance due to their inherent inability to learn the representations. In this paper, we aim at bridging this gap by presenting a novel architecture called RedEx (Reduced Expander Extractor) that is as expressive as neural networks and can also be trained in a layer-wise fashion via a convex program with semi-definite constraints and optimization guarantees. We also show that RedEx provably surpasses fixed representation methods, in the sense that it can efficiently learn a family of target functions which fixed representation methods cannot.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 30 of its 47 references that are in the map. First posted on arXiv 15 Jan 2024.

Builds on

30 of 47 references.

References · 30

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2014Convex Optimization: Algorithms and Complexitycited by 575
  3. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  4. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  5. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
  6. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  7. 2019Linearized two-layers neural networks in high dimensioncited by 155
  8. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  9. 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
  10. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  11. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  12. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
18 more
  1. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 81
  2. 2020Learning Parities with Neural Networkscited by 78
  3. 2014On the Computational Efficiency of Training Neural Networkscited by 71
  4. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  5. 2017SGD Learns the Conjugate Kernel Class of the Networkcited by 54
  6. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  7. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  8. 2020Learning a Single Neuron with Gradient Methodscited by 50
  9. 2020Agnostic Learning of a Single Neuron with Gradient Descentcited by 46
  10. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  11. 2017Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minimacited by 40
  12. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  13. 2018Small nonlinearities in activation functions create bad local minima in neural networkscited by 28
  14. 2020Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexitycited by 25
  15. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  16. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  17. 2021Learning a Single Neuron with Bias Using Gradient Descentcited by 17
  18. 2023On Single Index Models beyond Gaussian Datacited by 17

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Deep Networks Learn Deep Hierarchical Modelscited by 2