A Sublinear Adversarial Training Algorithm

• URL: http://arxiv.org/abs/2208.05395v1
• Date: Wed, 10 Aug 2022 15:31:40 GMT
• Title: A Sublinear Adversarial Training Algorithm
• Authors: Yeqi Gao, Lianke Qin, Zhao Song, Yitan Wang
• Abstract summary: We analyze the convergence guarantee of adversarial training procedure on a two-layer neural network with shifted ReLU activation. We develop an algorithm for adversarial training with time cost $o(m n d)$ per iteration by applying half-space reporting data structure.
• Score: 13.42699247306472
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Adversarial training is a widely used strategy for making neural networks resistant to adversarial perturbations. For a neural network of width $m$, $n$ input training data in $d$ dimension, it takes $\Omega(mnd)$ time cost per training iteration for the forward and backward computation. In this paper we analyze the convergence guarantee of adversarial training procedure on a two-layer neural network with shifted ReLU activation, and shows that only $o(m)$ neurons will be activated for each input data per iteration. Furthermore, we develop an algorithm for adversarial training with time cost $o(m n d)$ per iteration by applying half-space reporting data structure.

Related papers

• Bayesian Inference with Deep Weakly Nonlinear Networks [57.95116787699412]
  We show at a physics level of rigor that Bayesian inference with a fully connected neural network is solvable. We provide techniques to compute the model evidence and posterior to arbitrary order in $1/N$ and at arbitrary temperature.
  arXiv  Detail & Related papers  (2024-05-26T17:08:04Z)
• Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification [22.361338848134025]
  We present a fully connected two-layer neural network for shifted ReLU activation to enable activated neuron identification in sublinear time via geometric search. We also prove that our algorithm can converge in $O(M2/epsilon2)$ time with network size quadratic in the coefficient norm upper bound $M$ and error term $epsilon$.
  arXiv  Detail & Related papers  (2023-07-13T05:33:44Z)
• Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing [16.35997749365563]
  State-of-art deep neural networks are becoming larger in size every year to deliver increasing model accuracy. Recent work [Song, Yang and Zhang, NeurIPS 2021] reduces this time per iteration to $o(nmd)$, but requires exponential time to preprocess either the data or the neural network weights. We present a new preprocessing method that simply stores the weight-data correlation in a tree data structure in order to quickly, dynamically detect which neurons fire at each iteration.
  arXiv  Detail & Related papers  (2022-11-25T16:40:49Z)
• Training Overparametrized Neural Networks in Sublinear Time [14.918404733024332]
  Deep learning comes at a tremendous computational and energy cost. We present a new and a subset of binary neural networks, as a small subset of search trees, where each corresponds to a subset of search trees (Ds) We believe this view would have further applications in analysis analysis of deep networks (Ds)
  arXiv  Detail & Related papers  (2022-08-09T02:29:42Z)
• Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis [121.9821494461427]
  We show how to significantly reduce the number of neurons required for two-layer ReLU networks. We also prove new lower bounds that improve upon prior work, and that under certain assumptions, are best possible.
  arXiv  Detail & Related papers  (2022-06-26T06:51:31Z)
• Neural Capacitance: A New Perspective of Neural Network Selection via Edge Dynamics [85.31710759801705]
  Current practice requires expensive computational costs in model training for performance prediction. We propose a novel framework for neural network selection by analyzing the governing dynamics over synaptic connections (edges) during training. Our framework is built on the fact that back-propagation during neural network training is equivalent to the dynamical evolution of synaptic connections.
  arXiv  Detail & Related papers  (2022-01-11T20:53:15Z)
• Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time [12.348083977777833]
  We consider the problem of training a multi-layer over-parametrized neural network to minimize the empirical risk induced by a loss function. In this work, we show how to reduce the training cost per iteration.
  arXiv  Detail & Related papers  (2021-12-14T18:13:36Z)
• Does Preprocessing Help Training Over-parameterized Neural Networks? [19.64638346701198]
  We propose two novel preprocessing ideas to bypass the $Omega(mnd)$ barrier. Our results provide theoretical insights for a large number of previously established fast training methods.
  arXiv  Detail & Related papers  (2021-10-09T18:16:23Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We numerically demonstrate that the MNIST image dataset satisfies such conditions. We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
  arXiv  Detail & Related papers  (2021-07-19T23:41:03Z)
• Beyond Lazy Training for Over-parameterized Tensor Decomposition [69.4699995828506]
  We show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data. Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data.
  arXiv  Detail & Related papers  (2020-10-22T00:32:12Z)
• Taylorized Training: Towards Better Approximation of Neural Network Training at Finite Width [116.69845849754186]
  Taylorized training involves training the $k$-th order Taylor expansion of the neural network. We show that Taylorized training agrees with full neural network training increasingly better as we increase $k$. We complement our experiments with theoretical results showing that the approximation error of $k$-th order Taylorized models decay exponentially over $k$ in wide neural networks.
  arXiv  Detail & Related papers  (2020-02-10T18:37:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.