gradient descent makes a pass over all points to make one gradient step. We can instead approximate gradients on a minibatch of data. This is the idea behind stochastic-gradient-descent.

\begin{equation} \theta^{t+1} = \theta^{t} - \eta \nabla_{\theta} L(f_{\theta}(x), y) \end{equation}

this terminates when theta differences becomes small, or when progress halts: like when \(\theta\) begins going up instead.

we update the weights in SGD by taking a single random sample and moving weights to that direction.

strongly connected components expose local communities in a graph.

constituents

graph \(V,E\)

requirements

strongly connected: for all \(v,w \in V\), there is a path from \(v \to w\), and there’s a path for \(w \to v\).

We can decompose a graph into strongly connected components where a subgraph is strongly connected. (i.e. they form equivalence class under “is strongly connected.”)

additional information

Kosaraju’s Algorithm

A way to find strongly connected components in linear time \(O\qty(n+m)\).

Key Sequence

Notation

New Concepts

• strongly connected components
  • condensation graph
  • Kosaraju’s Algorithm

Important Results / Claims

Questions

Interesting Factoids

Neural Networks are powerful because of self organization of the intermediate levels.

Neural Network Layer

\begin{equation} z = Wx + b \end{equation}

for the output, and the activations:

\begin{equation} a = f(z) \end{equation}

where the activation function \(f\) is applied element-wise.

Why are NNs Non-Linear?

1. there’s no representational power with multiple linear (though, there is better learning/convergence properties even with big linear networks!)
2. most things are non-linear!

Activation Function

We want non-linear and non-threshold (0/1) activation functions because it has a slope—meaning we can perform gradient-based learning.