1
00:00:00,060 --> 00:00:05,010
So now it's recording and thank you. Over to you.

2
00:00:05,010 --> 00:00:12,300
Yes, thanks very much, Father, for the invitation and the kind introduction, so I'm very happy to be here today.

3
00:00:12,300 --> 00:00:20,430
And since we are in a rather small group, maybe what we can do is that whenever there is something which is unclear,

4
00:00:20,430 --> 00:00:28,680
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.

5
00:00:28,680 --> 00:00:34,080
It's not so relevant. So let's just do like something where as soon as something is unclear,

6
00:00:34,080 --> 00:00:41,520
you stop me and then we take time and it's like, yeah, it's manageable in a small group.

7
00:00:41,520 --> 00:00:46,830
OK, so I'm going to talk to you about the thresholding problem and the constraints.

8
00:00:46,830 --> 00:00:50,880
And this is a joint work with the people in my group.

9
00:00:50,880 --> 00:00:59,760
So Gemzar, James Churchill with finishing with me on how I look at it is finished actually last this year.

10
00:00:59,760 --> 00:01:06,750
In the beginning of the year, Maheu would say towards the you with me and I finished three years ago and Pamina,

11
00:01:06,750 --> 00:01:10,540
who is currently doing a concert in my group.

12
00:01:10,540 --> 00:01:21,890
So the topic of the stalky sequential learning in and shape constraints are sequential learning under constraints, and it's based on free papers.

13
00:01:21,890 --> 00:01:25,210
So the first one, which is rather older,

14
00:01:25,210 --> 00:01:33,940
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.

15
00:01:33,940 --> 00:01:41,800
US when I say working people, when in fact it was accepted in the middle of this year and ends in the war zone.

16
00:01:41,800 --> 00:01:49,110
So I'm going to present these three works and also put them in context of dijo.

17
00:01:49,110 --> 00:01:53,940
So just to start, because I guess many of you are not walking on sequential learning,

18
00:01:53,940 --> 00:01:58,920
which was the one that was Airfield's, I will explain what I mean here by sequential learning.

19
00:01:58,920 --> 00:02:06,120
And more precisely, those have been the problem. So it's a problem of resource optimisation, innovative and.

20
00:02:06,120 --> 00:02:12,870
So unlike in machine learning or statistics, you don't have the data available beforehand,

21
00:02:12,870 --> 00:02:17,910
but you collect them sequentially in time as you go through to.

22
00:02:17,910 --> 00:02:26,700
So you have distribution. Newquay with unknown means Muki and you have limited sampling resources.

23
00:02:26,700 --> 00:02:32,070
So it can be seen as the size of your as your sample size, so to say.

24
00:02:32,070 --> 00:02:39,240
But at the beginning you have no data. And what happens is that you can choose your data sequentially at each time.

25
00:02:39,240 --> 00:02:49,470
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.

26
00:02:49,470 --> 00:02:50,940
So, for instance, at nine one,

27
00:02:50,940 --> 00:02:58,330
you select for first distribution and you get a sample from the distribution a time to you select the second one at a time.

28
00:02:58,330 --> 00:03:05,700
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.

29
00:03:05,700 --> 00:03:13,830
And the main difference with batch learning is that you can base your choice of samples on the best.

30
00:03:13,830 --> 00:03:23,550
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.

31
00:03:23,550 --> 00:03:31,390
Katie, on that. So you are looking at your sample like that, typically in order to fulfil an objective.

32
00:03:31,390 --> 00:03:37,720
And for instance, in this talk shows, the AMA that we are going to study is the threshold,

33
00:03:37,720 --> 00:03:47,660
given the problems with the aim of finding all distribution so that women are above a given threshold.

34
00:03:47,660 --> 00:03:55,490
So you have a given threshold and you want to find through distribution with Menagh is above the threshold.

35
00:03:55,490 --> 00:04:03,380
So return my family, uh, you have a threshold now and what you want to find is who is the Victor Cuth,

36
00:04:03,380 --> 00:04:16,010
which is such that, uh, uh, Q is, um, is, um, is a sign of, um, U.K. minister.

37
00:04:16,010 --> 00:04:22,760
OK, so we invented vocabulary, I just say that because I want a word, I will say it even if I don't.

38
00:04:22,760 --> 00:04:27,350
If I don't, if I even if I pay attention.

39
00:04:27,350 --> 00:04:35,150
So so distributions are typically called arms. So if I say arms, what I mean, as a distribution, you can.

40
00:04:35,150 --> 00:04:41,840
Yes, and then when it comes actually from the slot machines with arms, so that's that's why.

41
00:04:41,840 --> 00:04:52,280
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,

42
00:04:52,280 --> 00:04:57,690
shape constraints are going to be. So.

43
00:04:57,690 --> 00:05:07,110
Here we are studying the company problem and in this talk, just to make things simpler, but we don't really have to.

44
00:05:07,110 --> 00:05:17,490
We are going to assume that the distribution Newquay, so the distribution of each amah is actually and distribution with mean Newquay and Valencian.

45
00:05:17,490 --> 00:05:24,880
So the Gushin assumption is not necessary, but for these talks, in order to keep things as simple as possible,

46
00:05:24,880 --> 00:05:33,670
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.

47
00:05:33,670 --> 00:05:38,700
Can I ask you a question? Yes, sure. So when you say that the resolution is not necessary.

48
00:05:38,700 --> 00:05:45,510
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?

49
00:05:45,510 --> 00:05:48,810
But it can be other than different emotions. Yes.

50
00:05:48,810 --> 00:05:53,580
So it's necessary to do to do some to do some better way.

51
00:05:53,580 --> 00:05:59,760
And we it so we need to do some assumptions and that parametric.

52
00:05:59,760 --> 00:06:05,290
But typically what so the assumption in the paper is that the distributions are bounded ossobuco.

53
00:06:05,290 --> 00:06:13,670
No, I think we do subquestion. So what you need in fact is subquestion and you need to know the subquestion constant.

54
00:06:13,670 --> 00:06:23,320
So, yeah, if, for instance, if it's a C-section, you need to know I don't abundance.

55
00:06:23,320 --> 00:06:32,500
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

56
00:06:32,500 --> 00:06:41,110
on surveillance of the distribution showing these Togusa algorithms that we are going to discuss do not add up to surveillance.

