search

pokutta / comments-blog

0 stars 0 forks source link

Comments: Cheat Sheet: Smooth Convex Optimization #2

Open pokutta opened 2 years ago

vaseline555 commented 1 year ago

Dear Pokutta,

I enjoyed reading your magnificinet article! One thing I have unclear is to induce (Rate-C) from (Rec-C). Though it is easy to prove via mathematical induction, but I am curious if it is possible to induce (Rate-C) directly from (Rec-C) using other known inequalities.

I've tried telescoping product from 0 to t after constructing h_{t+1}/h_t <= ~~~, and applying inequality (1 - x)^r <= exp(1 - rx), or AM-GM inequality to RHS... but I am stucked in here.

Could you please hint me on this? Thank you in advance.

Best, Adam

pokutta commented 1 year ago

Dear Adam,

great to hear from you and sorry for the rather late reply.

Thanks for the kind words. There is a "standard" way of going from (Rec-C) to (Rate-C), via a certain technical lemma (see e.g., here in our suvey https://arxiv.org/abs/2211.14103 Lemma 2.21). The proof also includes the recursion that you look for.

Let me know if you have any further questions -

Best, Sebastian

vaseline555 commented 1 year ago

Thank you for your kind reply, sir! The survey paper is certainly helpful for enhancing my understanding. Hope you have a nice day. 😄