accuracy, monotone

1 files changed, 32 insertions, 30 deletions

diff --git a/appendix.tex b/appendix.tex
index 3685c2f..e964a40 100644
--- a/appendix.tex
+++ b/appendix.tex
@@ -1,4 +1,5 @@
 
+\section{Proofs of Statements in Section~\ref{sec:concave}}
 \subsection{Proof of Lemma~\ref{lemma:relaxation-ratio}}\label{proofofrelaxation-ratio}
 %\begin{proof}
     The bound $F_{\mathcal{N}}(\lambda)\leq L_{\mathcal{N}}(\lambda)$ follows by the concavity of the $\log\det$ function and Jensen's inequality.
@@ -241,19 +242,20 @@ one fractional component such that
     \end{equation}
 Together, \eqref{eq:e1} and \eqref{eq:e2} imply the proposition.\qed
 
-\section{Proof of Proposition~\ref{prop:monotonicity}}
+\section{Proof of Proposition~\ref{prop:monotonicity}}\label{proofofpropmonotonicity}
 
-The $\log\det$ function is concave and self-concordant (see
-\cite{boyd2004convex}), in this case, the analysis of the barrier method in
-in \cite{boyd2004convex} (Section 11.5.5) can be summarized in the following
-lemma:
+%The $\log\det$ function is concave and self-concordant (see
+%\cite{boyd2004convex}), in this case, the analysis of the barrier method in
+%in \cite{boyd2004convex} (Section 11.5.5) can be summarized in the following
+%lemma:
 
-\begin{lemma}\label{lemma:barrier}
-For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate
-approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$.
-\end{lemma}
+%\begin{lemma}\label{lemma:barrier}
+%For any $\varepsilon>0$, the barrier method computes an $\varepsilon$-accurate
+%approximation of $L^*_c$ in time $O(poly(n,d,\log\log\varepsilon^{-1})$.
+%\end{lemma}
+\note{THIBAUT: ARE THE COSTS BELOW DIVIDED BY B? CAN YOU EITHER RENAME THEM OR CARRY THE B AROUND AS APPROPRIATE?}
 
-We show that the optimal value of \eqref{eq:perturbed-primal} is close to the
+We proceed by showing that the optimal value of \eqref{eq:perturbed-primal} is close to the
 optimal value of \eqref{eq:primal} (Lemma~\ref{lemma:proximity}) while being
 well-behaved with respect to changes of the cost
 (Lemma~\ref{lemma:monotonicity}). These lemmas together imply
@@ -315,7 +317,7 @@ Proposition~\ref{prop:monotonicity}.
     of the lemma's inequality.
 \end{proof}
 
-Let us introduce the lagrangian of problem, \eqref{eq:perturbed-primal}:
+Let us introduce the Lagrangian of problem, \eqref{eq:perturbed-primal}:
 
 \begin{displaymath}
     \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi) \defeq L(\lambda) 
@@ -323,7 +325,7 @@ Let us introduce the lagrangian of problem, \eqref{eq:perturbed-primal}:
 \end{displaymath}
 so that:
 \begin{displaymath}
-    L^*_c(\alpha) = \min_{\mu, \nu, \xi\geq 0}\max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi)
+    L^*_{c,\alpha} = \min_{\mu, \nu, \xi\geq 0}\max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu, \nu, \xi)
 \end{displaymath}
 Similarly, we define $\mathcal{L}_{c}\defeq\mathcal{L}_{c, 0}$ the lagrangian of \eqref{eq:primal}.
 
@@ -339,19 +341,19 @@ dual feasibility, the KKT conditions give $\forall i\in\{1, \ldots, n\}$:
 \begin{lemma}\label{lemma:proximity}
 We have:
 \begin{displaymath}
-    L^*_c - \alpha n^2\leq L^*_c(\alpha) \leq L^*_c
+    L^*_c - \alpha n^2\leq L^*_{c,\alpha} \leq L^*_c
 \end{displaymath}
-In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
+In particular, $|L^*_c - L^*_{c,\alpha}| \leq \alpha n^2$.
 \end{lemma}
 
 \begin{proof}
-    $\alpha\mapsto L^*_c(\alpha)$ is a decreasing function as it is the
+    $\alpha\mapsto L^*_{c,\alpha}$ is a decreasing function as it is the
     maximum value of the $L$ function over a set-decreasing domain, which gives
     the rightmost inequality.
 
     Let $\mu^*, \nu^*, \xi^*$ be dual optimal for $(P_{c, \alpha})$, that is:
     \begin{displaymath}
-        L^*_{c}(\alpha) = \max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*)
+        L^*_{c,\alpha} = \max_\lambda \mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*)
     \end{displaymath}
 
     Note that $\mathcal{L}_{c, \alpha}(\lambda, \mu^*, \nu^*, \xi^*)
@@ -360,11 +362,11 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
     problem \eqref{eq:primal}, $\mathcal{L}_{c}(\lambda, \mu^*, \nu^*, \xi^*)
     \geq L(\lambda)$. Hence,
     \begin{displaymath}
