Instructions

Instructions

User Manual:

Open the PDF directly: View PDF .
Page Count: 3

Download
Open PDF In Browser	View PDF

Department of Computer Science
Institute of Theoretical Computer Science
Bernd Gärtner, David Steurer

Optimization for Data Science









Special Assignment 1

FS19

The solution is due on Sunday, April 28, 2019 by 11:59 pm. Please send your solution as PDF
to hung.hoang@inf.ethz.ch. After receiving your le, we will send you a con rmation
on the following work day, and at the latest on Monday, April 29th. Make sure you
receive this con rmation, otherwise complain timely.
Please solve the exercises carefully and then write a nice and complete exposition of
your solution using a computer, where we strongly recommend to use LATEX. A tutorial
can be found at http://www.cadmo.ethz.ch/education/thesis/latex. Handwritten
solutions will not be graded!
For geometric drawings that can easily be integrated into LATEX documents, we recommend the drawing editor IPE, retrievable at http://ipe7.sourceforge.net/ in source
code and as an executable for Windows.
Keep in mind the following premises:
– When writing in English, write short and simple sentences.
– When writing a proof, write precise statements.

The conclusion is, of course, that your solution should consist of sentences that are short,
simple, and precise!








This is a theory course, which means: if an exercise does not explicitly say \you do not
need to prove your answer" or \justify intuitively", then a formal proof is always required.
You can of course refer in your solutions to the lecture notes and to the exercises, if a
result you need has already been proved there.
We would like to stress that the ETH Disciplinary Code applies to this special assignment
as it constitutes part of your nal grade. The only exception we make to the Code is
that we encourage you to verbally discuss the tasks with your colleagues. It is strictly
prohibited to share any (hand)written or electronic (partial) solutions with any of your
colleagues. We are obligated to inform the Rector of any violations of the Code.
There will be two special assignments. Both of them will be graded and the average
grade will contribute 20% to your nal grade. That is, if S1 and S2 are the (unrounded)
grades from your respective special assignments and E is the (unrounded) grade from
your exam, then your nal grade will be 0.1 
 S1 + 0.1 
 S2 + 0.8 
 E, rounded to the nearest
quarter (rounding is only applied in this last step). If you do not hand in one of the
special assignments, it will be counted with a grade of 1.0.
As with all exercises, the material of the special assignments is relevant for the exam.

1

Approximate testing of intersections of balls
We are interested in testing whether a set of balls in Rd have a common intersection point.
The idea is to use the machinery developed in class to nd an algorithm that approximately
answers the above question. Let B1 , B2 , . . . , Bn  Rd be a collection of n d-dimensional balls,
where each Bi is represented by a center ci and a radius ri such that Bi = {x : kx − ci k  ri },
where k
k denotes the Euclidean norm. Intuitively, our problem is to decide if there exists a
point that is \very close" to each Bi , or if every point in the Rd is suciently far away from at
least one of the balls. In the former case, we may not be able to di erentiate if the point is a
common intersection point, or just very close to all the given balls. In the latter case however,
we can guarantee that there is no common intersection point.
We proceed now to formalize this problem. Given two compact subsets X, Y  Rd , their
distance is denoted by d(X, Y) = min{kx − yk : x 2 X, y 2 Y}. If X = {x} consists of a single
point, we simplify the notation and assume that d(x, Y) = d({x}, Y).
For i 2 [n], let hi (x) = d(x, Bi ), and let h : Rd → R be the function such that
h(x) = max hi (x).
i2[n]

The ε-intersection problem is de ned as follows: Given ε > 0 and a collection of d-dimensional
balls B1 , B2 , . . . , Bn  Rd represented by the centers and radii, compute either a point x 2 Rd
such that h(x) < ε, or decide that \ni=1 Bi = ;. That is, show that for every x 2 Rd , it holds
that h(x) > 0.
Note that in some cases one may be able to compute both a point x such that h(x) < ε, and also
have a certi cate of no intersection. In this case both are valid solutions to the ε-intersection
problem.
In this assignment you are asked to design algorithms to solve the ε-intersection problem using
the techniques discussed in class.
Assignment 1.

Given i 2 [n] and x 2 Rd , let
gi (x) =


0
x−ci
kx−ci k

if x 2 Bi
otherwise.

Show that gi (x) is a subgradient of hi (x), i.e., gi (x) 2 ∂hi (x). Is hi di erentiable?
Assignment 2. For x 2 Rd , show that there is j 2 [n] such that gj (x) is a subgradient of h(x),
i.e., gj (x) 2 ∂h(x). Describe how to compute such subgradient and provide the running

time of this procedure.

Show that each hi is convex and 1-Lipschitz. Then use this to show that h
is convex and 1-Lipschitz.
Assignment 3.

2

Assignment 4. Assume that you are given x0 2 Rd such that kx0 − x k  R for some constant
R 2 R, where x is a global minimum of h.1 Show that there exists γ 2 R such that after
T iterations of subgradient descent on h(x) we get:

min

t2{0,...,T −1}

(h(xt ) − h(x )) 

Given ε > 0, show that
problem for the set of Bi 's.

O(n/ε2 )

Assignment 5.

R
.
T

p

time suces to solve the ε-intersection

While the above algorithm is independent of the dimension, the dependency on ε is really bad
for practical applications. In the next section we look at improving this dependency, at the
expense of having a slightly worse dependency on n.
For i 2 [n], let fi (x) = 21 d(x, Bi )2 , and let f : Rd → R be the function such that
f(x) =

n
X

fi (x).

i=1

You may assume that fi is convex and di erentiable for each i 2 [n]. Because the sum of
convex and di erentiable functions is also convex and di erentiable, one can also prove that f
is convex and di erentiable. For this assignment you may assume these facts without a proof.
We are now interested in computing the gradient of f to be able to apply gradient descent.
Assignment 6.

Using elementary calculus (e.g. partial derivatives) show that
fi (x) =

r


0

ri
kx−ci k

1−

Show how to compute the gradient
gradient?



f(x).

(x − ci )

if x 2 Bi
otherwise.

How much time is needed to compute this

r

The following is a helpful result that will allow us to prove the smoothness of the function f.
Assignment 7.

For u, v 2 Rd such that kuk = kvk and for real numbers α, β  1,
u − vk  kαu − βvk .

k

Assignment 8.

Using Assignment 7, show that each for each fi , it holds that
fi (x) − rfi (y)k  2 kx − yk .

kr

That is, fi is smooth with parameter 2 (Lemma 2.4). Using this fact and Lemma 2.5 we
also get that f is smooth with parameter 2n. Is f always strongly convex?
Given ε > 0, show that O( n3/2
ε ) time suces to solve the ε-intersection
problem for the set of Bi 's. Use accelerated gradient descent to show this bound.

Assignment 9.
1

For this speci c problem, one can provide explicit bounds on R in terms of the radii and positions of the
centers of the balls. For example, one can compute the bounding box of the set of centers, and choose x0 as
the center of this box.

3



---

Source Exif Data:

File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.5
Linearized                      : No
Page Count                      : 3
Page Mode                       : UseOutlines
Author                          : 
Title                           : 
Subject                         : 
Creator                         : LaTeX with hyperref package
Producer                        : pdfTeX-1.40.17
Create Date                     : 2019:03:26 17:56:15+01:00
Modify Date                     : 2019:03:26 17:56:15+01:00
Trapped                         : False
PTEX Fullbanner                 : This is pdfTeX, Version 3.14159265-2.6-1.40.17 (TeX Live 2016) kpathsea version 6.2.2

EXIF Metadata provided by EXIF.tools