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.





11 comments:

  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

    answer is Replica watches. Yes come here buySvizzeri Repliche Orologi

    ReplyDelete
  2. Hi your blog is very informative and useful. Machine Learning is steadily moving away from abstractions and engaging more in business problem solving with support from AI and Deep Learning. If you want to know more about this visit our Site: http://pridesys.com/machine-learning-in-bangladesh/

    ReplyDelete
  3. 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

    ReplyDelete
  4. 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.
    download game guardian free apk

    ReplyDelete
  5. 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.

    ReplyDelete
  6. 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.
    https://ifreedownloadings.com/window-10-activation-keylicense-patch/

    ReplyDelete
  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.
    http://androidhackmodapk.com/

    ReplyDelete
  8. 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

    ReplyDelete