BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:Europe/Stockholm
X-LIC-LOCATION:Europe/Stockholm
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20200227T164237Z
LOCATION:Analog 1\, 2
DTSTART;TZID=Europe/Stockholm:20190617T130500
DTEND;TZID=Europe/Stockholm:20190617T131000
UID:isc_hpc_ISC High Performance 2019_sess170_phd101@linklings.com
SUMMARY:(PhD01) A Fast Multipole Method for Training Neural Networks
DESCRIPTION:PhD Forum\n\n(PhD01) A Fast Multipole Method for Training Neur
al Networks\n\nReiz, Chen, Neckel, Biros, Bungartz\n\nWe propose a fast mu
ltipole method for the fast approximation and factorization of the Gauss-N
ewton Hessian for fully-connected multilayer perceptron and convolutional
neural networks. We use a block-low rank approximation scheme that is insp
ired by methods for N-body problems in computational physics. In addition,
we propose precomputation and sampling algorithms that reduce the complex
ity of the overall scheme. For a net with N weights, an average layer dime
nsion d, and batch size n, the Gauss-Newton Hessian requires O(N 2 n) work
and O(N 2 ) memory. By introducing a controllable approximation error, ou
r method requires only O(dnN ) work and O(N (n + r_o )) memory, where r o
is the rank of the off-diagonal blocks of the Gauss-Newton Hessian. After
construction, the cost of factorization of the regularized Gauss-Newton He
ssian is O(N r_o^2 ), which results in an improvement of several orders of
magnitude compared to the standard O(N^3 ) complexity for factorization o
f dense matrices of this size. If a global low-rank approximation of the G
auss-Newton Hessian is used, then we can construct an approximation and a
factorization in O(N r 2 ) work and O(N r) memory. Our method becomes pref
erable when r_o