It's mid-morning on a Wednesday, and the week is in full swing. Final-year graduate student Hamza Fawzi, 28, emerges from the seventh-floor office he shares with two other students.
The office is decidedly lived-in: a bicycle sits in one corner, hockey gear in another. Hamza's own desk is littered with scraps of scratch paper and a stack of large spiral-bound notebooks. This is where he does most of his thinking.
Hamza, whose advisor is Electrical Engineering and Computer Science Professor Pablo Parrilo, thinks a great deal about what's called convex optimization. Optimization, as the name suggests, is picking the best solution or element possible from a set of available choices. Convex optimization is when the set of choices has certain properties and constraints that give it, in technical terms, a 'convex' geometry. Picture a ball or a cube: any two points within the ball or cube can be joined by a line that is also entirely within that structure.
In real-world terms, Hamza explains, the set of choices might look like this: Let's say your goal is to control a robot in the best way possible. You have a number of inputs, but they have constraints: the robot's motor can only rotate so fast, its arms move within a certain arc, and so on. What he's trying to do is understand the properties of a set of available choices like these, and in doing so, to help engineers easily pick the best way to control the robot.
Certain techniques exist to solve these kinds of problems. One family of techniques is called lifting. Lifting techniques ask: can a given set of choices be understood as the projection of a simpler, higher-dimensional set? (Imagine a solid pyramid, casting a square shadow.) Can solving for that simpler set then allow you to solve the original optimization problem faster?
An analogous scenario is the so-called 'Netflix problem'. The movie-streaming service needs to figure out what each of its 75 million or so users might like to watch next.
“Each user seems unique, but there may be a small number of latent, or hidden, patterns that explain the complexity of all the users’ behavior,” Hamza says. That's the idea behind targeted user profiles. For instance, users who are male, own a dog, and stream things every week might enjoy romances, users who are female, watched a comedy last month, and stream things every night might enjoy comedies, and so on.
The challenge is to identify the underlying profile patterns that are hidden in the data. Part of Hamza’s work is to figure out ways to determine, for a given data set, whether such patterns exist and if so, how to identify them. “The point of my work is to come up with a 'simple' way to tell whether a set is inherently hard” - that means it can't be understood in terms of a projection or small number of profiles - “and develop tools to do this.”
That has applications beyond helping a video streaming site deliver better user choices. It can help businesses plan logistics, roboticists program machines efficiently, or doctors pick nascent tumors out of a brain scan and accurately tell them apart from something more benign, to name just a few examples.
In fact, part of the topic's appeal to Hamza is that it has so many applications in the first place. While he's personally more interested in the mathematical fundamentals of convex optimization, he says, “The reason I like optimization is it's always useful. I like talking with people who are users of optimization. Nearly every week at LIDS, there's a seminar on a different, related application – I like learning about all of these.”
In particular, he says, optimization is getting a lot of attention now in machine learning. “You want very efficient algorithms because they have to work with very large data sets.” Any inefficiency can eat up precious computing power and resources.
Part of Hamza’s work is also to study so-called convex relaxations. “If you have a problem that is non-convex, convex relaxations are systematic ways of converting it to a convex problem.” Take a power grid, for example. Working out the optimal grid operating conditions under constantly changing load constraints is a non-convex problem, and one that power companies have to solve every hour. In practice, you can use convex relaxations to tackle this problem and retain enough accuracy to keep the grid running safely.
“This is a very hot area, because of smart grids and large grids – you need to solve these problems efficiently,” Hamza says. “From a mathematical point of view, we want to know: when does this technique work? What characteristics of a problem indicate that it would be solvable by convex relaxation?”
We head back upstairs to Hamza's office. His office-mates, Jennifer Tang and Omer Tanovic, aren't there right now, but Hamza says he enjoys bouncing ideas around with them. “No two of us have the same advisor, so talking to each other keeps us up to date [across related fields], which is very useful. The interdisciplinary aspect of LIDS is great for this,” he adds.
Hamza's two brothers also play the ideas tennis-game with him from afar. An older brother is a professor of computer science; a younger brother is a PhD student in Switzerland. The formidably-educated trio were raised in Cairo by an Egyptian father and French mother who encouraged their love of mathematics and science.
It was his older brother, in fact, who inspired Hamza to work on a problem and implement a new functionality in existing convex optimization software. “He said, there's no solver that handles this particular function; so together with a colleague [former LIDS PhD student James Saunderson], we worked out the theory and wrote a piece of code in Matlab that performs this function.” Useful bits of code are put up on Hamza's website for all to use, in the hope they'll have some broader impact.
Besides ideas-tennis, Hamza also enjoys the real thing, along with soccer – he has been the athletic co-chair of the Electrical Engineering and Computer Science department, captaining and playing center midfield on its intramural soccer team.
After defending his thesis this summer, he will go on to Cambridge University this fall (2016), joining the newly established Cantab Capital Institute for the Mathematics of Information as a lecturer. There, Hamza hopes to help build an optimization group in the new institute. “I'd like to continue working on these aspects of mathematics of information,” he says. “Optimization is really critical.”