Summary This post serves as a broad overview of many optimization methods and algorithms. For specifics, please refer to the post of each algorithm. It is advised to read the post about Functional Analysis to better understand the notation used here. Setup We are going to consider a function $$ f = g + h. $$ Depending on the different hypothesis of $f$, $g$ and $h$ we may be able to use different optimization algorithms. ...
The study of optimization of general functions often rely on many Functional Analysis tools, particularly Hilbert spaces. One can think about Hilbert spaces as a generalization of Euclidean spaces. This allows us to define most algorithms in a generalized fashion, without worrying about the underlying structure of the problem’s domain. Of course, most applications consider an Euclidean space $\mathbb{R}^d$, but it is just a special case of a Hilbert space. ...
Discrete Measures Definition: Shannon-Boltzmann entropy Let $P \in U(a, b)$ be a coupling matrix for discrete measures with vectors $a$ and $b$. Then, the Shannon-Boltzmann entropy is $$ H(P) = - \sum_{i, j} P_{i, j} \log{(P_{i, j})}, $$ where $0 = \log{0}$. Note that $$ \nabla^2 H(P) = - \diag(P_{i, j}^{-1}). $$ So, $H$ is strictly concave. Let us add a regularization term to the discrete Kantorovich problem. $\varepsilon$ will be our regularization weight and it works as a kind of “temperature”. ...
Summary Up to this point we have studied Monge and Kantorovich problems. Duality of Kantorovich and the Wasserstein metric. Slicing OT as a way to lower bound $\W_p$. Now, we are interested in solving the Kantorovich problem in an alternative way. The goal here is to find a condition that is sufficient to retrieve a map from $\mathcal{X}$ to $\mathcal{Y}$. Then, the optimal transport will be given by the objects that minimize a certain criterion over this condition. ...
Goal: Identify items that are bought together by sufficiently many customers. We will do so by finding dependencies among items from data collected. Our input is composed of a table of items and a table of baskets. Each basket is a list of items purchased together. Then, we use the baskets to find dependencies of the form $\{x, y, z\} \rightarrow \{v, w\}$. Definition: Support The support of a set of items $I$ is the number of baskets that contain all the items in $I$. Given a support threshold, we can classify itemsets as frequent of not. ...