conf

1 files changed, 38 insertions, 38 deletions

diff --git a/main.tex b/main.tex
index 189156c..148aedc 100644
--- a/main.tex
+++ b/main.tex
@@ -37,7 +37,7 @@ Here, we use a relaxation of the objective function which is tailored to the
 problem of ridge regression. We define:
 \begin{displaymath}
     \forall\lambda\in[0,1]^{|\mathcal{N}|}\,\quad L_{\mathcal{N}}(\lambda) \defeq
-    \log\det\left(I_d + \mu\sum_{i\in\mathcal{N}} \lambda_i x_i x_i^*\right)
+    \log\det\left(I_d + \mu\sum_{i\in\mathcal{N}} \lambda_i x_i \T{x_i}\right)
 \end{displaymath}
 
 We can now present the mechanism we use, which has a same flavor to Chen's and
@@ -47,7 +47,7 @@ Singer's
     \caption{Mechanism for ridge regression}
     \begin{algorithmic}[1]
     \State $i^* \gets \argmax_{j\in\mathcal{N}}V(j)$
-    \State $x^* \gets \argmax_{x\in[0,1]^n} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
+    \State $x^* \gets \argmax_{x\in[0,1]^{|\mathcal{N}|}} \{L_{\mathcal{N}\setminus\{i^*\}}(x)
                                     \,|\, c(x)\leq B\}$
         \Statex
         \If{$L(x^*) < CV(i^*)$}