57
00:06:41,110 --> 00:06:52,690
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.

58
00:06:52,690 --> 00:06:59,040
As are some of the questions on the U.S. national.

59
00:06:59,040 --> 00:07:08,660
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.

60
00:07:08,660 --> 00:07:17,090
So at each Ronchi, the learner pulls Anana Katie Innocenti and observe a Sembler EKG,

61
00:07:17,090 --> 00:07:22,670
which is distributed according to a of MINNUCCI and Violence One.

62
00:07:22,670 --> 00:07:30,350
So Distribution Newgate and upon exertion of the budget, the aim of the donor will be to to predict.

63
00:07:30,350 --> 00:07:37,040
Q So just in store with your Q is simply a sign of Nuk.

64
00:07:37,040 --> 00:07:46,140
So director of Sign of Newquay to Cuba secured and Kuwait will be a vector of sign of minus one one.

65
00:07:46,140 --> 00:07:56,880
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,

66
00:07:56,880 --> 00:08:01,380
which I'm going to show now, the threshold here is the line.

67
00:08:01,380 --> 00:08:05,400
The black line of the exceptions corresponds to the index.

68
00:08:05,400 --> 00:08:15,320
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.

69
00:08:15,320 --> 00:08:23,160
So you can see, in fact, the zoomIn UK as a discrete function of.

70
00:08:23,160 --> 00:08:29,840
Is it clear the city? Yes, thank you.

71
00:08:29,840 --> 00:08:41,060
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.

72
00:08:41,060 --> 00:08:48,650
So we are going to have two measures of regrets, which we correspond in a sense to to whether we want to study things,

73
00:08:48,650 --> 00:08:53,840
some politically neutral, yet particularly in the long run or in the short run.

74
00:08:53,840 --> 00:09:02,330
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.

75
00:09:02,330 --> 00:09:12,270
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.

76
00:09:12,270 --> 00:09:18,240
The US Army is a measure of performance that we are going to use is a simple regret's,

77
00:09:18,240 --> 00:09:26,910
which is a higher expectation of the maximal gap with respect to the threshold of a misclassified arm.

78
00:09:26,910 --> 00:09:35,760
So, for instance, imagine that we predict here at Cubase you add and that we predict two arms wrongly.

79
00:09:35,760 --> 00:09:42,630
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.

80
00:09:42,630 --> 00:09:50,420
Then what we pay is the distance is the biggest distance to the Shultz was just one case.

81
00:09:50,420 --> 00:09:57,620
So it is harder to measure offer this as a hobby to a fellow is more conservative than to simply regrets,

82
00:09:57,620 --> 00:10:01,430
because if we just make a mistake on one arm, we are we are penalised.

83
00:10:01,430 --> 00:10:07,490
Whereas here if we make a mistake on an arm which is very close to the threshold, we don't pay too much.

84
00:10:07,490 --> 00:10:11,740
So it's a little bit less concise.

85
00:10:11,740 --> 00:10:20,650
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.

86
00:10:20,650 --> 00:10:35,140
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.

87
00:10:35,140 --> 00:10:38,890
But we are going also to consider more restrictive setting.

88
00:10:38,890 --> 00:10:50,880
So first the monotone setting where in fact Zsa Zsa Zsa menarche is supposed to be increasing, uh, depending on.

89
00:10:50,880 --> 00:11:00,420
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.

90
00:11:00,420 --> 00:11:05,560
The second shipment means that we are going to consider if damage is concave.

91
00:11:05,560 --> 00:11:10,870
So we assume that the concave function of.

92
00:11:10,870 --> 00:11:16,390
Which can be returned except for her discreet function.

93
00:11:16,390 --> 00:11:21,760
And the last ship constraint that we will consider again, if they are damaged is unique model.

94
00:11:21,760 --> 00:11:32,980
So it means that key first start by increasing and then by decreasing that Mukasa are a fast increase and then decrease depending on.

95
00:11:32,980 --> 00:11:40,120
So you have some Elser that you are first increasing and then decreasing.

96
00:11:40,120 --> 00:11:48,630
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.

97
00:11:48,630 --> 00:11:58,440
Any questions on anything related to the setting and you know.

98
00:11:58,440 --> 00:12:05,880
OK, so then we can start first with the unconstrained setting just to to fix a little bit.

99
00:12:05,880 --> 00:12:10,280
So in the unconstrained setting, Mulcahy's any function of key.

100
00:12:10,280 --> 00:12:19,880
And it's a setting which is quite classical now by now in invented, so it was introduced in 2016 by Senegal in 2014.

101
00:12:19,880 --> 00:12:27,560
In fact, already, you know you know, people didn't have this name, but it was the same setting.

102
00:12:27,560 --> 00:12:34,460
And it's it has been studied quite a lot by now.

103
00:12:34,460 --> 00:12:42,850
So there are many papers which have been proposing algorithms setting books in what people call the confidence setting and in the budget setting.

104
00:12:42,850 --> 00:12:46,970
So I'm not going to describe too much of in setting,

105
00:12:46,970 --> 00:12:54,710
but we are in a fixed budget setting that to say we have a fixed budget and we try to fulfil our objective.

106
00:12:54,710 --> 00:13:04,990
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.

107
00:13:04,990 --> 00:13:15,290
So, yeah, I'm going to describe a little bit of results in the paper by a look at earlier on on here.

108
00:13:15,290 --> 00:13:19,640
Look at the good side and myself. But all the yuzu.

109
00:13:19,640 --> 00:13:22,790
So it's one it's it's a little bit less refined,

110
00:13:22,790 --> 00:13:31,370
but also one which KARMELITA proposals for solutions to algorithmic solutions, which which are very, very good just because.

111
00:13:31,370 --> 00:13:38,170
Yeah, it's not really the focus of these talk. But Martha fix really terrific ideas.

112
00:13:38,170 --> 00:13:45,300
So let's start with the bounce on the simple Regret's a.m. act setting.

113
00:13:45,300 --> 00:13:57,030
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,

114
00:13:57,030 --> 00:14:06,930
so what's the best possible algorithm would we do on the most difficult problem when it comes to the simple regrette?

115
00:14:06,930 --> 00:14:15,180
So when it comes basically to the distance of the to the to the larger distance of the worst misclassified to the threshold,

