An efficient black-box reduction from PQ to TDS learning for any Boolean concept class in the distribution-free setting implies hardness for TDS learning of halfspaces, while membership queries enable efficient PQ learning of halfspaces via iterative Forster transforms.
Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
abstract
Training neural networks is a challenging non-convex optimization problem, and backpropagation or gradient descent can get stuck in spurious local optima. We propose a novel algorithm based on tensor decomposition for guaranteed training of two-layer neural networks. We provide risk bounds for our proposed method, with a polynomial sample complexity in the relevant parameters, such as input dimension and number of neurons. While learning arbitrary target functions is NP-hard, we provide transparent conditions on the function and the input for learnability. Our training method is based on tensor decomposition, which provably converges to the global optimum, under a set of mild non-degeneracy conditions. It consists of simple embarrassingly parallel linear and multi-linear operations, and is competitive with standard stochastic gradient descent (SGD), in terms of computational complexity. Thus, we propose a computationally efficient method with guaranteed risk bounds for training neural networks with one hidden layer.
verdicts
UNVERDICTED 5representative citing papers
A new tensor framework for multi-layer decoupling of multivariate functions is proposed via ParaTuck decompositions and bilevel optimization.
Presents new synchronous and asynchronous parallel approaches for GCP tensor decomposition and evaluates computational cost and accuracy on synthetic and real-world datasets.
SPIN lets weak LLMs become strong by self-generating training data from previous model versions and training to prefer human-annotated responses over its own outputs, outperforming DPO even with extra GPT-4 data on benchmarks.
Presents an active-sampling method that approximates the weight subspace from Hessian finite differences, recovers the rank-1 tensors by robust nonlinear programming, and attributes layers with gradient descent, yielding stable recovery under a-posteriori verifiable conditions.
citing papers explorer
-
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
An efficient black-box reduction from PQ to TDS learning for any Boolean concept class in the distribution-free setting implies hardness for TDS learning of halfspaces, while membership queries enable efficient PQ learning of halfspaces via iterative Forster transforms.
-
Tensor-based Multi-layer Decoupling
A new tensor framework for multi-layer decoupling of multivariate functions is proposed via ParaTuck decompositions and bilevel optimization.
-
Synchronous and Asynchronous Parallelism Approaches for Generalized Canonical Polyadic Tensor Decomposition with GenTen
Presents new synchronous and asynchronous parallel approaches for GCP tensor decomposition and evaluates computational cost and accuracy on synthetic and real-world datasets.
-
Self-Play Fine-Tuning Converts Weak Language Models to Strong Language Models
SPIN lets weak LLMs become strong by self-generating training data from previous model versions and training to prefer human-annotated responses over its own outputs, outperforming DPO even with extra GPT-4 data on benchmarks.
-
Robust and Resource Efficient Identification of Two Hidden Layer Neural Networks
Presents an active-sampling method that approximates the weight subspace from Hessian finite differences, recovers the rank-1 tensors by robust nonlinear programming, and attributes layers with gradient descent, yielding stable recovery under a-posteriori verifiable conditions.