@@ -118,7 +118,7 @@ The mechanism is monotone.
     \end{displaymath}
     in an earlier iteration of the greedy heuristic. Let us denote by $S_i$
     (resp. $S_i'$) the set to which $i$ is added when reporting cost $c_i$
-    (resp. $c_i'$). We have $S_i'\subset S_i$. Moreover:
+    (resp. $c_i'$). We have $S_i'\subseteq S_i$. Moreover:
     \begin{align*}
         c_i' & \leq c_i \leq
         \frac{B}{2}\frac{V(S_i\cup\{i\})-V(S_i)}{V(S_i\cup\{i\})}\\
@@ -245,30 +245,30 @@ of the objective function and thus ensures a constant approximation of the
 value function. The difficulty resides in showing that the ratio of the two
 relaxations is bounded.
 
-We say that $R_\mathcal{N}:[0,1]^n\rightarrow\mathbf{R}$ is a relaxation of the
+We say that $R_\mathcal{N}:[0,1]^{|\mathcal{N}|}\rightarrow\reals$ is a relaxation of the
 value function $V$ over $\mathcal{N}$ if it coincides with $V$ at binary
-points. Formally, for any $S\subset\mathcal{N}$, let $\mathbf{1}_S$ denote the
+points. Formally, for any $S\subseteq\mathcal{N}$, let $\mathbf{1}_S$ denote the
 indicator vector of $S$. $R_\mathcal{N}$ is a relaxation of $V$ over
 $\mathcal{N}$ iff:
 \begin{displaymath}
-    \forall S\subset\mathcal{N},\; R_\mathcal{N}(\mathbf{1}_S) = V(S)
+    \forall S\subseteq\mathcal{N},\; R_\mathcal{N}(\mathbf{1}_S) = V(S)
 \end{displaymath}
 
 We can extend the optimisation problem defined above to a relaxation by
 extending the cost function:
 \begin{displaymath}
-    \forall \lambda\in[0,1]^n,\; c(\lambda)
+    \forall \lambda\in[0,1]^{|\mathcal{N}|},\; c(\lambda)
     = \sum_{i\in\mathcal{N}}\lambda_ic_i
 \end{displaymath}
 The optimisation problem becomes:
 \begin{displaymath}
     OPT(R_\mathcal{N}, B) =
-    \max_{\lambda\in[0,1]^n}\left\{R_\mathcal{N}(\lambda)\,|\, c(\lambda)\leq B\right\}
+    \max_{\lambda\in[0,1]^{|\mathcal{N}|}}\left\{R_\mathcal{N}(\lambda)\,|\, c(\lambda)\leq B\right\}
 \end{displaymath}
 The relaxations we will consider here rely on defining a probability
 distribution over subsets of $\mathcal{N}$.
 
-Let $\lambda\in[0,1]^n$, let us define:
+Let $\lambda\in[0,1]^{|\mathcal{N}|}$, let us define:
 \begin{displaymath}
     P_\mathcal{N}^\lambda(S) = \prod_{i\in S}\lambda_i
     \prod_{i\in\mathcal{N}\setminus S}(1-\lambda_i)
@@ -284,17 +284,17 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
         \begin{align*}
             F_\mathcal{N}(\lambda) 
             & = \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[\log\det A(S)\big]\\
-            & = \sum_{S\subset\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)\\
-            & = \sum_{S\subset\mathcal{N}} P_\mathcal{N}^\lambda(S) \log\det A(S)\\
+            & = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) V(S)\\
+            & = \sum_{S\subseteq\mathcal{N}} P_\mathcal{N}^\lambda(S) \log\det A(S)\\
         \end{align*}
     \item the \emph{concave relaxation} of $V$:
         \begin{align*}
             L_{\mathcal{N}}(\lambda) 
             & = \log\det \mathbb{E}_{S\sim P_\mathcal{N}^\lambda}\big[A(S)\big]\\
-            & = \log\det\left(\sum_{S\subset N}
+            & = \log\det\left(\sum_{S\subseteq N}
                 P_\mathcal{N}^\lambda(S)A(S)\right)\\
             & = \log\det\left(I_d + \mu\sum_{i\in\mathcal{N}}
-                \lambda_ix_ix_i^*\right)\\
+                \lambda_ix_i\T{x_i}\right)\\
             & \defeq \log\det \tilde{A}(\lambda)
         \end{align*}
 \end{itemize}
@@ -315,8 +315,8 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
 \end{proof}
 
 \begin{lemma}[Rounding]\label{lemma:rounding}
-    For any feasible $\lambda\in[0,1]^n$, there exists a feasible
-    $\bar{\lambda}\in[0,1]^n$ such that at most one of its component is
+    For any feasible $\lambda\in[0,1]^{|\mathcal{N}|}$, there exists a feasible
+    $\bar{\lambda}\in[0,1]^{|\mathcal{N}|}$ such that at most one of its component is
     fractional, that is, lies in $(0,1)$ and:
     \begin{displaymath}
         F_{\mathcal{N}}(\lambda)\leq F_{\mathcal{N}}(\bar{\lambda})
@@ -373,7 +373,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
 \begin{lemma}\label{lemma:relaxation-ratio}
     The following inequality holds:
     \begin{displaymath}
-        \forall\lambda\in[0,1]^n,\; 
+        \forall\lambda\in[0,1]^{|\mathcal{N}|},\; 
         \frac{\log\big(1+\mu\big)}{2\mu}
         \,L_\mathcal{N}(\lambda)\leq
         F_\mathcal{N}(\lambda)\leq L_{\mathcal{N}}(\lambda)
@@ -422,9 +422,9 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     Hence:
     \begin{multline*}
         \partial_i F_\mathcal{N} =
-        \sum_{\substack{S\subset\mathcal{N}\\ i\in S}}
+        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S\setminus\{i\})V(S)\\
-        - \sum_{\substack{S\subset\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
+        - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)\\
     \end{multline*}
 
@@ -432,9 +432,9 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     $S'\cup\{i\}$, we can write:
     \begin{multline*}
         \partial_i F_\mathcal{N} =
-        \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S\cup\{i\})\\
-        - \sum_{\substack{S\subset\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
+        - \sum_{\substack{S\subseteq\mathcal{N}\\ i\in \mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)V(S)\\
     \end{multline*}
 
@@ -442,50 +442,50 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     $S$:
     \begin{displaymath}
         \partial_i F_\mathcal{N}(\lambda) = 
-        \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)
-        \log\Big(1 + \mu x_i^*A(S)^{-1}x_i\Big)
+        \log\Big(1 + \mu \T{x_i}A(S)^{-1}x_i\Big)
     \end{displaymath}
 
     The computation of the derivative of $L_\mathcal{N}$ uses standard matrix
     calculus and gives:
     \begin{displaymath}
         \partial_i L_\mathcal{N}(\lambda)
-        = \mu x_i^* \tilde{A}(\lambda)^{-1}x_i
+        = \mu \T{x_i}\tilde{A}(\lambda)^{-1}x_i
     \end{displaymath}
     
     Using the following inequalities:
     \begin{gather*}
-        \forall S\subset\mathcal{N}\setminus\{i\},\quad
+        \forall S\subseteq\mathcal{N}\setminus\{i\},\quad
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S)\geq
         P_{\mathcal{N}\setminus\{i\}}^\lambda(S\cup\{i\})\\
-        \forall S\subset\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) 
+        \forall S\subseteq\mathcal{N},\quad P_{\mathcal{N}\setminus\{i\}}^\lambda(S) 
         \geq P_\mathcal{N}^\lambda(S)\\
-        \forall S\subset\mathcal{N},\quad A(S)^{-1} \geq A(S\cup\{i\})^{-1}\\
+        \forall S\subseteq\mathcal{N},\quad A(S)^{-1} \geq A(S\cup\{i\})^{-1}\\
     \end{gather*}
     we get:
     \begin{align*}
         \partial_i F_\mathcal{N}(\lambda) 
-        & \geq \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        & \geq \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_\mathcal{N}^\lambda(S)
-        \log\Big(1 + \mu x_i^*A(S)^{-1}x_i\Big)\\
+        \log\Big(1 + \mu \T{x_i}A(S)^{-1}x_i\Big)\\
         & \geq \frac{1}{2}
-        \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_\mathcal{N}^\lambda(S)
-        \log\Big(1 + \mu x_i^*A(S)^{-1}x_i\Big)\\
+        \log\Big(1 + \mu \T{x_i}A(S)^{-1}x_i\Big)\\
         &\hspace{-3.5em}+\frac{1}{2}
-        \sum_{\substack{S\subset\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
+        \sum_{\substack{S\subseteq\mathcal{N}\\ i\in\mathcal{N}\setminus S}}
         P_\mathcal{N}^\lambda(S\cup\{i\})
-        \log\Big(1 + \mu x_i^*A(S\cup\{i\})^{-1}x_i\Big)\\
+        \log\Big(1 + \mu \T{x_i}A(S\cup\{i\})^{-1}x_i\Big)\\
         &\geq \frac{1}{2}
-        \sum_{S\subset\mathcal{N}}
+        \sum_{S\subseteq\mathcal{N}}
         P_\mathcal{N}^\lambda(S)
-        \log\Big(1 + \mu x_i^*A(S)^{-1}x_i\Big)\\
+        \log\Big(1 + \mu \T{x_i}A(S)^{-1}x_i\Big)\\
     \end{align*}
 
     Using that $A(S)\geq I_d$ we get that:
     \begin{displaymath}
-        \mu x_i^*A(S)^{-1}x_i \leq \mu
+        \mu \T{x_i}A(S)^{-1}x_i \leq \mu
     \end{displaymath}
     
     Moreover:
@@ -498,7 +498,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \begin{displaymath}
         \partial_i F_\mathcal{N}(\lambda) \geq
         \frac{\log\big(1+\mu\big)}{2\mu}
-        x_i^*\bigg(\sum_{S\subset\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i
+        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)^{-1}\bigg)x_i
     \end{displaymath}
     
     Finally, using that the inverse is a matrix convex function over symmetric
@@ -506,7 +506,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
     \begin{align*}
         \partial_i F_\mathcal{N}(\lambda) &\geq
         \frac{\log\big(1+\mu\big)}{2\mu}
-        x_i^*\bigg(\sum_{S\subset\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i\\
+        \T{x_i}\bigg(\sum_{S\subseteq\mathcal{N}}P_\mathcal{N}^\lambda(S)A(S)\bigg)^{-1}x_i\\
         & \geq \frac{\log\big(1+\mu\big)}{2\mu}
         \partial_i L_\mathcal{N}(\lambda)
     \end{align*}
@@ -515,7 +515,7 @@ We will consider two relaxations of the value function $V$ over $\mathcal{N}$:
 We can now prove lemma TODO from previous section.
 
 \begin{proof}
-    Let us consider a feasible point $\lambda^*\in[0,1]^n$ such that $L_\mathcal{N}(\lambda^*)
+    Let us consider a feasible point $\lambda^*\in[0,1]^{|\mathcal{N}|}$ such that $L_\mathcal{N}(\lambda^*)
     = OPT(L_\mathcal{N}, B)$. By applying lemma~\ref{lemma:relaxation-ratio}
     and lemma~\ref{lemma:rounding} we get a feasible point $\bar{\lambda}$ with at most
     one fractional component such that: