Wednesday, July 6, 2016

More than a decade of online convex optimization

This nostalgic post is written after a tutorial in ICML 2016 as a recollection of a few memories with my friend Satyen Kale.



In ICML 2003 Zinkevich published his paper "Online Convex Programming and Generalized Infinitesimal Gradient Ascent" analyzing the performance of the popular gradient descent method in an online decision-making framework.

The framework addressed in his paper was an iterative game, in which a player chooses a point in a convex decision set, an adversary chooses a cost function, and the player suffers the cost which is the value of the cost function evaluated at the point she chose. The performance metric in this setting is taken from game theory: minimize the regret of the player - which is defined to be the difference of the total cost suffered by the player and that of the best fixed decision in hindsight.

A couple of years later, circa 2004-2005, a group of theory students at Princeton decide to hedge their bets in the research world. At that time, finding an academic position in theoretical computer science was extremely challenging, and looking at other options was a reasonable thing to do. These were the days before the financial meltdown, when a Wall-Street job was the dream of Ivy League graduates.

In our case - hedging our bets meant taking a course in finance at the ORFE department and to look at research problems in finance. We fell upon Tom Cover's timeless paper "universal portfolios" (I was very fortunate to talk with the great information theorist a few years later in San Diego and him tell about his influence in machine learning).  As good theorists, our first stab at the problem was to obtain a polynomial time algorithm for universal portfolio selection, which we did. Our paper didn't get accepted to the main theory venues at the time, which turned out for the best in hindsight, pun intended :-)

Cover's paper on universal portfolios was written in the language of information theory and universal sequences, and applied to wealth which is multiplicatively changing. This was very different than the additive, regret-based and optimization-based paper of Zinkevich.

One of my best memories of all times is the moment in which the connection between optimization and Cover's method came to mind. It was more than a "guess" at first:  if online gradient descent is effective in online optimization, and if Newton's method is even better for offline optimization, why can we use Newton's method in the online world?  Better yet - why can't we use it for portfolio selection?

