So now it's recording and thank you. Over to you. Yes, thanks very much, Father, for the invitation and the kind introduction, so I'm very happy to be here today. And since we are in a rather small group, maybe what we can do is that whenever there is something which is unclear, just stop me immediately since we are not so many. So I think it's possible and I don't I don't really mind if I don't finish my slides.
It's not so relevant. So let's just do like something where as soon as something is unclear, you stop me and then we take time and it's like, yeah, it's manageable in a small group. OK, so I'm going to talk to you about the thresholding problem and the constraints. And this is a joint work with the people in my group. So Gemzar, James Churchill with finishing with me on how I look at it is finished actually last this year.
In the beginning of the year, Maheu would say towards the you with me and I finished three years ago and Pamina, who is currently doing a concert in my group. So the topic of the stalky sequential learning in and shape constraints are sequential learning under constraints, and it's based on free papers. So the first one, which is rather older, which I'm going to present just for for setting a little bit of a of the setting of this work and two more recent proposals.
US when I say working people, when in fact it was accepted in the middle of this year and ends in the war zone. So I'm going to present these three works and also put them in context of dijo. So just to start, because I guess many of you are not walking on sequential learning, which was the one that was Airfield's, I will explain what I mean here by sequential learning. And more precisely, those have been the problem. So it's a problem of resource optimisation, innovative and.
So unlike in machine learning or statistics, you don't have the data available beforehand, but you collect them sequentially in time as you go through to. So you have distribution. Newquay with unknown means Muki and you have limited sampling resources. So it can be seen as the size of your as your sample size, so to say. But at the beginning you have no data. And what happens is that you can choose your data sequentially at each time.
So how do you do that? Well, at each time you choose one of the distribution katee and you collect a sample from the distribution. So, for instance, at nine one, you select for first distribution and you get a sample from the distribution a time to you select the second one at a time. Three, you select a fifth one and so on and so forth, so that each time you choose one of the distribution, then you collect a sample from it.
And the main difference with batch learning is that you can base your choice of samples on the best. So you have observed up to time to eat you up to T minus one and you can then base your choice off of distribution. Katie, on that. So you are looking at your sample like that, typically in order to fulfil an objective.
And for instance, in this talk shows, the AMA that we are going to study is the threshold, given the problems with the aim of finding all distribution so that women are above a given threshold. So you have a given threshold and you want to find through distribution with Menagh is above the threshold. So return my family, uh, you have a threshold now and what you want to find is who is the Victor Cuth, which is such that, uh, uh, Q is, um, is, um, is a sign of, um, U.K. minister.
OK, so we invented vocabulary, I just say that because I want a word, I will say it even if I don't. If I don't, if I even if I pay attention. So so distributions are typically called arms. So if I say arms, what I mean, as a distribution, you can. Yes, and then when it comes actually from the slot machines with arms, so that's that's why. OK, so what we are going to do now is to just now formalise a little bit more of a problem and to explain also what the constraints,
shape constraints are going to be. So. Here we are studying the company problem and in this talk, just to make things simpler, but we don't really have to. We are going to assume that the distribution Newquay, so the distribution of each amah is actually and distribution with mean Newquay and Valencian.
So the Gushin assumption is not necessary, but for these talks, in order to keep things as simple as possible, we are going to assume that and we are going to also assume that zoomIn UK of each arm is between minus one and one, I think. Can I ask you a question? Yes, sure. So when you say that the resolution is not necessary. Do you mean that actually you can go with not knowing at all to distribution, or do you still need to make some kind of assumption?
But it can be other than different emotions. Yes. So it's necessary to do to do some to do some better way. And we it so we need to do some assumptions and that parametric. But typically what so the assumption in the paper is that the distributions are bounded ossobuco. No, I think we do subquestion. So what you need in fact is subquestion and you need to know the subquestion constant. So, yeah, if, for instance, if it's a C-section, you need to know I don't abundance.
But the barometric assumptions are not necessarily the reason why here I take unfussy stock is because I don't want to have a discussion on surveillance of the distribution showing these Togusa algorithms that we are going to discuss do not add up to surveillance. And so, yes, that's why in order to see where things are as as clear as possible, I think that you don't need that. As are some of the questions on the U.S. national.
OK, so so we take things like this and we take it a threshold, which is a tool which is equal to to zero just for simplicity. So at each Ronchi, the learner pulls Anana Katie Innocenti and observe a Sembler EKG, which is distributed according to a of MINNUCCI and Violence One. So Distribution Newgate and upon exertion of the budget, the aim of the donor will be to to predict. Q So just in store with your Q is simply a sign of Nuk.
So director of Sign of Newquay to Cuba secured and Kuwait will be a vector of sign of minus one one. And we want to predict as one or the arms which are above the threshold and as blue or the arm which you saw in the pictures, which I'm going to show now, the threshold here is the line. The black line of the exceptions corresponds to the index. So it doesn't really have like a meaning in a sense, just like a one, two, three, four, five A.K. and Zywiec corresponds to the minuti.
So you can see, in fact, the zoomIn UK as a discrete function of. Is it clear the city? Yes, thank you. Thanks. OK, so so I continue to define now the measures that we are going to use as regrets or as a measure of quality of our procedures. So we are going to have two measures of regrets, which we correspond in a sense to to whether we want to study things, some politically neutral, yet particularly in the long run or in the short run.
So the first thing is going to be the possibility of error, and it's going to be simply the possibility that you are not equal to. So we were right this year and this is a quite conservative measure for which will mostly be useful when the budget is quite large. The US Army is a measure of performance that we are going to use is a simple regret's, which is a higher expectation of the maximal gap with respect to the threshold of a misclassified arm.
So, for instance, imagine that we predict here at Cubase you add and that we predict two arms wrongly. So you predict this one in blue and this one in red. And we should have done this one in blue and this one in red. Then what we pay is the distance is the biggest distance to the Shultz was just one case. So it is harder to measure offer this as a hobby to a fellow is more conservative than to simply regrets, because if we just make a mistake on one arm, we are we are penalised.
Whereas here if we make a mistake on an arm which is very close to the threshold, we don't pay too much. So it's a little bit less concise. So in this talk, we are going to study this problem and the shape constraints so, so simple as to shape constraints is to have no constraint at all. Oops, sorry. So is this one. So it's like any functional, any discrete function of of the arm, so you can be any functional. But we are going also to consider more restrictive setting.
So first the monotone setting where in fact Zsa Zsa Zsa menarche is supposed to be increasing, uh, depending on. I'm Jonathan Shitake, increasing, decreasing with literacy, so what it means is a new one is more of a new to for any discrete function. The second shipment means that we are going to consider if damage is concave. So we assume that the concave function of. Which can be returned except for her discreet function.
And the last ship constraint that we will consider again, if they are damaged is unique model. So it means that key first start by increasing and then by decreasing that Mukasa are a fast increase and then decrease depending on. So you have some Elser that you are first increasing and then decreasing. So we are going to consider three years shaped by this Farshid constraint, the first one is not a constraint, but it's still setting. Any questions on anything related to the setting and you know.
OK, so then we can start first with the unconstrained setting just to to fix a little bit. So in the unconstrained setting, Mulcahy's any function of key. And it's a setting which is quite classical now by now in invented, so it was introduced in 2016 by Senegal in 2014. In fact, already, you know you know, people didn't have this name, but it was the same setting. And it's it has been studied quite a lot by now.
So there are many papers which have been proposing algorithms setting books in what people call the confidence setting and in the budget setting. So I'm not going to describe too much of in setting, but we are in a fixed budget setting that to say we have a fixed budget and we try to fulfil our objective. And in all this paper, they are what are called problem dependent results or results, which are only true for 40 years without a budget large enough.
So, yeah, I'm going to describe a little bit of results in the paper by a look at earlier on on here. Look at the good side and myself. But all the yuzu. So it's one it's it's a little bit less refined, but also one which KARMELITA proposals for solutions to algorithmic solutions, which which are very, very good just because. Yeah, it's not really the focus of these talk. But Martha fix really terrific ideas. So let's start with the bounce on the simple Regret's a.m. act setting.
So I want them to merge into the detail for but in fact, what it is possible to to prove is that if you look at the worst case scenario we get, so what's the best possible algorithm would we do on the most difficult problem when it comes to the simple regrette? So when it comes basically to the distance of the to the to the larger distance of the worst misclassified to the threshold, you can prove that us quote which.
So the reason we are mentioning this rate is because it's something that is quite intuitive and achieved by a very, very simple algorithm. So imagine an algorithm that just allocates to each distribution of budget hierarchy. Then if you do a confidence set around your your meana and this assumption of or subcutaneously energy, you have a confidence interval which would have the highest growth capability.
And since you have key arms distributions, if you do a union, which is in fact similar to multiplicative constants, you have a confidence interval which are all uniform and which have PSI square with Killock. So you pay additionally because of the multiplicity of the arms. And so this algorithm is then going to be misclassifying only arms, which are at a distance, which is less than square with Caillaux, Kiribati.
And so in the worst case, it will fail on Anoma, which is Autodefensas Growth Kadokawa. So the bond is rather trivial because it comes really just for this very simple uniform algorithm. Which does uniform confidence bonds as an alderman is somewhat more tricky because you have an. You are hearing that active setting and not in a bad setting. You need to prove that there is no algorithm which is able to do that.
So not just that uniform sampling doesn't work, but that any algorithm would not work. But it's not also too complicated to to prove that a square root colloquially is about. So this is for her father, the worst case results in this setting. Now, let's think about things which are not worst case, but which come when you try to adapt to the problems. When she becomes a little bit bigger.
So here, for instance, if you look at her as a distribution's or Axminster, so that means here are not all similarly difficult to to classify. So some of them are farther away from the threshold like this one than some others like this one.
And so since you can do adaptive sampling in this setting, probably you want to allocate more budgets to difficult distributions like this one than two easy distributions like this one, because then you can have confidence in Tarvaris, which will be wider for this one. But since you are farther from the from the threshold, it's too bad. And confidence interval, which are smaller for this one, and then you can improve your accuracy.
So what you would like to do if you knew the distance of the arms to the threshold would be to allocate more budget and have smaller confidence interval, which don't intersect the threshold. And in order to have a child, you would object to arms which are farther away as the end.
What counts is that the confidence interval intersects with measured. So, of course, if you don't know the nukes, you cannot do that in the beginning, but what you can do is to try to construct an algorithm that adapts to, uh, to the distributions, to the DNA distribution by learning it while allocating, uh, years to means nuking.
So it's possible to to do something like that, in fact, and what one can prove is that if the right data for the photo means in absolute value, so the gaps with respect to the threshold. And equal rights and a set of problems with capital.
So shall we localise our problem by saying we just can't see the problem, which corresponds to a fixed vector of gaps, then that one can prove that if we look now not at the simple regrets, but that the probability of misclassifying one arm, then this probability is bounded over two sets of Gap Delta for the best possible algorithm of the other exponential minority of each. So the square show is a constant and each eases with some of the other square.
So as the algorithms that achieve that, it's a relatively simple it's an algorithm which allocates, which selects at a time to distribution that maximise that that minimises 60 times the absolute value of an estimate of injury can mean at times of. So you select either because it's it's empirical meaning is very close to the threshold, so we knew at small.
In absolute value, our HKT, similar to yours, are selected because you are not simple enough or because it goes to the threshold where this algorithm does actually that it will allocate to each case a number of samples that is proportional to one the other Takizawa. Ask another question. Mm hmm. Uh, so so the difference between the reserves that you had before, is it related to the fact that you're not looking at but I eat or is it something else?
So here there are many different. So as you mentioned, first we look at it. So it's a quantity that is more conservative. But above all, the reason why we are able to look at the quantity that is more conservative is because we localise our problem. So here we just look, in fact, at problems where the gaps are known. So the algorithm doesn't know it. So algorithm is that. But when we characterise your rates, we localise the problem.
So we look at problems such as X amount are subject to one arm to get the Twitter down. And what is quite funny here is that if you look at the problem where we have localised and we have a Luebbe on which like that and there is an algorithm which doesn't know the other Tabarre and which still manages to achieve up to logarithmic terms, the same rights as robots, which in a sense knows the gaps. And the end in you are as long as you'd like a tree or something.
Yes. Yes. Thank you very. It's the it's the rest of of the rest of the typo. Yeah. So it's really because you look at Asia programme also you look at problems which have gaps fixed in a sense. And it's you can prove that if you don't sign them off of you, then you have to pay that. And there is an algorithm that knows nothing about the gaps, which still manages to to obtain something new, which is under the same authority. So, yeah, it's Mozes look at aspects which makes a difference.
And in fact, this result is only interesting for hotsy large enough with respect to the gaps was always trivial with the result, which is in a sense, it's not something which is only interesting for Valachi. With respect to the capital, the. So it's a typical programme dependent benefits because it depends on the problem. And it's interesting for children as opposed to the other result, which is minimum acceptable in many independence.
Also, questions with respect to that are maybe something is not so. OK, so maybe just to summarise. So to go back to your question, she did the comparison of these two things. So the first thing is really a minimum response, which is like you in Zawadski and it's, quote, colloquial Gharty. And so in order for this to make sense, we'll get to a simpler regret because it would be one of the worst cases you have on which arbitrarily close to the threshold,
you always have one which would be misclassify Sweetzer. That's why it doesn't really make sense to look at the probability of error into Lasky's. And in a sense. Then if he is large enough, it makes sense to look then at more local version of the problem, so to look at the probability of all of our problems, which have gaps which are of a certain nature. And if you look at the look at the sorry and the wisdom of the majority of how it's verminous, you're right.
There is something that something that's a bit of an intuitive knowledge, so you're asking to be GRITOS and look. They need to visit all the kids to be able to say something. Yes, so here in fact, I thought this was all you don't need anything on t I told. But are two things to say. Mother in law, bond, you need some finger on T now if you look at these bonda. So she knew that in fact you look at these bonds, that it's totally useless if she is more than H and H is much bigger than.
Because the delta is was on one. It's time went by because you could have imagined that the media are very large, and then, yes, you are right, but we assumed in the beginning that Samukai between minus one and one was always the weird things that happen. So it's a it's a it's an assumption there, which we did in the beginning, it was always we need to be careful and I think so, yeah, totally. So it's not explicitly done. Like, you don't need that to teach because I think.
But if she's more than gay, then the bond is trivial. So that's in fact, you need to be your authentic. Yeah, so, uh, so, yes, that's iterates, and that's just to get some benchmark where for when the following we look at shave constraints. Um, so maybe I have a question longer. It does seem, you know, it's easy to 45 minutes or one hour. We have one hour. And so it's on I think since since since we can have quite an interactive session.
I feel like you can just take up as much time as you like and we can have questions throughout if everyone is happy with that. OK, so then I am like, uh, fifty five. Yes. Yeah. OK, so any questions and you know, should I go to the to the shape. Constrain the. Um, settings. OK, so then I start with the ship resetting and we start with the turnkeys swimathon setting it, so setting where you observe the distributions means which are increasing functions of Mooky.
So it can be interesting, for instance, in problemi you are trying to find the right amount of droga in a medical trial of. So is said, in fact, has not been studied at all before, we we said it was not studied so much independent gigajoule, but it should be related to another problem, which is quite beginner in computer science and which is a noisy binary search.
So in those binary search, what people want to do is that they have a list of items which are there and they get a new item and they want to insert it in the last. So we share it with corresponds to having an item which is a threshold and to wanted to insert it in other list, why you don't know the items in the list and you have to query them in the least to to order them.
So there is a lot of research on on this, and it's a problem that is related to ours, but a little bit different in some aspects. So he said so in a in a in a noisy Bedi research, in fact, the algorithms that are proposed are totally different to what we discussed quickly in the unconstrained setting. And it's more related to binary search, to naive binary search. So what would one do in binary search in order to solve this problem?
Well, first of all, string two three matches that one would not at all sample alliums. One would not need to do that because they are the other. And so whenever you sample one AAMA, it is below a threshold. Then you know that all the arms, whichever index Morialta needs, are also below a threshold and you don't need to sample them anymore. And it's a key observation if you want to have a good algorithm in this setting and good algorithms are related to binary search.
So what one does in binary search is that when simplistically, typically three points or one point, depending on the version of the binary sort of let's say you sampled three points and if you have no nice, let's say first just to understand what's going on, you observe the means, you see that this one is above threshold, each one is above threshold, each one is on the threshold.
So you can just gather all this Alph of Xians. So with three observations in the nose they're setting, you have already discarded Alpha Swamp's. Then you go you go fast, so you observe again, you are in the middle. And if it's below threshold like here, you can discover all four of the remaining. And you can go on and on like that, always discarding all of the arms that are left to you and what it means is that you don't need to separate.
You just need to separate look to find the treasures in the city. So as a shape constraint here, change is totally the nature of the active learning problem. And now if we compare what we had in the unconstrained setting, so we had this bond fathers sympathy, Greitens is bound for the possibility of war.
And now if we think of an adaptation of what we just discussed in the in the naive binary search to what would happen with noise, so with noise, instead of sampling what time one time each each other, what we could do, for instance, would be to assemble a team of allocate time each other because we are going to the location, we are going to observe.
So if instead of sampling one tiny chanoyu centrality of Aulaqi timer, this would correspond in a sense to the uniform sampling from the beginning and now you have lockyear instead of. So instead of adding square with colloquial capability, you would get screwed. Look, look, look what. If you just do that. And so this was a fast moving and fast the other result, again, what happens is that instead of having a gay arms, you have lock arms.
And so morally, instead of being each, you would be like a logarithmic equivalent of H, which would be bonded like. So this one is maybe a little bit less easy to pass, but for the first one, the idea is really that instead of having gay arms now because of the binary search, we just need to sample lock arms. And so the key becomes looking. So that's Suzuki, it's when when first Niva, but important is setting.
Now, let's see what we can find if we look at lower bounds, so if you look at lower amounts, what is quite immediate to prove with that, with it coming from a financial equality applied in the planning setting, is the following lower bond? Well, you prove that the simple regret's is bonded in the worst case based, quote, lucht you are looking at. So if you compare that with the amount of square root, local level of kludgy, we lose a lot.
But it was always we are not. But then there are things that you can prove is that. If you look at the worst case, militant problem, then lower bombs on the possibility of Iraq is exponential, minus T minus a gap and intuitively just blew up on this makes a lot of sense because imagine that you know which arm is closest to to the threshold, but you don't know it, Sinem. So we don't know if it's up or down the threshold. So if you know which is closer then you know that's a threshold.
You just need to send pulses all the time to simply time and you are going to make little. In the last case, so this one is quite interesting. So if you compare it to the to the like, what is rich by naive binary search? Again, you lose a key, but you don't lose much. Is it clear or is it to be to be vague? Now, this is clear. I think so. So now let's let's continue a bit. And so one can say, OK, we are almost happy because we have everything up to Lockdown's.
But it's a bit, uh, it's a bit of pity because these locked arms are, in fact, meaningful, at least in terms of her story. And one can ask oneself whether these bonds are or whether these bonds are paid. And in fact, solo, our moms are tight and it's possible to have algorithms which do better. So why is it possible? Well, because the binary search is something that is quite conservative.
So what happens is that each time you say, OK, I want to make a correct decision for each of of the choices that I make in the binary search, until you have a union down, then you lose them, which corresponds to a union down on your luck decisions. Now, imagine that you have a binary search where you don't seem to be correct at every decision. So you don't have to be correct that every decision you continue in your binary search, you are going to be wrong.
But at the same time, all your decisions are not going to be incorrect together. And so at some point, you can realise that you are wrong. You can you will see it because you will see the two active segments, if you look at the three points, is it isn't is completely and completely without a threshold. So in a sense, it's possible to see if you maintain an active segment that you of arms that you think of being like close to the threshold.
If you sample at each time, all the points. So left, middle and right, you will see if you continue on binary search that there was an inconsistency. And then you can bolt or two corrections. So even an inconsistency detected at some point you can backtrack. So what is possible to do is to construct an algorithm is that instead of doing a naive binary search that as to be good at every step does a slightly longer binary search that he's allowed to backtrack. And intuitively, this would work.
Because if you don't want every decision to be good, but to just say I want to have a lot of good decision and some bad decision. Then you can have a bond, which is not a union bond, so you don't lose this gogolewski, but where you have more good decisions and bad decisions, it's just that you don't know whether good decisions and bad decisions are bad. The idea that each time that you make a good decision, you correct a bad decision.
And so if you have more good decisions and bad decision in your in your binary search, in the end you will come out and ask the question. So this new argument for describing it, it's behaving better than the naive one in the minimal sense. But do you know whether I said uniformly better or always better are often better? Yes. So I will come to that because we will also characterise this one so as the probability of [INAUDIBLE].
And this one is not so in Zawadski. This one is really. So if you think about this, go up on them. So about this bond, because we will prove that an algorithm manages to achieve that. What it tells you is that you show an algorithm that achieves that. What it tells you is that if you go to sleep, even if you knew from the beginning of where the threshold was. Which would you know, whether you are closer to the threshold is down there and if you spend all your budget on this,
then you cannot do better than that. And what we are going to do is to construct an algorithm that actually does that, so that manages to adapt to the problem in a sense, and that will also be like many experts, but that also adapting.
So it's not totally adapted in the sense that the Konstantin's the exponential shear is not tied with a deficit in the sense that if the problem as a gap as well as a smaller step, which is of a given order to find it, to adapt to it, and you allocate most of the budget to get. Who is not so perfectly adaptive, but it adapts quite a bit to the problem. Yeah, but, uh, yeah, in fact, uh, in fact, we have to vulgarism then thinking we don't have one that does,
but we have to agree someone that does that. And when they do that, we think that it's possible to prove that Numax algorithm is also doing that. But it's more complicated. So, yeah, no, it's not the same, which does both, but I think like one of them, Candlebox. But both of them were cohabitate with bad and good decisions, which are outwitting each other.
In fact. So just to explain a bit more, the algorithm, in fact, it works on a tree, so you have a tree on your set of ups and each node of the tree corresponds to a segment of arms. So here, for instance, the first note correspond to all the arms. And this one would correspond to one, two arms, one, two, three. And each time you assemble the arm on the left, in the middle and in the right to find Sentier, you would separate arm one arm free and arm five.
And depending on the outcome of the sampling, you go either left or right in the industry and you focus then more and more of a set of arms. So just to explain ours like ours is Wuxia at each time you assemble to allocate time, each time there's small consistency so that you'll have a longer binary search.
This constant is much smaller than one, but it's a unique circumstance. And what happens is that then at each time you control, so you see what you can see that the probability of having mukaddes close to you when you sample with tea or Wallachia sample is like, quote, looking obviously with a given probability that he's fixed. So and then, like, you know, sense to throw a coin and to coin is very biased toward a good, good outcome, but you have a small chance of having a bad outcome.
And if the outcome is good, then it means that you are going to do a step in the right direction of the tree. And if the outcome is bad, then you do a step in the wrong direction of the tree. And so imagine, for instance, that you do a step or it's a bad decision of the tree. So the threshold is severe, but you do step into the wrong decision. What happens is that when you do a good decision, you realise that the segment is actually completely above threshold and you go back.
And so each bad decision is outweighed by a good decision and. What happens is that we are going to be approving the people that didn't have good decision is much higher than the number of bad decisions. For instance, if you are four times more good decisions and bad decisions is auto correction mechanism works and then you correct these bad decisions, and so at the end, you can prove that there is an algorithm that satisfies.
Yes, in the worst case and there is another algorithm that is more simple, that satisfies something more local. And in fact, we prove we we don't prove it. But we think that the algorithms that I just described those both. But for the local version, we have a simple algorithm which which works and we didn't like bother too much at a checking whether the ones that satisfy, so does using.
So, yeah, so in the end, in fact, we have a bounce both for those regrets and the possibility of your father's problem, which are which are optimal in the sense that that they described. So as you can see, you gain quite a lot when you go from instructor to Manhattan because of these structural constraints, which is very, very helpful in active learning, much more than in.
In fact, interestingly. So maybe just to ask them, I can continue on, but I can also stop if you think that's what I mean, the. It's too tight or I can go quickly on concave, as you prefer. I'd personally be quite interested in seeing the concave setting, but if anyone has a strong preference to ask questions and please just shout.
Now, let's go ahead with concave, if that's OK, with pleasure, so I can present, so I can try to be a little bit quicker for because the ideas are, in fact, very, uh, related to Manhattan. But there is a big twist. But, uh, but there are many things that come from that. So let's go to the conclave said, you know, so the conclave said here you have a basic key, which is like a discreet conclave function of key.
So you said as not being distributed in the literature, but again, it's who said it, but there's not been also really investigating as such. But why? You have some literature which is related to in particular, you're related to zeros are there are no easy convex optimisation. So the aim is not to find a level set, but to find the maximum.
A function which is convex and noisy and it's also not into its dimension and it's not a it's not in a discrete setting, but nevertheless, there are some ideas that can be taken from the studio and adapt to this problem. And in particular, there is a quite a naive idea that can be adapted and which isn't an adaptation of the binary search to the set because concave function, it's like first increasing and then decreasing like this.
And you have a big plateau into because it's concave. And so what you can do is that you can sample four points. And since it can give you recover, you can interpolate your function like this when you have four points and you will be able to always discover one third of your space. So you'll be able to just sell them and you will have an active set here that you said you. So I'm forgetting for a moment about the right side on because it's the same on the left and on the right,
but then if you go on the left side, you can do the same. So you do take four points. You observe the function in these four points and you can discard, again, one part of the space, which is clearly above threshold. And you continue like this and you can always discard one third of the space, so it's something that is done in some people and zeroes are the optimisation, which is very related to binary search, just adapted to the to the Concave said.
So if you do like that, you just need to sample a multiple of Lacayo like arms and you can take the same thing that you had in a modern setting and you can sample you've allocated to each armour and you have Lakki steps and and then you can have the same kind of bombs as intermittent and into Morton modern setting. I remind you that the 1999 research was Ritchies, quote, lucky, lucky, lucky, divided by so. So we are going to look like because it's a nice version, which I'm presenting again.
And she has a look. And if you do that in the concave setting, it it will work in the same way because each time you discard a fraction of your space, so you will get the same bond almost for free with a naive algorithm. And, of course, doing the same trick, one can think of getting rid of the log and of the larger. So one could already think of that and to get a square root Lacayo Gadge in the concave section.
So now let's see if this is tight, because concave is something which is quite restricted. It's much more than the Manhattan. Um. Yeah, sorry, this is what I just said. So if you if you apply to correction, you can, like, remove the log log. So go from square root, lucky, lucky, lucky to squirrelled location and also keep searching if you think of the correct. OK, so now let's look at lower bonds.
And in fact, it doesn't look too good because what we ever used was, quote, lobola capability instead of Squirtle accurate. So what you can prove is that it's possible to construct a set of problems. So that's the simple regret's and far, far below our bonds, which is more local. You have against exponential minus koening that square.
So this is when it's clear that it's not really possible to improve it in the concave case because it tells you that even if you know so I'm closer to the threshold. You cannot do better than allocating all your budget to it and then you pay that off. So here you don't have much to win with respect to the Manhattan. But when it comes to the Earth, to the simple regrette bond, fasullo, our bond and you have a lot of Luckly and there are some big cap.
So just to I'm just going to present very, very quickly the structure of the lower bond, because it's extremely instructive for algorithms next. So why instead of looking. Well, because when the way to construct a lower bond here, which seems state is to others who arms like this and to have a concave function, which is in fact M'Naghten and which is like this, which is the first one, then a second one, then the first one and then another one, etc. So we can have functions like this.
And the thing is that they need to be exposed to exponentially space when it comes to the point where they touch the upper side of the threshold. So why is that? Well, because otherwise these functions are too close together when it comes to to the to the sense of the answer to the threshold. So if you make a mistake, uh, here on the threshold, if it's not exponential space, it's not a big enough mistake. So you can just in fact, if you can just pack your space with Lakki function.
Instead of key functions, as you can do in one of the. So why is it interesting, your father on the. Well. Because, in fact, the idea is to use this scale in the government, so we have to do our bombs, but it's something that is also relevant for the lower part of the problem. So the idea will be to take some algorithm and to use it on a large scale instead of using it on the on the scale of chaos and then to do a corrected binary search on the large scale.
So I will explain what I mean by that a little bit later. And now the problem is that we can do that. And if we do that on a large scale, what we can do is that each step we can reduce the error by a factor in the algorithm. And so doing looks good, approximation is sufficient, is not sufficient. And what we have to do on top of that is to do, uh, also a local approximation.
So we have to have a multiskilled sorry approximations when we try to explain this, and so the algorithm that will result from that perform iterative, connected by the research on the log scale and refines gradually delivers. So just to try to illustrate this, what we are going to do is that we are not going to do a binary such answer all set of arms,
but on a large scale of the set of arms. So you just put Lacourt like your first arm and assuming the force arm to its arms, so sixteen's arm, etc. So we would take on the log scale and that you do a binary search on the underdog scale. And because the function is convex, it's concave. Sorry, the threshold is going to still be here like between two of the arms like this.
And you can, uh, by doing a binary search, remove a significant portion of your arms and reduce the distance to the threshold by a constant factor. You should do that. And so you have to do that iteratively in a motorcade way that in a multi scale way in order to to go closer and closer to the threshold. And if you do like that lagom lacaze binary search on a on a large scale, then you you reach her, you reach a threshold at which time I look at most.
Yeah, so you and then you you you you should do that, like just by doing corrected by research, unlucky, you are already zooming and reducing the eho by a factor of. So like that, you can refine level assets and you do that Stazi. So it's the last level that will then have a basically and I was lucky because you just have lockdown's.
So this is OK, this is a little bit difficult to explain, the algorithm is quite complicated, but the idea is really instead of having to go on a large scale and reduce, to look and do that iteratively a different level. And if you do that, you get these crowd WQ. So it's quite interesting because really in the concave setting, you gain technology with respect to the militants setting, so that's quite so quite nice and the logarithm of the possibility of it all remains the same.
But as I mentioned, it's really already something which is a serious one. So, yeah. OK, so this is just a comparison of just researching the social structure that you take, look into it and say you have lucky and it's a concave setting and waiting to unstructured setting. You pay for all arms in the long run. But in concrete, you just before that is closer to the threshold in the local law in localities. So I think I will stop. I will stop there. I want presents a unique model.
But if you want to try to guess for the union model, whether it's closer to a concave or not, one structure in it's feel free and I can tell you then what we can say about the unique modalities. So thank you very much and sorry to end was a little bit a little bit messy. Thank you. Thank you so much. Applause On behalf of everyone that we've got, we've got a couple of minutes for some for some extra questions. So please just amuse yourself and go ahead. Uh.
All right, thanks very much for that. That was really interesting and very lovely. So my question is just on the lost functions you chose and I was wondering if one was to, for example, for four, if you were if you were only worried about the negative ones. So not both positive and negative, would that be would that be a kind of trivial change or would that be?
I mean, it seems like it was the sort of thing someone might ask, so if you just care about your which you make when you classify a name which is below threshold at the bottom. Yeah. But in this case, you could say your arms are below threshold. And then you would make zero for the hour then, you know, I mean. I mean. So. I guess I was thinking of only only. Counting the absolute value of new music was negative, I see, so you're saying so how would you formulate that?
I mean, I want to I want to identify any negative. So, yeah, so I wouldn't know I would try to formulate that, because if you don't pay for some type, your. Yeah, then, you know, since, um, uh, you just say they're all negative, uh. Maybe you can put different weights on both so you could say, like, I pay this price for misclassifying your negative arm and just price. So like, um. If you could maybe cast it like that and to have like a very unbalanced price on both.
I was just thinking that perhaps in some some kind of drug studies and so on, you would certainly pay a lot unsymmetrical prices. It would make a lot of sense actually like to them to have like a different price you have. Yeah, we don't look too much into that. But that would that would definitely make a lot of sense. I guess the question is how how how sort of constrained is it on the particular losses that you considered it what scope there is to generalise? Yeah. So it's. It's rather.
So the thing is that we are shot up to multiplicative constants, so if you put price with which are unbalanced and unbalanced is like, yeah, to multiplicative constant, it would be difficult to use the same analyses to catch that kind of effect because it would be a to effect on the it I'm not sure is. Oh that's great things. I'm just curious.
Thank you very much for your question. I had a quick question, which is, have you thought at all about, um, uh, if you have, like, higher dimensional shape constraints, so if your arms are like, you know, so, for example, you've got two drugs and you're interested in the dosage of of two drugs, how these types of results would would would generalised, uh, to meet certain constraints. Yeah. So that's, uh, that's actually a very, very interesting question.
And we have been thinking a bit about it, but it's not so easy to to pose a problem. Well, and also we think that those, again, would be way less addressed in dimension, for instance, to because if we should look at it. So you go from data to Lakki when it comes to unstructured to.
And what we believe is that if you are so if you are, uh, in dimension to for instance, so you have like one dimension, you would get here like a square with K one K two times like one kid, and you would get probably something which is rather the Makowski one and two times log of the other. So the beginning would be less drastic, but it's possible to do it, and in fact, you could gain one dimension when you go into the argument that what would happen.
But it's not so easy to to study. And it's very interesting. OK, thank you. I'm going to just stop recording.