116
00:14:15,180 --> 00:14:19,560
you can prove that us quote which.

117
00:14:19,560 --> 00:14:28,110
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.

118
00:14:28,110 --> 00:14:34,710
So imagine an algorithm that just allocates to each distribution of budget hierarchy.

119
00:14:34,710 --> 00:14:45,810
Then if you do a confidence set around your your meana and this assumption of or subcutaneously energy,

120
00:14:45,810 --> 00:14:49,740
you have a confidence interval which would have the highest growth capability.

121
00:14:49,740 --> 00:14:57,960
And since you have key arms distributions, if you do a union, which is in fact similar to multiplicative constants,

122
00:14:57,960 --> 00:15:06,150
you have a confidence interval which are all uniform and which have PSI square with Killock.

123
00:15:06,150 --> 00:15:11,070
So you pay additionally because of the multiplicity of the arms.

124
00:15:11,070 --> 00:15:21,420
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.

125
00:15:21,420 --> 00:15:30,060
And so in the worst case, it will fail on Anoma, which is Autodefensas Growth Kadokawa.

126
00:15:30,060 --> 00:15:37,050
So the bond is rather trivial because it comes really just for this very simple uniform algorithm.

127
00:15:37,050 --> 00:15:44,390
Which does uniform confidence bonds as an alderman is somewhat more tricky because you have an.

128
00:15:44,390 --> 00:15:50,680
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.

129
00:15:50,680 --> 00:15:55,910
So not just that uniform sampling doesn't work, but that any algorithm would not work.

130
00:15:55,910 --> 00:16:04,320
But it's not also too complicated to to prove that a square root colloquially is about.

131
00:16:04,320 --> 00:16:11,020
So this is for her father, the worst case results in this setting.

132
00:16:11,020 --> 00:16:17,770
Now, let's think about things which are not worst case, but which come when you try to adapt to the problems.

133
00:16:17,770 --> 00:16:20,650
When she becomes a little bit bigger.

134
00:16:20,650 --> 00:16:32,410
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.

135
00:16:32,410 --> 00:16:38,590
So some of them are farther away from the threshold like this one than some others like this one.

136
00:16:38,590 --> 00:16:43,210
And so since you can do adaptive sampling in this setting,

137
00:16:43,210 --> 00:16:51,670
probably you want to allocate more budgets to difficult distributions like this one than two easy distributions like this one,

138
00:16:51,670 --> 00:16:55,810
because then you can have confidence in Tarvaris, which will be wider for this one.

139
00:16:55,810 --> 00:16:59,560
But since you are farther from the from the threshold, it's too bad.

140
00:16:59,560 --> 00:17:06,370
And confidence interval, which are smaller for this one, and then you can improve your accuracy.

141
00:17:06,370 --> 00:17:10,180
So what you would like to do if you knew the distance of the arms to the

142
00:17:10,180 --> 00:17:14,950
threshold would be to allocate more budget and have smaller confidence interval,

143
00:17:14,950 --> 00:17:24,250
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.

144
00:17:24,250 --> 00:17:34,460
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,

145
00:17:34,460 --> 00:17:39,140
but what you can do is to try to construct an algorithm that adapts to,

146
00:17:39,140 --> 00:17:51,430
uh, to the distributions, to the DNA distribution by learning it while allocating, uh, years to means nuking.

147
00:17:51,430 --> 00:17:55,480
So it's possible to to do something like that, in fact,

148
00:17:55,480 --> 00:18:05,450
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.

149
00:18:05,450 --> 00:18:10,430
And equal rights and a set of problems with capital.

150
00:18:10,430 --> 00:18:15,560
So shall we localise our problem by saying we just can't see the problem,

151
00:18:15,560 --> 00:18:24,380
which corresponds to a fixed vector of gaps, then that one can prove that if we look now not at the simple regrets,

152
00:18:24,380 --> 00:18:29,180
but that the probability of misclassifying one arm,

153
00:18:29,180 --> 00:18:41,840
then this probability is bounded over two sets of Gap Delta for the best possible algorithm of the other exponential minority of each.

154
00:18:41,840 --> 00:18:50,080
So the square show is a constant and each eases with some of the other square.

155
00:18:50,080 --> 00:18:56,320
So as the algorithms that achieve that, it's a relatively simple it's an algorithm which allocates,

156
00:18:56,320 --> 00:19:11,240
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.

157
00:19:11,240 --> 00:19:23,150
So you select either because it's it's empirical meaning is very close to the threshold, so we knew at small.

158
00:19:23,150 --> 00:19:27,060
In absolute value, our HKT, similar to yours,

159
00:19:27,060 --> 00:19:33,410
are selected because you are not simple enough or because it goes to the threshold where this algorithm does

160
00:19:33,410 --> 00:19:41,120
actually that it will allocate to each case a number of samples that is proportional to one the other Takizawa.

161
00:19:41,120 --> 00:19:47,660
Ask another question. Mm hmm. Uh, so so the difference between the reserves that you had before,

162
00:19:47,660 --> 00:19:54,770
is it related to the fact that you're not looking at but I eat or is it something else?

163
00:19:54,770 --> 00:19:58,230
So here there are many different. So as you mentioned, first we look at it.

164
00:19:58,230 --> 00:20:00,860
So it's a quantity that is more conservative.

165
00:20:00,860 --> 00:20:07,940
But above all, the reason why we are able to look at the quantity that is more conservative is because we localise our problem.

166
00:20:07,940 --> 00:20:15,650
So here we just look, in fact, at problems where the gaps are known.

167
00:20:15,650 --> 00:20:22,640
So the algorithm doesn't know it. So algorithm is that. But when we characterise your rates, we localise the problem.

168
00:20:22,640 --> 00:20:30,330
So we look at problems such as X amount are subject to one arm to get the Twitter down.

169
00:20:30,330 --> 00:20:37,260
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

170
00:20:37,260 --> 00:20:45,510
and there is an algorithm which doesn't know the other Tabarre and which still manages to achieve up to logarithmic terms,

171
00:20:45,510 --> 00:20:50,610
the same rights as robots, which in a sense knows the gaps.

172
00:20:50,610 --> 00:20:55,410
And the end in you are as long as you'd like a tree or something.

