-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathindex.html
More file actions
218 lines (212 loc) · 10.1 KB
/
index.html
File metadata and controls
218 lines (212 loc) · 10.1 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Math 389L</title>
<meta name="description" content="Claremont Graduate University Advanced Big Data Analysis Spring 2019">
<link rel="stylesheet" href="css/styles.css">
</head>
<body>
<div class="body">
<div class="header">
<h2>
<a href="index.html">
<img style="height:1.05em;" src="img/logo.svg">
<span id="title">Math 389L</span>
</a>
</h2>
<h3>
<a href="index.html" id="underline">Schedule</a> |
<a href="info.html">Info</a>
</h3>
</div>
<div class="main">
<table>
<tr>
<th>Week</th>
<th>Topic</th>
<th>Due</th>
</tr>
<tr>
<td> January 22</br>
</td>
<td>
Overview. Review of key concepts from machine learning and statistics.
Canonical examples of large data problems; associated technical and ethical concerns
(genomics, recommender systems, advertising).
</td>
<td>Nothing.</td>
</tr>
<tr>
<td> January 29</br>
</td>
<td>
Convex sets and functions. Standard classes of convex optimization problems.
Specific examples and an overview of associated computational complexity.
Exponential lower bounds on generic optimization problems.
</td>
<td>Read: Boyd Chapter 4.</br>
Read: These <a href="supplementary/convex.pdf">notes</a> and <a href="https://people.eecs.berkeley.edu/~jordan/courses/294-fall09/lectures/optimization/slides.pdf">slides</a>.</br>
</td>
</tr>
<tr>
<td> February 5</br>
</td>
<td>
Large scale convex optimization problems and relation to our canonical settings.
Stochastic methods (eg. SGD) and a proof of
convergence. A sketching teaser.
</td>
<td>Read: Woodruff introduction.</br>
<a href="hw/pset1.pdf">Problem Set 1</a>. (<a href="hw/pset1.tex">tex</a>, <a href="hw/hmcpset.cls">cls</a>, <a href="soln/pset1.pdf">soln</a>)
</td>
</tr>
<tr>
<td> February 12</br>
</td>
<td>
Large scale least squares problems via sketching and theoretical comparison to other solution algorithms. Proof of correctness for Gaussian sketches, and why that doesn't result in fast algorithms. Fast JL Transforms, CountSketch Matrices, and applications.
</td>
<td>Read: Woodruff Chapter 2.</br>
<a href="hw/pset2.pdf">Problem Set 2</a>. (<a href="hw/pset2.tex">tex</a>, <a href="soln/pset2.pdf">soln</a>)
</td>
</tr>
<tr>
<td> February 19</br>
</td>
<td>
Finishing up sketching. Proof of correctness of Fast Johnson-Lindenstrauss Transform. Review of Lagrange Duality. Duality gaps and Slater's Condition. Duals of common optimization problems.
</td>
<td>Read: Boyd Chapter 5.</br>
Read: <a href="hw/great_example_solution.pdf">Great Example Solution</a></br>
<a href="hw/pset3.pdf">Problem Set 3</a>. (<a href="hw/pset3.tex">tex</a>)
</td>
</tr>
<tr>
<td> February 26</br>
</td>
<td>
More Lagrange duality theory. Duality-driven algorithms
for optimization (mirror descent) and applications (optimization on simplex).
Non-convex optimization problems and prevalence of use.
</td>
<td>Read: <a href="https://arxiv.org/pdf/0903.3131.pdf">this paper</a></br>
Read: <a href="https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf">this paper</a>.</br>
<a href="hw/pset4.pdf">Problem Set 4</a>. (<a href="hw/pset4.tex">tex</a>)
</td>
</tr>
<tr>
<td> March 5</br>
</td>
<td>
Optimization algorithms in the non-convex setting (Adam, saddle point aversion,
...) and recent guarantees. Provably solveable non-convex problems. Applications
to recommender systems.
</td>
<td>Read: <a href="https://ganguli-gang.stanford.edu/pdf/14.SaddlePoint.NIPS.pdf">this paper</a>.</br>
Read: <a href="https://arxiv.org/pdf/1602.04915.pdf">this paper</a>.</br>
Work on midterm project.
</td>
</tr>
<tr>
<td> March 12 </br>
</td>
<td>
High capacity convex alternatives to deep models (Gaussian Processes and kernel methods) and associated
comptuational drawbacks. Preconditioned kernel machine solvers and trace estimation to relieve these
difficulties.
</td>
<td>Read: <a href="https://arxiv.org/pdf/1602.06693.pdf">this paper</a>.</br>
Read: <a href="http://www.gaussianprocess.org/gpml/chapters/RW2.pdf">notes on GPs</a>.</br>
Read: <a href="http://infolab.stanford.edu/~ullman/mmds/ch9.pdf">notes on Rec. Systems</a>.</br>
<a href="info.html#midterm">Midterm project.</a></td>
</tr>
<tr>
<td> March 19</br> (no class)
</td>
<td>
</td>
<td>Enjoy Spring Break!</td>
</tr>
<tr>
<td> March 26</br>
</td>
<td>
Review of concentration. Some key results from non-asymptotic random matrix theory.
Associated random graphs (stochastic block model) and and some theory.
</td>
<td>Read: Vershynin Chapter 3.</br>
<a href="hw/pset5.pdf">Problem Set 5</a>. (<a href="hw/pset5.tex">tex</a>, very small, due <em>Friday</em>)
</td>
</tr>
<tr>
<td> April 2</br>
</td>
<td>
Clustering. Simple algorithms for NP-hard problems: k-means, and k-means++.
Spectral clustering algorithms for guaranteed clustering of graphs.
</td>
<td>Read: <a href="http://theory.stanford.edu/~sergei/papers/kMeans-socg.pdf">this paper</a>.</br>
Read: <a href="https://www.cs.cornell.edu/home/kleinber/nips15.pdf">this paper</a>.</br>
<a href="hw/pset6.pdf">Problem Set 6</a>. (<a href="hw/pset6.tex">tex</a>)</br>
<a href="info.html#final-project">Literature Review.</a>
</td>
</tr>
<tr>
<td> April 9</br>
</td>
<td>
Matrix completion redux. SVD and provable recovery of observed sparse, low rank matrices.
Computational considerations and faster iterative algorithms.
</td>
<td>Read: Vershynin Chapter 6.</br>
<a href="hw/pset7.pdf">Problem Set 7</a>. (<a href="hw/pset7.tex">tex</a>)</br>
</td>
</tr>
<tr>
<td> April 16
</td>
<td>
More streaming algorithms; the turnstile model.
Counting large numbers with very little memory (Morris' algorithm).
Lower bounds for number storage. Sketching vector norms in the turnstile model.
</td>
<td>
Read: <a href="https://people.csail.mit.edu/indyk/Rice/lec1.pdf">these slides.</a></br>
Work on final project!
</td>
</tr>
<tr>
<td> April 23</br>
</td>
<td>
Approximate matrix multiplication in the turnstile model via sketching.
Associated lower bound.
</td>
<td>
<a href="hw/pset8.pdf">Problem Set 8</a>. (<a href="hw/pset8.tex">tex</a>)
</td>
</tr>
<tr>
<td> April 30</br>
</td>
<td>
Work on final project.
</td>
<td>
</td>
</tr>
<tr>
<td> May <em>8</em></br>
</td>
<td>
Final Project Presentations. Note this is on <em>Wednesday</em> from 5-8pm.
</td>
<td><a href="info.html#final-project">Final projects.</a> (<em>no extensions</em>)
</td>
</tr>
</table>
</div>
</div>
</body>
</html>