GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — diffprog.github.io/source-code.html at main · diffprog/diffprog.github.io

Expand file tree

/

source-code.html

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
547 lines (547 loc) · 53.9 KB
/

source-code.html

Copy path

File metadata and controls

547 lines (547 loc) · 53.9 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Source code – The Elements of Differentiable Programming</title>
<script>
(function(){try{var T={"sky": "light", "solarized": "light", "mint": "light", "stone": "light", "dark": "dark"};
var m=document.cookie.match(/(?:^|; )theme=([a-z]+)/),t=m?m[1]:null;
if(!t){try{t=localStorage.getItem('theme');}catch(e){}}
if(t==='slate'||t==='black')t='dark';
if(!T[t])t=(window.matchMedia&&matchMedia('(prefers-color-scheme: dark)').matches)?"dark":"sky";
var r=document.documentElement;r.setAttribute('data-theme',t);r.setAttribute('data-tone',T[t]);}catch(e){}})();
</script>
<link rel="stylesheet" href="vendor/katex/katex.min.css">
<link rel="stylesheet" href="assets/style.css">
</head>
<body>
<header id="topbar">
<button id="menu-toggle" aria-label="Table of contents" aria-controls="sidebar" aria-expanded="false">&#9776;</button>
<a class="topbar-title" href="index.html">The Elements of Differentiable Programming</a>
</header>
<aside id="sidebar">
<div class="sidebar-head"><a class="book-title" href="index.html">The Elements of<br>Differentiable Programming</a>
</div>
<nav class="toc"><ul class="toc-chapters">
<li class="toc-chapter toc-external"><a href="https://arxiv.org/abs/2403.14606">PDF</a></li>
<li class="toc-chapter">
<a href="abstract.html">Abstract</a>
</li>
<li class="toc-chapter">
<a href="cite.html">How to cite</a>
</li>
<li class="toc-chapter">
<a href="acknowledgements.html">Acknowledgements</a>
</li>
<li class="toc-chapter current">
<a href="source-code.html">Source code</a>
</li>
<li class="toc-chapter">
<a href="notation.html">Notation</a>
</li>
<li class="toc-chapter">
<details><summary><a href="intro.html"><span class="num">1</span>Introduction</a></summary><ul>
<li class="toc-l1"><a href="intro.html#sec-1.1"><span class="num">1.1</span>What is differentiable programming?</a></li>
<li class="toc-l2"><a href="intro.html#sec-neural-networks-as-parameterized-programs">Neural networks as parameterized programs</a></li>
<li class="toc-l2"><a href="intro.html#sec-why-do-we-need-derivatives">Why do we need derivatives?</a></li>
<li class="toc-l2"><a href="intro.html#sec-why-is-autodiff-so-useful">Why is autodiff so useful?</a></li>
<li class="toc-l2"><a href="intro.html#sec-differentiable-programming-is-not-just-deep-learning">Differentiable programming is not just deep learning</a></li>
<li class="toc-l2"><a href="intro.html#sec-differentiable-programming-is-not-just-autodiff">Differentiable programming is not just autodiff</a></li>
<li class="toc-l2"><a href="intro.html#sec-our-vision-for-differentiable-programming">Our vision for differentiable programming</a></li>
<li class="toc-l2"><a href="intro.html#sec-where-does-differentiable-programming-come-from">Where does “differentiable programming” come from?</a></li>
<li class="toc-l1"><a href="intro.html#sec-1.2"><span class="num">1.2</span>Book goals and scope</a></li>
<li class="toc-l1"><a href="intro.html#sec-1.3"><span class="num">1.3</span>Intended audience</a></li>
<li class="toc-l1"><a href="intro.html#sec-1.4"><span class="num">1.4</span>How to read this book?</a></li>
<li class="toc-l1"><a href="intro.html#sec-1.5"><span class="num">1.5</span>Related work</a></li>
</ul></details>
</li>
<li class="toc-part">Part I<span>Fundamentals</span></li>
<li class="toc-chapter">
<details><summary><a href="diff.html"><span class="num">2</span>Differentiation</a></summary><ul>
<li class="toc-l1"><a href="diff.html#sec-2.1"><span class="num">2.1</span>Univariate functions</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:der_def"><span class="num">2.1.1</span>Derivatives</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:calculus_rules"><span class="num">2.1.2</span>Calculus rules</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.1.3"><span class="num">2.1.3</span>Leibniz’s notation</a></li>
<li class="toc-l1"><a href="diff.html#sec-2.2"><span class="num">2.2</span>Multivariate functions</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.2.1"><span class="num">2.2.1</span>Directional derivatives</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:grad"><span class="num">2.2.2</span>Gradients</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:jac"><span class="num">2.2.3</span>Jacobians</a></li>
<li class="toc-l1"><a href="diff.html#diff:sec:jvp_vjp"><span class="num">2.3</span>Linear maps</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:need_linear_maps"><span class="num">2.3.1</span>The need for linear maps</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:euc_spaces"><span class="num">2.3.2</span>Euclidean spaces</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.3.3"><span class="num">2.3.3</span>Linear maps and their adjoints</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.3.4"><span class="num">2.3.4</span>Jacobian-vector products</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.3.5"><span class="num">2.3.5</span>Vector-Jacobian products</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.3.6"><span class="num">2.3.6</span>Chain rule using linear maps</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.3.7"><span class="num">2.3.7</span>Functions of multiple inputs (fan-in)</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.3.8"><span class="num">2.3.8</span>Functions with multiple outputs (fan-out)</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:extension_non_euc"><span class="num">2.3.9</span>Extensions to non-Euclidean linear spaces</a></li>
<li class="toc-l1"><a href="diff.html#diff:sec:second_derivative"><span class="num">2.4</span>Second-order differentiation</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.4.1"><span class="num">2.4.1</span>Second derivatives</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.4.2"><span class="num">2.4.2</span>Second directional derivatives</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.4.3"><span class="num">2.4.3</span>Hessians</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.4.4"><span class="num">2.4.4</span>Hessian-vector products</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.4.5"><span class="num">2.4.5</span>Second-order Jacobians</a></li>
<li class="toc-l1"><a href="diff.html#diff:sec:higher"><span class="num">2.5</span>Higher-order differentiation</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.5.1"><span class="num">2.5.1</span>Higher-order derivatives</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.5.2"><span class="num">2.5.2</span>Higher-order directional derivatives</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.5.3"><span class="num">2.5.3</span>Higher-order Jacobians</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:taylor_exp"><span class="num">2.5.4</span>Taylor expansions</a></li>
<li class="toc-l1"><a href="diff.html#sec-2.6"><span class="num">2.6</span>Differential geometry</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.6.1"><span class="num">2.6.1</span>Differentiability on manifolds</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.6.2"><span class="num">2.6.2</span>Tangent spaces and pushforward operators</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.6.3"><span class="num">2.6.3</span>Cotangent spaces and pullback operators</a></li>
<li class="toc-l1"><a href="diff.html#sec-2.7"><span class="num">2.7</span>Generalized derivatives</a></li>
<li class="toc-l2"><a href="diff.html#diff:sec:rademacher"><span class="num">2.7.1</span>Rademacher’s theorem</a></li>
<li class="toc-l2"><a href="diff.html#sec-2.7.2"><span class="num">2.7.2</span>Clarke derivatives</a></li>
<li class="toc-l1"><a href="diff.html#sec-2.8"><span class="num">2.8</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="proba_learn.html"><span class="num">3</span>Probabilistic learning</a></summary><ul>
<li class="toc-l1"><a href="proba_learn.html#proba_learn:sec:dist"><span class="num">3.1</span>Probability distributions</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.1.1"><span class="num">3.1.1</span>Discrete probability distributions</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.1.2"><span class="num">3.1.2</span>Continuous probability distributions</a></li>
<li class="toc-l1"><a href="proba_learn.html#proba_learn:sec:mle"><span class="num">3.2</span>Maximum likelihood estimation</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.2.1"><span class="num">3.2.1</span>Negative log-likelihood</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.2.2"><span class="num">3.2.2</span>Consistency <span>w.r.t. </span>the Kullback-Leibler divergence</a></li>
<li class="toc-l1"><a href="proba_learn.html#proba_learn:sec:cpd"><span class="num">3.3</span>Probabilistic supervised learning</a></li>
<li class="toc-l2"><a href="proba_learn.html#proba_learn:sec:conditional_proba"><span class="num">3.3.1</span>Conditional probability distributions</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.3.2"><span class="num">3.3.2</span>Inference</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.3.3"><span class="num">3.3.3</span>Binary classification</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.3.4"><span class="num">3.3.4</span>Multiclass classification</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.3.5"><span class="num">3.3.5</span>Regression</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.3.6"><span class="num">3.3.6</span>Multivariate regression</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.3.7"><span class="num">3.3.7</span>Integer regression</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.3.8"><span class="num">3.3.8</span>Loss functions</a></li>
<li class="toc-l1"><a href="proba_learn.html#proba_learn:sec:exp_family"><span class="num">3.4</span>Exponential family distributions</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.4.1"><span class="num">3.4.1</span>Definition</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.4.2"><span class="num">3.4.2</span>The log-partition function</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.4.3"><span class="num">3.4.3</span>Maximum entropy principle</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.4.4"><span class="num">3.4.4</span>Maximum likelihood estimation</a></li>
<li class="toc-l2"><a href="proba_learn.html#sec-3.4.5"><span class="num">3.4.5</span>Probabilistic learning with exponential families</a></li>
<li class="toc-l1"><a href="proba_learn.html#sec-3.5"><span class="num">3.5</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-part">Part II<span>Differentiable programs</span></li>
<li class="toc-chapter">
<details><summary><a href="neural_nets.html"><span class="num">4</span>Parameterized programs</a></summary><ul>
<li class="toc-l1"><a href="neural_nets.html#sec-4.1"><span class="num">4.1</span>Representing computer programs</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:comput_chains"><span class="num">4.1.1</span>Computation chains</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.1.2"><span class="num">4.1.2</span>Directed acyclic graphs</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:comput_graphs"><span class="num">4.1.3</span>Computer programs as DAGs</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:arithmetic_circuits"><span class="num">4.1.4</span>Arithmetic circuits</a></li>
<li class="toc-l1"><a href="neural_nets.html#neural_nets:sec:ff"><span class="num">4.2</span>Feedforward networks</a></li>
<li class="toc-l1"><a href="neural_nets.html#neural_nets:sec:mlp"><span class="num">4.3</span>Multilayer perceptrons</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.3.1"><span class="num">4.3.1</span>Combining affine layers and activations</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.3.2"><span class="num">4.3.2</span>Link with generalized linear models</a></li>
<li class="toc-l1"><a href="neural_nets.html#neural_nets:sec:activations"><span class="num">4.4</span>Activation functions</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.4.1"><span class="num">4.4.1</span>ReLU and softplus</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:vector_to_scalar"><span class="num">4.4.2</span>Max pooling and log-sum-exp</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:sigmoids"><span class="num">4.4.3</span>Sigmoids: binary step and logistic functions</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.4.4"><span class="num">4.4.4</span>Probability mappings: argmax and softargmax</a></li>
<li class="toc-l1"><a href="neural_nets.html#neural_nets:sec:normalization"><span class="num">4.5</span>Normalization layers</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.5.1"><span class="num">4.5.1</span>Batch normalization</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:layer_norm"><span class="num">4.5.2</span>Layer normalization</a></li>
<li class="toc-l1"><a href="neural_nets.html#neural_nets:sec:residual"><span class="num">4.6</span>Residual neural networks</a></li>
<li class="toc-l1"><a href="neural_nets.html#seq_net:sec:rnn"><span class="num">4.7</span>Recurrent neural networks</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.7.1"><span class="num">4.7.1</span>Vector to sequence</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.7.2"><span class="num">4.7.2</span>Sequence to vector</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.7.3"><span class="num">4.7.3</span>Sequence to sequence (aligned)</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.7.4"><span class="num">4.7.4</span>Sequence to sequence (unaligned)</a></li>
<li class="toc-l1"><a href="neural_nets.html#neural_nets:sec:transformers"><span class="num">4.8</span>Transformers</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.8.1"><span class="num">4.8.1</span>Attention</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.8.2"><span class="num">4.8.2</span>Self-attention</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_net:sec:multi_head_attention"><span class="num">4.8.3</span>Multi-head attention</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.8.4"><span class="num">4.8.4</span>Transformer layer</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_net:sec:transformer_block"><span class="num">4.8.5</span>Transformer block</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:input_encoding"><span class="num">4.8.6</span>Token encoding</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_net:sec:positional_encoding"><span class="num">4.8.7</span>Positional encoding</a></li>
<li class="toc-l2"><a href="neural_nets.html#neural_nets:sec:decoder_only_transformer"><span class="num">4.8.8</span>Decoder-only architectures</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.8.9"><span class="num">4.8.9</span>Encoder-only architectures</a></li>
<li class="toc-l2"><a href="neural_nets.html#sec-4.8.10"><span class="num">4.8.10</span>Encoder-decoder architectures</a></li>
<li class="toc-l1"><a href="neural_nets.html#sec-4.9"><span class="num">4.9</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="cf.html"><span class="num">5</span>Control flows</a></summary><ul>
<li class="toc-l1"><a href="cf.html#sec-5.1"><span class="num">5.1</span>Comparison operators</a></li>
<li class="toc-l1"><a href="cf.html#cf:sec:soft_cmp"><span class="num">5.2</span>Soft inequality operators</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.2.1"><span class="num">5.2.1</span>Heuristic definition</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.2.2"><span class="num">5.2.2</span>Stochastic process perspective</a></li>
<li class="toc-l1"><a href="cf.html#sec-5.3"><span class="num">5.3</span>Soft equality operators</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.3.1"><span class="num">5.3.1</span>Heuristic definition</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.3.2"><span class="num">5.3.2</span>Stochastic process perspective</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.3.3"><span class="num">5.3.3</span>Gaussian process perspective</a></li>
<li class="toc-l1"><a href="cf.html#sec-5.4"><span class="num">5.4</span>Logical operators</a></li>
<li class="toc-l1"><a href="cf.html#sec-5.5"><span class="num">5.5</span>Continuous extensions of logical operators</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.5.1"><span class="num">5.5.1</span>Probabilistic continuous extension</a></li>
<li class="toc-l2"><a href="cf.html#cf:sec:t_norms"><span class="num">5.5.2</span>Triangular norms and co-norms</a></li>
<li class="toc-l1"><a href="cf.html#cf:sec:if_else"><span class="num">5.6</span>If-else statements</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.6.1"><span class="num">5.6.1</span>Differentiating through branch variables</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.6.2"><span class="num">5.6.2</span>Differentiating through predicate variables</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.6.3"><span class="num">5.6.3</span>Continuous relaxations</a></li>
<li class="toc-l1"><a href="cf.html#cf:sec:else_if"><span class="num">5.7</span>Else-if statements</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.7.1"><span class="num">5.7.1</span>Encoding <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>K</mi></mrow><annotation encoding="application/x-tex">K</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.07153em;">K</span></span></span></span> branches</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.7.2"><span class="num">5.7.2</span>Conditionals</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.7.3"><span class="num">5.7.3</span>Differentiating through branch variables</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.7.4"><span class="num">5.7.4</span>Differentiating through predicate variables</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.7.5"><span class="num">5.7.5</span>Continuous relaxations</a></li>
<li class="toc-l1"><a href="cf.html#cf:sec:for_loops"><span class="num">5.8</span>For loops</a></li>
<li class="toc-l1"><a href="cf.html#sec-5.9"><span class="num">5.9</span>Scan functions</a></li>
<li class="toc-l1"><a href="cf.html#cf:sec:while_loops"><span class="num">5.10</span>While loops</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.10.1"><span class="num">5.10.1</span>While loops as cyclic graphs</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.10.2"><span class="num">5.10.2</span>Unrolled while loops</a></li>
<li class="toc-l2"><a href="cf.html#sec-5.10.3"><span class="num">5.10.3</span>Markov chain perspective</a></li>
<li class="toc-l1"><a href="cf.html#sec-5.11"><span class="num">5.11</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="ds.html"><span class="num">6</span>Data structures</a></summary><ul>
<li class="toc-l1"><a href="ds.html#ds:lists"><span class="num">6.1</span>Lists</a></li>
<li class="toc-l2"><a href="ds.html#sec-6.1.1"><span class="num">6.1.1</span>Basic operations</a></li>
<li class="toc-l2"><a href="ds.html#sec-6.1.2"><span class="num">6.1.2</span>Operations on variable-length lists</a></li>
<li class="toc-l2"><a href="ds.html#sec-6.1.3"><span class="num">6.1.3</span>Continuous relaxations using soft indexing</a></li>
<li class="toc-l1"><a href="ds.html#ds:dict"><span class="num">6.2</span>Dictionaries</a></li>
<li class="toc-l2"><a href="ds.html#sec-6.2.1"><span class="num">6.2.1</span>Basic operations</a></li>
<li class="toc-l2"><a href="ds.html#sec-6.2.2"><span class="num">6.2.2</span>Continuous relaxation using kernel regression</a></li>
<li class="toc-l2"><a href="ds.html#sec-6.2.3"><span class="num">6.2.3</span>Discrete probability distribution perspective</a></li>
<li class="toc-l2"><a href="ds.html#sec-6.2.4"><span class="num">6.2.4</span>Link with attention in Transformers</a></li>
<li class="toc-l1"><a href="ds.html#sec-6.3"><span class="num">6.3</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-part">Part III<span>Differentiating through programs</span></li>
<li class="toc-chapter">
<details><summary><a href="finite_diff.html"><span class="num">7</span>Finite differences</a></summary><ul>
<li class="toc-l1"><a href="finite_diff.html#sec-7.1"><span class="num">7.1</span>Forward differences</a></li>
<li class="toc-l1"><a href="finite_diff.html#sec-7.2"><span class="num">7.2</span>Backward differences</a></li>
<li class="toc-l1"><a href="finite_diff.html#sec-7.3"><span class="num">7.3</span>Central differences</a></li>
<li class="toc-l1"><a href="finite_diff.html#sec-7.4"><span class="num">7.4</span>Higher-accuracy finite differences</a></li>
<li class="toc-l1"><a href="finite_diff.html#sec-7.5"><span class="num">7.5</span>Higher-order finite differences</a></li>
<li class="toc-l1"><a href="finite_diff.html#sec-7.6"><span class="num">7.6</span>Complex-step derivatives</a></li>
<li class="toc-l1"><a href="finite_diff.html#sec-7.7"><span class="num">7.7</span>Complexity</a></li>
<li class="toc-l1"><a href="finite_diff.html#sec-7.8"><span class="num">7.8</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="auto_diff.html"><span class="num">8</span>Automatic differentiation</a></summary><ul>
<li class="toc-l1"><a href="auto_diff.html#auto_diff:sec:chains"><span class="num">8.1</span>Computation chains</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.1.1"><span class="num">8.1.1</span>Forward-mode</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.1.2"><span class="num">8.1.2</span>Reverse-mode</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.1.3"><span class="num">8.1.3</span>Complexity of computing entire Jacobians</a></li>
<li class="toc-l1"><a href="auto_diff.html#sec-8.2"><span class="num">8.2</span>Feedforward networks</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.2.1"><span class="num">8.2.1</span>Computing the adjoint</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.2.2"><span class="num">8.2.2</span>Computing the gradient</a></li>
<li class="toc-l1"><a href="auto_diff.html#auto_diff:sec:graphs"><span class="num">8.3</span>Computation graphs</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.3.1"><span class="num">8.3.1</span>Forward mode</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.3.2"><span class="num">8.3.2</span>Reverse mode</a></li>
<li class="toc-l2"><a href="auto_diff.html#auto_diff:sec:complexity_dag"><span class="num">8.3.3</span>Complexity, the Baur-Strassen theorem</a></li>
<li class="toc-l1"><a href="auto_diff.html#sec-8.4"><span class="num">8.4</span>Implementation</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.4.1"><span class="num">8.4.1</span>Primitive functions</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.4.2"><span class="num">8.4.2</span>Closure under function composition</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.4.3"><span class="num">8.4.3</span>Examples of JVPs and VJPs</a></li>
<li class="toc-l2"><a href="auto_diff.html#auto_diff:sec:auto_linear_transposition"><span class="num">8.4.4</span>Automatic linear transposition</a></li>
<li class="toc-l1"><a href="auto_diff.html#auto_diff:sec:checkpointing"><span class="num">8.5</span>Checkpointing</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.5.1"><span class="num">8.5.1</span>Recursive halving</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.5.2"><span class="num">8.5.2</span>Dynamic programming</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.5.3"><span class="num">8.5.3</span>Online checkpointing</a></li>
<li class="toc-l1"><a href="auto_diff.html#auto_diff:sec:reversible"><span class="num">8.6</span>Reversible layers</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.6.1"><span class="num">8.6.1</span>General case</a></li>
<li class="toc-l2"><a href="auto_diff.html#sec-8.6.2"><span class="num">8.6.2</span>Case of orthonormal JVPs</a></li>
<li class="toc-l1"><a href="auto_diff.html#auto_diff:sec:randomized_forward"><span class="num">8.7</span>Randomized forward-mode gradient estimator</a></li>
<li class="toc-l1"><a href="auto_diff.html#sec-8.8"><span class="num">8.8</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="higher.html"><span class="num">9</span>Second-order automatic differentiation</a></summary><ul>
<li class="toc-l1"><a href="higher.html#higher:sec:hvp"><span class="num">9.1</span>Hessian-vector products</a></li>
<li class="toc-l2"><a href="higher.html#higher:ssec:formulas"><span class="num">9.1.1</span>Four possible methods</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.1.2"><span class="num">9.1.2</span>Complexity</a></li>
<li class="toc-l1"><a href="higher.html#higher:sec:gnvp"><span class="num">9.2</span>Gauss-Newton matrix</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.2.1"><span class="num">9.2.1</span>An approximation of the Hessian</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.2.2"><span class="num">9.2.2</span>Gauss-Newton chain rule</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.2.3"><span class="num">9.2.3</span>Gauss-Newton vector product</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.2.4"><span class="num">9.2.4</span>Gauss-Newton matrix factorization</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.2.5"><span class="num">9.2.5</span>Stochastic setting</a></li>
<li class="toc-l1"><a href="higher.html#higher:sec:fisher"><span class="num">9.3</span>Fisher information matrix</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.3.1"><span class="num">9.3.1</span>Definition using the score function</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.3.2"><span class="num">9.3.2</span>Link with the Hessian</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.3.3"><span class="num">9.3.3</span>Equivalence with the Gauss-Newton matrix</a></li>
<li class="toc-l1"><a href="higher.html#higher:sec:ihvp"><span class="num">9.4</span>Inverse-Hessian vector product</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.4.1"><span class="num">9.4.1</span>Definition as a linear map</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.4.2"><span class="num">9.4.2</span>Implementation with matrix-free linear solvers</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.4.3"><span class="num">9.4.3</span>Complexity</a></li>
<li class="toc-l1"><a href="higher.html#higher:sec:hbp"><span class="num">9.5</span>Second-order backpropagation</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.5.1"><span class="num">9.5.1</span>Second-order Jacobian chain rule</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.5.2"><span class="num">9.5.2</span>Computation chains</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.5.3"><span class="num">9.5.3</span>Fan-in and fan-out</a></li>
<li class="toc-l1"><a href="higher.html#higher:sec:block_diagonal"><span class="num">9.6</span>Block diagonal approximations</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.6.1"><span class="num">9.6.1</span>Feedforward networks</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.6.2"><span class="num">9.6.2</span>Computation graphs</a></li>
<li class="toc-l1"><a href="higher.html#higher:sec:diag_approx"><span class="num">9.7</span>Diagonal approximations</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.7.1"><span class="num">9.7.1</span>Computation chains</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.7.2"><span class="num">9.7.2</span>Computation graphs</a></li>
<li class="toc-l1"><a href="higher.html#sec-9.8"><span class="num">9.8</span>Randomized estimators</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.8.1"><span class="num">9.8.1</span>Girard-Hutchinson estimator</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.8.2"><span class="num">9.8.2</span>Bartlett estimator for the factorization</a></li>
<li class="toc-l2"><a href="higher.html#sec-9.8.3"><span class="num">9.8.3</span>Bartlett estimator for the diagonal</a></li>
<li class="toc-l1"><a href="higher.html#sec-9.9"><span class="num">9.9</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="gm.html"><span class="num">10</span>Inference in graphical models as differentiation</a></summary><ul>
<li class="toc-l1"><a href="gm.html#gm:sec:chain_rule_proba"><span class="num">10.1</span>Chain rule of probability</a></li>
<li class="toc-l1"><a href="gm.html#sec-10.2"><span class="num">10.2</span>Conditional independence</a></li>
<li class="toc-l1"><a href="gm.html#sec-10.3"><span class="num">10.3</span>Inference problems</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.3.1"><span class="num">10.3.1</span>Joint probability distributions</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.3.2"><span class="num">10.3.2</span>Likelihood</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.3.3"><span class="num">10.3.3</span>Maximum a-posteriori inference</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.3.4"><span class="num">10.3.4</span>Marginal inference</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.3.5"><span class="num">10.3.5</span>Expectation, convex hull, marginal polytope</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.3.6"><span class="num">10.3.6</span>Complexity of brute force</a></li>
<li class="toc-l1"><a href="gm.html#sec-10.4"><span class="num">10.4</span>Markov chains</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.4.1"><span class="num">10.4.1</span>The Markov property</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.4.2"><span class="num">10.4.2</span>Time-homogeneous Markov chains</a></li>
<li class="toc-l2"><a href="gm.html#gm:sec:higher_order_Markov_chain"><span class="num">10.4.3</span>Higher-order Markov chains</a></li>
<li class="toc-l1"><a href="gm.html#gm:sec:bayesian_net"><span class="num">10.5</span>Bayesian networks</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.5.1"><span class="num">10.5.1</span>Expressing variable dependencies using DAGs</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.5.2"><span class="num">10.5.2</span>Parameterizing Bayesian networks</a></li>
<li class="toc-l2"><a href="gm.html#gm:sec:ancestral_sampling"><span class="num">10.5.3</span>Ancestral sampling</a></li>
<li class="toc-l1"><a href="gm.html#gm:sec:mrf"><span class="num">10.6</span>Markov random fields</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.6.1"><span class="num">10.6.1</span>Expressing factors using undirected graphs</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.6.2"><span class="num">10.6.2</span>MRFs as exponential family distributions</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.6.3"><span class="num">10.6.3</span>Conditional random fields</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.6.4"><span class="num">10.6.4</span>Sampling</a></li>
<li class="toc-l1"><a href="gm.html#sec-10.7"><span class="num">10.7</span>Inference on chains</a></li>
<li class="toc-l2"><a href="gm.html#gm:sec:forward_backward_chain"><span class="num">10.7.1</span>The forward-backward algorithm</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.7.2"><span class="num">10.7.2</span>The Viterbi algorithm</a></li>
<li class="toc-l1"><a href="gm.html#sec-10.8"><span class="num">10.8</span>Inference on trees</a></li>
<li class="toc-l1"><a href="gm.html#sec-10.9"><span class="num">10.9</span>Inference as differentiation</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.9.1"><span class="num">10.9.1</span>Inference as gradient of the log-partition</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.9.2"><span class="num">10.9.2</span>Semirings and softmax operators</a></li>
<li class="toc-l2"><a href="gm.html#sec-10.9.3"><span class="num">10.9.3</span>Inference as backpropagation</a></li>
<li class="toc-l1"><a href="gm.html#sec-10.10"><span class="num">10.10</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="imp_diff.html"><span class="num">11</span>Differentiating through optimization</a></summary><ul>
<li class="toc-l1"><a href="imp_diff.html#sec-11.1"><span class="num">11.1</span>Implicit functions</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.1.1"><span class="num">11.1.1</span>Optimization problems</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.1.2"><span class="num">11.1.2</span>Nonlinear equations</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.1.3"><span class="num">11.1.3</span>Application to bilevel optimization</a></li>
<li class="toc-l1"><a href="imp_diff.html#implicit:sec:danskin"><span class="num">11.2</span>Envelope theorems</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.2.1"><span class="num">11.2.1</span>Bertsekas’ theorem</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.2.2"><span class="num">11.2.2</span>Rockafellar’s theorem</a></li>
<li class="toc-l2"><a href="imp_diff.html#imp_diff:sec:danskin"><span class="num">11.2.3</span>Danskin’s theorem</a></li>
<li class="toc-l1"><a href="imp_diff.html#imp_diff:sec:ift"><span class="num">11.3</span>Implicit function theorem</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.3.1"><span class="num">11.3.1</span>Univariate functions</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.3.2"><span class="num">11.3.2</span>Multivariate functions</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.3.3"><span class="num">11.3.3</span>JVP and VJP of implicit functions</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.3.4"><span class="num">11.3.4</span>Proof of the implicit function theorem</a></li>
<li class="toc-l1"><a href="imp_diff.html#imp_diff:sec:adjoint_method"><span class="num">11.4</span>Adjoint state method</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.4.1"><span class="num">11.4.1</span>Differentiating nonlinear equations</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.4.2"><span class="num">11.4.2</span>Relation with envelope theorems</a></li>
<li class="toc-l2"><a href="imp_diff.html#implicit:sec:proof_adjoint_lagrange"><span class="num">11.4.3</span>Proof using the method of Lagrange multipliers</a></li>
<li class="toc-l2"><a href="imp_diff.html#implicit:sec:proof_adjoint_ift"><span class="num">11.4.4</span>Proof using the implicit function theorem</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.4.5"><span class="num">11.4.5</span>Reverse mode as adjoint method with backsubstitution</a></li>
<li class="toc-l1"><a href="imp_diff.html#implicit:sec:inverse_function"><span class="num">11.5</span>Inverse function theorem</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.5.1"><span class="num">11.5.1</span>Differentiating inverse functions</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.5.2"><span class="num">11.5.2</span>Link with the implicit function theorem</a></li>
<li class="toc-l2"><a href="imp_diff.html#sec-11.5.3"><span class="num">11.5.3</span>Proof of inverse function theorem</a></li>
<li class="toc-l1"><a href="imp_diff.html#sec-11.6"><span class="num">11.6</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="grad_est.html"><span class="num">12</span>Differentiating through integration</a></summary><ul>
<li class="toc-l1"><a href="grad_est.html#grad_est:rem:swap_derivative_integration"><span class="num">12.1</span>Differentiation under the integral sign</a></li>
<li class="toc-l1"><a href="grad_est.html#grad_est:sec:diff_thru_expect"><span class="num">12.2</span>Differentiating through expectations</a></li>
<li class="toc-l2"><a href="grad_est.html#grad_est:sec:param_indepdent_expect"><span class="num">12.2.1</span>Parameter-independent distributions</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.2.2"><span class="num">12.2.2</span>Parameter-dependent distributions</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.2.3"><span class="num">12.2.3</span>Application to expected loss functions</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.2.4"><span class="num">12.2.4</span>Application to experimental design</a></li>
<li class="toc-l1"><a href="grad_est.html#grad_est:sec:sfe"><span class="num">12.3</span>Score function estimators, REINFORCE</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.3.1"><span class="num">12.3.1</span>Scalar-valued functions</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.3.2"><span class="num">12.3.2</span>Variance reduction</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.3.3"><span class="num">12.3.3</span>Vector-valued functions</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.3.4"><span class="num">12.3.4</span>Second derivatives</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.3.5"><span class="num">12.3.5</span>Autodiff-friendly implementation</a></li>
<li class="toc-l1"><a href="grad_est.html#grad_est:sec:pge"><span class="num">12.4</span>Path gradient estimators, reparametrization trick</a></li>
<li class="toc-l2"><a href="grad_est.html#grad_est:sec:location_scale_transform"><span class="num">12.4.1</span>Location-scale transforms</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.4.2"><span class="num">12.4.2</span>Differentiable transforms</a></li>
<li class="toc-l2"><a href="grad_est.html#grad_est:sec:its"><span class="num">12.4.3</span>Inverse transforms</a></li>
<li class="toc-l2"><a href="grad_est.html#grad_est:sec:push_forward"><span class="num">12.4.4</span>Pushforward operators</a></li>
<li class="toc-l2"><a href="grad_est.html#grad_est:sec:change_of_var_theorem"><span class="num">12.4.5</span>Change-of-variables theorem</a></li>
<li class="toc-l1"><a href="grad_est.html#sec-12.5"><span class="num">12.5</span>Stochastic programs</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.5.1"><span class="num">12.5.1</span>Stochastic computation graphs</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.5.2"><span class="num">12.5.2</span>Examples</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.5.3"><span class="num">12.5.3</span>Unbiased gradient estimators</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.5.4"><span class="num">12.5.4</span>Local vs. global expectations</a></li>
<li class="toc-l1"><a href="grad_est.html#chap:ode"><span class="num">12.6</span>Differential equations</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.6.1"><span class="num">12.6.1</span>Parameterized differential equations</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.6.2"><span class="num">12.6.2</span>Continuous adjoint method</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.6.3"><span class="num">12.6.3</span>Gradients via the continuous adjoint method</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.6.4"><span class="num">12.6.4</span>Gradients via reverse-mode on discretization</a></li>
<li class="toc-l2"><a href="grad_est.html#sec-12.6.5"><span class="num">12.6.5</span>Reversible discretization schemes</a></li>
<li class="toc-l2"><a href="grad_est.html#ode:sec:proofs"><span class="num">12.6.6</span>Proof of the continuous adjoint method</a></li>
<li class="toc-l1"><a href="grad_est.html#sec-12.7"><span class="num">12.7</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-part">Part IV<span>Smoothing programs</span></li>
<li class="toc-chapter">
<details><summary><a href="smoothing.html"><span class="num">13</span>Smoothing by optimization</a></summary><ul>
<li class="toc-l1"><a href="smoothing.html#smoothing:sec:primal"><span class="num">13.1</span>Primal approach</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.1.1"><span class="num">13.1.1</span>Infimal convolution</a></li>
<li class="toc-l2"><a href="smoothing.html#smoothing:sec:moreau_env"><span class="num">13.1.2</span>Moreau envelope</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.1.3"><span class="num">13.1.3</span>Vector-valued functions</a></li>
<li class="toc-l1"><a href="smoothing.html#duality:sec:conjugates"><span class="num">13.2</span>Legendre–Fenchel transforms, convex conjugates</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.2.1"><span class="num">13.2.1</span>Definition</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.2.2"><span class="num">13.2.2</span>Closed-form examples</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.2.3"><span class="num">13.2.3</span>Properties</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.2.4"><span class="num">13.2.4</span>Conjugate calculus</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.2.5"><span class="num">13.2.5</span>Fast Legendre transform</a></li>
<li class="toc-l1"><a href="smoothing.html#smoothing:sec:dual_approach"><span class="num">13.3</span>Dual approach</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.3.1"><span class="num">13.3.1</span>Duality between strong convexity and smoothness</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.3.2"><span class="num">13.3.2</span>Smoothing by dual regularization</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.3.3"><span class="num">13.3.3</span>Equivalence between primal and dual regularizations</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.3.4"><span class="num">13.3.4</span>Regularization scaling</a></li>
<li class="toc-l2"><a href="smoothing.html#smoothing:sec:entropies"><span class="num">13.3.5</span>Generalized entropies</a></li>
<li class="toc-l1"><a href="smoothing.html#smoothing:sec:relu"><span class="num">13.4</span>Smoothed ReLU functions</a></li>
<li class="toc-l1"><a href="smoothing.html#smoothing:sec:max_argmax"><span class="num">13.5</span>Smoothed max operators</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.5.1"><span class="num">13.5.1</span>Definition and properties</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.5.2"><span class="num">13.5.2</span>Reduction to root finding</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.5.3"><span class="num">13.5.3</span>The softmax</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.5.4"><span class="num">13.5.4</span>The sparsemax</a></li>
<li class="toc-l2"><a href="smoothing.html#sec-13.5.5"><span class="num">13.5.5</span>Recovering smoothed ReLU functions</a></li>
<li class="toc-l1"><a href="smoothing.html#inf_conv:sec:sigmoid"><span class="num">13.6</span>Relaxed step functions (sigmoids)</a></li>
<li class="toc-l1"><a href="smoothing.html#inf_conv:sec:relaxed_argmax"><span class="num">13.7</span>Relaxed argmax operators</a></li>
<li class="toc-l1"><a href="smoothing.html#sec-13.8"><span class="num">13.8</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="conv.html"><span class="num">14</span>Smoothing by integration</a></summary><ul>
<li class="toc-l1"><a href="conv.html#sec-14.1"><span class="num">14.1</span>Convolution</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.1.1"><span class="num">14.1.1</span>Convolution operators</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.1.2"><span class="num">14.1.2</span>Convolution with a kernel</a></li>
<li class="toc-l2"><a href="conv.html#conv:sec:discrete_conv"><span class="num">14.1.3</span>Discrete convolution</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.1.4"><span class="num">14.1.4</span>Differentiation</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.1.5"><span class="num">14.1.5</span>Multidimensional convolution</a></li>
<li class="toc-l2"><a href="conv.html#conv:sec:link_conv_inf_conv"><span class="num">14.1.6</span>Link between convolution and infimal convolution</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.1.7"><span class="num">14.1.7</span>The soft infimal convolution</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.1.8"><span class="num">14.1.8</span>The soft Moreau envelope</a></li>
<li class="toc-l1"><a href="conv.html#sec-14.2"><span class="num">14.2</span>Fourier and Laplace transforms</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.2.1"><span class="num">14.2.1</span>Convolution theorem</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.2.2"><span class="num">14.2.2</span>Link between Fourier and Legendre transforms</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.2.3"><span class="num">14.2.3</span>The soft Legendre-Fenchel transform</a></li>
<li class="toc-l1"><a href="conv.html#sec-14.3"><span class="num">14.3</span>Examples</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.3.1"><span class="num">14.3.1</span>Smoothed step function</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.3.2"><span class="num">14.3.2</span>Smoothed ReLU function</a></li>
<li class="toc-l1"><a href="conv.html#perturb:sec:blackbox"><span class="num">14.4</span>Perturbation of blackbox functions</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.4.1"><span class="num">14.4.1</span>Expectation in a location-scale family</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.4.2"><span class="num">14.4.2</span>Gradient estimation by reparametrization</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.4.3"><span class="num">14.4.3</span>Gradient estimation by SFE, Stein’s lemma</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.4.4"><span class="num">14.4.4</span>Link between reparametrization and SFE</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.4.5"><span class="num">14.4.5</span>Variance reduction and evolution strategies</a></li>
<li class="toc-l2"><a href="conv.html#pert:sec:zero_temp_limit"><span class="num">14.4.6</span>Zero-temperature limit</a></li>
<li class="toc-l1"><a href="conv.html#pert:sec:gumbel_trick"><span class="num">14.5</span>Gumbel tricks</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.5.1"><span class="num">14.5.1</span>The Gumbel distribution</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.5.2"><span class="num">14.5.2</span>Perturbed comparison</a></li>
<li class="toc-l2"><a href="conv.html#perturb:sec:argmax"><span class="num">14.5.3</span>Perturbed argmax</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.5.4"><span class="num">14.5.4</span>Perturbed max</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.5.5"><span class="num">14.5.5</span>Gumbel trick for sampling</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.5.6"><span class="num">14.5.6</span>Perturb-and-MAP</a></li>
<li class="toc-l2"><a href="conv.html#sec-14.5.7"><span class="num">14.5.7</span>Gumbel-softargmax</a></li>
<li class="toc-l1"><a href="conv.html#sec-14.6"><span class="num">14.6</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-part">Part V<span>Optimizing differentiable programs</span></li>
<li class="toc-chapter">
<details><summary><a href="optimization-basics.html"><span class="num">15</span>Optimization basics</a></summary><ul>
<li class="toc-l1"><a href="optimization-basics.html#sec-15.1"><span class="num">15.1</span>Objective functions</a></li>
<li class="toc-l1"><a href="optimization-basics.html#sec-15.2"><span class="num">15.2</span>Oracles</a></li>
<li class="toc-l1"><a href="optimization-basics.html#sec-15.3"><span class="num">15.3</span>Variational perspective of optimization algorithms</a></li>
<li class="toc-l1"><a href="optimization-basics.html#optim:sec:function_classes"><span class="num">15.4</span>Classes of functions</a></li>
<li class="toc-l2"><a href="optimization-basics.html#sec-15.4.1"><span class="num">15.4.1</span>Lipschitz functions</a></li>
<li class="toc-l2"><a href="optimization-basics.html#sec-15.4.2"><span class="num">15.4.2</span>Smooth functions</a></li>
<li class="toc-l2"><a href="optimization-basics.html#sec-15.4.3"><span class="num">15.4.3</span>Convex functions</a></li>
<li class="toc-l2"><a href="optimization-basics.html#sec-15.4.4"><span class="num">15.4.4</span>Strongly-convex functions</a></li>
<li class="toc-l2"><a href="optimization-basics.html#sec-15.4.5"><span class="num">15.4.5</span>Nonconvex functions</a></li>
<li class="toc-l1"><a href="optimization-basics.html#optim:sec:perf"><span class="num">15.5</span>Performance guarantees</a></li>
<li class="toc-l1"><a href="optimization-basics.html#sec-15.6"><span class="num">15.6</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="optim.html"><span class="num">16</span>First-order optimization</a></summary><ul>
<li class="toc-l1"><a href="optim.html#optim:sec:gd"><span class="num">16.1</span>Gradient descent</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.1.1"><span class="num">16.1.1</span>Variational perspective</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.1.2"><span class="num">16.1.2</span>Convergence for smooth functions</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.1.3"><span class="num">16.1.3</span>Momentum and accelerated variants</a></li>
<li class="toc-l1"><a href="optim.html#optim:sec:sgd"><span class="num">16.2</span>Stochastic gradient descent</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.2.1"><span class="num">16.2.1</span>Stochastic gradients</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.2.2"><span class="num">16.2.2</span>Vanilla SGD</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.2.3"><span class="num">16.2.3</span>Momentum variants</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.2.4"><span class="num">16.2.4</span>Adaptive variants</a></li>
<li class="toc-l1"><a href="optim.html#optim:sec:proj_grad"><span class="num">16.3</span>Projected gradient descent</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.3.1"><span class="num">16.3.1</span>Variational perspective</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.3.2"><span class="num">16.3.2</span>Optimality conditions</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.3.3"><span class="num">16.3.3</span>Commonly used projections</a></li>
<li class="toc-l1"><a href="optim.html#optim:sec:prox_grad"><span class="num">16.4</span>Proximal gradient method</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.4.1"><span class="num">16.4.1</span>Variational perspective</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.4.2"><span class="num">16.4.2</span>Optimality conditions</a></li>
<li class="toc-l2"><a href="optim.html#sec-16.4.3"><span class="num">16.4.3</span>Commonly-used proximal operators</a></li>
<li class="toc-l1"><a href="optim.html#sec-16.5"><span class="num">16.5</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="optim2.html"><span class="num">17</span>Second-order optimization</a></summary><ul>
<li class="toc-l1"><a href="optim2.html#optim:sec:newton"><span class="num">17.1</span>Newton’s method</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.1.1"><span class="num">17.1.1</span>Variational perspective</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.1.2"><span class="num">17.1.2</span>Regularized Newton method</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.1.3"><span class="num">17.1.3</span>Approximate direction</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.1.4"><span class="num">17.1.4</span>Convergence guarantees</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.1.5"><span class="num">17.1.5</span>Linesearch</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.1.6"><span class="num">17.1.6</span>Geometric interpretation</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.1.7"><span class="num">17.1.7</span>Stochastic Newton’s method</a></li>
<li class="toc-l1"><a href="optim2.html#optim:sec:gauss_newton"><span class="num">17.2</span>Gauss-Newton method</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.2.1"><span class="num">17.2.1</span>With exact outer function</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.2.2"><span class="num">17.2.2</span>With approximate outer function</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.2.3"><span class="num">17.2.3</span>Linesearch</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.2.4"><span class="num">17.2.4</span>Stochastic Gauss-Newton</a></li>
<li class="toc-l1"><a href="optim2.html#optim:sec:nat_grad"><span class="num">17.3</span>Natural gradient descent</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.3.1"><span class="num">17.3.1</span>Variational perspective</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.3.2"><span class="num">17.3.2</span>Stochastic natural gradient descent</a></li>
<li class="toc-l1"><a href="optim2.html#sec-17.4"><span class="num">17.4</span>Quasi-Newton methods</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.4.1"><span class="num">17.4.1</span>BFGS</a></li>
<li class="toc-l2"><a href="optim2.html#sec-17.4.2"><span class="num">17.4.2</span>Limited-memory BFGS</a></li>
<li class="toc-l1"><a href="optim2.html#sec-17.5"><span class="num">17.5</span>Approximate Hessian diagonal inverse preconditioners</a></li>
<li class="toc-l1"><a href="optim2.html#sec-17.6"><span class="num">17.6</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<details><summary><a href="duality.html"><span class="num">18</span>Duality</a></summary><ul>
<li class="toc-l1"><a href="duality.html#duality:sec:dual_norms"><span class="num">18.1</span>Dual norms</a></li>
<li class="toc-l1"><a href="duality.html#sec-18.2"><span class="num">18.2</span>Fenchel duality</a></li>
<li class="toc-l1"><a href="duality.html#sec-18.3"><span class="num">18.3</span>Bregman divergences</a></li>
<li class="toc-l1"><a href="duality.html#sec-18.4"><span class="num">18.4</span>Fenchel-Young loss functions</a></li>
<li class="toc-l1"><a href="duality.html#sec-18.5"><span class="num">18.5</span>Summary</a></li>
</ul></details>
</li>
<li class="toc-chapter">
<a href="references.html">References</a>
</li>
</ul></nav>
<div class="sidebar-foot"><label class="theme-picker">Style <select id="theme-select" aria-label="Page style"><option value="sky" data-tone="light">Sky</option><option value="solarized" data-tone="light">Solarized</option><option value="mint" data-tone="light">Mint</option><option value="stone" data-tone="light">Stone</option><option value="dark" data-tone="dark">Dark</option></select></label></div>
</aside>
<main id="content">
<article>
<h1 id="top">Source code</h1>
<p>We provide some Python source code to accompany the book on <a href="https://github.com/diffprog/code">github</a>.</p>
</article>
<nav class="pager">
<a class="prev" href="acknowledgements.html">&larr; Acknowledgements</a>
<a class="next" href="notation.html">Notation &rarr;</a>
</nav>
</main>
<script src="assets/app.js"></script>
</body>
</html>
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.