diff options
Diffstat (limited to 'appendix.tex')
| -rw-r--r-- | appendix.tex | 62 |
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} |