A Fun Optimization Problem
February 9, 2013 Leave a comment
I spent the last several hours trying to come up with an efficient algorithm to the following problem:
Problem: Suppose that we have a sequence of 
![\left[\sum_{r=1}^k a_{i_r}\log(a_{i_r}/b_{i_r})\right] + \left[A-\sum_{r=1}^k a_{i_r}\right]\log\left(\frac{A-\sum_{r=1}^k a_{i_r}}{B-\sum_{r=1}^k b_{i_r}}\right).](http://s0.wp.com/latex.php?latex=%5Cleft%5B%5Csum_%7Br%3D1%7D%5Ek+a_%7Bi_r%7D%5Clog%28a_%7Bi_r%7D%2Fb_%7Bi_r%7D%29%5Cright%5D+%2B+%5Cleft%5BA-%5Csum_%7Br%3D1%7D%5Ek+a_%7Bi_r%7D%5Cright%5D%5Clog%5Cleft%28%5Cfrac%7BA-%5Csum_%7Br%3D1%7D%5Ek+a_%7Bi_r%7D%7D%7BB-%5Csum_%7Br%3D1%7D%5Ek+b_%7Bi_r%7D%7D%5Cright%29.&bg=f0f0f0&fg=555555&s=0 "\left[\sum_{r=1}^k a_{i_r}\log(a_{i_r}/b_{i_r})\right] + \left[A-\sum_{r=1}^k a_{i_r}\right]\log\left(\frac{A-\sum_{r=1}^k a_{i_r}}{B-\sum_{r=1}^k b_{i_r}}\right).")
Commentary: I don’t have a fully satisfactory solution to this yet, although I do think I can find an algorithm that runs in 
While attempting to solve this problem, I’ve managed to utilize a pretty large subset of my bag of tricks for optimization problems, so I think working on it is pretty worthwhile intellectually. It also happens to be important to my research, so if anyone comes up with a good algorithm I’d be interested to know.
matrices with eigenvalues 
and 
respectively, then 
.
principle submatrix of A, then 
, where 
is the ith largest eigenvalue of X.
.
principle submatrix of X, whose eigenvalues are by Theorem 2 bounded by the k largest eigenvalues of X. 
and 
are such that 
for all k (with equality when 
), and 
, then 
.
. But by Corollary 1, we also know that 
for all k. Since by assumption the 
are a decreasing sequence, Theorem 3 then implies that 
and 
, the KL divergence is defined as
. Intuitively, a small KL(p || q) means that there are few points that p assigns high probability to but that q does not. We can also think of KL(p || q) as the number of bits of information needed to update from the distribution q to the distribution p.
and 
. Can we bound 
in terms of the 
? In some sense this is asking to upper bound the KL divergence in terms of some more local KL divergence. It turns out this can be done:
and 
and 
are all probability distributions, then
.
, so that it is certainly true for the integral. Using 
, re-write the condition for a given value of 
function:
in terms of 
, it is enough to first locate the 
th term in the sum and then to describe 
, it also says that the KL divergence between two different mixtures of the same set of distributions is at most the KL divergence between the mixture weights.
of polynomials be quadratically independent, in the sense that 
is a linearly independent set?”
are all polynomials in one variable, and we further restrict to just monomials, (i.e. 
for some 
), the condition is just that there are no distinct unordered pairs 
such that 
. Arun was interested in the largest such a set could be for a given maximum degree 
, so we are left with the following interesting combinatorics problem:
of 
such that no two distinct pairs of elements of 
denote the size of 
, since there are 
pairs to take a sum of, and all pairwise sums lie between 
and 
. We therefore have 
.
; we can do slightly better by taking the Fibonacci numbers instead, but this still only gives us logarithmic growth. So the question is, can we find sets that grow polynomially in D?
. If k is odd, then there are (k-1)/2 possible pairs that could add up to k: (1,k-1), (2,k-2),…,((k-1)/2,(k+1)/2). The probability of each such pair existing is 
. Note that each of these events is independent.
, and there are 
such pairs for a given 
such pairs total (since we were just looking at odd k). Therefore, the probability of an odd value of k invalidating S is at most 
.
, so that the total probability of an even value of k invalidating S is at most 
.
. If we set p to be $\frac{1}{2}D^{-\frac{3}{4}}$ then the probability of S being invalid is then at most 
, so with probability at least 
a set S with elements chosen randomly with probability 
will be valid. On the other hand, such a set has 
elements in expectation, and asymptotically the probability of having at least this many elements is 
. Therefore, with probability at least 
a randomly chosen set will be both valid and have size greater than 
.
, then one can show that the expected number of invalid pairs is at most 
, and hence we can pick randomly with probability 
, remove one element of each of the invalid pairs, and still be left with 
elements in S.
; choosing randomly and then removing any offending pairs gives us S of size 
. What is the actual asymptotic answer? I don’t actually know the answer to this, but I thought I’d share what I have so far because I think the techniques involved are pretty cool.