173
00:20:55,410 --> 00:21:05,240
Yes. Yes. Thank you very. It's the it's the rest of of the rest of the typo.

174
00:21:05,240 --> 00:21:13,020
Yeah. So it's really because you look at Asia programme also you look at problems which have gaps fixed in a sense.

175
00:21:13,020 --> 00:21:21,060
And it's you can prove that if you don't sign them off of you, then you have to pay that.

176
00:21:21,060 --> 00:21:30,660
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.

177
00:21:30,660 --> 00:21:34,860
So, yeah, it's Mozes look at aspects which makes a difference.

178
00:21:34,860 --> 00:21:43,830
And in fact, this result is only interesting for hotsy large enough with respect to the gaps was always trivial with the result,

179
00:21:43,830 --> 00:21:49,960
which is in a sense, it's not something which is only interesting for Valachi.

180
00:21:49,960 --> 00:21:58,450
With respect to the capital, the. So it's a typical programme dependent benefits because it depends on the problem.

181
00:21:58,450 --> 00:22:09,400
And it's interesting for children as opposed to the other result, which is minimum acceptable in many independence.

182
00:22:09,400 --> 00:22:18,040
Also, questions with respect to that are maybe something is not so.

183
00:22:18,040 --> 00:22:26,020
OK, so maybe just to summarise. So to go back to your question, she did the comparison of these two things.

184
00:22:26,020 --> 00:22:35,530
So the first thing is really a minimum response, which is like you in Zawadski and it's, quote, colloquial Gharty.

185
00:22:35,530 --> 00:22:37,330
And so in order for this to make sense,

186
00:22:37,330 --> 00:22:44,450
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,

187
00:22:44,450 --> 00:22:53,920
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.

188
00:22:53,920 --> 00:23:04,520
And in a sense. Then if he is large enough, it makes sense to look then at more local version of the problem,

189
00:23:04,520 --> 00:23:10,880
so to look at the probability of all of our problems, which have gaps which are of a certain nature.

190
00:23:10,880 --> 00:23:19,780
And if you look at the look at the sorry and the wisdom of the majority of how it's verminous, you're right.

191
00:23:19,780 --> 00:23:28,090
There is something that something that's a bit of an intuitive knowledge, so you're asking to be GRITOS and look.

192
00:23:28,090 --> 00:23:34,710
They need to visit all the kids to be able to say something.

193
00:23:34,710 --> 00:23:41,010
Yes, so here in fact, I thought this was all you don't need anything on t I told.

194
00:23:41,010 --> 00:23:48,600
But are two things to say. Mother in law, bond, you need some finger on T now if you look at these bonda.

195
00:23:48,600 --> 00:24:00,280
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.

196
00:24:00,280 --> 00:24:12,970
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,

197
00:24:12,970 --> 00:24:20,780
but we assumed in the beginning that Samukai between minus one and one was always the weird things that happen.

198
00:24:20,780 --> 00:24:30,150
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.

199
00:24:30,150 --> 00:24:35,870
So it's not explicitly done. Like, you don't need that to teach because I think.

200
00:24:35,870 --> 00:24:43,990
But if she's more than gay, then the bond is trivial. So that's in fact, you need to be your authentic.

201
00:24:43,990 --> 00:24:55,900
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.

202
00:24:55,900 --> 00:25:03,640
Um, so maybe I have a question longer. It does seem, you know, it's easy to 45 minutes or one hour.

203
00:25:03,640 --> 00:25:10,030
We have one hour. And so it's on I think since since since we can have quite an interactive session.

204
00:25:10,030 --> 00:25:16,990
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.

205
00:25:16,990 --> 00:25:22,670
OK, so then I am like, uh, fifty five. Yes. Yeah.

206
00:25:22,670 --> 00:25:27,250
OK, so any questions and you know, should I go to the to the shape.

207
00:25:27,250 --> 00:25:34,670
Constrain the. Um, settings.

208
00:25:34,670 --> 00:25:41,210
OK, so then I start with the ship resetting and we start with the turnkeys swimathon setting it,

209
00:25:41,210 --> 00:25:48,050
so setting where you observe the distributions means which are increasing functions of Mooky.

210
00:25:48,050 --> 00:25:56,170
So it can be interesting, for instance, in problemi you are trying to find the right amount of droga in a medical trial of.

211
00:25:56,170 --> 00:26:03,220
So is said, in fact, has not been studied at all before, we we said it was not studied so much independent gigajoule,

212
00:26:03,220 --> 00:26:11,900
but it should be related to another problem, which is quite beginner in computer science and which is a noisy binary search.

213
00:26:11,900 --> 00:26:13,490
So in those binary search,

214
00:26:13,490 --> 00:26:22,610
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.

215
00:26:22,610 --> 00:26:30,110
So we share it with corresponds to having an item which is a threshold and to wanted to insert it in other list,

216
00:26:30,110 --> 00:26:36,650
why you don't know the items in the list and you have to query them in the least to to order them.

217
00:26:36,650 --> 00:26:47,850
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.

218
00:26:47,850 --> 00:26:53,340
So he said so in a in a in a noisy Bedi research, in fact,

219
00:26:53,340 --> 00:26:59,190
the algorithms that are proposed are totally different to what we discussed quickly in the unconstrained setting.

220
00:26:59,190 --> 00:27:03,780
And it's more related to binary search, to naive binary search.

221
00:27:03,780 --> 00:27:08,790
So what would one do in binary search in order to solve this problem?

222
00:27:08,790 --> 00:27:14,100
Well, first of all, string two three matches that one would not at all sample alliums.

223
00:27:14,100 --> 00:27:21,900
One would not need to do that because they are the other. And so whenever you sample one AAMA, it is below a threshold.

224
00:27:21,900 --> 00:27:29,520
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.

225
00:27:29,520 --> 00:27:40,740
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.

226
00:27:40,740 --> 00:27:46,890
So what one does in binary search is that when simplistically, typically three points or one point,

227
00:27:46,890 --> 00:27:52,530
depending on the version of the binary sort of let's say you sampled three points and if you have no nice,

228
00:27:52,530 --> 00:27:57,420
let's say first just to understand what's going on, you observe the means,

229
00:27:57,420 --> 00:28:02,220
you see that this one is above threshold, each one is above threshold, each one is on the threshold.

