Saturday, October 29, 2016

Unsupervised Learning II: the power of improper convex relaxations

In this continuation post I'd like to bring out a critical component of learning theory that is essentially missing in today's approaches for unsupervised learning: improper learning by convex relaxations.

Consider the task of learning a sparse linear separator. The sparsity, or $\ell_0$, constraint is non-convex and computationally hard. Here comes the Lasso - replace the $\ell_0$ constraint with $\ell_1$ convex relaxation --- et voila --- you've enabled polynomial-time solvable convex optimization.

Another more timely example: latent variable models for recommender systems, a.k.a. the matrix completion problem. Think of a huge matrix, with one dimension corresponding to users and the other corresponding to media items (e.g. movies as in the Netflix problem). Given a set of entries in the matrix, corresponding to ranking of movies that the users already gave feedback on, the problem is to complete the entire matrix and figure out the preferences of people on movies they haven't seen.
This is of course ill posed without further assumptions. The low-rank assumption intuitively states that people's preferences are governed by few factors (say genre, director, etc.).  This corresponds to the user-movie matrix having low algebraic rank.

Completing a low-rank matrix is NP-hard in general. However, stemming from the compressed-sensing literature, the statistical-reconstruction approach is to assume additional statistical and structural properties over the user-movie matrix. For example, if this matrix is "incoherent", and the observations of the entires are obtained via a uniform distribution, then this paper by Emmanuel Candes and Ben Recht shows efficient reconstruction is still possible.

But is there an alternative to incoherent assumptions such as incoherence and i.i.d. uniform observations?

A long line of research has taken the "improper learning by convex relaxation approach" and applied it to matrix completion in works such as Srebro and Shraibman, considering convex relaxations to rank such as the trace norm and the max norm. Finally, in  joint work with Satyen Kale and Shai Shalev-Shwartz, we take this approach to the extreme by not requiring any distribution at all, giving regret bounds in the online convex optimization model (see previous post).

By the exposition above one may think that this technique of improper convex relaxations applies only to problems whose hardness comes from "sparsity".  This is far from the truth, and in the very same paper referenced above, we show how the technique can be applied to combinatorial problems such as predicting cuts in graphs, and outcomes of matches in tournaments.

In fact, improper learning is such a powerful concept, that problems such that the complexity of problems such as learning DNF formulas has remained open for quite a long time, despite the fact that showing proper learnability was long known to be NP-hard.

On the other hand, improper convex relaxation is not an all powerful magic pill. When designing convex relaxations to learning problems, special care is required so not to increase sample complexity. Consider for example the question of predicting tournaments, as given in this COLT open problem formulation by Jake Abernethy. The problem, loosely stated, is to iteratively predict the outcome of a match between two competing teams from a league of N teams. The goal is to compete, or make as few mistakes, as the best ranking of teams in hindsight. Since the number of rankings scales as $N!$, the multiplicative weights update method can be used to guarantee regret that scales as $\sqrt{T \log N!} = O(\sqrt{T N \log N})$. However, the latter, naively implemented, runs in time proportional to $N!$. Is there an efficient algorithm for the problem attaining similar regret bounds?

A naive improper learning relaxation would treat each pair of competing teams as an instance of binary prediction, for which we have efficient algorithms. The resulting regret bound, however, would scale as the number of pairs of teams over $N$ candidate teams, or as $\sqrt{T N^2}$, essentially removing any meaningful prediction property. What has gone wrong?

By removing the restriction of focus from rankings to pairs of teams, we have enlarged the decision set significantly, and increased the number of examples needed to learn. This is a general and important concern for improper convex relaxations: one needs to relax the problem in such a way that sample complexity (usually measured in terms of Rademacher complexity) doesn't explode. For the aforementioned problem of predicting tournaments, a convex relaxation that preserves sample complexity up to logarithmic factors is indeed possible, and described in the same paper.

In the coming posts we'll describe a framework for unsupervised learning that allows us to use the power of improper convex relaxations.

1. Every time you stop outside that glass window showing those glittering, stunning Rolex

