opt_from_mem.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass optbook
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Section
Optimization from Membership via Sampling
\end_layout

\begin_layout Standard
In this chapter, we assumed the oracle can be computed exactly.
 However, it is still open to determine the best runtime for reductions
 between 
\emph on
noisy
\emph default
 oracles, where the oracle provides answers to within some bounded error.
 In particular, the question about minimizing (approximately) convex functions
 under noisy oracles is an active research area, and the gaps between the
 lower bound and upper bound for many problems are still quite large (
\begin_inset CommandInset citation
LatexCommand cite
key "belloni2015escaping,Feldman2015statistical,bubeck2016kernel"
literal "true"

\end_inset

 based on 
\begin_inset CommandInset citation
LatexCommand cite
key "Kalai2006simulated"
literal "false"

\end_inset

).
 We will see these methods in detail later.
 For now, to put them in the context of oracles, we just discuss the following
 theorem.
\end_layout

\begin_layout Theorem
\begin_inset Argument 1
status open

\begin_layout Plain Layout
OPT via sampling
\end_layout

\end_inset


\begin_inset CommandInset label
LatexCommand label
name "thm:OPTviaSampling"

\end_inset

 Let 
\begin_inset Formula $F(x)=e^{-\alpha c^{T}x}1_{K}(x)$
\end_inset

 for some convex set 
\begin_inset Formula $K$
\end_inset

 in 
\begin_inset Formula $\R^{n}$
\end_inset

 and vector 
\begin_inset Formula $c\in\R^{n}.$
\end_inset

 Suppose 
\begin_inset Formula $\min_{x\in K}c^{T}x$
\end_inset

 is bounded.
 Let x be a random sample from the distribution with density proportional
 to 
\begin_inset Formula $F(x)$
\end_inset

.
 Then, 
\begin_inset Formula 
\[
\E\left(c^{T}x\right)\le\min_{K}c^{T}x+\frac{n}{\alpha}.
\]

\end_inset


\end_layout

\begin_layout Proof
We will show that the worst case is when the convex set 
\begin_inset Formula $K$
\end_inset

 is an infinite cone.
 WLOG assume that the minimum is at 
\begin_inset Formula $x=0.$
\end_inset

 Replace every cross-section of 
\begin_inset Formula $K$
\end_inset

 along 
\begin_inset Formula $c$
\end_inset

 with an 
\begin_inset Formula $(n-1)$
\end_inset

-dimensional ball of the same volume as the cross-section.
 This does not affect the expectation.
 Suppose the expectation is 
\begin_inset Formula $\E(c^{T}x)=a$
\end_inset

.
 Next, replace the subset of 
\begin_inset Formula $K$
\end_inset

 with 
\begin_inset Formula $c^{T}x\le a$
\end_inset

 with a cone whose base is the cross-section at 
\begin_inset Formula $a$
\end_inset

 and apex is at zero.
 This only makes the expectation larger.
 Next, replace the subset of 
\begin_inset Formula $K$
\end_inset

 on the right of 
\begin_inset Formula $a$
\end_inset

 with the infinite conical extension of the cone to the left of 
\begin_inset Formula $a$
\end_inset

.
 Again, this expectation can only be higher.
 
\begin_inset Note Note
status open

\begin_layout Plain Layout
add figure!
\end_layout

\end_inset


\end_layout

\begin_layout Proof
Now for this infinite cone, we compute, using 
\begin_inset Formula $y=c^{T}x$
\end_inset

, 
\begin_inset Formula 
\begin{align*}
\E\left(c^{T}x\right) & =\frac{\int_{0}^{\infty}ye^{-\alpha y}y^{n-1}\,dy}{\int_{0}^{\infty}e^{-\alpha y}y^{n-1}\,dy}\\
 & =\frac{1}{\alpha}\frac{\int_{0}^{\infty}e^{-y}y^{n}\,dy}{\int_{0}^{\infty}e^{-y}y^{n-1}\,dy}\\
 & =\frac{1}{\alpha}\frac{n!}{(n-1)!}=\frac{n}{\alpha}.
\end{align*}

\end_inset


\end_layout

\begin_layout Standard
The theorem says that if we sample according to 
\begin_inset Formula $e^{-\alpha c^{T}x}$
\end_inset

 for 
\begin_inset Formula $\alpha=n/\varepsilon$
\end_inset

, we will get an 
\begin_inset Formula $\varepsilon$
\end_inset

-approximation to the optimum.
 However, sampling from such a density is not trivial.
 Instead, we will have to go through a sequence of overlapping distributions,
 starting with one that is easy to sample and ending with a distribution
 that is focused close to the minimum.
 This method is known as 
\emph on
simulated annearling 
\emph default
and is the subject of Chapter 
\begin_inset CommandInset ref
LatexCommand ref
reference "chap:Annealing"
plural "false"
caps "false"
noprefix "false"

\end_inset

.
 The complexity of sampling is polynomial in the dimension and logarithmic
 in a suitable notion of probabilistic distance between the starting distributio
n and the target distribution.
 The sampling algorithm only uses a membership (EVAL) oracle.
\end_layout

\begin_layout Exercise
Extend Theorem 
\begin_inset CommandInset ref
LatexCommand ref
reference "thm:OPTviaSampling"
plural "false"
caps "false"
noprefix "false"

\end_inset

 by replacing 
\begin_inset Formula $c^{T}x$
\end_inset

 with any convex function 
\begin_inset Formula $f(x)$
\end_inset

.
\end_layout

\begin_layout Problem*
Given an approximately convex function 
\begin_inset Formula $F$
\end_inset

 on unit ball such that 
\begin_inset Formula $\max_{\norm x_{2}\leq1}|f(x)-F(x)|\leq\varepsilon/n$
\end_inset

 for some convex function 
\begin_inset Formula $f$
\end_inset

, how efficiently can we find 
\begin_inset Formula $x$
\end_inset

 in the unit ball such that 
\begin_inset Formula $F(x)\leq\min_{\norm x_{2}\leq1}F(x)+O(\varepsilon)$
\end_inset

? The current fastest algorithm takes 
\begin_inset Formula $O(n^{4}\log^{O(1)}(n/\varepsilon))$
\end_inset

 calls to the noisy EVAL oracle for 
\begin_inset Formula $F$
\end_inset

 
\begin_inset Note Note
status open

\begin_layout Plain Layout
Reference?
\end_layout

\end_inset

.
\end_layout

\end_body
\end_document