230
00:28:02,220 --> 00:28:13,360
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.

231
00:28:13,360 --> 00:28:17,890
Then you go you go fast, so you observe again, you are in the middle.

232
00:28:17,890 --> 00:28:25,320
And if it's below threshold like here, you can discover all four of the remaining.

233
00:28:25,320 --> 00:28:34,560
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.

234
00:28:34,560 --> 00:28:39,060
You just need to separate look to find the treasures in the city.

235
00:28:39,060 --> 00:28:46,170
So as a shape constraint here, change is totally the nature of the active learning problem.

236
00:28:46,170 --> 00:28:58,020
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.

237
00:28:58,020 --> 00:29:07,640
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,

238
00:29:07,640 --> 00:29:11,490
so with noise, instead of sampling what time one time each each other,

239
00:29:11,490 --> 00:29:20,490
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.

240
00:29:20,490 --> 00:29:25,200
So if instead of sampling one tiny chanoyu centrality of Aulaqi timer,

241
00:29:25,200 --> 00:29:32,970
this would correspond in a sense to the uniform sampling from the beginning and now you have lockyear instead of.

242
00:29:32,970 --> 00:29:37,560
So instead of adding square with colloquial capability, you would get screwed.

243
00:29:37,560 --> 00:29:42,170
Look, look, look what. If you just do that.

244
00:29:42,170 --> 00:29:53,210
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.

245
00:29:53,210 --> 00:30:01,630
And so morally, instead of being each, you would be like a logarithmic equivalent of H, which would be bonded like.

246
00:30:01,630 --> 00:30:07,090
So this one is maybe a little bit less easy to pass, but for the first one,

247
00:30:07,090 --> 00:30:13,600
the idea is really that instead of having gay arms now because of the binary search, we just need to sample lock arms.

248
00:30:13,600 --> 00:30:25,960
And so the key becomes looking. So that's Suzuki, it's when when first Niva, but important is setting.

249
00:30:25,960 --> 00:30:36,470
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,

250
00:30:36,470 --> 00:30:43,270
with it coming from a financial equality applied in the planning setting, is the following lower bond?

251
00:30:43,270 --> 00:30:51,940
Well, you prove that the simple regret's is bonded in the worst case based, quote, lucht you are looking at.

252
00:30:51,940 --> 00:31:00,810
So if you compare that with the amount of square root, local level of kludgy, we lose a lot.

253
00:31:00,810 --> 00:31:10,710
But it was always we are not. But then there are things that you can prove is that.

254
00:31:10,710 --> 00:31:17,160
If you look at the worst case, militant problem, then lower bombs on the possibility of Iraq is exponential,

255
00:31:17,160 --> 00:31:28,170
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,

256
00:31:28,170 --> 00:31:32,790
but you don't know it, Sinem. So we don't know if it's up or down the threshold.

257
00:31:32,790 --> 00:31:35,830
So if you know which is closer then you know that's a threshold.

258
00:31:35,830 --> 00:31:42,690
You just need to send pulses all the time to simply time and you are going to make little.

259
00:31:42,690 --> 00:31:52,890
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?

260
00:31:52,890 --> 00:32:01,410
Again, you lose a key, but you don't lose much. Is it clear or is it to be to be vague?

261
00:32:01,410 --> 00:32:07,110
Now, this is clear. I think so. So now let's let's continue a bit.

262
00:32:07,110 --> 00:32:12,660
And so one can say, OK, we are almost happy because we have everything up to Lockdown's.

263
00:32:12,660 --> 00:32:22,050
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.

264
00:32:22,050 --> 00:32:27,650
And one can ask oneself whether these bonds are or whether these bonds are paid.

265
00:32:27,650 --> 00:32:34,290
And in fact, solo, our moms are tight and it's possible to have algorithms which do better.

266
00:32:34,290 --> 00:32:40,470
So why is it possible? Well, because the binary search is something that is quite conservative.

267
00:32:40,470 --> 00:32:50,670
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,

268
00:32:50,670 --> 00:32:58,290
until you have a union down, then you lose them, which corresponds to a union down on your luck decisions.

269
00:32:58,290 --> 00:33:05,440
Now, imagine that you have a binary search where you don't seem to be correct at every decision.

270
00:33:05,440 --> 00:33:11,740
So you don't have to be correct that every decision you continue in your binary search, you are going to be wrong.

271
00:33:11,740 --> 00:33:17,410
But at the same time, all your decisions are not going to be incorrect together.

272
00:33:17,410 --> 00:33:26,470
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,

273
00:33:26,470 --> 00:33:35,070
if you look at the three points, is it isn't is completely and completely without a threshold.

274
00:33:35,070 --> 00:33:44,370
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.

275
00:33:44,370 --> 00:33:53,920
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.

276
00:33:53,920 --> 00:34:01,740
And then you can bolt or two corrections. So even an inconsistency detected at some point you can backtrack.

277
00:34:01,740 --> 00:34:07,530
So what is possible to do is to construct an algorithm is that instead of doing a naive binary search

278
00:34:07,530 --> 00:34:15,150
that as to be good at every step does a slightly longer binary search that he's allowed to backtrack.

279
00:34:15,150 --> 00:34:17,170
And intuitively, this would work.

280
00:34:17,170 --> 00:34:26,870
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.

281
00:34:26,870 --> 00:34:33,950
Then you can have a bond, which is not a union bond, so you don't lose this gogolewski,

282
00:34:33,950 --> 00:34:41,180
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.

283
00:34:41,180 --> 00:34:46,310
The idea that each time that you make a good decision, you correct a bad decision.

284
00:34:46,310 --> 00:34:56,660
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.

285
00:34:56,660 --> 00:35:04,160
So this new argument for describing it, it's behaving better than the naive one in the minimal sense.

286
00:35:04,160 --> 00:35:10,820
But do you know whether I said uniformly better or always better are often better?

287
00:35:10,820 --> 00:35:19,820
Yes. So I will come to that because we will also characterise this one so as the probability of [INAUDIBLE].

288
00:35:19,820 --> 00:35:27,370
And this one is not so in Zawadski. This one is really. So if you think about this, go up on them.

289
00:35:27,370 --> 00:35:31,670
So about this bond, because we will prove that an algorithm manages to achieve that.

290
00:35:31,670 --> 00:35:35,720
What it tells you is that you show an algorithm that achieves that.