watches. This is a heartfelt desire to wrap your wrist with this most well- known name,Svizzeri perfetti Orologi. There is good news

for you. Now, you need not to spend those big bucks for acquiring your dream watch. Your

2. -Such a great blog is very difficult to get. I am very happy to join this Blog in today automaketing help 2018 blog.automaketing help login here facebook chat messenger apps.face.book-shopify

4. Your pieces of advice are very effective. I can solve difficulties by apply them. I'm grateful for your sharing. I hope you will write often and post more articles. emailwithlove bestemailwithlove

5. Nice post. I learn something more challenging on different blogs every day. It will always be stimulating to read content from other writers and practice a little something from their store. I’d prefer to use some with the content on my blog whether you don’t mind. Naturally I’ll give you a link on your web blog. Thanks for sharing.

6. Hello, I Completly agree with this, education can be an extremely appealing option for so many people. Here at https://typicalstudent.org/hot/students-life/haunted-abandoned-places-in-usa-for-students-to-visit-summer-2018 you will get such type of information.

7. There are certainly a lot of details like that to take into consideration. That is a great point to bring up. I offer the thoughts above as general inspiration but clearly there are questions like the one you bring up where the most important thing will be working in honest good faith. I don?t know if best practices have emerged around things like that, but I am sure that your job is clearly identified as a fair game. Both boys and girls feel the impact of just a moment?s pleasure, for the rest of their lives.

8. There are certainly a lot of details like that to take into consideration. That is a great point to bring up. I offer the thoughts above as general inspiration but clearly there are questions like the one you bring up where the most important thing will be working in honest good faith. I don?t know if best practices have emerged around things like that, but I am sure that your job is clearly identified as a fair game. Both boys and girls feel the impact of just a moment?s pleasure, for the rest of their lives.
http://androidhackmodapk.com/

9. I really appreciate for this great information. Thanks to your sharing, I can enrich my knowledge. Thanks a million. I am waiting new posts.
best autoketing, Shopify free shipping bar app, shipping bar shopify

10. I learn some new stuff from it too, thanks for sharing your information.More new Update and I Already Read your Recent Post its Great Thanks.
autoketing app, Product discount app, Product discount master app

11. Nice post. I study one thing tougher on completely different blogs everyday. i'll be actual to check verify inside the works anew particular
pop sales , sale notification website, autoketing.com

12. A few colleges offer extra classes that understudies can visit on the off chance that they wish,COMPUTER SCIENCE MUT where they can meet their educators and individual schoolmates.

13. here is such a great amount in this article I would never have considered all alone.I think this article has a lot of information needed.
app autoketing App Shipping Bar Master Shipping Bar for Shopify

14. This was a wonderful site and I really enjoy it the data you shared. I recently came across your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often. I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well.
abcya3 free games motox3m3 free games gogy Games to play

15. I have read all your articles. Those are what I want to know.Your articles help me so much. They are the best ones. I want to enjoy more and more about your writing.

best game Rapunzel Fashionista Busy Day Game Break The Cup play Battle for the Galaxy

16. Thanks for the auspicious writeup. When I have spare time, I often read your posts.When I need a piece of advice, I will find your posts and read them.
Ride The Bus Simulator online free game game Mommy Elsa Baby Caring Blocky Craft Police Squad game online

17. This game has very amazing 3D graphics and the best color combination. You can easily play it best online free game on your mobiles, tablets, laptops, and desktops.

18. Nice post.Thanks for sharing this post. Machine Learning is steadily moving away from abstractions and engaging more in business problem solving with support from AI and Deep Learning. With Big Data making its way back to mainstream business activities, to know more information visit: Pridesys IT Ltd

19. Raft Wars is the original version of this amazing and prequel for the popular game Raft Wars 2. Simon and his brother found hidden treasures in a desert, but greedy and greedy pirates would like to correct them!

20. Watch movies online through the free movie streaming online sites for the entertainment. There arenumber of sites are available from where you can watch.

21. Thanks for sharing this amazing information https://educationonline2019.wordpress.com/