Stating the optimization problem
Let \(q = (q_1, \ldots, q_n)\) be the resampling distribution. Here, \(n\) is the number of rows in the original dataset, and \(q_i\) is the probability that row \(i\) will be chosen for a given row of the bootstrap dataset. Let \(p = (p_1, \ldots, p_n)\) be uniform (i.e., \(p_i = 1/n\), the resampling distribution of the ordinary bootstrap).
We want to find a \(q\) that is as close to \(p\) as possible. We consider three possible measures of distance. First, the Euclidean distance is defined as: \[
D_{Euclidian}= \sum_{i = 1}^n (p_i - q_i)^2
\] Second, the Backwards Kullback-Leibler (KL) divergence (which is technically not considered a distance metric) from \(p\) to \(q\) is defined as: \[
\begin{aligned}
D_{KL}(q||p)
&= \sum_{i = 1}^n q_i \log \frac{q_i}{p_i} \\
&= \sum_{i = 1}^n q_i \log nq_i
\end{aligned}
\]
Third, the Forwards Kullback-Leibler (KL) divergence from \(q\) to \(p\) is defined as: \[
D_{KL}(p||q) = \sum_{i = 1}^n p_i \log \frac{p_i}{q_i} \\
\]
Note that minimizing \(D_{KL}(p||q)\) is the same as minimizing \(-\sum_{i = 1}^n \log q_i\).
The goal of determining the weights for the ‘tilted bootstrap’ may be formulated as a constrained optimization problem: \[
q=\underset{q \in S}{\operatorname{argmin}} {D(p,q)}
\] where,
\[
S=\{q|\space q_i>0 \space for \space i \in {1...n}, \space and \space \sum_{i = 1}^n q_i=1, \space and \space X^Tq = y \space \}.
\] Here \(y\) is a vector of target means for the columns.
Solving the optimization problem
In the case of the Euclidean distance, the problem is a standard “Quadratic Programming” problem which we solve using the ‘solve.QP’ function from the ‘quadprog’ package.
To solve the problem for the Backwards KL distance, we use the Lagrangian approach. Define \(A=[X|1]\) (i.e. \(A\) is the concatenation of \(X\) with a conformal column of all ones). Also, let \(b=[y^T|1]^T\) (i.e. \(b\) is the \(y\) vector with a “one” element concatenated to the end). The Lagrangian for this optimization problem is
\[
\begin{aligned}
L(q, \lambda) &= \sum_{i = 1}^n q_i \log nq_i + \lambda (A'q - b) \\
&= \sum_{i = 1}^n \left [ q_i \log nq_i + \sum_{k = 1}^{K+1} \lambda_k (A_{ik} q_i - b_k) \right ]
\end{aligned}
\]
where
- The vector \(\lambda\) of length \(K+1\) represents the Lagrange multipliers.
- \(K\) is the number of columns of \(X\).
- \(A_{ik}\) is the element of \(A\) in row \(i\) and column \(k\).
To optimize, we start by setting the gradient of \(L\) equal to zero and solve for a locally optimal \(q\) in terms of \(\lambda\). \[
\begin{aligned}
0 &= \left . \frac{\partial L}{\partial q_i} \right |_{(q, \ \lambda)} \\
&= \log nq_i + \frac{1}{n} + A_i' \lambda \\
\log nq_i &= -\frac{1}{n} - A_i' \lambda \\
q_i &= e^{-A_i' \lambda^*}
\end{aligned}
\] Here, \(\lambda^*\) is scaled and recentered to absorb the constants in the equation.
Here, \(X_i\) is the \(i\)’th row of \(X\) (expressed as a column vector). Hence, the locally optimal \(q\) in terms of the vector \(\lambda^*\) is
\[q^*(\lambda^*) = \left (e^{-A_1' \lambda^*}, \ldots, e^{-A_n' \lambda^*} \right ) \] To find \(\lambda^*\), we solve the equation \(A'q^*(\lambda^*) = b\) by using the Newton-Raphson algorithm. Thus, it turns out that the backwards version of the KL distance results in what is called “exponential tilting.” Some of the elegant properties of exponential tilting are described in a different vignette.
Similarly, it may be shown for the forward version of the KL, that the locally optimal \(q\) in terms of \(\lambda\) is
\[q^*(\lambda) = \left (\frac{1}{A_1^T \lambda}, \ldots, \frac{1}{ A_n^T \lambda} \right ) \]
However, tboot’s current implementation of forward KL distance is not very stable. A warning will be issued if the user selects the forward KL distance in the tboot package.
