Seminar • Algorithms and Complexity — A Classification of High-Dimensional Loss Landscapes for the Performance of Stochastic Gradient DescentExport this event to calendar

Wednesday, September 30, 2020 10:00 AM EDT

Please note: This seminar will be given online.

Aukosh Jagannath, Department of Statistics and Actuarial Science
University of Waterloo

I will report on recent work with G. Ben Arous (NYU) and R. Gheissari (Berkeley) on the performance of online stochastic gradient in high-dimensional inference tasks. We develop a classification of loss landscapes for the difficulty of such problems, namely whether for a given loss function and typical realizations of the data, SGD requires linear, quasilinear, or polynomially many samples in the dimension to perform the inference task. This classification depends on an intrinsic property of the population loss which we call the “information exponent” as opposed to almost sure properties of the loss landscape (e.g., quasi-convexity saddle-type properties). We find that from uniform at random starts, the majority of the data is used in the initial “search” phase (where the landscape is highly non-convex) as compared to the final “descent” phase (where the algorithm is in a trust region).

In this talk, I will illustrate our methods on a simple class of problems, namely supervised learning with a single-layer network in the case of Gaussian patterns. Here we obtain a classification of the sample complexity as one varies the activation function. If there is time remaining, I will illustrate how this approach can be extended to analyze gradient descent in the case of in Tensor PCA.


To join this seminar on Zoom, please go to https://zoom.us/j/92937099244.

Location 
Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2024 (100)
    1. April (23)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)