291
00:35:35,720 --> 00:35:45,250
What it tells you is that if you go to sleep, even if you knew from the beginning of where the threshold was.

292
00:35:45,250 --> 00:35:52,120
Which would you know, whether you are closer to the threshold is down there and if you spend all your budget on this,

293
00:35:52,120 --> 00:35:58,800
then you cannot do better than that. And what we are going to do is to construct an algorithm that actually does that,

294
00:35:58,800 --> 00:36:08,100
so that manages to adapt to the problem in a sense, and that will also be like many experts, but that also adapting.

295
00:36:08,100 --> 00:36:13,170
So it's not totally adapted in the sense that the Konstantin's the exponential shear is not

296
00:36:13,170 --> 00:36:19,650
tied with a deficit in the sense that if the problem as a gap as well as a smaller step,

297
00:36:19,650 --> 00:36:26,380
which is of a given order to find it, to adapt to it, and you allocate most of the budget to get.

298
00:36:26,380 --> 00:36:32,090
Who is not so perfectly adaptive, but it adapts quite a bit to the problem.

299
00:36:32,090 --> 00:36:41,870
Yeah, but, uh, yeah, in fact, uh, in fact, we have to vulgarism then thinking we don't have one that does,

300
00:36:41,870 --> 00:36:49,790
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.

301
00:36:49,790 --> 00:37:00,260
But it's more complicated. So, yeah, no, it's not the same, which does both, but I think like one of them, Candlebox.

302
00:37:00,260 --> 00:37:07,200
But both of them were cohabitate with bad and good decisions, which are outwitting each other.

303
00:37:07,200 --> 00:37:14,590
In fact. So just to explain a bit more, the algorithm, in fact, it works on a tree,

304
00:37:14,590 --> 00:37:21,130
so you have a tree on your set of ups and each node of the tree corresponds to a segment of arms.

305
00:37:21,130 --> 00:37:28,570
So here, for instance, the first note correspond to all the arms. And this one would correspond to one, two arms, one, two, three.

306
00:37:28,570 --> 00:37:38,250
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.

307
00:37:38,250 --> 00:37:49,740
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.

308
00:37:49,740 --> 00:37:55,830
So just to explain ours like ours is Wuxia at each time you assemble to allocate time,

309
00:37:55,830 --> 00:38:00,420
each time there's small consistency so that you'll have a longer binary search.

310
00:38:00,420 --> 00:38:10,260
This constant is much smaller than one, but it's a unique circumstance. And what happens is that then at each time you control,

311
00:38:10,260 --> 00:38:20,870
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,

312
00:38:20,870 --> 00:38:27,940
quote, looking obviously with a given probability that he's fixed.

313
00:38:27,940 --> 00:38:35,410
So and then, like, you know, sense to throw a coin and to coin is very biased toward a good,

314
00:38:35,410 --> 00:38:39,370
good outcome, but you have a small chance of having a bad outcome.

315
00:38:39,370 --> 00:38:46,600
And if the outcome is good, then it means that you are going to do a step in the right direction of the tree.

316
00:38:46,600 --> 00:38:50,890
And if the outcome is bad, then you do a step in the wrong direction of the tree.

317
00:38:50,890 --> 00:38:54,580
And so imagine, for instance, that you do a step or it's a bad decision of the tree.

318
00:38:54,580 --> 00:38:59,990
So the threshold is severe, but you do step into the wrong decision.

319
00:38:59,990 --> 00:39:08,810
What happens is that when you do a good decision, you realise that the segment is actually completely above threshold and you go back.

320
00:39:08,810 --> 00:39:13,440
And so each bad decision is outweighed by a good decision and.

321
00:39:13,440 --> 00:39:21,480
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.

322
00:39:21,480 --> 00:39:29,820
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,

323
00:39:29,820 --> 00:39:33,510
and so at the end, you can prove that there is an algorithm that satisfies.

324
00:39:33,510 --> 00:39:41,880
Yes, in the worst case and there is another algorithm that is more simple, that satisfies something more local.

325
00:39:41,880 --> 00:39:49,260
And in fact, we prove we we don't prove it. But we think that the algorithms that I just described those both.

326
00:39:49,260 --> 00:39:51,150
But for the local version,

327
00:39:51,150 --> 00:40:03,620
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.

328
00:40:03,620 --> 00:40:12,440
So, yeah, so in the end, in fact, we have a bounce both for those regrets and the possibility of your father's problem,

329
00:40:12,440 --> 00:40:19,620
which are which are optimal in the sense that that they described.

330
00:40:19,620 --> 00:40:28,200
So as you can see, you gain quite a lot when you go from instructor to Manhattan because of these structural constraints,

331
00:40:28,200 --> 00:40:32,980
which is very, very helpful in active learning, much more than in.

332
00:40:32,980 --> 00:40:44,720
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.

333
00:40:44,720 --> 00:40:50,510
It's too tight or I can go quickly on concave, as you prefer.

334
00:40:50,510 --> 00:41:02,330
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.

335
00:41:02,330 --> 00:41:07,820
Now, let's go ahead with concave, if that's OK, with pleasure, so I can present,

336
00:41:07,820 --> 00:41:15,420
so I can try to be a little bit quicker for because the ideas are, in fact, very, uh, related to Manhattan.

337
00:41:15,420 --> 00:41:21,860
But there is a big twist. But, uh, but there are many things that come from that.

338
00:41:21,860 --> 00:41:31,180
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.

339
00:41:31,180 --> 00:41:41,650
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.

340
00:41:41,650 --> 00:41:51,790
But why? You have some literature which is related to in particular, you're related to zeros are there are no easy convex optimisation.

341
00:41:51,790 --> 00:41:58,110
So the aim is not to find a level set, but to find the maximum.

342
00:41:58,110 --> 00:42:06,030
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,

343
00:42:06,030 --> 00:42:12,870
but nevertheless, there are some ideas that can be taken from the studio and adapt to this problem.

344
00:42:12,870 --> 00:42:13,800
And in particular,

345
00:42:13,800 --> 00:42:23,700
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,

346
00:42:23,700 --> 00:42:28,020
it's like first increasing and then decreasing like this.

347
00:42:28,020 --> 00:42:36,390
And you have a big plateau into because it's concave. And so what you can do is that you can sample four points.

