Online learning via congregational gradient descent

Kim L. Blackmore; Robert C. Williamson; Iven M.Y. Mareels; William A. Sethares

doi:10.1145/225298.225330

Online learning via congregational gradient descent

Kim L. Blackmore, Robert C. Williamson, Iven M.Y. Mareels, William A. Sethares

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

We propose and analyse a populational version of stepwise gradient descent suitable for a wide range of learning problems. The algorithm is motivated by genetic algorithms which update a population of solutions rather than just a single representative as is typical for gradient descent. This modification of traditional gradient descent (as used for example in the backpropagation algorithm) avoids getting trapped in local minima. We use an averaging analysis of the algorithm to relate its behaviour to an associated ordinary differential equation. We derive a result concerning how long one has to wait in order that with a given high probability, the algorithm is within a certain neighbourhood of the global minimum. We also analyze the effect of different population sizes. An example is presented which corroborates our theory very well.

Original language	English
Title of host publication	Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
Publisher	Association for Computing Machinery (ACM)
Pages	265-272
Number of pages	8
ISBN (Electronic)	0897917235, 9780897917230
DOIs	https://doi.org/10.1145/225298.225330
Publication status	Published - 5 Jul 1995
Event	8th Annual Conference on Computational Learning Theory, COLT 1995 - Santa Cruz, United States Duration: 5 Jul 1995 → 8 Jul 1995

Publication series

Name	Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995
Volume	1995-January

Conference

Conference	8th Annual Conference on Computational Learning Theory, COLT 1995
Country/Territory	United States
City	Santa Cruz
Period	5/07/95 → 8/07/95

Access to Document

10.1145/225298.225330

Cite this

Blackmore, K. L., Williamson, R. C., Mareels, I. M. Y., & Sethares, W. A. (1995). Online learning via congregational gradient descent. In Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995 (pp. 265-272). (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January). Association for Computing Machinery (ACM). https://doi.org/10.1145/225298.225330

@inproceedings{e2a4f795115e497684ff3e9bf539e287,

title = "Online learning via congregational gradient descent",

abstract = "We propose and analyse a populational version of stepwise gradient descent suitable for a wide range of learning problems. The algorithm is motivated by genetic algorithms which update a population of solutions rather than just a single representative as is typical for gradient descent. This modification of traditional gradient descent (as used for example in the backpropagation algorithm) avoids getting trapped in local minima. We use an averaging analysis of the algorithm to relate its behaviour to an associated ordinary differential equation. We derive a result concerning how long one has to wait in order that with a given high probability, the algorithm is within a certain neighbourhood of the global minimum. We also analyze the effect of different population sizes. An example is presented which corroborates our theory very well.",

author = "Blackmore, {Kim L.} and Williamson, {Robert C.} and Mareels, {Iven M.Y.} and Sethares, {William A.}",

note = "Publisher Copyright: {\textcopyright} 1995 ACM.; 8th Annual Conference on Computational Learning Theory, COLT 1995 ; Conference date: 05-07-1995 Through 08-07-1995",

year = "1995",

month = jul,

day = "5",

doi = "10.1145/225298.225330",

language = "English",

series = "Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995",

publisher = "Association for Computing Machinery (ACM)",

pages = "265--272",

booktitle = "Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995",

address = "United States",

}

Blackmore, KL, Williamson, RC, Mareels, IMY & Sethares, WA 1995, Online learning via congregational gradient descent. in Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995. Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995, vol. 1995-January, Association for Computing Machinery (ACM), pp. 265-272, 8th Annual Conference on Computational Learning Theory, COLT 1995, Santa Cruz, United States, 5/07/95. https://doi.org/10.1145/225298.225330

Online learning via congregational gradient descent. / Blackmore, Kim L.; Williamson, Robert C.; Mareels, Iven M.Y. et al.
Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995. Association for Computing Machinery (ACM), 1995. p. 265-272 (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995; Vol. 1995-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Online learning via congregational gradient descent

AU - Blackmore, Kim L.

AU - Williamson, Robert C.

AU - Mareels, Iven M.Y.

AU - Sethares, William A.

PY - 1995/7/5

Y1 - 1995/7/5

N2 - We propose and analyse a populational version of stepwise gradient descent suitable for a wide range of learning problems. The algorithm is motivated by genetic algorithms which update a population of solutions rather than just a single representative as is typical for gradient descent. This modification of traditional gradient descent (as used for example in the backpropagation algorithm) avoids getting trapped in local minima. We use an averaging analysis of the algorithm to relate its behaviour to an associated ordinary differential equation. We derive a result concerning how long one has to wait in order that with a given high probability, the algorithm is within a certain neighbourhood of the global minimum. We also analyze the effect of different population sizes. An example is presented which corroborates our theory very well.

AB - We propose and analyse a populational version of stepwise gradient descent suitable for a wide range of learning problems. The algorithm is motivated by genetic algorithms which update a population of solutions rather than just a single representative as is typical for gradient descent. This modification of traditional gradient descent (as used for example in the backpropagation algorithm) avoids getting trapped in local minima. We use an averaging analysis of the algorithm to relate its behaviour to an associated ordinary differential equation. We derive a result concerning how long one has to wait in order that with a given high probability, the algorithm is within a certain neighbourhood of the global minimum. We also analyze the effect of different population sizes. An example is presented which corroborates our theory very well.

UR - http://www.scopus.com/inward/record.url?scp=84926172756&partnerID=8YFLogxK

U2 - 10.1145/225298.225330

DO - 10.1145/225298.225330

M3 - Conference contribution

AN - SCOPUS:84926172756

T3 - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

SP - 265

EP - 272

BT - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

PB - Association for Computing Machinery (ACM)

T2 - 8th Annual Conference on Computational Learning Theory, COLT 1995

Y2 - 5 July 1995 through 8 July 1995

ER -

Blackmore KL, Williamson RC, Mareels IMY, Sethares WA. Online learning via congregational gradient descent. In Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995. Association for Computing Machinery (ACM). 1995. p. 265-272. (Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995). doi: 10.1145/225298.225330

Online learning via congregational gradient descent

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this