CaltechAUTHORS
  A Caltech Library Service

The Early Restart Algorithm

Magdon-Ismail, Malik and Atiya, Amir F. (2000) The Early Restart Algorithm. Neural Computation, 12 (6). pp. 1303-1312. ISSN 0899-7667. http://resolver.caltech.edu/CaltechAUTHORS:20111128-151723698

[img]
Preview
PDF - Published Version
See Usage Policy.

174Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111128-151723698

Abstract

Consider an algorithm whose time to convergence is unknown (because of some random element in the algorithm, such as a random initial weight choice for neural network training). Consider the following strategy. Run the algorithm for a specific time T. If it has not converged by time T, cut the run short and rerun it from the start (repeat the same strategy for every run). This so-called restart mechanism has been proposed by Fahlman (1988) in the context of backpropagation training. It is advantageous in problems that are prone to local minima or when there is a large variability in convergence time from run to run, and may lead to a speed-up in such cases. In this article, we analyze theoretically the restart mechanism, and obtain conditions on the probability density of the convergence time for which restart will improve the expected convergence time. We also derive the optimal restart time. We apply the derived formulas to several cases, including steepest-descent algorithms.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1162/089976600300015376 DOIUNSPECIFIED
http://www.mitpressjournals.org/doi/abs/10.1162/089976600300015376PublisherUNSPECIFIED
Additional Information:© 2000 Massachusetts Institute of Technology. Received October 2, 1998; accepted April 13, 1999. Posted Online March 13, 2006. We thank Yaser Abu-Mostafa and the Caltech Learning Systems Group for their useful input. We also acknowledge the support of NSF’s Engineering Research Center at Caltech.
Funders:
Funding AgencyGrant Number
Caltech NSF Engineering Research CenterUNSPECIFIED
Record Number:CaltechAUTHORS:20111128-151723698
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20111128-151723698
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27980
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:29 Nov 2011 17:38
Last Modified:26 Dec 2012 14:27

Repository Staff Only: item control page