0

I'm looking for a proof of a lower bound of the Mirror Descent optimization algorithm over l_1 simplex. I am not asking to reproduce a proof here, but rather for a reference.

I did go over the Nemirovsky & Yudin book on the subject (A. Nemirovski and D. Yudin. Problem complexity and method efficiency in optimization. Nauka Publishers, Moscow, 1978), but just could not make it through the details, so I am looking for something more suitable for a grad level CS student.

I will try to be more specific with my questions. Please take a look at the section 3.1.4 which gives an overview of mirror descent methods. I have a number of technical questions:

  1. Why is V'(phi) a linear functional on E* if all we know about V is that it is strongly convex and uniformly differentiable?
  2. Phi \in E*, but what is the trajectory \phi(t)?
  3. What does differential equation 1.1 mean?

I have seen some other formulations of mirror descent which speak of minimizing local approximation when the locality is measured using Bregman divergence term with some strongly convex potential function. How is this current formulation related to the one provided in the book?

Thanks

enter image description here enter image description here

Alex Kreimer
  • 151
  • 4
  • If you're having problem with a particular step of a proof, that's fine; you should share that and ask a more specific question about it. But I don't think it's reasonable to ask for a reproduction of a full proof something you're already finding elsewhere. Sometimes proofs are difficult because a simpler one doesn't exist. – Michael Grant Jan 15 '15 at 15:59
  • Michael, I see your point. The original source provides proofs that are a lot more general than what I am interested in. I am not asking to reproduce a proof here, but rather point me in the right direction, which your answer and down vote were not any helpful with. – Alex Kreimer Jan 15 '15 at 16:16
  • I sympathize, but the fact of the matter is that others agree this is not an appropriate question has posed for this forum. I offered a specific way for you to clarify, and if you do so, I will happily vote to reopen. – Michael Grant Jan 15 '15 at 20:53
  • 1
    Hi Michael, i tried to be more specific, hope these questions are more aligned with the policies of the forum. – Alex Kreimer Jan 17 '15 at 20:07

0 Answers0