a power series centered at \(a\) is defined with \(c_{n} \in \mathbb{R}\), whereby:

\begin{equation} f(x) = \sum_{n=0}^{\infty} c_{n}(x-a)^{n} \end{equation}

meaning it is written as \(c_0 + c_1(x-a) + c_2(x-a)^{2} + c_3 (x-a)^{3} + \cdots\)

radius of convergence

• there is a radius of convergence \(R \geq 0\) for any power series, possibly infinite, by which the series is absolutely convergent where \(|x-a| < R\), and it does not converge when \(|x-a| > R\) , the case where \(|x-a| = R\) is uncertain
• ratio test: if all coefficients \(c_{n}\) are nonzero, and some \(\lim_{n \to \infty} \left| \frac{c_{n}}{c_{n+1}} \right|\) evaluates to some \(c\) — if \(c\) is positive or \(+\infty\), then that limit is equivalent to the radius of convergence
• Taylor’s Formula: a power series \(f(x)\) can be differentiated, integrated on the bounds of \((a-R, a+R)\), the derivatives and integrals will have radius of convergence \(R\) and \(c_{n} = \frac{f^{(n)}(a)}{n!}\) to construct the series

linear combinations of power series

When \(\sum_{n=0}^{\infty} a_{n}\) and \(\sum_{n=0}^{\infty} b_{n}\) are both convergent, linear combinations of them can be described in the usual fashion:

Key Sequence

Notation

New Concepts

• Exponential Family
• Generalized Linear Models
• Softmax Regression

Important Results / Claims

Questions

Interesting Factoids

• properties of exponential family
• Bernoulli distribution is in the exponential family

Scratch

Key Sequence

New Concepts

• substitution method
• k-select

Important Results / Claims

Questions

Interesting Factoids

scratchpad

A Generalized Linear Model is a model of data with the following properties:

1. The model for \(P(y \mid x; \theta)\) should come from a exponential family (depending on what your distribution of \(y\) is—for real data, we pick Gaussian distribution, for binary data, we pick Bernoulli distribution, for counts, we use poisson distribution, \(\mathbb{R}^{+}\) we use gamma distribution or exponential distribution, and for distributions of distributions we use Beta Distribution or Dirichlet Distribution).
2. \(\eta = \theta^{T}x\), where \(\theta,x \in \mathbb{R}^{d}\)
3. at test time…
   • we want to output \(\mathbb{E}\qty [y|x; \theta]\)
   • so our predictor is written as \(h_{\theta}\qty(x) = \mathbb{E}\qty [y|x; \theta]\)
4. at train time, we maximize log likelihood \(\max_{\theta} \sum_{i=1}^{n} \log P\qty(y^{(i)} | \theta^{T}x^{(i)})\)
5. to update using gradient ascend, \(\theta_{j} = \theta_{j} + \alpha \sum_{i=1}^{n} \qty(y^{(i)} - h_{\theta}\qty(x^{(i)}))x_{j}^{(i)}\)

We also have two fancy names for things

\begin{equation} \text{SELECT}\qty(A,k) \end{equation}

returns the kth smallest element of \(A\).

additional information

properties of k-select

• \(\text{SELECT}\qty(A,1)\) is the smallest
• \(\text{SELECT}\qty(A, \frac{n}{2})\) is the median
• \(\text{SELECT}\qty(A,n)\) is the maximum

a naive solution

Naively, \(\text{SELECT}\qty(A,C)\) for any constant \(C\) is in \(O\qty(n)\) because you can just keep track of the \(C\) smallest array. But turns out, something like the median \(\text{SELECT}\qty(A, \frac{n}{2})\) is basically insertion sort, so \(O\qty(n^{2})\).

an actual linear-time solution

Proof idea: we want to pick a “pivot” value which is in the list; then partition the array into things that are less than that value, or more than that value.