348
00:42:36,390 --> 00:42:38,970
And since it can give you recover,

349
00:42:38,970 --> 00:42:49,910
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.

350
00:42:49,910 --> 00:42:56,570
So you'll be able to just sell them and you will have an active set here that you said you.

351
00:42:56,570 --> 00:43:03,320
So I'm forgetting for a moment about the right side on because it's the same on the left and on the right,

352
00:43:03,320 --> 00:43:08,660
but then if you go on the left side, you can do the same. So you do take four points.

353
00:43:08,660 --> 00:43:18,390
You observe the function in these four points and you can discard, again, one part of the space, which is clearly above threshold.

354
00:43:18,390 --> 00:43:23,460
And you continue like this and you can always discard one third of the space,

355
00:43:23,460 --> 00:43:28,470
so it's something that is done in some people and zeroes are the optimisation,

356
00:43:28,470 --> 00:43:34,500
which is very related to binary search, just adapted to the to the Concave said.

357
00:43:34,500 --> 00:43:35,370
So if you do like that,

358
00:43:35,370 --> 00:43:46,000
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

359
00:43:46,000 --> 00:43:59,970
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.

360
00:43:59,970 --> 00:44:05,800
I remind you that the 1999 research was Ritchies, quote, lucky, lucky, lucky, divided by so.

361
00:44:05,800 --> 00:44:10,650
So we are going to look like because it's a nice version, which I'm presenting again.

362
00:44:10,650 --> 00:44:20,400
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,

363
00:44:20,400 --> 00:44:26,240
so you will get the same bond almost for free with a naive algorithm.

364
00:44:26,240 --> 00:44:33,390
And, of course, doing the same trick, one can think of getting rid of the log and of the larger.

365
00:44:33,390 --> 00:44:42,010
So one could already think of that and to get a square root Lacayo Gadge in the concave section.

366
00:44:42,010 --> 00:44:47,560
So now let's see if this is tight, because concave is something which is quite restricted.

367
00:44:47,560 --> 00:44:54,210
It's much more than the Manhattan. Um.

368
00:44:54,210 --> 00:45:01,960
Yeah, sorry, this is what I just said. So if you if you apply to correction, you can, like, remove the log log.

369
00:45:01,960 --> 00:45:12,540
So go from square root, lucky, lucky, lucky to squirrelled location and also keep searching if you think of the correct.

370
00:45:12,540 --> 00:45:15,560
OK, so now let's look at lower bonds.

371
00:45:15,560 --> 00:45:27,770
And in fact, it doesn't look too good because what we ever used was, quote, lobola capability instead of Squirtle accurate.

372
00:45:27,770 --> 00:45:31,250
So what you can prove is that it's possible to construct a set of problems.

373
00:45:31,250 --> 00:45:40,370
So that's the simple regret's and far, far below our bonds, which is more local.

374
00:45:40,370 --> 00:45:44,210
You have against exponential minus koening that square.

375
00:45:44,210 --> 00:45:48,470
So this is when it's clear that it's not really possible to improve it in the concave

376
00:45:48,470 --> 00:45:55,020
case because it tells you that even if you know so I'm closer to the threshold.

377
00:45:55,020 --> 00:46:01,010
You cannot do better than allocating all your budget to it and then you pay that off.

378
00:46:01,010 --> 00:46:04,850
So here you don't have much to win with respect to the Manhattan.

379
00:46:04,850 --> 00:46:15,470
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.

380
00:46:15,470 --> 00:46:26,280
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.

381
00:46:26,280 --> 00:46:28,940
So why instead of looking.

382
00:46:28,940 --> 00:46:38,150
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,

383
00:46:38,150 --> 00:46:43,910
which is in fact M'Naghten and which is like this, which is the first one, then a second one,

384
00:46:43,910 --> 00:46:49,830
then the first one and then another one, etc. So we can have functions like this.

385
00:46:49,830 --> 00:47:01,670
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.

386
00:47:01,670 --> 00:47:12,700
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.

387
00:47:12,700 --> 00:47:20,840
So if you make a mistake, uh, here on the threshold, if it's not exponential space, it's not a big enough mistake.

388
00:47:20,840 --> 00:47:27,240
So you can just in fact, if you can just pack your space with Lakki function.

389
00:47:27,240 --> 00:47:32,250
Instead of key functions, as you can do in one of the.

390
00:47:32,250 --> 00:47:36,830
So why is it interesting, your father on the.

391
00:47:36,830 --> 00:47:44,450
Well. Because, in fact, the idea is to use this scale in the government, so we have to do our bombs,

392
00:47:44,450 --> 00:47:49,550
but it's something that is also relevant for the lower part of the problem.

393
00:47:49,550 --> 00:47:56,000
So the idea will be to take some algorithm and to use it on a large scale instead of using it

394
00:47:56,000 --> 00:48:04,700
on the on the scale of chaos and then to do a corrected binary search on the large scale.

395
00:48:04,700 --> 00:48:11,040
So I will explain what I mean by that a little bit later. And now the problem is that we can do that.

396
00:48:11,040 --> 00:48:17,870
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.

397
00:48:17,870 --> 00:48:22,220
And so doing looks good, approximation is sufficient, is not sufficient.

398
00:48:22,220 --> 00:48:31,210
And what we have to do on top of that is to do, uh, also a local approximation.

399
00:48:31,210 --> 00:48:37,060
So we have to have a multiskilled sorry approximations when we try to explain this,

400
00:48:37,060 --> 00:48:47,170
and so the algorithm that will result from that perform iterative, connected by the research on the log scale and refines gradually delivers.

401
00:48:47,170 --> 00:48:55,060
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,

402
00:48:55,060 --> 00:49:06,300
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,

403
00:49:06,300 --> 00:49:13,450
etc. So we would take on the log scale and that you do a binary search on the underdog scale.

404
00:49:13,450 --> 00:49:17,110
And because the function is convex, it's concave.

405
00:49:17,110 --> 00:49:23,640
Sorry, the threshold is going to still be here like between two of the arms like this.

406
00:49:23,640 --> 00:49:35,580
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.

407
00:49:35,580 --> 00:49:36,840
You should do that.

408
00:49:36,840 --> 00:49:45,420
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.

