Close this search box.

João Mota Uses Distributed Algorithms to Solve Optimization Problems

João Mota Uses Distributed Algorithms to Solve Optimization Problems

The study of distributed algorithms to solve optimization problems took João Mota on a journey that he finished in October 2013, when he successfully defended his Ph.D. dissertation on “Communication-Efficient Algorithms For Distributed Optimization.”

For five years, João Mota was a dual degree doctoral student in Electrical and Computer Engineering, at Instituto Superior Técnico of the Universidade de Lisboa (IST/UL) and Carnegie Mellon University (CMU), in the scope of the CMU Portugal Program, funded by the Fundação para a Ciência e a Tecnologia. João Mota was advised by João Xavier and Pedro Aguiar, from IST/UL, and Markus Püschel, from CMU.

In his dissertation, João Mota developed “a classification scheme for distributed optimization problems,” and “a set of algorithms for distributed optimization.” In looking back, João Mota feels that these positive results reflect the important role his advisors played, not only on guiding his research, but also on teaching him “technical knowledge, how to think and to do research, and how to expose findings to an audience.”

During his studies, João Mota followed a mantra that he felt could be good for prospective students: “Do the type of research that you like and do what inspires you.”

CMU Portugal: Can you give us an overview of the main findings of your dissertation?

João Mota (JM): My dissertation is about solving optimization problems in scenarios where the problem data, rather than being known at one location, is distributed over several nodes of a network. That is, it is about distributed optimization. For example, suppose you have a database that is spread over several computers; this might happen because the database is too large to fit into the memory of a single computer, or because the data was generated in different locations, for instance, in different companies or hospitals. If you want to do some complex operation on that data, like extracting high-level information from it without transmitting all the databases to a single location or computer, then you have to use distributed algorithms. In this dissertation, we studied distributed algorithms that solve optimization problems. There are many problems that can be formulated as optimization problems, many of which arise naturally in distributed scenarios.

CMU Portugal: What is the impact of these findings?

JM: This dissertation has two main contributions. The first is a classification scheme for distributed optimization problems. This scheme not only allows a systematic approach to solve generic distributed optimization problems, but also allows the organization of most of the prior work in the field. In other words, it gives a big picture, which was missing before. The second and most important contribution is a set of algorithms for distributed optimization. These algorithms solve very general classes of problems, but exhibit an excellent performance; they solve problems using less communication between the nodes than prior distributed algorithms. Solving a problem with less communication is important, because communication between nodes (that is, computers or sensors) is usually the slowest operation, or the operation that consumes the most energy. Therefore, the algorithms proposed in this dissertation can make, for example, a sensor network operate longer, because the nodes do not consume as much energy as with other algorithms. Surprisingly, we have found that our algorithms, which solve very general classes of problems, often perform better than the best algorithms designed for very specific problems.

CMU Portugal: How do you position your research?

JM: My research is mostly theoretical, but has some practical implications. Actually, this is the case of all research on algorithms, since these can be theoretically challenging, but also have an immediate practical impact on a given field. I would say that my research lies at the intersection of Electrical Engineering, Computer Science, and Applied Mathematics.


“The algorithms proposed in this dissertation can make, for example, a sensor network operate longer, because the nodes do not consume as much energy as with other algorithms.” – João Mota


CMU Portugal: A dual degree Ph.D. involves a lot of work and study. In looking back to these five years, which were the most difficult periods and the key learning experiences?

JM: Yes, that is true. But I think that no Ph.D. is a simple job. In my case, with a dual degree, I had to move twice between two continents, each time for a period of two years. This is not easy, since a Ph.D. student always has deadlines and each move involves a considerable amount of time-consuming bureaucracy. Fortunately, the people involved in the program were very supportive and helped a lot with this. Also, the first and second years of the Ph.D. were quite difficult, because that is the time to take courses and pass the qualifiers, while starting research. The problem is that starting research involves finding an important problem that has not been solved before, and this requires knowing the field of research very well. I think most of my key learning experiences involved my advisors. Although I did not really notice it on a daily basis, looking back, I learned a lot from them: not only technical knowledge, but also how to think and to do research, and how to expose our findings to an audience.

CMU Portugal: How was it to work with three advisors, from different countries?

JM: I had three advisors, two in Portugal and one in the U.S., and all of them worked in different areas. In spite of this, our interaction turned out to work very well. I ended up working more in the area of one of the advisors, but the other two always contributed with complementary knowledge and interaction. Almost all of our meetings were with everyone. Of course, it is always hard to find a common meeting time between four people. Also, videoconference meetings are hard, because you cannot really write equations during the meeting. However, this forced me to be more organized and, before every meeting, I prepared a small document with everything that I wanted to discuss. This actually helped my research a lot, because it forced me to focus on the essential ideas and to organize them better.

CMU Portugal: At the beginning of your degree you said that your main goals were “to develop my skills as a researcher, but also to contribute to solving difficult problems arising in ECE.” Did you achieve your goals?

JM: I think they were partially achieved. During the Ph.D., I developed some skills, but I also realized that there are many more to develop, and many things to learn. I solved some interesting problems, but I also found many more to be solved. Overall, I am happy with the outcome of the Ph.D. and with the research that I have done.

CMU Portugal: You already have a postdoctoral fellowship at University College London. What are your expectations for this position?

JM: I am very excited with this new step in my career and in my life. Initially, I will be working on problems similar to the ones I addressed in my dissertation, but from a slightly different perspective. After a while, I expect to change my research area and bring my knowledge in distributed optimization to other fields. I am also excited to be in London.

CMU Portugal: What would you highlight from your experience to inspire a prospective student?

JM: I don’t know if this is very inspirational, but what I would say to a prospective student is that although a Ph.D. is hard work, you generally do what you like and you have some independence (although, of course, this depends on your advisors). Also, you get to interact with many people, both in your university and at conferences. And a piece of advice: do the type of research that you like and do what inspires you; most advisors are flexible on that, and you can negotiate with them what you want to do.

December, 2013