-        L^*_{c}(\alpha) \geq L(\lambda) - \alpha\T{\mathbf{1}}\mu^*
+        L^*_{c,\alpha} \geq L(\lambda) - \alpha\T{\mathbf{1}}\mu^*
     \end{displaymath}
     for any $\lambda$ feasible for \eqref{eq:primal}. In particular, for $\lambda$ primal optimal for $\eqref{eq:primal}$:
     \begin{equation}\label{eq:local-1}
-        L^*_{c}(\alpha) \geq L^*_c - \alpha\T{\mathbf{1}}\mu^*
+        L^*_{c,\alpha} \geq L^*_c - \alpha\T{\mathbf{1}}\mu^*
     \end{equation}
 
     Let us denote by the $M$ the support of $\mu^*$, that is $M\defeq
@@ -420,7 +422,7 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
 \begin{lemma}\label{lemma:monotonicity}
     If $c'$ = $(c_i', c_{-i})$, with $c_i'\leq c_i - \delta$, we have:
     \begin{displaymath}
-        L^*_{c'}(\alpha) \geq L^*_c(\alpha) + \frac{\alpha\delta b}{2^n}
+        L^*_{c',\alpha} \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^n}
     \end{displaymath}
 \end{lemma}
 
@@ -432,11 +434,11 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
     \end{displaymath}
     we get similarly to Lemma~\ref{lemma:proximity}:
     \begin{displaymath}
-        L^*_{c'}(\alpha) \geq L(\lambda) + \lambda_i\xi^*\delta
+        L^*_{c',\alpha} \geq L(\lambda) + \lambda_i\xi^*\delta
     \end{displaymath}
     for any $\lambda$ feasible for \eqref{eq:perturbed-primal}. In particular, for $\lambda^*$ primal optimal for \eqref{eq:perturbed-primal}:
     \begin{displaymath}
-        L^*_{c'}(\alpha) \geq L^*_{c}(\alpha) + \alpha\xi^*\delta
+        L^*_{c',\alpha} \geq L^*_{c,\alpha} + \alpha\xi^*\delta
     \end{displaymath}
     since $\lambda_i^*\geq \alpha$.
 
@@ -447,14 +449,14 @@ In particular, $|L^*_c - L^*_c(\alpha)| \leq \alpha n^2$.
     with $\lambda^{'*}$ optimal for $(P_{c', \alpha})$. Since $c_i'\leq 1$, using Lemma~\ref{lemma:derivative-bounds}, we get that $\xi^*\geq \frac{b}{2^n}$, which concludes the proof.
 \end{proof}
 
-\subsection*{End of the proof of Proposition~\ref{prop:monotonicity}}
-
-Let $\tilde{L}^*_c$ be the approximation computed by
+%\subsection*{End of the proof of Proposition~\ref{prop:monotonicity}}
+We are now ready to conclude the  proof of Proposition~\ref{prop:monotonicity}.
+Let $\hat{L}^*_{c,\alpha}$ be the approximation computed by
 Algorithm~\ref{alg:monotone}.
 \begin{enumerate}
     \item using Lemma~\ref{lemma:proximity}:
 \begin{displaymath}
-        |\tilde{L}^*_c - L^*_c| \leq |\tilde{L}^*_c - L^*_c(\alpha)| + |L^*_c(\alpha) - L^*_c|
+        |\hat{L}^*_{c,\alpha} - L^*_c| \leq |\hat{L}^*_{c,\alpha} - L^*_{c,\alpha}| + |L^*_{c,\alpha} - L^*_c|
         \leq \alpha\delta + \alpha n^2 = \varepsilon
 \end{displaymath}
 which proves the $\varepsilon$-accuracy.
@@ -462,14 +464,14 @@ which proves the $\varepsilon$-accuracy.
 \item for the $\delta$-decreasingness, let $c' = (c_i', c_{-i})$ with $c_i'\leq
     c_i-\delta$, then:
 \begin{displaymath}
-    \tilde{L}^*_{c'} \geq L^*_{c'} - \frac{\alpha\delta b}{2^{n+1}} 
-                     \geq L^*_c + \frac{\alpha\delta b}{2^{n+1}}
-    \geq \tilde{L}^*_c
+    \hat{L}^*_{c',\alpha} \geq L^*_{c',\alpha} - \frac{\alpha\delta b}{2^{n+1}} 
+                     \geq L^*_{c,\alpha} + \frac{\alpha\delta b}{2^{n+1}}
+    \geq \hat{L}^*_{c,\alpha}
 \end{displaymath}
-where the first and inequality come from the accuracy of the approximation, and
+where the first and last inequalities follow from the accuracy of the approximation, and
 the inner inequality follows from Lemma~\ref{lemma:monotonicity}.
 
-\item the accuracy of the approximation $\tilde{L}^*_c$ is:
+\item the accuracy of the approximation $\hat{L}^*_{c,\alpha}$ is:
 \begin{displaymath}
     A\defeq\frac{\varepsilon\delta b}{2^{n+1}(\delta + n^2)}
 \end{displaymath}