409
00:49:45,420 --> 00:50:01,500
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.

410
00:50:01,500 --> 00:50:08,430
Yeah, so you and then you you you you should do that, like just by doing corrected by research,

411
00:50:08,430 --> 00:50:20,140
unlucky, you are already zooming and reducing the eho by a factor of.

412
00:50:20,140 --> 00:50:26,020
So like that, you can refine level assets and you do that Stazi.

413
00:50:26,020 --> 00:50:35,960
So it's the last level that will then have a basically and I was lucky because you just have lockdown's.

414
00:50:35,960 --> 00:50:40,490
So this is OK, this is a little bit difficult to explain, the algorithm is quite complicated,

415
00:50:40,490 --> 00:50:50,430
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.

416
00:50:50,430 --> 00:50:55,030
And if you do that, you get these crowd WQ.

417
00:50:55,030 --> 00:51:00,790
So it's quite interesting because really in the concave setting, you gain technology with respect to the militants setting,

418
00:51:00,790 --> 00:51:05,530
so that's quite so quite nice and the logarithm of the possibility of it all remains the same.

419
00:51:05,530 --> 00:51:10,810
But as I mentioned, it's really already something which is a serious one.

420
00:51:10,810 --> 00:51:19,710
So, yeah. OK, so this is just a comparison of just researching the social structure that you take,

421
00:51:19,710 --> 00:51:27,180
look into it and say you have lucky and it's a concave setting and waiting to unstructured setting.

422
00:51:27,180 --> 00:51:36,660
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.

423
00:51:36,660 --> 00:51:41,130
So I think I will stop. I will stop there. I want presents a unique model.

424
00:51:41,130 --> 00:51:48,060
But if you want to try to guess for the union model, whether it's closer to a concave or not,

425
00:51:48,060 --> 00:51:56,200
one structure in it's feel free and I can tell you then what we can say about the unique modalities.

426
00:51:56,200 --> 00:52:01,050
So thank you very much and sorry to end was a little bit a little bit messy.

427
00:52:01,050 --> 00:52:09,630
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.

428
00:52:09,630 --> 00:52:17,140
So please just amuse yourself and go ahead. Uh.

429
00:52:17,140 --> 00:52:22,680
All right, thanks very much for that. That was really interesting and very lovely.

430
00:52:22,680 --> 00:52:33,400
So my question is just on the lost functions you chose and I was wondering if one was to,

431
00:52:33,400 --> 00:52:41,680
for example, for four, if you were if you were only worried about the negative ones.

432
00:52:41,680 --> 00:52:52,400
So not both positive and negative, would that be would that be a kind of trivial change or would that be?

433
00:52:52,400 --> 00:52:56,840
I mean, it seems like it was the sort of thing someone might ask,

434
00:52:56,840 --> 00:53:05,970
so if you just care about your which you make when you classify a name which is below threshold at the bottom.

435
00:53:05,970 --> 00:53:12,550
Yeah. But in this case, you could say your arms are below threshold.

436
00:53:12,550 --> 00:53:18,880
And then you would make zero for the hour then, you know, I mean.

437
00:53:18,880 --> 00:53:28,230
I mean. So.

438
00:53:28,230 --> 00:53:35,270
I guess I was thinking of only only.

439
00:53:35,270 --> 00:53:44,660
Counting the absolute value of new music was negative, I see, so you're saying so how would you formulate that?

440
00:53:44,660 --> 00:53:52,910
I mean, I want to I want to identify any negative.

441
00:53:52,910 --> 00:54:03,170
So, yeah, so I wouldn't know I would try to formulate that, because if you don't pay for some type, your.

442
00:54:03,170 --> 00:54:11,510
Yeah, then, you know, since, um, uh, you just say they're all negative, uh.

443
00:54:11,510 --> 00:54:20,520
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.

444
00:54:20,520 --> 00:54:31,380
So like, um. If you could maybe cast it like that and to have like a very unbalanced price on both.

445
00:54:31,380 --> 00:54:42,970
I was just thinking that perhaps in some some kind of drug studies and so on, you would certainly pay a lot unsymmetrical prices.

446
00:54:42,970 --> 00:54:50,110
It would make a lot of sense actually like to them to have like a different price you have.

447
00:54:50,110 --> 00:54:54,880
Yeah, we don't look too much into that. But that would that would definitely make a lot of sense.

448
00:54:54,880 --> 00:55:05,470
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?

449
00:55:05,470 --> 00:55:11,120
Yeah. So it's. It's rather.

450
00:55:11,120 --> 00:55:21,790
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,

451
00:55:21,790 --> 00:55:24,070
to multiplicative constant,

452
00:55:24,070 --> 00:55:32,120
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.

453
00:55:32,120 --> 00:55:36,730
Oh that's great things. I'm just curious.

454
00:55:36,730 --> 00:55:46,670
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,

455
00:55:46,670 --> 00:55:51,560
like, higher dimensional shape constraints, so if your arms are like, you know, so,

456
00:55:51,560 --> 00:55:57,200
for example, you've got two drugs and you're interested in the dosage of of two drugs,

457
00:55:57,200 --> 00:56:03,860
how these types of results would would would generalised, uh, to meet certain constraints.

458
00:56:03,860 --> 00:56:08,090
Yeah. So that's, uh, that's actually a very, very interesting question.

459
00:56:08,090 --> 00:56:14,690
And we have been thinking a bit about it, but it's not so easy to to pose a problem.

460
00:56:14,690 --> 00:56:23,480
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.

461
00:56:23,480 --> 00:56:28,550
So you go from data to Lakki when it comes to unstructured to.

462
00:56:28,550 --> 00:56:39,650
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,

463
00:56:39,650 --> 00:56:44,510
you would get here like a square with K one K two times like one kid,

464
00:56:44,510 --> 00:56:55,650
and you would get probably something which is rather the Makowski one and two times log of the other.

465
00:56:55,650 --> 00:57:02,340
So the beginning would be less drastic, but it's possible to do it, and in fact,

466
00:57:02,340 --> 00:57:06,990
you could gain one dimension when you go into the argument that what would happen.

467
00:57:06,990 --> 00:57:13,620
But it's not so easy to to study. And it's very interesting. OK, thank you.

468
00:57:13,620 --> 00:57:14,997
I'm going to just stop recording.