Multi-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere!

Is this the >> I think so. Yeah, you might need that. Is it on? The switch on the side. Perfect. Awesome. So, our next speaker all the way from Berkeley Way West is Nika Haghtelen Park. >> [laughter] >> Um Yeah, well, I just wanted to first start by wishing Avrim happy birthday for the nth time. And I don't want to rehash for the nth time all these accolades of Avrim and the influence we know he's had on the history of ML and the future of ML. And we heard a lot from everyone about his humility, what a great advisor he's been, and the community of people he's created around him. But I did want to just share a reflection of that on my own life because I feel like all of us when we look at our lives, there are definitely those rare moments that sort of transformation we couldn't have even sort of dream about. And I think one of those moments was when Avrim unknowingly accepted to be my advisor. So, thank you very much because I definitely wouldn't have been here either in Simon's or Berkeley or be a faculty or be able to actually be part of contributing to uh research in computer science had it not been for Avrim. More emotional than I was planning. Let me talk about this um what has come to be for me to be called multi-objective learning. And the reason I wanted to talk about this project is because um [snorts] the seeds of this project actually started >> [clears throat] >> in conversations that we were having with Avrim almost 10 years ago at CMU. So, there was once in 2016 2017, a young Nika that actually did look different than the current Nika. And um she was thinking about um, kind of like what what machine learning look like if there were agents with different interests and what they wanted to learn and different access to data sets. But a world in which they might want to share some of this data or they might want to actually help each other learn because data and interests in data and task can come from many different settings. And of course, it's not surprising I was thinking about these things because well, I was advised by Avrim. I also had a co-advisor Ariel Procaccia and I was surrounded by ideas of incentives, distributed kind of computation, privacy, which were all really related to this question of how would you learn across multiple data sets across multiple agents. But the question that I really wanted to think about was slightly different than incentives, the distributed computation, privacy, which actually works of Avrim, Ishai, collaborations with Ishai, Nina that spoke and also the works of my other advisor Ariel had covered a lot of that. I really wanted to think about how would you actually approach machine learning itself, like the learning design when you have multiple data sets and multiple agents. And I started getting into a wrong way of thinking about this problem, thinking that well, really the right way of knowing how to collaborate across multiple agents is you need to figure out sort of how their tasks and interests are related. That seems to be like a pretty difficult learning problem. Rather than bringing efficiency through collaboration, that seems to be bringing inefficiency through collaboration. I was very close to giving up on this. And kind of in passing one day in a meeting with Avrim, I was telling him about wouldn't have this been cool idea, but like it seems just like not the right way for theory to be addressing this problem. And Avrim, this is all paraphrasing. Unfortunately, I don't have any emails about this. These are all in person. And Avrim was like, "Whoa, wait, whoa, wait, hold on a second. You're going a little bit fast. Are you sure? Do you actually need to know how different agents' interests and learning and abilities and task and difficulty actually relate to each other a priori?" In learning, we tend to just figure out what we learn as we go. And maybe this is all that you need. And then he literally told me, "Have you thought about the following approach?" Well, I think this is a good word of wisdom regardless that you don't need to know everything in life. And that you can learn what you need to learn as you go as long as you can reflect on what still needs to be learned. And I feel like this is an age-old ML wisdom. We've seen it in works of Rob, Ishai, Avrim, many people here. And you're going to see this realizing and how you approach collaboration across multiple um agents and what's come to be known for me as multi-objective learning. So, long title, multi-objective learning, >> [clears throat] >> an algorithmic toolbox for optimal predictions on any task and loss. Let me first start by talking about what do I mean by optimal predictions on any task and loss? And actually, I think Ishai did such a great job kind of telling you guys why you need the multi-objective learning yesterday. So, I won't rehash all of that, but let me just say a little bit about an example of where you might want to learn something that you want to use in different ways. So, for example, imagine that you have a task and a loss could be defined by you have patient health records. Those are your x's. You're trying to predict an event like a cardiac event. And you have a distribution over these uh x's and y's. And um you might think that there are many different age groups that are relevant to this prediction. So, you want to have predictions that are good for younger people, for older people, for people who have pre-existing conditions, or perhaps like if you're you know, so so something related to insurance for policy-relevant populations. So, a task in this sense could be like the conditional distribution of looking at that distribution D, but then zooming in on um some particular population. And then, in some sense, optimal prediction in some sense is that you're trying to learn a predictor that can then be used by many different people, like maybe a physician, maybe the the discharge coordinator, maybe even the insurance, you know, actuary, who definitely have different interests in coming to this prediction task. Maybe the physician just wants to make sure that on every group he's making good decisions or she's making good decisions. The discharge coordinator has a different attitude to risk, perhaps. Um and actually certainly has a different attitude towards how he would handle risk. So, it's still the same event. It's still very much kind of the same types of people, the same types of things you're trying to predict, but they get realized in very different ways. So, the question is how do you do this? And this talk is really about an algorithmic toolbox, very general purpose algorithmic toolbox, about how to make these predictions that then can be used downstream in any situation. >> [clears throat] >> I'll start by giving you a definition of multi-objective learning as a unifying framework, and then I'll talk about the toolkit, and if I have time, um how this applies to the literal example that I gave you. Okay. So, what is multi-objective learning definition-wise? Uh you can imagine that you have K distributions D1 to DK. You can actively sample from whichever you want at any time you want. There are possible loss functions L1 to LR. >> [cough] >> You can imagine this as being a binary loss function, for example, just whether your prediction's correct or not, but nothing is binding you that. I actually think uh thinking about calibration type um objectives, where you're trying to look at the bias of uh prediction condition on what value you predicted is also a really valid loss that we should be thinking about more and more. Um when I use capital L, that's just the expected loss. So now, multi-objective learning is a finer grain version of PAC or agnostic learning in the sense that in PAC learning, you're trying to learn a function F that is good for some distribution for some loss that's told to you. So essentially, you want to learn this function that's universally good abs um its error is epsilon. Now, multi-objective says that it's good for any distribution of interest and any loss of interest. Of course, if this is possible, you're uncovering something that's kind of universally good. Sometimes this is not possible. Like maybe your distributions or losses just disagree with each other fundamentally. And in those cases, we change this definition to competing with the best possible, which is the minimax. Um there are many variations between these. I'm going to use these definitions because every other version of this definition that's come up ends up being solved optimally by this toolkit anyway. So, this is the definition we're going to be using for the rest of the talk. Any questions? Okay. So, let me give you two examples of why this is a more fine-grained version of the types of things we're used to thinking about. So, when we think about um for example, uh classic statistical learning or PAC learning here, um you could sort of think about this as if you have a function that has a 5% error, it could be that it has actually 50% error on 1/10 of the population. And it's problematic if that 1/10 of the population is a meaningful subpopulation across certain socioeconomic axis. So, what our per group guarantees essentially do is to say that, well, let's take all the subgroups of potential interest into account D1, D2, DK and then we ask for something that's more fine-grained than PAC learning. The second example is where you're trying to make per prediction guarantees. These are the calibration style types of guarantees. And again, you could think about learning a predictor and you're trying to measure its bias. So, unbiasedness could be thought about as just saying that my expected prediction is the expected um observation. And this is I mean, this is a caricature, but this is very naive and very coarse because you could just predict on every person without even looking at their features, the average of the population, which is not good at all because it's not personalized in any way. Um calibration error is saying that at least you're trying to make sure that every prediction you make by itself is unbiased in the sense that uh if you haven't seen calibration, what it really is saying is that condition on you making a prediction. So, condition on me saying that you have a 70% chance of developing um cardiac event in the next 24 hours, that population actually 70% of them do develop it. So, in some sense, you're unbiased condition on your predictions. You're trustworthy in that sense. So, again, this is a more fine-grained notion uh of unbiasedness and you can condition that on the PX equal to V or as well with X being in S. And the relevant losses for this example, I think for PAC it was clear that it was binary loss where this example the relevant losses are actually these ones that look at the the gap of the prediction joint with uh the you actually making a prediction value of V or also taking a group into account. Okay. So, I said that this is unifying perspective and sort of to track it back we first started about thinking about these collaborations with Avrim and the way we started thinking was that these DIs there was no there was a single loss but the DIs were sort of different data sets, different agents who wanted to collaborate. Um but really so this is like almost 10 years ago and now before federated learning took off and um also even fair ML taking off to a degree. Um and this is a type of problem that keeps repeating itself. For example, in agnostic fair federated learning this is exactly the same thing where DI now represents some client distributions and you have some fairness goals in mind. And more and more I'm not going to go through everything but group distribution robust optimization again same issue comes up where you're trying to make sure that for any possible DI which is a perturbation of a possible world you think about you want to have good performance. It's like an issue of robustness. Um and in the TCS community beautiful work coming from multi-group agnostic learning, multi-calibration learning, omni predictions not even in this list. It's been really in the past few years these fine-grained guarantees have been really important to the uh development of the theory of machine learning. So, I like to think about multi-objective learning as unifying them from an algorithmic perspective and it does um as I'll show you in a little bit. Okay. So, what are we doing for the rest of the talk? The way I want to think about multi-objective learning is that with a single loss, single objective um we're sort of in the statistical classical statistical learning world. And what we're trying to do is multiple losses, multiple distributions. Um, and the healthy way of knowing what you're doing if it's good is to actually do comparisons here. And the types types of questions we want to answer are we understand statistical learning pretty well, we understand the sample complexity perspective as defined by VC dimension. We actually understand that there isn't a from a worst-case perspective, there is like the algorithm being empirical risk minimization that you can just apply and it's the algorithm that solved any problem. And we're asking the same questions in multiple distribution setting and multiple losses. We're asking, "What is the algorithmic paradigm? What is the ERM paradigm like analog? And what is the sample complexity?" And those are the questions I'm going to answer. Um, how am I doing on time? 16 minutes, okay. Okay, so let me give you the algorithmic perspective on the toolbox. Um, for conciseness for the rest of the talk, I'm just going to assume single loss, but multiple distributions because everything else goes similarly. And the works I'm going to be highlighting, so I will very briefly mention like the the 2017 paper I mentioned, but um, Avrim, Ariel, and Mingda, who was an undergrad and did major part of the proofs. Um, but the papers that I would highlight are more are um, the work that's been developed here at Berkeley um, with my students, Eric Zhao, Brian Lee, and some other collaborators. Okay, so to start with a little bit of insight about the challenges of this problem and why I thought that it was impossible in some sense to do was that I just like in some sense, if you're thinking about learning without a priori knowing the relationship or the difficulty of these different tasks. Um you have to sort of collect a lot of data from everyone's distribution to accommodate the fact that these distributions might be related in any which way to each other. And that's kind of this kind of a standard approach. So, collecting a a priori fixed-size data set, it ignores the degree of different difficulty and relevance between the tasks. And uh if you sort of limit yourself to that kind of thinking, then there is no benefit from collaboration in some sense, which means that at least the sample complexity of existing algorithms for solving the distri- multi-distribution problem for K distributions, they actually take K times the sample complexity of solving a single problem. So, in some sense, you're not getting really anything from any benefit from collaboration. So, what this is really saying is that the right way to be thinking in about this problem is that you need to allow yourself an adaptive protocol for data collection. You can't start with a fixed amount of data from every distribution. If you do that, you're sort of losing out on the benefit of collaboration. So, this is where on what now we call on-demand sampling um comes up, which is that to effectively learn with multi-objective guarantees, the learning algorithm has to actively curate curate and shape its own data set, not just scale the size of data set. As in, you should generate your training data wherever it's needed, whenever you decide that it's needed. And with that, what you could do is potentially think about a situation where you collect some number of samples from your multiple tasks. Then um you see where you're doing well, where you're not doing very well, and that tells you where you should focus your sampling effort in the future. And if you do that, you can shave this K and exponentially improve it to a log K. In fact, it's even better than that. Uh, let me write what it is. Um, if you are non-adaptive, the complexity of the objectives you have, which is K, and the complexity of the learning task, which is either the VC dimension or if you want to be naive, the log of the class, they multiply with each other. If you allow yourself adaptivity, they add. So, it's not even that log, you don't even actually incur the multiplicative log K, it's that you're incurring an adaptive additive um, penalty in some sense. Yes. Yeah. Great question. We have a recent paper on this last year with um, Omar Montasser and uh, Mingda Choo. And uh, we can Let me tell you a little bit about the algorithm design and then come back to that. What I can say is that there's some really interesting open problems left there. Um, and we still have a pretty good understanding of how to do that for realizable setting, but for the setting where it's not realizable, you have to compete with min-max, there's some really interesting problems left over. Okay. So, how do you use on-demand sampling and how do you think about this from first principles? And this is uh, very much thanks to the beautiful work that I think Rob has done and we have all benefited from it throughout the years. Um, I really like to think about multi-objective learning as the zero-sum game equivalent version of it, which is that what you're trying to do is to solve this problem where you're learning something whose worst case loss is no worse than the minimax value plus some epsilon. And the way that you algorithmically can think about these paradigms is to think about them as having two agents, hypothetical agents, a minimizing agent who is interested in minimizing that loss and a maximizing agent who is interested in maximizing that loss. And now the approximate minimax equilibria in some sense is the thing you're trying to beat. I'm not going to go into the details of does it exist or not, finite and infinite. We can all kind of, you know, cover that under the rug for now. But what this does inspire is to think about the usual algorithms that you could think about for solving minimax, which are based on no-regret algorithms. So a typical way to go about solving this is that you assume one of these hypothetical agents is a no-regret learner. The other one could be a no-regret learner or could be a best responser. So what that means is that you have a range of sort of things to be playing with where player one is no-regret, player two is no-regret, both are no-regret, and go from there. Now what's fundamentally different between this situation and games is that in games typically somebody writes a game table for you. You know what is in that game table, so that loss capital L that is in the cells of the game. But in this situation, nobody's writing the game for you. The game exists. You can sort of get a sense of what is in the cell value of the game, but that's a literally unexpected loss of a hypothesis on a distribution. So you have to pay samples to access that. And that's one place sample complexity has to come in, which is that the quality of the estimator you could get away with because the game is not written down for you. Naturally, a second place that's going to come up is that we're talking about ways of solving minimax problems through online algorithms. So, the regret rate, or if you want to think about the convergence, how quickly you actually converge in a minimax equilibrium, that also plays a role, because at every round you have to use an estimator. So, these are two places that sample complexity come in. So, how does online sampling help? Let me give you a recipe for this. If I have time, I can prove something, but I'm not super sure if I will have time. So, one approach is to think about the minimizing player as the best responding player, and the maximizing player as a no regret. What do I mean by that? Well, it's an interactive game. So, at each step, each of them goes one by one. When it's time for the minimizing player to go, what it's dealing with is a solution that the maximizing player has created. That solution is essentially a set of weights over distributions, alpha one to alpha K. So, effectively, the maximizing player is creating a new mixture of distribution. And what the minimizing player is doing is now something that we do in offline learning and statistical learning, literally running empirical risk minimization on some number of samples. What about the maximizing player perspective? Well, what the maximizing player is looking at is a solution, or a series of historical solution that came from the minimizing player. H1 >> [clears throat] >> to HK so far, or HT so far. And what this guy is trying to do is to come up with mixing weights that put more weight on the distributions that haven't been learned well enough to make it harder, because this guy wants to maximize loss. Where is the sampling happening? Both of them have to sample. The empirical risk minimization naturally has to sample because you need to know what that mixture distribution looks like, and the only way to do that is to sample from that mixture distribution. The maximizing player has to have a proxy of how poorly distributions so far are being treated. So, that's where the sampling for the maximizing player is coming in. Why is this on demand? Because there is interaction. When the max player maintains these weights next time around, the min player samples. When the min player samples and learns a new distribution, the max player has to know if the Sorry, a new hypothesis, the max player has to know if it's good or not. >> Why does the min player really have to sample? He has to sample already the amount and we just need to readjust the weights on the sample, no? >> So, if you That's a very good question. So, one question is, maybe I don't need to resample, I can just start with a big enough samples and re-weight. You can do that. If you do that, you're in a non-adaptive setting, you end up paying the K-fold. But, this So, so, in some sense, like you you still need to start because in some sense, maybe there was one distribution that's really hard that you have to keep sampling and bringing up its weight. So, for that distribution, you need K times because you keep repeating it. And uh in some sense, if you allow yourself to not just re-weight an original sample sample, but refocus your sampling effort by small amounts, you don't pay that linear cost. >> sort of my question was more unless you need to increase the amount of sample from a given distribution, you can just re-weight. >> That's true. So, and I will show you some experiments where re-weighting is interesting, but something that comes from here plus re-weighting does even better in practice. So, even if you start from existing data sets. Okay. How am I doing on time now? >> [laughter] >> Maybe I shouldn't ask you and just go over time. >> Uh 5 minutes. >> Okay. Um, I'm going to skip the proof of this. It's not that hard. I have like a toy proof in the setting of realizability. The There is nothing mysterious happening here. It's very much like how, you know, why no-regret algorithms solve minimax problems and just the analysis of sample complexity. Now, if you go very naively about this, the sample complexity can build up. For example, ERM, if you are really learning to convergence, you're taking like VC dimension over epsilon squared number of samples per round. And if you start running no-regret algorithms with root T guarantees, you have another one over epsilon squared that's coming in. So, then you're really looking at sample complexity that's blowing up in epsilon, even though maybe kind of the dependence on K and D is not terrible. Um, there are ways to solve this, and I just want to say that there's different perspectives, and I told you there is you can have no-regret versus no-regret, no-regret versus best response. And some of the questions Moses asked about, you know, how quickly can you converge in some sense, like how many rounds of adaptivity you need, they become relevant. And to me, the way I like to think about these problems because all of these different dynamics have been optimal in certain types of problems, it's really think that this is the game setting where the L is known, and we are in an estimate setting when the L is not known. And typically, there's two tradeoffs we need to figure out which one matters to us more. And one is that in a known game, there's a trajectory that's being taken by this hypothetical, you know, perfect dynamics that I don't have access to. And now, there's a trajectory that I'm actually taking with my estimators. And there's two ways to to control that trajectory. One approach with which is the ERM approach I was telling you about is to say that per step I'm going to keep my trajectory close. ERM is going to convergence have a very good exact kind of best response but my no regret maybe is not that great. And that's very valid strategy sometimes could be wasteful because you're learning to perfection before you take a giant step again and it's unclear if you should be doing that. Um this is good though for Moses' question. This tends to converge faster and rounds of adaptivity are smaller but sample complexity could be a little bit larger. The alternative way is to allow the trajectory to diverge quite a bit like per round just take an unbiased estimator for both of the agents that are involved. That means that the trajectories are definitely diverging but hope that the something about the nature of the trajectories do concentrate. And that essentially is more like a martingale way of thinking about these problems where the trajectory something very funky might be happening to them but you could prove that the true regret and empirical regret converge to each other because of martingale property so because you're using unbiased estimators. And if you do that that's more of a no regret no regret perspective a lot more adaptive because it takes a single sample per round and it sample complexity and round complexity become the same but it's the optimal sample complexity one can hope for. So this is kind of different kind of approaches to thinking about solving this problem. And uh the I guess the the second one the no regret no regret gives the optimal bounds that I showed you and the second in one of the additive bounds. It's there's like a log K in the in the union bound you have to pay. It's Yeah, it's the K log K. So Yeah, it's funny. Um I I'm being a little bit I'm cheating a little bit because I'm putting log H versus VC dimension. This is if you put VC you have to pay the log K. Best case we know, it's open better that's actually necessary. But yeah, this is what I was just talking about. And you can replace that log with little stone dimension if you want. But you can't replace it with VC dimension. Um I usually skip this but since Ishay asked >> [laughter] >> I think this is actually really interesting because um you might ask yourself, well, what if the data set already exists? Can I just re-weight? And that's absolutely what you should be doing at least as a start. And actually this Sagaris all paper is doing that. This is coming from distribution robust group distribution robust optimization. Um but something interesting that we observe is that if you just re-weight, um you're not introducing randomness back. So it's harder like you have some no regret guarantees but not the right no regret guarantees. If you re-weight and resample or resample with the new weights, um you actually end up beating the performance of all those re-weighting models significantly. And I think that's just like another kind of, you know, you want to actually have a little bit of randomness to deal with the bad decisions you might have made earlier. Was that my timer? Okay. Um I started off talking about optimal predictions. So, let me at least have two slides and then I finish it off there. I've already shown you like multi-objective and multi-distribution learning. But, predictions are much more nuanced in the sense that um all the relevant information that you might want to capture about a heart risk disease like heart risk of a patient, I mean, you could capture it in base optimal predictor. But, base optimal predictor is impossible to learn efficiently. So, it goes back to this whole thing of like, "Hey, if you need to know everything a priori, it's a really hard job to do that." So, one way to think about multi-objective learning is that you're figuring out what coarsening of base predictor is the right coarsening that's related to your task. What do I mean? While base predictor is not learnable, we're asking is there a tractable and learnable version of a base predictor that can be adjusted for any loss and any population? And this is what we're calling a pan predictor. If you've seen omni predictors, this is just a general generalization of that. Um what this means is that a predictor is a pan predictor if no matter what type of population and no matter what loss you look at it, you can post-process it so that it's an optimal predictor for it. Now, how would you think about this? A base predictor is a pan predictor because it has literally all information. You can always take a base predictor, no additional access to the data, and just post-process best response to it or do something with it. But, it's a not learnable pan predictor. What are learnable versions of pan predictors? The way I like to think about this, and it came in actually two recent works, one by my students and one also from Cornell, was to really think about this as the sufficient thing you need from a base predictor is not unbiasedness condition every X, but unbiasedness condition on some level sets, and in fact thresholds of level sets. What this is meant is that for well-behaved losses, like if I tell you that I'm predicting the probability of rain today, and you're trying to make a decision as to wear boots or not, and maybe Esha is trying to make a decision as to bring an umbrella or not. You have a different point at which you start wearing your boots and you at which you start wearing your umbrella or bringing your umbrella. You're not going to go zigzag up and down that at 31% I'm going to bring my boots, 32 I won't, 33 I will. So, it's like thresholds that matter on the risk. And that's exactly what's kind of this multi-objective tries to isolate, which is that you care about thresholds on your predictor and on the competitor predictor, and then you care about the bias. And if you only care about those losses, and then on the distributions of people you care about, that's all you need. You just need a multi-objective with respect to these things. You put that into the algorithmic recipe I gave you, and here comes a perfect easy way to learn a pan predictor with barely any blow-up in sample complexity, again epsilon square, log H, log number of groups that you care about. And in some sense, you're learning these predictors that can be used downstream by anyone for any reason. Finishing this by saying that it's interesting where we went from collaboration to multi-objectives. I think fine grain guarantees on ML are going to be relevant for historical and modern and future ML because we want more and more the better we can do things with ML. And this is kind of a very flexible algorithmic paradigm to achieve those multi objective guarantees no matter what they are. Thank you. >> [applause] >> Questions please. >> Yes. >> So two short questions. So first you mainly concentrated related about multiple distributions. You did mention the multiple losses. >> How does it change? >> So so so I I guess if you're taking a max of multiple losses of multiple convex losses it will remain convex. >> Yeah. >> But you're taking an expectation in between so I'm not sure. Okay, you you need to answer not me. >> Yeah, there is so there there are some subtleties but actually taking dealing with losses are easier as long as losses are I don't know what they're called but like >> Nice. >> Nice. >> [laughter] >> As long as they're nice. And calibration type losses are nice. Like these losses that are about you know Y minus P of X and then some joint indicator with whatever whatever function of X happens to be nice to the point that you don't even actually pay log of the size of the loss class. You can sort of show that and there there's a few works. I think Abhijay has like this work that also surfaces this. These losses you can have a basis for them that's actually really small. So you can essentially literally have no blow up in the number of losses that you're handling. So the blow up in K is even worse than the blow up in number of losses. >> Maybe one last yeah, Abhiram. Um Do you have a sense of if the the set of groups or losses you care about perhaps changes over time and new groups kind of come in or new things, whether you know, some of these methods would would scale naturally? >> Yeah, so there's the highs um in my group we haven't worked on this, but um several groups are going to be coming uh soon. Um this idea of online multi-calibration and online um omni-prediction, these are ideas that people have studied. The dynamics actually we've also studied them in one work. Um it's interesting there that the the dynamics that's optimal changes. So, I was talking about no regret no regret no regret best response. It so happens that if you are in an online setting, you might actually want to swap who is doing the best response, but there are certainly ways to adjust for this. And they kind of also relate back to the work you did with Todorov and others on like swap regret for fairness, um kind of bringing all of those together in some sense. >> [laughter] >> Yeah. >> Awesome. Then let's uh take defer other questions for now. Thank Nico. >> THANK YOU. >> [applause] >> YEAH, YOU CAN >> AWESOME. >> YOUR MIC. >> YOU CAN TALK. >> YOU'RE THE MIC PERSON.