It turns out that indeed it can, thereby the Online Newton Step algorithm came to life, applied to portfolio selection, and presented in COLT 2016 (along with a follow-up paper devoted only to portfolio selection, with Rob Schapire.  Satyen and me had the nerve to climb up to Rob's office and waste his time for hours at a time, and Rob was too nice to kick us out...).

The connection between optimization, online learning, and the game theoretic notion of regret has been very fruitful since, giving rise to a multitude of applications, algorithms and settings. To mention a few areas that spawned off:

  • Bandit convex optimization - in which the cost value is the only information available to the online player (rather than the entire cost function, or its derivatives).
    This setting is useful to model a host of limited-observation problems common in online routing and reinforcement learning.
  • Matrix learning (also called "local learning") - for capturing problems such as recommendation systems and the matrix completion problem, online gambling and online constraint-satisfaction problems such as online max-cut.
  • Projection free methods - motivated by the high computational cost of projections of first order methods, the Frank-Wolfe algorithm came into renewed interest in recent years. The online version is particularly useful for problems whose decision set is hard to project upon, but easy to perform linear optimization over. Examples include the spectahedron for various matrix problems, the flow polytope for various graph problems, the cube for submodular optimization, etc.
     
  • Fast first-order methods - the connection of online learning to optimization introduced some new ideas into optimization for machine learning. One of the first examples is the Pegasus paper. By now there is a flurry of optimization papers in each and every major ML conference, some incorporate ideas from online convex optimization such as adaptive regularization, introduced in the AdaGrad paper. 
There are a multitude of other connections that should be mentioned here, such as the recent literature on adversarial MDPs and online learning, connections to game theory and equilibrium in online games, and many more. For more (partial) information, see our tutorial webpage and this book draft

It was a wild ride!  What's next in store for online learning?  Some exciting new directions in future posts...



59 comments:

  1. Your post is providing good information. I liked it and enjoyed reading it. Keep sharing such important posts. I am very much pleased with the contents you have mentioned. I wanted to thank you for this great article. visit website

    ReplyDelete
  2. incorrect products. Being recommended with the aid of glamorous Perlelux celebrities and leading the recognition race via advertisements.
    http://www.drozhelp.com/perlelux/

    ReplyDelete
  3. D BAL Max The commitment and would love to attempt it out first, consider joining a local gymnasium or rec middle You could get your exercising .
    http://xtrfact.com/d-bal-max-review/

    ReplyDelete
  4. Slimfire Forskolin That an overweight individual has in his or her psyche. It is critical Forskolin that the brain science of weight reduction is .
    http://supplementdigestdog.com/slimfire-forskolin/

    ReplyDelete
  5. Xtrfact Before they can guarantee protection cash Buyer driven medicinal services designs incorporate Health Reimbursement .
    http://xtrfact.com/

    ReplyDelete
  6. Pure CBD Oil pumpkin seeds, and in addition pine nuts that are the seeds of pine trees. They are costly however incredible tasting.
    http://www.drozhealthblog.com/pure-cbd-oil/

    ReplyDelete
  7. Dermagen IQ to be in any way consumed by the skin. In this way it renders no impact However for Dermagen IQ for UK legitimate aggregate.
    http://www.drozhealthblog.com/dermagen-iq/

    ReplyDelete
  8. Nitridex However as time has gone on, greater consciousness is being given to girls's sexual troubles too.
    http://supplementdigestdog.com/nitridex/

    ReplyDelete
  9. Zylix Plus the engagement. Try this for 2 weeks after which see what kind of exchange happens. I would really like.
    http://www.drozhealthblog.com/zylix-plus/

    ReplyDelete
  10. This is exceptionally instructive substance and composed well for a change. It's decent to see that a few individuals still see how to compose a quality post! Movierulz

    ReplyDelete
  11. Just try to say ones substance can be as mind blowing. This clarity with your post is magnificent and that i might believe you're a master for this issue. High caliber alongside your agree license me to grab your present provide for keep altered by utilizing drawing closer blog entry. Much appreciated several alongside you ought to go on the pleasurable take care of business.
    COMPREHENSIVE COMMERCIAL SERVICES

    ReplyDelete
  12. Kids who experienced difficulty with their wellbeing or money related issues could essentially utilize their books and study all the material at home. https://www.adlist24.com

    ReplyDelete
  13. Rapid Tone Weight Loss :- If you are tired of carrying excess body fat and want to look slim and sexy, then nothing can stop you from getting the same. Yes, with the help of Rapid Tone Weight Loss, one can easily achieve a healthy weight loss process that you were wishing for long. It is 100% natural and helps to remove excess body fat as well as improves metabolism rate. Let’s find out more about this product.
    Where to Buy?
    Visit its official site to get your bottle it is available on its official page only…
    https://supplementch3mistry.wordpress.com/2018/06/27/rapid-tone-diet/

    ReplyDelete
  14. What is Coleus Rapid Tone Weight Loss – Rapid Tone Weight Loss?
    Rapid Tone Weight Loss is a very simple, and organic compound that is produced Thermo Burn naturally by plants in South East Asia. Its scientific name is Labdane Diterpene and the plant is actually called an Indian Coleus Rapid Tone Weight Loss plant.


    https://supplementch3mistry.wordpress.com/2018/06/28/thermo-burn-review/

    ReplyDelete
  15. Keto Tone Diet
    When you take Keto Tone Diet your body will begin to produce exceptional enzymes: one is known as cAMP and the opposite is lipase. When each of those chemicals are expanded to your frame on the same time, your body reports a dramatic increase in metabolism and fat blocking energy. What that ultimately means is which you are able to keep fats from storing and the fats you have already got is melted away faster than ever before. https://supplementch3mistry.wordpress.com/2018/07/01/keto-tone-diet/

    ReplyDelete
  16. PureFit Keto Reviews
    What Are The Benefits Of Using PureFit Keto & Its Ingredients?
    There are numerous blessings that can be received via the consumption of this complement. It isn't always simply restricted to a weight loss complement however is known to be an powerful fitness complement. It improves your overall health along side the weight loss.
    Improves mind function: This supplement is able to reaching the mind nerves and thus, it improves your intellectual health and allows you to focus greater on your habitual lifestyles.
    Burns universal fat: This supplement burns the cussed fat from the adipose tissue. These fat are not without problems burned by means of the frame in a regular time. Therefore, it burns those fat and also prevents the deposition of latest fats. https://supplementch3mistry.wordpress.com/2018/07/04/purefit-keto/

    ReplyDelete
  17. Diet Plan Forskolin
    What is Diet Plan Forskolin and how does it paintings?
    It is significantly crucial to speak about Diet Plan Forskolin due to the fact there are so many rip-off forester people get be tracked. For all those human beings who've tried exceptional forms of can product inside the beyond, I’ll come here to discuss about this brilliant weight reduction method that is hundred percent beneficial. It is a dietary supplements containing all of the natural substances and these substances are extremely good for making your frame well-toned and well-fashioned. https://dietplanforskolin.com/

    ReplyDelete
  18. Exaggerating is too easy to overheat. But usually do not provide up rapid tone fat loss, in the event that you will once have a fat sausage or simple again. Re-establish the stability with more motion and continue the dietary plan!

    ReplyDelete
  19. Kara Keto Reviews
    Choice Solutions Kara Keto prosperity will have the capacity to expect control over our enlargement Her weight moreover extraordinarily strong with a huge bit of our excess fat reducing is through our rec focus. This particular method incredible stunning achievement with upgrading our quality, joined with opposition Level just by improving the level of our processing framework and remain strong and sound. Regardless A substantial segment of the a bit of exchange courses of action I by and large examine here, clearly, if people hold quick to these individuals At that point

    ReplyDelete

  20. Through this technique, the energy super chewer barkbox coupon codeby the body will be very much cleaner and efficient thus.

    ReplyDelete

  21. You can trust this pounds loss complex to keto plus supplementprovide you with the best results, considering that the supplement is certainly had by you since recommended with an effective keto diet

    ReplyDelete

  22. well the product protectsbest anti aging cream the skin from UVB damage.

    ReplyDelete
  23. Kara Keto Burn
    Who can use Kara Keto BurnCambogia?
    Individuals experiencing largeness and fat can utilize this arrangement. While then again, ensure that you should be over 18 years. On the off chance that you are a child, this supplement isn't proposed for you. This thing is in like manner not for women who are pregnant and foreseeing. http://xtrfact.com/kara-keto/

    ReplyDelete
  24. benefit {people|persons|many people|brain enhancementmost people} {in different|in various} ways

    ReplyDelete
  25. It worked. Over another eight a few months keto factor x australia, I lost about 1 / 3 of my own body weight. I've maintained

    ReplyDelete
  26. But as times transformation, so do the diet plans keto factor x by granite nutrition themselves also, in addition to what they guarantee to

    ReplyDelete
  27. Keto Blaze The back teeth actually aid in the chewing and breaking down of food and their surfaces. Premolars are smaller than molars and help and the chewing process by crushing food. There are also two premolars in each quadrant of the mouth and they are situated in-between the molars and incisors. How Saliva Starts the Digestive Process When you eat food, it’s first mixed and saliva that is secreted by sets of glands. The three main salivary glands are the parotid, submandibular and sublingual glands.


    http://www.reliablenutritions.com/keto-blaze

    ReplyDelete
  28. The woman who follows the crowd will usually go no further than the crowd. The woman who walks alone is likely to find herself in places no one has been before. Click here

    ReplyDelete
  29. When one door closes, another opens; but we often look so long and so regretfully upon the closed door that we do not see the one that has opened for us. Click here

    ReplyDelete
  30. The one thing that you have that nobody else has is you. Your voice, your mind, your story, your vision. So write and draw and build and play and dance and live as only you can. Click here

    ReplyDelete
  31. Qui nous permet in addition to discussion in fast resultats remarquables finaux Castillo.
    Ji dois avoir besoin de CONSEILS going to Professionnel de la Sante?
    Ni Jie suis quand-Pas-de soutien du medecin besoin watchful depuis What's incroyablement Foundation divider arrangement nearness

    http://x4fact.com/

    ReplyDelete
  32. Pretty! This was a really wonderful post. Thank you for providing these details. Click here to read more

    ReplyDelete
  33. Kara Keto Burn

    Benefits Of Kara Keto Burn Shark Container Weight Reduction Pills:
    It is here to help you out when it comes to enhancing the metabolic process to decrease fat in a quicker way.

    https://supplementforhelp.com/kara-keto-burn/

    ReplyDelete

  34. Keto ToneWhat Are The Benefits Of Keto Tone Shark Tank?
    Keto Tone has plenty of benefits. Some of the benefits of this complement are as follows:-

    1) Enhance metabolism:- This complement allows to improve metabolic amount program to reach the human body in the procedure of ketosis.

    https://supplementforhelp.com/keto-tone-shark-tank/

    ReplyDelete
  35. If you want a good fat burning supplement then Premier Diet Keto is the one for you. Using ingredients like Garcinia Cambogia and Forskolin its both effective and free from side effects. For review click here

    ReplyDelete
  36. Keto ToneRemove the acne.
    Boost metabolic amount.
    No side effects.
    Alternative to Keto Tone:
    Pure Forskolin is also weight loss tablet. This weight loss tablet gives you enough power to use for the exercises and when you will be effective in your exercises. But this weight loss tablet is much expensive and out of budget, most of individuals can’t afford Keto Tone weight loss tablet. Pure Forskolin is similar and execute slower than Keto Tone. Keto Tone show outcome faster whiten 2 a few weeks.

    https://supplementforhelp.com/keto-tone-shark-tank/

    ReplyDelete
  37. Kara Keto BurnHelps boost the classifieds of sleep
    When you are able to rest better your body system gets enough a chance to rejuvenate and re-energise so that you are ready to begin a new day in better emotions. With enough rest you also have the ability to keep up with a normal schedule. Moreover, you are also able to prevent poor nutritional habits such as binge consuming and midnight snacking. The insufficient rest leads to fatigue, which is an enemy to weight-loss.

    ReplyDelete
  38. Much obliged for setting aside an ideal opportunity to talk about that, I feel firmly about this thus truly like becoming acquainted with additional on this sort of field. Do you mind overhauling your blog entry with extra understanding? It ought to be truly helpful for every one of us. online gaming merchant account

    ReplyDelete
  39. PureFit KetoMany individuals try to shed those unwanted weight to add some muscle which does not show any excellent outcomes. People get disappointed and decrease their self-esteem when they get negative leads to spite of following all the possible diet plans continuously. Weight decrease is the biggest challenge it’s not easy.

    ReplyDelete
  40. If you've ever experienced that annoying ringing sound for no reason at all, you're probably experiencing Tinnitus. Tokanki Tinnitus Protocol is just the thing you need for this. For review click here

    ReplyDelete
  41. Rapid Tone Ginseng

    This amazing element comes with various medical properties that play an important aspect in your overall health and fitness. Plus, it regulates the growth and growth of glucose in your whole personal whole body.
    https://supplementforhelp.com/rapid-tone/

    ReplyDelete
  42. If you want a good fat burning supplement then Premier Diet Keto is the one for you. Using ingredients like Garcinia Cambogia and Forskolin its both effective and free from side effects. For review click here

    ReplyDelete
  43. V Tight Gel
    Talking about Vaginoplasty, there are many reactions related once you get over with it.
    The strategy is exceptionally costly and does not promise you the lasting outcomes.

    https://www.quora.com/Does-V-Tight-Gel-work

    ReplyDelete
  44. If you want a good fat burning supplement then Rapid Tone Diet is the one for you. Using ingredients like Garcinia Cambogia and Forskolin its both effective and free from side effects. For review click here Rapid Tone Diet

    ReplyDelete
  45. Keto Rapid Tone
    From where to purchase?
    Keto rapid tone is offered only on the web. For those individuals who are enthused about procuring this weight diminishing course of action, an affiliation is given underneath. Not simply this, this thing correspondingly gives "Risk FREE TRIAL" inquisitively clients. This licenses them to review the effectiveness of the thing before buying it.


    https://ketorapidtone.com/

    ReplyDelete
  46. keto trim ingredients
    Together this powerful mechanism can help you slim down for summer so you can be ready to show off a sexier, is keto trim safeslimmed body. A large number of men and women around the united states have successfully lost fat with Keto Trim and in the event that you order today, you can be the next success story.
    http://www.cureidea.com/keto-trim-diet-reviews/

    ReplyDelete
  47. When it comes to weight loss. Only a few suppliments can get the job done without any side effects. The best one being Rapid Tone Diet. Watch a review here: Rapid Tone Diet.

    ReplyDelete
  48. When it comes to weight loss. Only a few suppliments can get the job done without any side effects. The best one being Rapid Tone Diet. Watch a review here: Rapid Tone Diet.

    ReplyDelete
  49. Dr OZ Diet Blog Baking soft drinks "prompts" the stomach to generate more gastric acidity, which allows it to digest meals quicker and easier. But, in addition to this, it also seems to tell the mesothelial tissues that range the spleen to "take it easy," because there is no threat.

    Basically, in O'Connor words, mesothelial tissues understand that "[i]t's most likely a hamburger not a infection." So they, in turn, do not activate the spleen's "army" of macrophages, or white-colored blood vessels tissues tasked with clearing up possibly destructive mobile detritus.


    http://drozdietblog.com/

    ReplyDelete
  50. Ever got headache from that annoying ringing sound going off in your head? That condition is known as Tinnitus. To get a solution of how to cure it, Tonaki Tinnitus is here for you. Guaranteed recovery! For reviews click here Tonaki Tinnitus.

    ReplyDelete
  51. Male Extra Male Enhancement Pills You can take 2 pills consistently, one in morning consequent to having the breakfast, and other amid the night in the wake of eating and you are prepared. If you take after the beforehand specified routine really by then nothing can comes in the best way to deal with accomplish your body goals i.e. to shred or mass.

    It is recommended that near 3 pills to be exhausted in multi day just to influence sure of fitting recovering and working of muscles, taking in excess of 2 pills to can in like manner cause horrendous effects on your muscles and tissues which may get hard to recover once in a while. It respects be under to housetop as opposed to breaking it! So be protected and don't go over the most remote point and in case you do then it is at your own specific danger. https://www.smore.com/yaenw-male-extra-male-enhancement-pills

    ReplyDelete
  52. You're Not Eating Mindfully

    Turmeric Forskolin A method called careful eating might be one of the world's most intense weight reduction apparatuses

    It includes backing off, eating without diversion, relishing and getting a charge out of each chomp, while tuning in to the regular flags that tell your cerebrum when your body has had enough

    Turmeric Forskolin Diet Various investigations have demonstrated that careful eating can cause critical weight reduction and diminish the recurrence of voraciously consuming food.

    Official Site - https://dietplanforskolin.com/turmeric-forskolin-reviews/

    For More Info Visit Our Blog - https://www.smore.com/63ewk-turmeric-forskolin-diet-canada

    ReplyDelete
  53. I like to read your posts very much.Thank you for sharing what you know.interesting challenge for a weblog.Thanks for informative post.
    shipping bar app, Shopify free shipping bar app, best autoketing

    ReplyDelete