## Homework #4

On the webpage, and here. Due on Feb 27th. I will be away that day, so you’ll have to submit it to Euiwoong directly — we’ll figure out a plan soon.

4 problems. Questions, comments, clarifications below.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

### 9 Responses to Homework #4

1. Adam says:

Do you know when the scribe notes for lecture 11 will be posted?

Like

• I gave an extension to those scribe notes, so please don’t wait for them. Please use my hand-written notes, my latexed notes from the Spring 11 randomized class, and other resources I’ve pointed to on the webpage. That should cover most of the things you need for the HW.

Like

2. Adam says:

Okay thank you.
Another question: I’m confused on what we’re doing in S. We’re supposed to give an algorithm, but it seems like the algorithm is already given in the problem.

Do we choose the weights as we go? Or are the weights given to us when we’re given S?

Can we see the labels?

It seems like if we can see the labels and choose the weights, we can pick a point that the majority got right, give it all the weight, then our error would be zero…

Like

• You mean problem #3? The input is S, weights w of the points (I forgot to mention that), and labels for S. You can see the labels. Also, you know algorithm A that is a weak learner, it will output h that gets the labels for 0.5 + eta of the weight correct. You are also given a target error rate epsilon.

For the moment, think of eta = epsilon = 0.01. And think of the input weight as 1 for each point in S. So your h needs to correctly label 99% of the points in S (and also must be of the form “majority of functions from H”). Ideally, you’d like just output the function $\ell$. But $\ell$ may not be of this form (“majority of functions from H”).

So what can you do? If you run algorithm A on S, it will output some h_1 in H that correctly labels 51% of the points in S. If you run it again, it may return the same h_1 again. How can you run A on some sets of points with some weights, so that you get some functions h_1, h_2, …, h_T (all in H) such that h = MAJ(h1, h2, …, hT) correctly classifies 99% of the points in S?

Like

• Another thing you could do is: run A on S. It outputs h1 which gets 51% of the points right. Now run A just on the remaining points in S (on which h1 made a mistake). This gives h2. Run A on the points both h1 and h2 got wrong, to get h3, etc. Finally, h = MAJ(h1, h2…., hT).

But the problem is: the points on which h1 was correct, maybe h2, h3, … all get wrong. And the points h2 was correct on, maybe h1, h3, … all get wrong. So this approach is a terrible idea.

Like

3. Adam says:

I’m confused on 4.c. If we can and do push F units onto the shortest path, aren’t we guaranteed that the smallest capacity on the shortest path is at least F? That’s to say, if the smallest capacity in the path were less than F, isn’t it impossible to push F onto the path?

So isn’t max F/ce guaranteed to be O(1)?

Like

• Not quite, and here’s why. When we find the shortest path, do we look at the capacities? Nope, we just find the shortest path according to whatever the lengths we set on the edges. Then we send flow F on that path. So say the capacities on this graph are all 1 (like in that example we did in class), if we send F units of flow on the shortest path, the congestion is F. Which is possibly very high.

This particular flow is not a capacity-respecting flow, sure — but our MW-based theorems show that if we do this for enough times, and average out all these flows, the resulting average flow is almost-capacity respecting.

Like

• BTW, congestion on an edge = (flow on that edge)/(capacity of the edge).

Like

4. Adam says:

Or put another way, because we already pushed F onto the shortest path in 4.b., Ce > F so F/Ce < O(1)
This argument proves something much stronger than what the problem asks in a single line, so I feel like I am understanding the setup incorrectly.

Like