In short, Computational Learning Theory has been my absolute favorite class at Columbia, and Rocco is the single best instructor I have had. This course is only taught once in a blue moon, and I strongly encourage you to take it if it is offered, regardless of your track. This is not easy material. I'd say it is most similar in nature to Analysis of Algorithms, but it is definitely conceptually harder. The class is math/proof based; you will not write a single line of code, and some proofs take a few classes to walk through. Five problem sets (with five questions each) comprise 70% of your grade, and these are incredibly difficult, but also very rewarding to solve. Averages are typically in the 60s; the class is curved. If you try to look for resources online that might provide additional background, you will just find a research paper that Rocco wrote a few years ago. I could not imagine having another instructor guiding us through the material, let alone in such an intuitive and humorous way. Rocco's teaching style is to provide intuition behind an idea before digging into the math, and I find that this worked very well for me. Not to mention his incredibly intelligent and witty jokes that kept me paying attention even if the proof got a little dry! Plus, I do not know of any other Professor has a poster of The Hobbit on his wall or gives us exam questions about applying Machine Learning to Herman Melville novels (you will soon discover that Rocco loves Herman Melville). His TAs were excellent as well, and would monitor the chat for questions. Rocco deserves his gold nugget and position as CS department chair. I will readily take any other course he offers. I'm heaping all of this praise onto Rocco despite getting a B+ in the class, which should tell you just how highly I think of him; I also know that I am not the only one with this opinion :)
Not only is Rocco the best educator I have come across at Columbia, he is also downright hilarious. I would consider taking a course simply because it is taught by Prof. Servedio. The TA's were also very helpful and solid peeps. Whether you are interested in learning theory or not, the course really makes you go back and forth between intuition and math, translating one into the other - this is really valuable for anyone in a technical field and is also just super interested in my opinion. Rocco makes complex theorems accessible and sets p-sets in such a way that they seem impossible until you have one little creative idea that seems obvious in hindsight and manage to put that down as an expression. I haven't taken many technical courses that have felt like they needed a good amount of creativity like this course did. At the end of the course, I know a fair amount more about learning theory, but I think the course has taught me more about the process of problem solving and deconstructing more complicated ideas (and bounding things!).
Well taught course, like the others claimed. Very humorous, nice and resourceful professor! The only thing is that I don't find the topic too interesting, comparing to courses like computational complexity or information theory.
Great topics course from a great professor. Rocco is great at concrete complexity! Comprehensive survey of different low-level computational models (Boolean formulas, decision trees, branching programs, and constant depth circuits) and representative lower bounds in each model. We used communication complexity, linear algebra, and Fourier analysis of the hypercube as tools throughout. He proved all the results he presented, which was impressive: usually it is hard to present state-of-the art results due to the length of the proofs. Very convincing and thorough.
In short, Rocco is the best professor I had in Columbia so far. He is kind, clear, and intelligent. He made a difficult subject accessible and interesting. That said, if you hate proofs and theory, maybe this class is not for you, but this is not his fault. He already tried his best to focus on the concept rather than the details. I don’t think that the class has no applications. It’s basically an algorithm class, but on algorithms that can learn. If you think algorithms have no real world application, then I am not sure what to say. It’s cool to see that a seemingly simple-minded algorithm can learn complex concepts well, on par with humans (maybe it is how human brains work). The homework takes a long time, so start early so that you have enough time to get help. He won’t tell you the solution directly, but at least can tell you if you are on the right track. A lot of times, people are just completely off the track because they have misconceptions. For me, I think part of the homework difficulty comes from my unfamiliarity with the area, so the 3rd and 4th homeworks turned out more difficult for me, but by the end of the last (5th) homework, I had already seen enough proof strategies that they became a bit like old tricks (I’m not saying they are easy, but just more familiar to me). As a previous post said, the final project turned out to be an educational experience for me. But I guess it depends on what paper you choose. I chose something closely related to what we learned and also not too ambitious, and it turned out to be a good choice. I am glad that I was able to understand at least some parts of an original research paper in the field, which depends your understanding of class material but also adds onto that. About latex, I have mixed feelings. It’s really a pain to type in latex. I feel I spent close to half of my homework time on typing up in latex. But I understand that it makes things easier for TAs, who already have a lot of work. Also, some other classes (e.g ML) may require latex. In summary, I learned a lot without too much stress. (the homeworks can be stressful/frustrating , but overall, the amount learned/stress ratio is much higher than an average CS class at Columbia).
I'm much more lukewarm on Servedio than most folks here. I'm an ML type undergrad, not an algos type, so without taking analysis of algorithms or similar I was maybe underprepared for this class. A bit of probability is pretty key for the PAC model in the middle half of the class. The material was kind of interesting, but it's very much intellectual exercises with very little real world implications (which isn't exactly a hidden fact). The book for most of the semester (Kearns and Vazirani) is ok, at least it's nice and concise. In lectures Servedio was generally clear, but I found that his answers to questions were only so-so. I think part of it is that the class was huge this semester, and it seemed like he wasn't scaling well from 30 students to 100, but maybe that will improve. The problem sets kicked my ass, I rarely got more than a few points above the average, which was typically 20-30 out of 50 points. They require a huge amount of thought, and almost all required some novel proof technique. Some questions were from research papers from only 5 or 10 years ago, many were papers Servedio wrote 10-20 years ago. In retrospect I think those who did well were focusing much more on these problem sets earlier, and spending a lot of time in office hours. The "final exam" wasn't bad though, don't worry about it.
I don't have much to add to what previous reviewers have said, but I'm posting this mostly to say, yes, Rocco Servedio is still (Fall 2014) just as great as he's apparently always been. He's the first professor I've had who is an articulate, charismatic lecturer AND teaches a genuinely interesting, deep and challenging course AND is passionate about his subject. I've had two out of three before (e.g. Jae Lee, charismatic and passionate, or Yannakakis, challenging and passionate) but Professor Servedio is in a class of his own. My only complaint is that this is the only class he teaches. I'd take anything taught by him.
Some thoughts about this course, in no particular order: 1. Rocco is a stellar professor, well deserving of the gold nugget. He is excellent at distilling complicated subject matter in an intuitive manner. He cares about his students. If you ask a question during class, Rocco will make sure you understand it 100% before moving on. He never treats any question like a stupid question, and completely lacks the condescending demeanor of so many profs. Amazingly, Rocco would personally answer many of my questions to the course email account, often within minutes. I'm actually amazed how much of a shit he gives about every single person in the class, given that almost none of us will continue in his field. 2. The course requires a lot of time. Every homework has 5 difficult proof based questions. You need to think things through very deeply. I was close to the top of the class and still spent around 20 hours for each homework. Some individual problems took me 5-10 hours of deliberate thought to break through on. This can be frustrating, but the reward when you finish is worth it. If you don't have much aptitude for theoretical CS, this class will punish you. 3. Clement Cannone is a fantastic TA. 4. As other reviewers have mentioned, this class will give you virtually no practical skills to apply in machine learning. That being said, it CLT is a beautiful field that will make you better understand some of the fundamental issues in ML. If you're the type of person who stays up at night wondering how things REALLY WORK, this is the course for you. 5. The final was very reasonable. If you payed attention in class and understand the concepts at a high level, you'll do well. It doesn't require anywhere near the intellectual sophistication of the homeworks, which is a good thing. 6. The project feels like annoying busy work, and is probably the only thing I'd criticize about the class structure. Reading a research paper is fun and all, but writing 10 pages at the end of the term with all the other finals going on seems like fluff. I think a 2-3 page summary would be better (perhaps for a smaller portion of the grade). 7. Out of the 3 profs who teach the core ML courses (Rocco, Jebara, Hsu), Rocco is BY FAR the best instructor. No contest.
In short: Dr. Servedio is the man. He absolutely deserves the gold stud. I've never had a professor who was as approachable as Rocco. Of all the times I went to speak with him he was never short with me and was always genuinely interested in helping me learn the material. The man has a clear and present passion about what he teaches to the point where he seemed like he didn't want to hold back in his explanations (and thus divulge too much information about a particular problem I was having issues with). At one point he offered to meet with me since I wasn't going to be able to make his office hours that Friday. I can't imagine any of my other professors at Columbia doing the same thing. His teaching is impeccable; no lazy PowerPoint slides here. I've always appreciated the teachers who give explanations to the class as they write; this level of engagement has always made learning feel much more natural and Dr. Servedio is very gifted at doing this. Every class he writes the notes and explains them at the same time and in general the process is paced very well and feels incredibly engaging. All that being said, this class is HARD. Unless you have a passion for theory and machine learning, DO NOT TAKE THIS CLASS. This class is not for those with a superficial interest in either of those areas. I took this class because I had a passing interest in both fields and I had heard good things from classmates who had previously taken his class. I needed a class to fill out the rest of my semester and so I chose to take it; I chose wrong. The above words are not meant to be taken lightly; if you are not grounded in theory or lack the passion for this material, I assure you in the utmost that this class is not for you. This class was meant to be my crash course in CS theory and I had not had much exposure to it outside of discrete math from my undergraduate school. I was also taking Algorithms at the same time. If there was ever a class that needed a pre-requisite, CLT might take the cake; some background in theory and notation would have, I believe, made worlds of difference for me. Rocco does have materials on his website that are meant to help you brush up on the basics needed for this class but the preparation seemed to fall very short of where I needed to be to do the assignments (more below).
A really fun class. As other reviewers have already pointed out, Prof. Servedio gives the clearest, best-organized lectures in the department---he made a large body of complicated theory totally intelligible. The format of the class is nice: no exams, just a few problem sets and a final project. His argument is that the insight necessary to solve most of the problems in this class doesn't come right away even if you have a solid understanding of the material, so a test isn't a fair evaluation. This was certainly my experience---I felt like I had a better grasp of the theory than most of the class (this is judging by the pset averages: as so often seems to happen in this department, the undergrads inevitably outperform the grad students) and I would regularly spend hours staring at the homework assignments without making any progress. Prof. Servedio was also extremely available outside of class, and was extremely helpful in suggesting references and proof techniques for my final project. Some advice: as soon as every problem set comes out, take an hour or so to just think about the problems without any expectation of solving them. Your brain has this marvelous ability to process subconsciously, and you'll find that if you return to the pset in a few days you've already made a great deal of progress without reading this. In short, if you're in either the theory track or the AI track, this is a fun, low-stress (but not low-workload!) class that will do wonders for your development as as a computer scientist.
Prof. Servedio's very good, gifted even, at explaining section a.b.c through to x.y.z of the textbook. His lectures, notes, and problem sets are high quality, better than those found elsewhere on course websites at CMU or UT Austin. So you will learn something or even a lot but is the right thing and is it worth taking for credit? No. DO NOT think that taking his learning theory course is of help in machine learning or data mining courses. I did well on the latter without needing or being able to use ANY of what I learnt here. His style is lemma, proof, lemma, proof and a large fraction of the time is spent on proof minutae at the cost of developing re-usable big picture ideas or connections to topics in machine learning. This fatal flaw in his presentation also results in a poor breadth of topics covered. Once I asked Prof. Jebara a question and he replied "That comes from the PAC model" or such. Imagine your frustration at spending a 20 hr/week semester learning the PAC model in this course but not being able to relate it or apply your knowledge. Do not think that you can get help at that point because the standard response is "take Prof. Servedio's course". It's my belief that he's on a personal crusade against grade inflation and tries to actively deflate your grade: 1) The solutions to the assignments are deliberately written poorly. You'll soon give up on trying to learn where you went wrong and may miss key "tricks" or key conceptual points in solving problems in general. This is quite devious because a lot of important course material is left to the assignments to develop and it's hard to improve your problem solving ability on future assignments. The only reason I can think of why anyone would do this is to prevent copying/selling of materials. The course staff should consider having a 30 minute recitation to go over the solutions if they are paranoid (or you should ask during office hours). 2) There is no feedback on average/median/max/min and marks distribution for any assignment. Make SURE you specifically ask for this to judge your progress and calibrate your effort. It's easy to get blindsided and find out that there are 10 students who have scored near perfect on every assignment or 70% of the class has the same average. 3) He takes the view proofs are either completely right or wrong, the latter gets you a 0 with unpredictable partial credit. Nothing infuriates you like a 0 on something you spent 6 hours crafting because you missed a minor detail. It feels like a penalty on attempting to solve the problem. Expect this to happen a lot and do not underestimate the effect on your motivation. 4) The grading system is ill-conditioned (e.g. 84-86 = A, 79.5-83.99 = A-,..) therefore I feel that your grade precariously hangs on his impression of you. Based on the above I would have serious doubts about taking another one of Prof. Servedio's courses for credit. Definitely do not take his learning theory course if you're not a Phd student in theory. If you're aiming to become one I suggest you take a computational complexity course or algorithms/optimization/math courses as this course will not help you in the future.
Rocco Servedio is absolutely the best professor in the computer science department. He exhibits a level of competence and clarity that is a refreshing change from the general level of instruction at the Columbia CS department. He makes a complicated subject seem crystal clear, and the class never (amazingly), ever is boring -- The 75 minutes are over before you know it. Even the problemsets are a joy to complete -- and they are difficult. If you can, absolutely, positively, definitely, without question take a course with this man.
DEFINITELY the BEST professor I ever had at Columbia. At the same time, he was definitely the HARDEST professor I ever had at Columbia. I took computational complexity last semester and it was the hardest class I had taken. However, because he was such a great professor, I decided to take computational learning theory, and now i can say that that is the hardest class I've ever taken. However, if you're not afraid to face the challenge, you will find that he is an excellent teacher, and you will definitely learn a lot. I definitely don't consider myself a very motivated learner, but I think the hard work was worth it for these classes.
Truly, one of the VERY BEST professors I've had at Columbia (I'm a CS senior)--the whole school, not just the department. Both super intelligent and very capable of transmitting his knowledge to students (I heard he won a lot of accolades for teaching back at Harvard.) His lectures are very well-organized, and he recaps key concepts every time to ensure students follow. Rocco is also a very nice and approachable guy, always encouraging and answering questions in or out of class. The subject material is very, very interesting. It is also very abstract and may be difficult for those who are not well-versed in CS theory and math. All the HW questions are proofs. His problem sets are challenging and take a lot of time. But I think it is worth it. If you care about learning (he certainly cares about teaching) and are willing to work hard and think a lot, you will definitely enjoy this class.
BY FAR the best professor I have had at Columbia. His lectures are very ogranized and he really makes an attempt to explain everything. He is a sincerely nice guy and actually cares whether or not his students understand the material. Some of the stuff covered in this course is really complex, but he is able to break it down to make it more understandable. He likes when students ask questions in class and he really tries to make sure he answers them sufficiently. He tries to get to know the names of all his students. His office hours are really helpful...they were always packed when I took this class. In a nutshell...this guy is awesome.