Renegar's Condition Number and Compressed Sensing Performance
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Aspremont, Alexandre d'
Renegar's condition number is a data-driven computational complexity measure for convex programs, generalizing classical condition numbers in linear systems. We provide evidence that for a broad class of compressed sensing problems, the worst case value of this algorithmic complexity measure taken over all signals matches the restricted eigenvalue of the observation matrix, which controls compressed sensing performance. This means that, in these problems, a single parameter directly controls computational complexity and recovery performance. Joint work with Vincent Roulet and Nicolas Boumal.
 Thank you and I'm very grateful for the invitation and for the opportunity to talk during the CESTA slot or Wi-Fi, whatever. And so I should start by saying that this is joint work with a number of people, including Cris Abel Guzman, Vincent Roulet who is in the room and he's going to be lasered in a second if I can find him. Where are you? Well, here. And Nicolas Boumal who's now at Princeton and Martin Yaggy who's now at EPFL. So the title changed but the content remained the same. And the content is a lot simpler than what the title sort of influenced. So the idea in general is that when you get a complexity bound it looks like this, roughly speaking. You get a certain dependence on the problem dimension and a certain dependence on the target precision. So that's a generic complex optimization problem. In this case you're lucky because the exponent is not too high, etc. But this is what it roughly looks like. If you're lucky it looks a little bit like this, a little bit more like this. And well now you have a leapschitz constant and at least you have some dependence on the problem structure. But clearly one thing important is missing from this complexity bound and this is the data. The complexity bound you get on the complex optimization problem you're trying to solve only very, very loosely depends on the problem data. And if you want to study computational trade-offs or computational complexity versus statistical performance trade-offs, in general the fact that you're bound on the complexity of the problem you're studying is so coarse and so roughly dependent on the structure of your data is a big issue. This is of course an upper bound to begin with so it's hard to make comparisons between the complexity of value optimization problems using only upper bounds. It's even worse because this upper bounds is very loose and in particular only loosely dependent on the problem data. And so the general idea behind the two quick results I'm going to present today is to get closer to data-driven complexity bounds. And hopefully get closer to something that would be tight data-driven complexity bounds on optimization problems. If you want to start to make comparisons between the complexity of values optimization problems you need something more than upper bounds. You need tight bounds on the complexity. And if you want to compare problems based on their structure you need bounds that depend on the problem structure and on the data in a meaningful way. And so the material I'm going to present today is an effort in that direction. Of course it's a broad topic and the two results I'm going to present today are just very specialized results in this direction but that's the general idea. You want data-driven complexity bounds that hopefully are tight and allow you to quantify in a much finer way what happens on the computational side when you're considering and comparing optimization problems coming from statistics for example. So again if you're studying the complexity versus statistical performance trade-off well it helps if you have a fine description of the complexity aspect. And at this point we don't. So you can talk a lot about this trade-off but at least on the complexity side are measures of problem complexity and the way they relate to the problem structure are really approximate now and pretty far from the truth. And they suffer from a certain number of clear deficiencies and among these deficiencies is affine invariance. So it makes sense that if you're going to describe the complexity of a problem the bound you use to describe this complexity should not be affected by elementary transformations of your problem. And in particular if you make a simple affine change of coordinates the complexity of your problem should not change. Just a renormalization should not have any impact on the complexity of an optimization problem. Yes. Well. Machine learning is. It's okay so I guess you're implementing this on machines so machines are finite precision so obviously there are limits to what I'm saying. But on the other hand it's okay I see what you mean. Good point. It's a matter of robustness. If your problem can be fixed by a simple affine change of coordinates perhaps your method should be smart enough to recognize it. So it's setting the bar a bit high I guess maybe but at least as far as I'm concerned maybe your algorithm should be robust enough to recognize that the problem you're facing numerically is simple conditioning. And the algorithm itself should be robust to these conditioning issues. The condition number is not affine invariant. The condition number is not affine invariant but I mean conditioning in a more abstract sense. No but that's precisely the point so it's a conditioning issue you can fix it by just changing coordinates. But what I mean by affine invariance is you make an affine change of coordinates. You don't expect your problem to change in nature. In particular you haven't done anything to your data. So if you're looking at statistics you're not manufacturing data. It's a simple preprocessing step you could do etc. So this is something that should be within reach basically. But I agree that it's partially subjective. There's no imperative reason for this to be true. But if it can't be true we all agree it's a good thing. Is that okay? Feel free to question my motivations even more deeply. So affine invariance is a good thing and we want more good things in optimization. That's sort of the essence of the domain. And so that's the first point. So I'm going to start by talking about affine invariance. Can we get it? And if yes what does it say? And separate but equal and important in importance renegars condition number and compressed sensing. So this would be again in a slightly different direction but in the same spirit we see that in certain cases like compressed sensing problems the same quantity drives both computational complexity and statistical performance. So in this particular case we are lucky because we have a single metric for both computational complexity and sparse recovery thresholds. So in that case the problem is solved. In general of course it's still open. So affine invariance we're going to consider a very simple generic optimization problem. You minimize a convex function f over a simple compact convex set q. And you're going to assume here that f is convex and smooth and I'm going to make all these precise later and that q is compact convex and simple and again simple will be made precise later. So that's the general problem we're interested in. And if the set over which we optimize is not too big we have a complete theory for this problem. So we have Newton's method and Newton's method at each iteration does a simple thing. It takes a step in the direction given by the gradient but it normalizes this step by the fashion. And if you assume that the function is self-concordant and that the set q as a self-concordant barrier you have a very explicit estimate on the complexity of minimizing a convex self-concordant function using Newton's method. If you haven't seen it before the self-concordant assumption feels a bit bizarre to say the least but if you think about it for a second you see that it basically does two things at the same time. If you read it in one direction it's essentially a lower bound on the second derivative of the function and so it's a way of writing strong convexity while maintaining affine invariance in the condition. And if you read it in the other direction then it becomes an upper bound on the absolute value of the third derivative of the function and that's a way of saying that the second derivative will not change too much when you move from one point to another. And optimization in general is just about minimizing quadratic functions in the end and that's exactly what Newton's method does. And so it's kind of intuitive why this is the right set of assumptions. You're using a quadratic model to minimize your function and you want this quadratic model to remain true even outside your current point and that's why you bound, you need to bound the third derivative. So this really looks bizarre but in the end it's simply a way of combining both an upper bound on the third derivative and a lower bound on the second derivative. And to do so in a way that makes the condition invariant with respect to an affine change of coordinates in the point x. And this is why you have this exponent 1.5 here. So everything, it's bizarre but everything has a meaning. And once you make that assumption you use focus on solving a bioproblem of course, you need the bi itself to be self-concordant but basically then you can bound the number of iterations required to get a solution with precision epsilon by some coefficient times the difference between the value of the barrier at the initial point and its optimum plus log of log of 1 over epsilon iterations. And for all reasonable values of epsilon this is basically 3. And this term here depends only on parameters that you set for the line search in the Newton's step. So you decide what the value of this parameter is. This term is. And alpha is typically something like 0.2 and beta is 0.5. So this is a fixed quantity. So to summarize, the complexity of Newton's method is basically 3. So the number of iterations you need to reach essentially any precision is bounded by something like 375 times h of x0 minus h star plus 6. And that's clean enough for me. I don't know about you but it's empirically valid up to a factor let's say 300. It's a constant. And what's striking is what is not inside this bound. So in particular it's independent from the dimension n which is pretty spectacular. And again this is empirically valid. And it's also a fine invariant of course because it only depends on the values of the function. Okay? Well, the only thing missing from this bound is the cost of solving the Newton's system, the KKT system, but that's just linear algebra. So this is something you can measure very precisely from your data and the structure of your problem. Okay? And it's just linear algebra. Conditioning plus problem structures, sparsity, block structure, etc. But you can get a very fine estimate of the complexity of solving the KKT system using simple linear algebra procedures. Okay? But doesn't this depend on some conditioning? What do you mean? This here? The efficiency of solving the system? It does if you look at things in a slightly more precise way and I will at the end of the talk. But overall the number of iterations varies between 15 and 20. And so the number of iterations will be the cost of every iteration. Clearly, but at least you can read it directly from the data. So you can write the cost of solving the Newton's step as a function of the problem structure, dimension, its block structure, things like that, and the data conditioning. So you have a completely explicit data-driven description of the complexity of your problem. Okay? And this is what you're looking for. It's affine invariant and it fits the structure of the data very well. And in particular, if you want to compare two problems, you just compare their complexity estimate, okay, coming from the linear algebra side. So at least you have an upper bound that's useful for making comparisons between the complexity of various problems, okay, which is something you don't have for first order methods. That's my next point, basically. Yes? I've got a question. So if I have a value h or h divided by 2, it should be the same. And y is not the same. What am I missing? Good point. There should be probably a... Scale in the... Yeah, scale somewhere, but it should make a difference. No, I don't remember exactly, but that's an issue. I know it's an issue. I can't tell you why. Okay. So this is the picture for Newton's method and essentially the topic is completely closed, okay? So we know exactly how to bound the number of iterations the method goes through and we know exactly how to measure the cost of these iterations. So you have a problem and you can describe very precisely how much it's going to cost to solve it numerically using Newton's method. Meaning when you have two problems, you know which one is going to be more expensive than the other, okay? So that's the beautiful world of small scale problems. Yeah, so in addition to that, I've mentioned it several times, but Newton's method is affine invariant, meaning if you do an affine change of coordinates to your problem, the iterates of Newton's method applied to the transform problem will simply be the affine transformations of the iterates of Newton's method on the original problem formulation, meaning that in particular the number of iterations doesn't change and the complexity bound doesn't change either. And so you have an affine invariant complexity bound on an affine invariant procedure. And so again, this is a very important feature. So the problem is that at a certain point, your problem becomes too big and you can't even solve a single instance of the KKT system, let alone run several iterations of Newton's method, okay? And so beyond a certain scale, second order information is out of reach. You cannot form the Hessian or solve the KKT system. And second order information is what makes Newton's method affine invariant, okay? So what people do is they just drop second order of information and use gradients instead, first order information. But the problem is now, can we get similarly clean complexity bounds for first order methods that are tight enough to say something truly meaningful about the complexity of the optimization problems and satisfy some of these invariant properties? Okay, and the answer is yes in certain cases. So just to go back to an algorithm that is a big favorite among some members of the audience. If you look at Frank Vol, for example, which is also known as the conditional gradient method or the Fedorov method, at each iteration you solve an affine minimization problem whose vector is given by the gradient. And you get an extreme point of the feasible set, you take convex combinations of these extreme points and magically you converge to the optimum. And somewhat more magically, you can show that the complexity of the Frank Vol algorithm is bounded by four times Cf divided by the target epsilon, the target precision epsilon, where Cf is a bound on the curvature of your function, okay? And so the good news about Cf first, this complexity estimate is fairly simple in itself, but the additional piece of good news about this bound is that Cf is invariant with respect to an affine change of coordinates in your problem, okay? So that's excellent news. The only issue with this is that in many cases, the dependence in the target precision epsilon is suboptimal, okay? In particular, when f has a Lipschitz continuous gradient, then the lower bound can be as low as 1 over a square root of epsilon, okay? So your bound is nice, but it's really far from being tight. And it's kind of useless if at some point you want, for example, to compare the complexity of several problems, yes? So why is it actually a fine invariant? I mean, if I stretch or scale the function by some... Just plug it this time here, if you plug it in here, do you get a fine invariance? This is the first order of expansion, so it is invariant. If the first we use gradients, makes it independent on the product, but as soon as it's a differential, yeah, get a fine invariant. But I have another question. So when you say tightness of the bound, you mean tightness of the bound for the algorithm or for the problem? So tightness is you make a certain number, so you have a certain number of facts about your problem, smoothness of the function, regularity of the set, et cetera. So you have a black box, and then you have a few... You open a little bit the black box and you know a few things about your problem, and suddenly... So if you only have curvature, then things are a bit different. But if you know, for example, that f has a Lipschitz gradient, then you can do better in terms of epsilon. You need to know more about q2. What I mean is that if this was universally optimal and a fine invariant, we wouldn't have a problem. But isn't this optimal given the different order of f and the support function of q? Yes, but what I mean is that in certain instances, you have more than that. And in that case, then you have to use another algorithm. If you want to be as close as possible to the bound, and this other method will not have an affine invariant bound. That's what I mean. So, of course, this might be optimal in certain scenarios, but when you leave these scenarios, then you're in trouble because suddenly you lose your method. The best option for solving your problem doesn't have a clean complexity bound. That's what I mean. Okay? Other questions? Okay, so at least we know it's possible for a first order method to have an affine invariant bound. So it's not the fact that we are losing second order information that makes it impossible to produce invariant bounds. Okay? It's really about algorithm design and the way we bound the complexity of the method. Okay? So the sort of classical method that reaches lower complexity bounds for smooth optimization, for example, is the Nesterov method of 1983. Okay? The original paper was in a nucleon setting, but in the general case, the algorithm requires you to do two things. Okay? So it's fully specified up to a certain number of choices. Okay? So in particular, when you write down Nesterov's method for a specific optimization problem, the general algorithm, not the one in 1983, you have to choose a norm. Okay? And that norm is important because when you say that the gradient has a lip sheet's continuous, sorry, that the gradient is lip sheets continuous, with constant L with respect to a norm, your choice of norm will affect L. Okay? And if you change L, then you change your complexity bound. So you choose a norm that has an impact on complexity. And once you've chosen a norm, you also need to choose a pox function for the set Q. And you want that pox function to be strongly convex with respect to your choice of norm. Okay? And again, the strong convexity parameter will show up in the complexity bound. So how you choose the pox will have an impact on the problem complexity. Okay? And then once you've done that, the algorithm basically computes a gradient. Those two rough projection steps averages the result and iterates. Okay? And it will produce an epsilon solution in at most a square root of 8L dx star divided by epsilon sigma. And now the dependence in epsilon is optimal because it's in one over a square root of epsilon. However, the constant L and sigma used in the description of that bound are not invariant with respect to an affine change of coordinates. Okay? And so you do a simple transformation of your problem. You scale the parameters and suddenly the complexity can vary massively. So when you say optimal here, when people say optimal here, what they really mean is optimal with respect to epsilon. In the general case, if you don't really look carefully at how you choose your norm and how you choose your pox, there's no reason for the numerator here to be optimal. And not only that, this numerator can have a very significant impact on the complexity of your problem. Okay? And we also, this numerator makes the complexity bound vary with affine changes of coordinates in the original problem. Okay? So this is something you'd like to fix. So in particular, what you want is a bound on the complexity of your problem that is not only optimal in epsilon, but also in everything else. Okay? You want a complexity bound that is optimal up to a constant factor, just like what we got for Newton's method. And the problem is that you cannot write such a bound using the quantities L and sigma, and for that matter, D of x star. Because all these quantities depend, vary with an affine change of coordinates in your problem. Okay? So we have to find something else to write this complexity bound and make it affine invariant. And we also have to check if this something else is optimal. In the sense that it matches the best possible bound on this numerator. Okay? So just to give you an example of what this choice of norm and pox function means, suppose you look at, it's an example taken from a paper by Jusid Nimeovsky-Lan and Shapiro, you have this simple matrix game problem. So it's an affine matrix game problem. And you have some smoothing to do, etc. But the details don't matter too much here. But if you pick an Euclidean setting, and in this case, a squared Euclidean pox, you can bound the number of iterations by four times the spectral norm of the matrix A divided by N plus one. If on the other hand you think a little bit more carefully and you pick the L1 norm and an un-tropic pox, and then your bound becomes square root of log N log M max coefficient, so the max norm, the max magnitude of the coefficients of the matrix A. Okay? So again, I'm using the same algorithm. I'm getting the same dependence on the number of iterations N. However, my numerator is changing very significantly. For example, when the matrix A is Bernoulli, the difference between these two terms is square root of N. Okay? So the method may be optimal in epsilon, but if you don't pay attention to your choice of norm and choice of pox, you can still be a factor square root of N from the best complexity bound possible. Okay? And that's a big deal. Okay? So there's a question of invariance. There's also a question of optimality. You want the best possible implementation of your optimal method to make it fast. Capital N is the number of iterations. It's not, so after N iterations you reach that precision. N max is the precision? No, N is the number of iterations. Oh, wait, wait, wait. No, okay, so it's whatever makes it correct. So either this should be the precision and this the number of iterations are the opposite, but not both at the same time, good point. Okay? But you see what I mean. Okay, sorry. So this should be either epsilon or N, whatever you prefer. Let's move on. And so, okay, so I hope I've convinced you that choosing the norm and choosing the pox had an impact and was an important step. And if you want things to behave properly, this should be done in a principled way. Okay? And here in some sense, looking for affine-invariant bounds, so the optimal bounds are going to be in affine-invariant. Okay? So the optimal numerator in the complexity of the problem is going to be affine-invariant because you can always do an affine transformation of your norm and renormalize your all-year-old coefficients. Okay? But that doesn't mean that if you get an affine-invariant bound, it's going to be optimal. But looking for affine-invariant is probably a good way of choosing a norm and choosing a pox. You just have to check afterwards that what you're getting is indeed optimal. Okay? And this will turn out to be the case here. So think about it for a minute. If you want your choice of norm and your choice of pox to be invariant, it cannot come from outside of your problem. Okay? If suddenly you decide that your norm has to be a clillion, there's no way, if it doesn't depend on your problem, there's no way it will vary as your problem varies. Okay? So you have to extract your norm and your pox from the problem itself. And there's a good way to start doing that in certain classical scenarios. One is when Q is a centrally symmetric convex set with non-empty interior. In that case, Q is the unit ball of a norm. And the natural norm to pick out of your optimization problem is the one corresponding to Q. Okay? The Minkowski gauge of Q. Okay? That turns out to be a norm. Good news. And what makes this a particularly good choice is that when you pick this Q norm as the underlying norm defining your algorithm, the corresponding Lipschitz constant for the gradient will be invariant with respect to an affine change of coordinates. So you do an affine change of coordinates to your problem. If you pick the new Q norm corresponding to the transforms feasible set, it will have the same Lipschitz constant. The gradient will have the same Lipschitz constant with respect to the transformed norm, then with respect to the original one. Okay? So choosing the norm corresponding to the feasible set Q makes your Lipschitz constant and the strong convexity constant of the pox invariant with respect to an affine change of coordinates. Okay? So that seems to be a good option. Now the last thing that remains to be done is to choose the pox. And for choosing the pox, I need to start with two quick definitions. Yes? If you deviate from the central symmetry... Then you have to do a little bit more. I don't have... Well, if you take the simplex, then it makes sense to symmetrize it. And then it becomes the L1 ball. Can you do anything other than the simplex, polyhedral? I wish I had a general answer in that case, but I don't at this point. So we can cover centrally symmetric and everything that looks or can be turned into a centrally symmetric set. If we presented the matrix game in which Q was more or less... Yeah, yeah, so it turns out... I'm going to handle... I'll discuss in a few slides the case where we optimize over simplex and where if you take the L1 ball, everything works out fine. Yeah, but in more interesting games, if you take the sequential games, these strategy profiles, more general polytops, which might deviate very violently from simplex, do you think convex compact... Open fun... I have no idea. I mean, I don't know. So far, only centrally symmetric is easy, but in the general case, I don't know. Yes? Can you go back one slide? The definition of smoothness is used as a square norm, can you replace it by a bryman divergence? Why do you... You can have... Simplex you can do, you just get the L1 norm. I point out that so here you... Let's hit yourself to consider like proximity of x and y for a square norm, but what if you rely yourself to consider like more general functions like bryman divergence, you could maybe do the bryman, that is centrally symmetric. Maybe, yes. It's just that I still need a norm in the end. And so the problem is how do I... Oh, or bryman... Yeah, I see what you mean. Good point, maybe. But I only have a proof of optimality at least in the... So getting a fine invariance is probably easy, but the ultimate price is to get both a fine invariance and optimality, and so far we only have optimality in the centrally symmetric cases because we only have lower bounds in the centrally symmetric case. So that's the idea. So I think it's probably doable to come up with affine invariant procedures to construct a norm when your original set is not centrally symmetric. No big deal probably, but unfortunately it's not clear that you're going to get the optimal norm corresponding to that particular set. And I don't even know at this point what to look for. So maybe bryman divergences give you additional flexibility, but I'm not sure how to use that flexibility yet. That's the idea. So at least we have a norm in the centrally symmetric case and it's pretty obvious. What's a little bit less obvious is now that we have this norm, it may not be smooth, etc. So we have to come up with a pox. And for a pox I need the definition of the pox, I need a few more definitions. So the first is the bad act measure distance between two norms or two spaces. And this is just defined as the smallest product AB such that 1 over b times the first norm is smaller than the second, which is itself smaller than a times the first norm. So this product AB measures the distortion between these two norms. And we're going to use it in our choice of the pox. And the second definition is a bit more obscure and less classical and it's called the regularity constant. And so it's taken from a paper by Yuditsky and Mirovsky on a large deviations of vector valued martingales. So it doesn't really have anything to do with the optimization context. But it's a way of measuring the regularity of a banach space. And so this regularity constant of a banach is the smallest constant delta that does two things. So first we want the pox function p squared divided by two to have a Lipschitz continuous gradient with respect to the norm p. So we look for a smooth norm p to construct our pox. We want that smooth norm to define a pox that has a Lipschitz continuous gradient with respect to itself. And we also want this norm p to be not too far away from the original norm of the banach. So this norm here may not be smooth, but we approximate it by a smooth norm p. And because the norm p is smooth, it allows us to derive a pox by just squaring it. And delta will control two things at the same time. It will control one, how far p is from the original norm, and two, how smooth the pox is. OK? So there's a trade-off between the two. There's a square root here. Here delta is a direct bound on the parameter mu. But for some happy by some happy accident, this is exactly the trade-off we need in our bound. So what you can show using this definition is that the complexity of Nesterov's method applied to this problem here can be bounded by square root of 4 times LQ times dQ, where LQ is the Lipschitz constant of the gradient of F with respect to the norm induced by Q. And dQ is the regularity constant of the Banach space, Rn, and the dual norm of the Q norm. OK? And the good news is that these two terms here, LQ and dQ, are invariant with respect to an affine change of coordinates in your problem. OK? So at least we solved our first problem. So now the numerator in this complexity estimate, we still have the optimal dependence in epsilon. And at least now we have the affine invariance of the numerator with respect to an affine change of coordinates. Yes? You have to say something very stupid. The conjugate and affine invariant that takes the infimum over all possible, like, the affine. Yeah, but you need to know that here you want to make it as constructive as possible. That's the idea. And my thing is constructive. The infimum over all affine all. So you would take the infimum over all affine change of coordinates of L times d of x star. Yeah, but how do you solve that problem? How do you compute LQ and dQ in practice? Yeah. No, but LQ, well, I'll show you in a minute. You can do it for certain specific instances. In the general case, you can't. But for certain specific instances, it's easy. So when Q is an LP ball, for example. And so coming back to the simplex example, when you're optimizing over a simplex, it makes sense to symmetrize that set into an L1 ball. And when you do that, classically, people take the L1 norm as the underlying norm and the entropy as the proxy function, because the entropy turns out to be strongly convex with respect to L1. And the bound you get is the L1 Lipschitz constant of your function times log n divided by epsilon. If you do the same thing, but using what is suggested by the previous construction, you don't select the L1 norm as the underlying norm. You take something that is the reciprocal of the two log n norm. OK? Don't ask me why. Read the paper. But basically, this suggests another way of constructing a norm based on the geometry of your problem, and you measure the Lipschitz continuity of your function with respect to that norm as well. And the complexity bound you get can be written L1 times log n divided by epsilon times 16. Yes? Maybe you have a very stupid question, but do you consider at all how epsilon is affected by these affine transformations as well? I mean, if you multiply everything by two, shouldn't you precision also? I don't think that should make a difference. Because the affine action of x, not of x. Yeah, yeah, yeah. Yes, but I mean. No, it has no impact on the objective value. Yeah. Other questions? Yes. So the bound you just put in the previous slide, that was for running the stirrup algorithm with this norm and this prox? So with the norm induced by q and the prox, which is induced by this definition of the regularity constant. P of x. P of x, exactly. P of x squared divided by two. OK? So if you can compute the q norm and you can compute P of x, then you have a specification of Nester's method, which is affine invariant. OK? And do you know that this is smaller than the nth over all affine transformations? That's the question I'm going to discuss next. So clearly affine invariance is not sufficient to give you optimality of the numerator. So in the end, what you want is a constant where, sorry, a complexity bound which is optimal up to an absolute constant. And we don't have it yet. Yes. Thank you. So there is a recent paper showing that indeed on each specific problem, the lower bound is better than this. In the sense that Nester's method is the best. Yes. I haven't read a little old paper, I haven't really digested this one yet, so I'm not sure exactly what it means. But the lower bounds are pretty tight on this thing too, so I have doubts. Yes, but so the lower bounds in this finite dimensional setting, we know that they hold only for the first iterations, right? After them, we don't know. So they may ask you the result. Tell us. If the number of iterations becomes bigger than n, then the absolute method is a better idea. So this only applies in the high dimensional regime where you're doing fewer iterations than the dimension, clearly. But this is typically the regime you care about. But I'm going to talk about other scenarios where the Nester of bounds are not optimal. So when you have, but all of this depends on getting a little bit more information on the black box. So I'll come back to that in a minute. And so before saying anything about optimality, this bound actually allows us to say something about easy and hard problems. If we read the bound and try to understand what it means from a geometrical point of view. So on easy problems, so easy problems where problems means here problems where LQ is low. Okay? Well, LQ will be low if the norm is large in directions where the gradient is large. Okay? And that means roughly then the sublevel sets of f of x and q are aligned. And what that means geometrically is that when the sublevel sets are aligned, there is a naffine change of coordinates that is going to make your problem roughly spherical. So and optimizing a spherical quadratic over a sphere is actually the simplest problem you can think of. So that sort of makes sense. Okay? And second, if you think about LP spaces, the unit balls BP have low regularity constants. Okay? And regularity constant of the L1 ball is n, that's the worst case. But remember that here, regularity is defined on the dual space. And so what that means is that problems written over unit balls BQ for Q between 1 and 2 are easier than problem written over Q for example. Just because of the way this bound works on LP balls. Okay? But the question is how good are these bounds? So okay, nice enough, they are fine in variant, but it doesn't mean that the complexity bound is tight. And in particular, the worst possible choice of product LDx star divided by sigma will also nicely be a fine in variant. Okay? But we don't expect that bound to be really good. Okay? So the inf is that fine in variant, the sup is also a fine in variant. Okay? You'd rather take the inf. So the question is can we show optimality or at least can we show optimality in certain particular cases? And it turns out that we can. And in particular, we can do so for LP balls. Okay? So now we're going to focus on a very specific class of problems where Q is the LP ball. Okay? And in that case, the bound is LP times DP divided by, square root of LP times DP divided by epsilon. And the constants DP can be computed explicitly. Okay? Same thing for the corresponding norms, they are simply LP norms. Okay? So when P is between 2 and infinity, DP is simply n to the power P minus 2 over P. And when P is between 1 and 2, you can bound DP by, pretty tightly by this quantity here. Okay? Where C is an absolute constant. And that means that we can compare this upper bound with lower bounds we have for optimizing smooth convex functions over LP balls. And for P in the range 1, 2, the lower bound we have is this one here, L divided by log n divided by epsilon. Sorry, L divided by epsilon log n. And our complexity bound is 4 times an absolute constant times L log n divided by epsilon. Yes? Can you please, the LP, the ball by essentially symmetric convex set that has a sufficiently regular boundary? That's essentially what you're doing when you define P. So the original norm is directly derived from the set and may not be smooth. And P is there to produce a smooth approximation of the set, essentially. So that's how it's constructed. It's not constructive in the sense that you don't manufacture it, but the regularity constant is computed using a smooth approximation. Okay? So it turns out that here the bound is optimal up to a polylogarithmic factor. And in the range P between 2 and infinity, the lower bound is given by this, and the upper bound, our upper bound is given by this. And this is again optimal up to a polylog when K is proportional to n. And by optimal here, I mean optimal in both epsilon and n, okay? Which is a much stronger statement than simple optimality with respect to epsilon. Is there the number of iterations? So there are annoying things that happen when you run. So you have to show optimality for the entire square of values epsilon and n, okay? And here in certain regimes, it turns out that Frank-Volff is optimal when you're not running a number of iterations that is proportional to n. Okay? But we can discuss about this offline. I don't have time to mention details here. So in particular, there are results that tell you that if you have a little bit more information on the smoothness of your space and on the regularity of your function, then in that case, you can get much more precise estimates of the complexity. And in that case, we are not yet able to produce affine invariant bounds that work similarly as the bounds I detailed before, but we're close to that, okay? But this is probably too much information for today, okay? So that's it. We have affine invariant bounds on the complexity of Nestor's method that give you at least a principled way of specifying the method, choosing a norm and choosing a prox. And these bounds are affine invariant. And in addition to that, in certain problem instances, for example, when you're optimizing over LP balls, these bounds also turn out to be optimal. And by optimal, we mean now optimal in terms of their dependence with respect to the precision epsilon and optimal with respect to the dependence on the problem parameters, okay? On the dimension, right? And so that's important. Okay, so very briefly, in the few minutes I have left, I have a few slides about another scenario where we are lucky and where the description of the problem complexity matches exactly the quantity we use to describe its statistical performance. And even though there's no immediate connection with the topic I just discussed, in the end, the objective is exactly the same, describe the complexity of an optimization problem that is in a way that is data-driven and allows you to compare the complexity of optimization problems in a meaningful way, okay? So here I have to specialize things a little bit again and focus on the conical linear systems that follow, the primal dual pair of conical linear systems, one where you try to find a vector inside a cone and the intersection of the cone and the subspace, and another where you try to find a vector y such that minus a transpose y belongs to the dual cone, okay? And it turns out we can see very fine things, we have a very refined way of characterizing the complexity of solving such an alternative conical linear system, okay? And this complexity description is written in terms of the distance to infeasibility, okay? So what is the distance to infeasibility? It's essentially the minimum perturbation you need to introduce to the matrix A to make your problem infeasible, okay? Or symmetrically, the minimum perturbation you need to make to your matrix A to make the problem feasible, right? And forget about the details here, what distance to feasibility or infeasibility means is that problems that are clearly feasible or problems that are clearly infeasible will be much easier to solve than problems that are near the region where feasibility starts to break down or infeasibility starts to break down, yes? So just a quick question, but to know if there is a spectral norm or the… You can choose, but clearly here it's the spectral norm, yeah. But yeah, you may want to pick another one, that is flexible, okay? So what Renegard's condition number does is measure this distance to feasibility or infeasibility in a scale invariant way, okay? So it takes this distance to infeasibility and normalize it by the spectral norm, right? So when rho, the distance to infeasibility is very small, then relatively speaking, this condition number is going to be really high, okay? And the idea of this condition number is to do for optimization problems or at least in this case alternative conical linear systems, what the traditional condition number does for linear systems, okay? So you compute the condition number of a linear system, it's going to tell you at the same time how hard this system is going to be… It's going to be to solve this problem numerically and how stable the solution will be. The condition number defined by Renegard is exactly the same thing for optimization problems. It tells you first how hard it's going to be to solve this optimization problem and second how stable the solution will be, okay? So this is very good if you can compute it, of course. It's a very good description of the data-driven description of the complexity of an optimization problem, okay? And so there's a lot of work on bounding the complexity of classical optimization techniques using this condition number and a more refined analysis of bias methods shows, for example, that this condition number shows up in the bound on the number of iterations of interpoint methods and that the complexity of solving the KKT system of equations actually varies with this condition number as well. So this turns out to be a good way of measuring the complexity of an optimization problem using its precise structure and the input data. But when you focus on compress sensing problems and sparse recovery problems where this should be the L1 norm here, I forgot a pretty important index, you can define in very precise terms the performance of this sparse recovery problem using conically restricted minimum singular values of the matrix A, okay? And these are just, look very much like the quotient defining the classical singular values except you restrict the vector Z to belong to a certain cone, which is the descent cone of the L1 norm. And these generalized eigenvalues allow you to bound the performance of the sparse recovery algorithm, okay? And what's pretty striking here is that we're lucky enough that these two quantities match, meaning that Ronegaard's condition number is actually equal to the corner restricted eigenvalue controlling statistical recovery performance in compress sensing problems. So the quantity that controls numerical performance on the optimization side in this case is also the quantity that controls sparse recovery performance on the statistical side, okay? And we can generalize this to much broader class of recovery problems and more details are in the paper over here, okay? And numerically this works. So this is an example where we can go as far as possible in reconciling complexity descriptions or complexity bounds with statistical performance metrics, okay? So what you see here is the classical phase transition in sparse recovery, so this is the probability of recovery using various algorithms, okay? And this is the phase transition in the condition number, okay? It's non-symmetric. It should be symmetric if we had symmetrized our definition of the condition number, but what happens on this side of the phase transition is not that interesting. So the really interesting part is the fact that this condition number decreases as you move away from the phase transition threshold here, okay? And that these two phase transitions are pretty well synchronized, okay? And indeed what you observe is that the complexity of the corresponding numerical methods has the same phase transition when you move away from around, sorry, the sparse recovery threshold, meaning that it's much harder numerically to solve sparse recovery problems when you're near the transition threshold than when you're much further away from it. And this is something that was observed empirically starting with the papers by Dono in 2008, for example. But here it's made completely explicit by this concordance between the conditioning of the optimization problem on one side and the cone-affected eigenvalues on the other. I guess this is my cue to conclude before I get electrocuted. And so just to sum up, somewhat unrelated results, but the idea here is to produce complexity estimates that are near enough to the data to say something about the complexity of one optimization problem versus another. And so in particular, we got a formulation of the optimal algorithm by Nesterov whose complexity bounds are affine invariant with respect to an affine change of coordinates and turned out to be optimal, at least on LQBos. And a completely data-driven complexity measure for sparse recovery problems, which matches exactly the quantities used to measure the statistical performance of these procedures. So there's a long list of open problems if you're interested. One is to show optimality of the product LQDQ in the general case. And as you mentioned, produce a cue norm when cue is not centrally symmetric and then not obviously a norm. We don't know how to do that. There's also a key question, which is CF is a low-bound on LQDQ. Is that low-bound tight? We'd like to know because it would solve a lot of our problems. We don't know. And Nesterov's bet is that it's not. But you can bet against him. And so again, the best known choice in non-symmetric sets, Q, I've mentioned that already. And also more important in some sense, a systematic tractable procedure for smoothing cue. And that would preserve affine invariance. And so that would allow us to produce pox functions in cases where cue is not an LP ball. We don't know how to do that yet. And that makes the algorithm unimplementable in the general case. And so that's still open at this point. Thank you. Thank you. So we have time for a few more questions. Francis? Yes? For the spectral ball, you get similar results. Yes, because then for the spectral ball, you know what the cue is. And is it tight or not? I don't remember, probably hard to say. It would be optimistic and say yes. We could be optimistic and say yes up to a polylog. And I guess that's the answer, but I'm not 100% sure. But so basically, the important part is that the reason why we're able to check optimality here is that we know exactly what the cue is for LP balls, or the LQ balls, sorry. And the same thing is true for the spectral norm and all matrix norms. So we know exactly what the cue constant is for these matrix norms. So at least we have an explicit bound. Yes? You also have the same analysis for the linear convergence rate, I guess so. No, not yet. You could, well, I guess you get the strong convexity constant. But for the, I have to check. I don't know yet. Because yeah, I guess it would work because then cue and no, I guess it holds too. I need to check. You said the lemma also holds. Yeah, but I haven't checked the lower bounds. That's the point. So I don't know exactly if this is optimal or not. But it should be. But you can just run the algorithm and it's linear convergence. Yeah, yeah, yeah. Everything depends on the ratio sigma over L and sigma is a fine invariant. L is a fine invariant. The ratio should be a fine invariant. But I haven't checked is the lower bounds and if we have the same match. That's it. Yes? So I don't understand what your motivation for obtaining these fine invariant for the first order method. What I don't understand in particular is that somehow you're assuming that you're not considering the cost of computing the proximal operator or the. No, that's true. So on the motivation side, at least I think one way to answer the problem is to flip the question. So what you're really interested in is the optimal bound period. So not only the optimal numerator and the optimal dependence on epsilon, you also want the optimal dependence on the dimension n. Okay, you can only do that. Get that if you pick the best choice of norm and the best choice of pox. Okay. So if you get the choice of norm and the choice of pox wrong, then you lose, you can lose a pretty significant factor in your bound. Square root of n in the example I just mentioned. But aren't you explicitly assuming that all the pox are equally cost costly? I mean that essentially it's, you're not taking into account. I'm not using the, that's true. But in this case, they turn out to be in four LPBs. I agree with you that you don't have a generic statement on the pox, but in a sense when you compute a bound for Nesterov's method, you start from the assumption that your projection steps will be solvable, whatever for your given set Q. So you need to, you make that assumption in Nesterov whatever happens. So here this is the same thing. Sure, but if you want to do some, to have a measure which is really dependent on the data, is that a secret perspective somehow? Problems which have a high amount of correlation should be harder than problems which have no correlation and this might be reflected in that. So I agree with you that there's a gap in the analysis. But at least the problem we decided to focus on right now is to have a bound that is optimal in both n and epsilon. Okay? So now we do not have that by far. So in many cases, so in some cases we know exactly how to pick the pox and it's a routine. If you see L1, you pick the entropy and everything's fine. But for a generic problem, you're faced with a feasible set. No one tells you which pox you should pick and you could really lose a factor square root of n, for example, by not picking the right pox. So what we wanted originally was a principle procedure to choose the norm and choose the pox. And it turns out that when you do that by nature, what you get is affine invariant. Otherwise you can simply, so you should get something that looks like the infimum over all affine changes of coordinates of Ld over sigma. Okay? Otherwise you can always take an affine scaling of your norm. You see what I mean? So whatever you do, if you want to be optimal, you need to be affine invariant. And it's easier to look first for affine invariance. That's the reason why I talk so much about affine invariance. In the end, the real goal is to find, of course, the optimal bound for Nestero's method in a principled way. So in a way that tells you exactly how to select the norm and how to select the pox. I agree with you that this doesn't solve the problem of computing the corresponding pox and solving the projection steps. But I guess that we'll have to wait until we solve this problem first, I guess, no? So I agree with you, but my message is that getting the optimal bound in itself is not a resolved issue at this point yet. Thank you. So let's thank Alex again. Thank you. grandstandive.
 Thank you and I'm very grateful for the invitation and for the opportunity to talk during the  CESTA slot or Wi-Fi, whatever.  And so I should start by saying that this is joint work with a number of people, including  Cris Abel Guzman, Vincent Roulet who is in the room and he's going to be lasered in  a second if I can find him.  Where are you?  Well, here.  And Nicolas Boumal who's now at Princeton and Martin Yaggy who's now at EPFL.  So the title changed but the content remained the same.  And the content is a lot simpler than what the title sort of influenced.  So the idea in general is that when you get a complexity bound it looks like this, roughly  speaking.  You get a certain dependence on the problem dimension and a certain dependence on the  target precision.  So that's a generic complex optimization problem.  In this case you're lucky because the exponent is not too high, etc.  But this is what it roughly looks like.  If you're lucky it looks a little bit like this, a little bit more like this.  And well now you have a leapschitz constant and at least you have some dependence on the  problem structure.  But clearly one thing important is missing from this complexity bound and this is the  data.  The complexity bound you get on the complex optimization problem you're trying to solve  only very, very loosely depends on the problem data.  And if you want to study computational trade-offs or computational complexity versus statistical  performance trade-offs, in general the fact that you're bound on the complexity of the  problem you're studying is so coarse and so roughly dependent on the structure of your  data is a big issue.  This is of course an upper bound to begin with so it's hard to make comparisons between  the complexity of value optimization problems using only upper bounds.  It's even worse because this upper bounds is very loose and in particular only loosely  dependent on the problem data.  And so the general idea behind the two quick results I'm going to present today is to get  closer to data-driven complexity bounds.  And hopefully get closer to something that would be tight data-driven complexity bounds  on optimization problems.  If you want to start to make comparisons between the complexity of values optimization  problems you need something more than upper bounds.  You need tight bounds on the complexity.  And if you want to compare problems based on their structure you need bounds that depend  on the problem structure and on the data in a meaningful way.  And so the material I'm going to present today is an effort in that direction.  Of course it's a broad topic and the two results I'm going to present today are just  very specialized results in this direction but that's the general idea.  You want data-driven complexity bounds that hopefully are tight and allow you to quantify  in a much finer way what happens on the computational side when you're considering and comparing  optimization problems coming from statistics for example.  So again if you're studying the complexity versus statistical performance trade-off well  it helps if you have a fine description of the complexity aspect.  And at this point we don't.  So you can talk a lot about this trade-off but at least on the complexity side are measures  of problem complexity and the way they relate to the problem structure are really approximate  now and pretty far from the truth.  And they suffer from a certain number of clear deficiencies and among these deficiencies  is affine invariance.  So it makes sense that if you're going to describe the complexity of a problem the bound  you use to describe this complexity should not be affected by elementary transformations  of your problem.  And in particular if you make a simple affine change of coordinates the complexity of your  problem should not change.  Just a renormalization should not have any impact on the complexity of an optimization  problem.  Yes.  Well.  Machine learning is.  It's okay so I guess you're implementing this on machines so machines are finite precision  so obviously there are limits to what I'm saying.  But on the other hand it's okay I see what you mean.  Good point.  It's a matter of robustness.  If your problem can be fixed by a simple affine change of coordinates perhaps your method  should be smart enough to recognize it.  So it's setting the bar a bit high I guess maybe but at least as far as I'm concerned  maybe your algorithm should be robust enough to recognize that the problem you're facing  numerically is simple conditioning.  And the algorithm itself should be robust to these conditioning issues.  The condition number is not affine invariant.  The condition number is not affine invariant but I mean conditioning in a more abstract  sense.  No but that's precisely the point so it's a conditioning issue you can fix it by just  changing coordinates.  But what I mean by affine invariance is you make an affine change of coordinates.  You don't expect your problem to change in nature.  In particular you haven't done anything to your data.  So if you're looking at statistics you're not manufacturing data.  It's a simple preprocessing step you could do etc.  So this is something that should be within reach basically.  But I agree that it's partially subjective.  There's no imperative reason for this to be true.  But if it can't be true we all agree it's a good thing.  Is that okay?  Feel free to question my motivations even more deeply.  So affine invariance is a good thing and we want more good things in optimization.  That's sort of the essence of the domain.  And so that's the first point.  So I'm going to start by talking about affine invariance.  Can we get it?  And if yes what does it say?  And separate but equal and important in importance renegars condition number and compressed sensing.  So this would be again in a slightly different direction but in the same spirit we see that  in certain cases like compressed sensing problems the same quantity drives both computational  complexity and statistical performance.  So in this particular case we are lucky because we have a single metric for both computational  complexity and sparse recovery thresholds.  So in that case the problem is solved.  In general of course it's still open.  So affine invariance we're going to consider a very simple generic optimization problem.  You minimize a convex function f over a simple compact convex set q.  And you're going to assume here that f is convex and smooth and I'm going to make all  these precise later and that q is compact convex and simple and again simple will be  made precise later.  So that's the general problem we're interested in.  And if the set over which we optimize is not too big we have a complete theory for this  problem.  So we have Newton's method and Newton's method at each iteration does a simple thing.  It takes a step in the direction given by the gradient but it normalizes this step by  the fashion.  And if you assume that the function is self-concordant and that the set q as a self-concordant  barrier you have a very explicit estimate on the complexity of minimizing a convex self-concordant  function using Newton's method.  If you haven't seen it before the self-concordant assumption feels a bit bizarre to say the  least but if you think about it for a second you see that it basically does two things  at the same time.  If you read it in one direction it's essentially a lower bound on the second derivative of  the function and so it's a way of writing strong convexity while maintaining affine  invariance in the condition.  And if you read it in the other direction then it becomes an upper bound on the absolute  value of the third derivative of the function and that's a way of saying that the second  derivative will not change too much when you move from one point to another.  And optimization in general is just about minimizing quadratic functions in the end  and that's exactly what Newton's method does.  And so it's kind of intuitive why this is the right set of assumptions.  You're using a quadratic model to minimize your function and you want this quadratic  model to remain true even outside your current point and that's why you bound, you need to  bound the third derivative.  So this really looks bizarre but in the end it's simply a way of combining both an upper  bound on the third derivative and a lower bound on the second derivative.  And to do so in a way that makes the condition invariant with respect to an affine change  of coordinates in the point x.  And this is why you have this exponent 1.5 here.  So everything, it's bizarre but everything has a meaning.  And once you make that assumption you use focus on solving a bioproblem of course, you  need the bi itself to be self-concordant but basically then you can bound the number of  iterations required to get a solution with precision epsilon by some coefficient times  the difference between the value of the barrier at the initial point and its optimum plus  log of log of 1 over epsilon iterations.  And for all reasonable values of epsilon this is basically 3.  And this term here depends only on parameters that you set for the line search in the Newton's  step.  So you decide what the value of this parameter is.  This term is.  And alpha is typically something like 0.2 and beta is 0.5.  So this is a fixed quantity.  So to summarize, the complexity of Newton's method is basically 3.  So the number of iterations you need to reach essentially any precision is bounded by something  like 375 times h of x0 minus h star plus 6.  And that's clean enough for me.  I don't know about you but it's empirically valid up to a factor let's say 300.  It's a constant.  And what's striking is what is not inside this bound.  So in particular it's independent from the dimension n which is pretty spectacular.  And again this is empirically valid.  And it's also a fine invariant of course because it only depends on the values of the  function.  Okay?  Well, the only thing missing from this bound is the cost of solving the Newton's system,  the KKT system, but that's just linear algebra.  So this is something you can measure very precisely from your data and the structure  of your problem.  Okay?  And it's just linear algebra.  Conditioning plus problem structures, sparsity, block structure, etc.  But you can get a very fine estimate of the complexity of solving the KKT system using  simple linear algebra procedures.  Okay?  But doesn't this depend on some conditioning?  What do you mean?  This here?  The efficiency of solving the system?  It does if you look at things in a slightly more precise way and I will at the end of  the talk.  But overall the number of iterations varies between 15 and 20.  And so the number of iterations will be the cost of every iteration.  Clearly, but at least you can read it directly from the data.  So you can write the cost of solving the Newton's step as a function of the problem structure,  dimension, its block structure, things like that, and the data conditioning.  So you have a completely explicit data-driven description of the complexity of your problem.  Okay?  And this is what you're looking for.  It's affine invariant and it fits the structure of the data very well.  And in particular, if you want to compare two problems, you just compare their complexity  estimate, okay, coming from the linear algebra side.  So at least you have an upper bound that's useful for making comparisons between the  complexity of various problems, okay, which is something you don't have for first order  methods.  That's my next point, basically.  Yes?  I've got a question.  So if I have a value h or h divided by 2, it should be the same.  And y is not the same.  What am I missing?  Good point.  There should be probably a...  Scale in the...  Yeah, scale somewhere, but it should make a difference.  No, I don't remember exactly, but that's an issue.  I know it's an issue.  I can't tell you why.  Okay.  So this is the picture for Newton's method and essentially the topic is completely closed,  okay?  So we know exactly how to bound the number of iterations the method goes through and  we know exactly how to measure the cost of these iterations.  So you have a problem and you can describe very precisely how much it's going to cost  to solve it numerically using Newton's method.  Meaning when you have two problems, you know which one is going to be more expensive than  the other, okay?  So that's the beautiful world of small scale problems.  Yeah, so in addition to that, I've mentioned it several times, but Newton's method is affine  invariant, meaning if you do an affine change of coordinates to your problem, the iterates  of Newton's method applied to the transform problem will simply be the affine transformations  of the iterates of Newton's method on the original problem formulation, meaning that  in particular the number of iterations doesn't change and the complexity bound doesn't change  either.  And so you have an affine invariant complexity bound on an affine invariant procedure.  And so again, this is a very important feature.  So the problem is that at a certain point, your problem becomes too big and you can't  even solve a single instance of the KKT system, let alone run several iterations of Newton's  method, okay?  And so beyond a certain scale, second order information is out of reach.  You cannot form the Hessian or solve the KKT system.  And second order information is what makes Newton's method affine invariant, okay?  So what people do is they just drop second order of information and use gradients instead,  first order information.  But the problem is now, can we get similarly clean complexity bounds for first order methods  that are tight enough to say something truly meaningful about the complexity of the optimization  problems and satisfy some of these invariant properties?  Okay, and the answer is yes in certain cases.  So just to go back to an algorithm that is a big favorite among some members of the audience.  If you look at Frank Vol, for example, which is also known as the conditional gradient method  or the Fedorov method, at each iteration you solve an affine minimization problem whose  vector is given by the gradient.  And you get an extreme point of the feasible set, you take convex combinations of these  extreme points and magically you converge to the optimum.  And somewhat more magically, you can show that the complexity of the Frank Vol algorithm  is bounded by four times Cf divided by the target epsilon, the target precision epsilon,  where Cf is a bound on the curvature of your function, okay?  And so the good news about Cf first, this complexity estimate is fairly simple in itself,  but the additional piece of good news about this bound is that Cf is invariant with respect  to an affine change of coordinates in your problem, okay?  So that's excellent news.  The only issue with this is that in many cases, the dependence in the target precision epsilon  is suboptimal, okay?  In particular, when f has a Lipschitz continuous gradient, then the lower bound can be as low  as 1 over a square root of epsilon, okay?  So your bound is nice, but it's really far from being tight.  And it's kind of useless if at some point you want, for example, to compare the complexity  of several problems, yes?  So why is it actually a fine invariant?  I mean, if I stretch or scale the function by some...  Just plug it this time here, if you plug it in here, do you get a fine invariance?  This is the first order of expansion, so it is invariant.  If the first we use gradients, makes it independent on the product, but as soon as it's a differential,  yeah, get a fine invariant.  But I have another question.  So when you say tightness of the bound, you mean tightness of the bound for the algorithm  or for the problem?  So tightness is you make a certain number, so you have a certain number of facts about  your problem, smoothness of the function, regularity of the set, et cetera.  So you have a black box, and then you have a few...  You open a little bit the black box and you know a few things about your problem, and  suddenly...  So if you only have curvature, then things are a bit different.  But if you know, for example, that f has a Lipschitz gradient, then you can do better  in terms of epsilon.  You need to know more about q2.  What I mean is that if this was universally optimal and a fine invariant, we wouldn't  have a problem.  But isn't this optimal given the different order of f and the support function of q?  Yes, but what I mean is that in certain instances, you have more than that.  And in that case, then you have to use another algorithm.  If you want to be as close as possible to the bound, and this other method will not  have an affine invariant bound.  That's what I mean.  So, of course, this might be optimal in certain scenarios, but when you leave these scenarios,  then you're in trouble because suddenly you lose your method.  The best option for solving your problem doesn't have a clean complexity bound.  That's what I mean.  Okay?  Other questions?  Okay, so at least we know it's possible for a first order method to have an affine invariant  bound.  So it's not the fact that we are losing second order information that makes it impossible  to produce invariant bounds.  Okay?  It's really about algorithm design and the way we bound the complexity of the method.  Okay?  So the sort of classical method that reaches lower complexity bounds for smooth optimization,  for example, is the Nesterov method of 1983.  Okay?  The original paper was in a nucleon setting, but in the general case, the algorithm requires  you to do two things.  Okay?  So it's fully specified up to a certain number of choices.  Okay?  So in particular, when you write down Nesterov's method for a specific optimization problem,  the general algorithm, not the one in 1983, you have to choose a norm.  Okay?  And that norm is important because when you say that the gradient has a lip sheet's continuous,  sorry, that the gradient is lip sheets continuous, with constant L with respect to a norm, your  choice of norm will affect L. Okay?  And if you change L, then you change your complexity bound.  So you choose a norm that has an impact on complexity.  And once you've chosen a norm, you also need to choose a pox function for the set Q. And  you want that pox function to be strongly convex with respect to your choice of norm.  Okay?  And again, the strong convexity parameter will show up in the complexity bound.  So how you choose the pox will have an impact on the problem complexity.  Okay?  And then once you've done that, the algorithm basically computes a gradient.  Those two rough projection steps averages the result and iterates.  Okay?  And it will produce an epsilon solution in at most a square root of 8L dx star divided  by epsilon sigma.  And now the dependence in epsilon is optimal because it's in one over a square root of  epsilon.  However, the constant L and sigma used in the description of that bound are not invariant  with respect to an affine change of coordinates.  Okay?  And so you do a simple transformation of your problem.  You scale the parameters and suddenly the complexity can vary massively.  So when you say optimal here, when people say optimal here, what they really mean is  optimal with respect to epsilon.  In the general case, if you don't really look carefully at how you choose your norm and  how you choose your pox, there's no reason for the numerator here to be optimal.  And not only that, this numerator can have a very significant impact on the complexity  of your problem.  Okay?  And we also, this numerator makes the complexity bound vary with affine changes of coordinates  in the original problem.  Okay?  So this is something you'd like to fix.  So in particular, what you want is a bound on the complexity of your problem that is  not only optimal in epsilon, but also in everything else.  Okay?  You want a complexity bound that is optimal up to a constant factor, just like what we  got for Newton's method.  And the problem is that you cannot write such a bound using the quantities L and sigma,  and for that matter, D of x star.  Because all these quantities depend, vary with an affine change of coordinates in your  problem.  Okay?  So we have to find something else to write this complexity bound and make it affine invariant.  And we also have to check if this something else is optimal.  In the sense that it matches the best possible bound on this numerator.  Okay?  So just to give you an example of what this choice of norm and pox function means, suppose  you look at, it's an example taken from a paper by Jusid Nimeovsky-Lan and Shapiro,  you have this simple matrix game problem.  So it's an affine matrix game problem.  And you have some smoothing to do, etc.  But the details don't matter too much here.  But if you pick an Euclidean setting, and in this case, a squared Euclidean pox, you  can bound the number of iterations by four times the spectral norm of the matrix A divided  by N plus one.  If on the other hand you think a little bit more carefully and you pick the L1 norm and  an un-tropic pox, and then your bound becomes square root of log N log M max coefficient,  so the max norm, the max magnitude of the coefficients of the matrix A. Okay?  So again, I'm using the same algorithm.  I'm getting the same dependence on the number of iterations N.  However, my numerator is changing very significantly.  For example, when the matrix A is Bernoulli, the difference between these two terms is  square root of N. Okay?  So the method may be optimal in epsilon, but if you don't pay attention to your choice  of norm and choice of pox, you can still be a factor square root of N from the best complexity  bound possible.  Okay?  And that's a big deal.  Okay?  So there's a question of invariance.  There's also a question of optimality.  You want the best possible implementation of your optimal method to make it fast.  Capital N is the number of iterations.  It's not, so after N iterations you reach that precision.  N max is the precision?  No, N is the number of iterations.  Oh, wait, wait, wait.  No, okay, so it's whatever makes it correct.  So either this should be the precision and this the number of iterations are the opposite,  but not both at the same time, good point.  Okay?  But you see what I mean.  Okay, sorry.  So this should be either epsilon or N, whatever you prefer.  Let's move on.  And so, okay, so I hope I've convinced you that choosing the norm and choosing the pox  had an impact and was an important step.  And if you want things to behave properly, this should be done in a principled way.  Okay?  And here in some sense, looking for affine-invariant bounds, so the optimal bounds are going to  be in affine-invariant.  Okay?  So the optimal numerator in the complexity of the problem is going to be affine-invariant  because you can always do an affine transformation of your norm and renormalize your all-year-old  coefficients.  Okay?  But that doesn't mean that if you get an affine-invariant bound, it's going to be optimal.  But looking for affine-invariant is probably a good way of choosing a norm and choosing  a pox.  You just have to check afterwards that what you're getting is indeed optimal.  Okay?  And this will turn out to be the case here.  So think about it for a minute.  If you want your choice of norm and your choice of pox to be invariant, it cannot come from  outside of your problem.  Okay?  If suddenly you decide that your norm has to be a clillion, there's no way, if it doesn't  depend on your problem, there's no way it will vary as your problem varies.  Okay?  So you have to extract your norm and your pox from the problem itself.  And there's a good way to start doing that in certain classical scenarios.  One is when Q is a centrally symmetric convex set with non-empty interior.  In that case, Q is the unit ball of a norm.  And the natural norm to pick out of your optimization problem is the one corresponding  to Q.  Okay?  The Minkowski gauge of Q.  Okay?  That turns out to be a norm.  Good news.  And what makes this a particularly good choice is that when you pick this Q norm as the underlying  norm defining your algorithm, the corresponding Lipschitz constant for the gradient will be  invariant with respect to an affine change of coordinates.  So you do an affine change of coordinates to your problem.  If you pick the new Q norm corresponding to the transforms feasible set, it will have  the same Lipschitz constant.  The gradient will have the same Lipschitz constant with respect to the transformed norm, then  with respect to the original one.  Okay?  So choosing the norm corresponding to the feasible set Q makes your Lipschitz constant  and the strong convexity constant of the pox invariant with respect to an affine change  of coordinates.  Okay?  So that seems to be a good option.  Now the last thing that remains to be done is to choose the pox.  And for choosing the pox, I need to start with two quick definitions.  Yes?  If you deviate from the central symmetry...  Then you have to do a little bit more.  I don't have...  Well, if you take the simplex, then it makes sense to symmetrize it.  And then it becomes the L1 ball.  Can you do anything other than the simplex, polyhedral?  I wish I had a general answer in that case, but I don't at this point.  So we can cover centrally symmetric and everything that looks or can be turned into a centrally  symmetric set.  If we presented the matrix game in which Q was more or less...  Yeah, yeah, so it turns out...  I'm going to handle...  I'll discuss in a few slides the case where we optimize over simplex and where if you  take the L1 ball, everything works out fine.  Yeah, but in more interesting games, if you take the sequential games, these strategy  profiles, more general polytops, which might deviate very violently from simplex, do you  think convex compact...  Open fun...  I have no idea.  I mean, I don't know.  So far, only centrally symmetric is easy, but in the general case, I don't know.  Yes?  Can you go back one slide?  The definition of smoothness is used as a square norm, can you replace it by a bryman  divergence?  Why do you...  You can have...  Simplex you can do, you just get the L1 norm.  I point out that so here you...  Let's hit yourself to consider like proximity of x and y for a square norm, but what if  you rely yourself to consider like more general functions like bryman divergence, you could  maybe do the bryman, that is centrally symmetric.  Maybe, yes.  It's just that I still need a norm in the end.  And so the problem is how do I...  Oh, or bryman...  Yeah, I see what you mean.  Good point, maybe.  But I only have a proof of optimality at least in the...  So getting a fine invariance is probably easy, but the ultimate price is to get both a fine  invariance and optimality, and so far we only have optimality in the centrally symmetric  cases because we only have lower bounds in the centrally symmetric case.  So that's the idea.  So I think it's probably doable to come up with affine invariant procedures to construct  a norm when your original set is not centrally symmetric.  No big deal probably, but unfortunately it's not clear that you're going to get the optimal  norm corresponding to that particular set.  And I don't even know at this point what to look for.  So maybe bryman divergences give you additional flexibility, but I'm not sure how to use that  flexibility yet.  That's the idea.  So at least we have a norm in the centrally symmetric case and it's pretty obvious.  What's a little bit less obvious is now that we have this norm, it may not be smooth, etc.  So we have to come up with a pox.  And for a pox I need the definition of the pox, I need a few more definitions.  So the first is the bad act measure distance between two norms or two spaces.  And this is just defined as the smallest product AB such that 1 over b times the first norm  is smaller than the second, which is itself smaller than a times the first norm.  So this product AB measures the distortion between these two norms.  And we're going to use it in our choice of the pox.  And the second definition is a bit more obscure and less classical and it's called the regularity  constant.  And so it's taken from a paper by Yuditsky and Mirovsky on a large deviations of vector  valued martingales.  So it doesn't really have anything to do with the optimization context.  But it's a way of measuring the regularity of a banach space.  And so this regularity constant of a banach is the smallest constant delta that does  two things.  So first we want the pox function p squared divided by two to have a Lipschitz continuous  gradient with respect to the norm p.  So we look for a smooth norm p to construct our pox.  We want that smooth norm to define a pox that has a Lipschitz continuous gradient with  respect to itself.  And we also want this norm p to be not too far away from the original norm of the banach.  So this norm here may not be smooth, but we approximate it by a smooth norm p.  And because the norm p is smooth, it allows us to derive a pox by just squaring it.  And delta will control two things at the same time.  It will control one, how far p is from the original norm, and two, how smooth the pox  is.  OK?  So there's a trade-off between the two.  There's a square root here.  Here delta is a direct bound on the parameter mu.  But for some happy by some happy accident, this is exactly the trade-off we need in our  bound.  So what you can show using this definition is that the complexity of Nesterov's method  applied to this problem here can be bounded by square root of 4 times LQ times dQ, where  LQ is the Lipschitz constant of the gradient of F with respect to the norm induced by Q.  And dQ is the regularity constant of the Banach space, Rn, and the dual norm of the Q norm.  OK?  And the good news is that these two terms here, LQ and dQ, are invariant with respect  to an affine change of coordinates in your problem.  OK?  So at least we solved our first problem.  So now the numerator in this complexity estimate, we still have the optimal dependence in epsilon.  And at least now we have the affine invariance of the numerator with respect to an affine  change of coordinates.  Yes?  You have to say something very stupid.  The conjugate and affine invariant that takes the infimum over all possible, like, the  affine.  Yeah, but you need to know that here you want to make it as constructive as possible.  That's the idea.  And my thing is constructive.  The infimum over all affine all.  So you would take the infimum over all affine change of coordinates of L times d of x star.  Yeah, but how do you solve that problem?  How do you compute LQ and dQ in practice?  Yeah.  No, but LQ, well, I'll show you in a minute.  You can do it for certain specific instances.  In the general case, you can't.  But for certain specific instances, it's easy.  So when Q is an LP ball, for example.  And so coming back to the simplex example, when you're optimizing over a simplex, it  makes sense to symmetrize that set into an L1 ball.  And when you do that, classically, people take the L1 norm as the underlying norm and  the entropy as the proxy function, because the entropy turns out to be strongly convex  with respect to L1.  And the bound you get is the L1 Lipschitz constant of your function times log n divided  by epsilon.  If you do the same thing, but using what is suggested by the previous construction, you  don't select the L1 norm as the underlying norm.  You take something that is the reciprocal of the two log n norm.  OK?  Don't ask me why.  Read the paper.  But basically, this suggests another way of constructing a norm based on the geometry  of your problem, and you measure the Lipschitz continuity of your function with respect to  that norm as well.  And the complexity bound you get can be written L1 times log n divided by epsilon times 16.  Yes?  Maybe you have a very stupid question, but do you consider at all how epsilon is affected  by these affine transformations as well?  I mean, if you multiply everything by two, shouldn't you precision also?  I don't think that should make a difference.  Because the affine action of x, not of x.  Yeah, yeah, yeah.  Yes, but I mean.  No, it has no impact on the objective value.  Yeah.  Other questions?  Yes.  So the bound you just put in the previous slide, that was for running the stirrup algorithm  with this norm and this prox?  So with the norm induced by q and the prox, which is induced by this definition of the  regularity constant.  P of x.  P of x, exactly.  P of x squared divided by two.  OK?  So if you can compute the q norm and you can compute P of x, then you have a specification  of Nester's method, which is affine invariant.  OK?  And do you know that this is smaller than the nth over all affine transformations?  That's the question I'm going to discuss next.  So clearly affine invariance is not sufficient to give you optimality of the numerator.  So in the end, what you want is a constant where, sorry, a complexity bound which is  optimal up to an absolute constant.  And we don't have it yet.  Yes.  Thank you.  So there is a recent paper showing that indeed on each specific problem, the lower bound  is better than this.  In the sense that Nester's method is the best.  Yes.  I haven't read a little old paper, I haven't really digested this one yet, so I'm not  sure exactly what it means.  But the lower bounds are pretty tight on this thing too, so I have doubts.  Yes, but so the lower bounds in this finite dimensional setting, we know that they hold  only for the first iterations, right?  After them, we don't know.  So they may ask you the result.  Tell us.  If the number of iterations becomes bigger than n, then the absolute method is a better  idea.  So this only applies in the high dimensional regime where you're doing fewer iterations  than the dimension, clearly.  But this is typically the regime you care about.  But I'm going to talk about other scenarios where the Nester of bounds are not optimal.  So when you have, but all of this depends on getting a little bit more information on  the black box.  So I'll come back to that in a minute.  And so before saying anything about optimality, this bound actually allows us to say something  about easy and hard problems.  If we read the bound and try to understand what it means from a geometrical point of  view.  So on easy problems, so easy problems where problems means here problems where LQ is low.  Okay?  Well, LQ will be low if the norm is large in directions where the gradient is large.  Okay?  And that means roughly then the sublevel sets of f of x and q are aligned.  And what that means geometrically is that when the sublevel sets are aligned, there  is a naffine change of coordinates that is going to make your problem roughly spherical.  So and optimizing a spherical quadratic over a sphere is actually the simplest problem you  can think of.  So that sort of makes sense.  Okay?  And second, if you think about LP spaces, the unit balls BP have low regularity constants.  Okay?  And regularity constant of the L1 ball is n, that's the worst case.  But remember that here, regularity is defined on the dual space.  And so what that means is that problems written over unit balls BQ for Q between 1 and 2 are  easier than problem written over Q for example.  Just because of the way this bound works on LP balls.  Okay?  But the question is how good are these bounds?  So okay, nice enough, they are fine in variant, but it doesn't mean that the complexity bound  is tight.  And in particular, the worst possible choice of product LDx star divided by sigma will  also nicely be a fine in variant.  Okay?  But we don't expect that bound to be really good.  Okay?  So the inf is that fine in variant, the sup is also a fine in variant.  Okay?  You'd rather take the inf.  So the question is can we show optimality or at least can we show optimality in certain  particular cases?  And it turns out that we can.  And in particular, we can do so for LP balls.  Okay?  So now we're going to focus on a very specific class of problems where Q is the LP ball.  Okay?  And in that case, the bound is LP times DP divided by, square root of LP times DP divided  by epsilon.  And the constants DP can be computed explicitly.  Okay?  Same thing for the corresponding norms, they are simply LP norms.  Okay?  So when P is between 2 and infinity, DP is simply n to the power P minus 2 over P. And  when P is between 1 and 2, you can bound DP by, pretty tightly by this quantity here.  Okay?  Where C is an absolute constant.  And that means that we can compare this upper bound with lower bounds we have for optimizing  smooth convex functions over LP balls.  And for P in the range 1, 2, the lower bound we have is this one here, L divided by log  n divided by epsilon.  Sorry, L divided by epsilon log n.  And our complexity bound is 4 times an absolute constant times L log n divided by epsilon.  Yes?  Can you please, the LP, the ball by essentially symmetric convex set that has a sufficiently  regular boundary?  That's essentially what you're doing when you define P. So the original norm is directly  derived from the set and may not be smooth.  And P is there to produce a smooth approximation of the set, essentially.  So that's how it's constructed.  It's not constructive in the sense that you don't manufacture it, but the regularity constant  is computed using a smooth approximation.  Okay?  So it turns out that here the bound is optimal up to a polylogarithmic factor.  And in the range P between 2 and infinity, the lower bound is given by this, and the  upper bound, our upper bound is given by this.  And this is again optimal up to a polylog when K is proportional to n.  And by optimal here, I mean optimal in both epsilon and n, okay?  Which is a much stronger statement than simple optimality with respect to epsilon.  Is there the number of iterations?  So there are annoying things that happen when you run.  So you have to show optimality for the entire square of values epsilon and n, okay?  And here in certain regimes, it turns out that Frank-Volff is optimal when you're not  running a number of iterations that is proportional to n.  Okay?  But we can discuss about this offline.  I don't have time to mention details here.  So in particular, there are results that tell you that if you have a little bit more information  on the smoothness of your space and on the regularity of your function, then in that  case, you can get much more precise estimates of the complexity.  And in that case, we are not yet able to produce affine invariant bounds that work similarly  as the bounds I detailed before, but we're close to that, okay?  But this is probably too much information for today, okay?  So that's it.  We have affine invariant bounds on the complexity of Nestor's method that give you at least  a principled way of specifying the method, choosing a norm and choosing a prox.  And these bounds are affine invariant.  And in addition to that, in certain problem instances, for example, when you're optimizing  over LP balls, these bounds also turn out to be optimal.  And by optimal, we mean now optimal in terms of their dependence with respect to the precision  epsilon and optimal with respect to the dependence on the problem parameters, okay?  On the dimension, right?  And so that's important.  Okay, so very briefly, in the few minutes I have left, I have a few slides about another  scenario where we are lucky and where the description of the problem complexity matches  exactly the quantity we use to describe its statistical performance.  And even though there's no immediate connection with the topic I just discussed, in the end,  the objective is exactly the same, describe the complexity of an optimization problem  that is in a way that is data-driven and allows you to compare the complexity of optimization  problems in a meaningful way, okay?  So here I have to specialize things a little bit again and focus on the conical linear  systems that follow, the primal dual pair of conical linear systems, one where you try  to find a vector inside a cone and the intersection of the cone and the subspace, and another  where you try to find a vector y such that minus a transpose y belongs to the dual cone,  okay?  And it turns out we can see very fine things, we have a very refined way of characterizing  the complexity of solving such an alternative conical linear system, okay?  And this complexity description is written in terms of the distance to infeasibility,  okay?  So what is the distance to infeasibility?  It's essentially the minimum perturbation you need to introduce to the matrix A to make  your problem infeasible, okay?  Or symmetrically, the minimum perturbation you need to make to your matrix A to make  the problem feasible, right?  And forget about the details here, what distance to feasibility or infeasibility means is that  problems that are clearly feasible or problems that are clearly infeasible will be much easier  to solve than problems that are near the region where feasibility starts to break down or  infeasibility starts to break down, yes?  So just a quick question, but to know if there is a spectral norm or the…  You can choose, but clearly here it's the spectral norm, yeah.  But yeah, you may want to pick another one, that is flexible, okay?  So what Renegard's condition number does is measure this distance to feasibility or  infeasibility in a scale invariant way, okay?  So it takes this distance to infeasibility and normalize it by the spectral norm, right?  So when rho, the distance to infeasibility is very small, then relatively speaking, this  condition number is going to be really high, okay?  And the idea of this condition number is to do for optimization problems or at least  in this case alternative conical linear systems, what the traditional condition number does  for linear systems, okay?  So you compute the condition number of a linear system, it's going to tell you at the same  time how hard this system is going to be…  It's going to be to solve this problem numerically and how stable the solution will be.  The condition number defined by Renegard is exactly the same thing for optimization problems.  It tells you first how hard it's going to be to solve this optimization problem and  second how stable the solution will be, okay?  So this is very good if you can compute it, of course.  It's a very good description of the data-driven description of the complexity of an optimization  problem, okay?  And so there's a lot of work on bounding the complexity of classical optimization techniques  using this condition number and a more refined analysis of bias methods shows, for example,  that this condition number shows up in the bound on the number of iterations of interpoint  methods and that the complexity of solving the KKT system of equations actually varies  with this condition number as well.  So this turns out to be a good way of measuring the complexity of an optimization problem  using its precise structure and the input data.  But when you focus on compress sensing problems and sparse recovery problems where this should  be the L1 norm here, I forgot a pretty important index, you can define in very precise terms  the performance of this sparse recovery problem using conically restricted minimum singular  values of the matrix A, okay?  And these are just, look very much like the quotient defining the classical singular values  except you restrict the vector Z to belong to a certain cone, which is the descent cone  of the L1 norm.  And these generalized eigenvalues allow you to bound the performance of the sparse recovery  algorithm, okay?  And what's pretty striking here is that we're lucky enough that these two quantities match,  meaning that Ronegaard's condition number is actually equal to the corner restricted  eigenvalue controlling statistical recovery performance in compress sensing problems.  So the quantity that controls numerical performance on the optimization side in this case is also  the quantity that controls sparse recovery performance on the statistical side, okay?  And we can generalize this to much broader class of recovery problems and more details  are in the paper over here, okay?  And numerically this works.  So this is an example where we can go as far as possible in reconciling complexity descriptions  or complexity bounds with statistical performance metrics, okay?  So what you see here is the classical phase transition in sparse recovery, so this is  the probability of recovery using various algorithms, okay?  And this is the phase transition in the condition number, okay?  It's non-symmetric.  It should be symmetric if we had symmetrized our definition of the condition number, but  what happens on this side of the phase transition is not that interesting.  So the really interesting part is the fact that this condition number decreases as you  move away from the phase transition threshold here, okay?  And that these two phase transitions are pretty well synchronized, okay?  And indeed what you observe is that the complexity of the corresponding numerical methods has  the same phase transition when you move away from around, sorry, the sparse recovery threshold,  meaning that it's much harder numerically to solve sparse recovery problems when you're  near the transition threshold than when you're much further away from it.  And this is something that was observed empirically starting with the papers by Dono in 2008,  for example.  But here it's made completely explicit by this concordance between the conditioning  of the optimization problem on one side and the cone-affected eigenvalues on the other.  I guess this is my cue to conclude before I get electrocuted.  And so just to sum up, somewhat unrelated results, but the idea here is to produce complexity  estimates that are near enough to the data to say something about the complexity of one  optimization problem versus another.  And so in particular, we got a formulation of the optimal algorithm by Nesterov whose  complexity bounds are affine invariant with respect to an affine change of coordinates  and turned out to be optimal, at least on LQBos.  And a completely data-driven complexity measure for sparse recovery problems, which matches  exactly the quantities used to measure the statistical performance of these procedures.  So there's a long list of open problems if you're interested.  One is to show optimality of the product LQDQ in the general case.  And as you mentioned, produce a cue norm when cue is not centrally symmetric and then not  obviously a norm.  We don't know how to do that.  There's also a key question, which is CF is a low-bound on LQDQ.  Is that low-bound tight?  We'd like to know because it would solve a lot of our problems.  We don't know.  And Nesterov's bet is that it's not.  But you can bet against him.  And so again, the best known choice in non-symmetric sets, Q, I've mentioned that already.  And also more important in some sense, a systematic tractable procedure for smoothing  cue.  And that would preserve affine invariance.  And so that would allow us to produce pox functions in cases where cue is not an LP  ball.  We don't know how to do that yet.  And that makes the algorithm unimplementable in the general case.  And so that's still open at this point.  Thank you.  Thank you.  So we have time for a few more questions.  Francis?  Yes?  For the spectral ball, you get similar results.  Yes, because then for the spectral ball, you know what the cue is.  And is it tight or not?  I don't remember, probably hard to say.  It would be optimistic and say yes.  We could be optimistic and say yes up to a polylog.  And I guess that's the answer, but I'm not 100% sure.  But so basically, the important part is that the reason why we're able to check optimality  here is that we know exactly what the cue is for LP balls, or the LQ balls, sorry.  And the same thing is true for the spectral norm and all matrix norms.  So we know exactly what the cue constant is for these matrix norms.  So at least we have an explicit bound.  Yes?  You also have the same analysis for the linear convergence rate, I guess so.  No, not yet.  You could, well, I guess you get the strong convexity constant.  But for the, I have to check.  I don't know yet.  Because yeah, I guess it would work because then cue and no, I guess it holds too.  I need to check.  You said the lemma also holds.  Yeah, but I haven't checked the lower bounds.  That's the point.  So I don't know exactly if this is optimal or not.  But it should be.  But you can just run the algorithm and it's linear convergence.  Yeah, yeah, yeah.  Everything depends on the ratio sigma over L and sigma is a fine invariant.  L is a fine invariant.  The ratio should be a fine invariant.  But I haven't checked is the lower bounds and if we have the same match.  That's it.  Yes?  So I don't understand what your motivation for obtaining these fine invariant for the  first order method.  What I don't understand in particular is that somehow you're assuming that you're not considering  the cost of computing the proximal operator or the.  No, that's true.  So on the motivation side, at least I think one way to answer the problem is to flip the  question.  So what you're really interested in is the optimal bound period.  So not only the optimal numerator and the optimal dependence on epsilon, you also want  the optimal dependence on the dimension n.  Okay, you can only do that.  Get that if you pick the best choice of norm and the best choice of pox.  Okay.  So if you get the choice of norm and the choice of pox wrong, then you lose, you can lose  a pretty significant factor in your bound.  Square root of n in the example I just mentioned.  But aren't you explicitly assuming that all the pox are equally cost costly?  I mean that essentially it's, you're not taking into account.  I'm not using the, that's true.  But in this case, they turn out to be in four LPBs.  I agree with you that you don't have a generic statement on the pox, but in a sense when you  compute a bound for Nesterov's method, you start from the assumption that your projection  steps will be solvable, whatever for your given set Q.  So you need to, you make that assumption in Nesterov whatever happens.  So here this is the same thing.  Sure, but if you want to do some, to have a measure which is really dependent on the  data, is that a secret perspective somehow?  Problems which have a high amount of correlation should be harder than problems which have  no correlation and this might be reflected in that.  So I agree with you that there's a gap in the analysis.  But at least the problem we decided to focus on right now is to have a bound that is optimal  in both n and epsilon.  Okay?  So now we do not have that by far.  So in many cases, so in some cases we know exactly how to pick the pox and it's a routine.  If you see L1, you pick the entropy and everything's fine.  But for a generic problem, you're faced with a feasible set.  No one tells you which pox you should pick and you could really lose a factor square  root of n, for example, by not picking the right pox.  So what we wanted originally was a principle procedure to choose the norm and choose the  pox.  And it turns out that when you do that by nature, what you get is affine invariant.  Otherwise you can simply, so you should get something that looks like the infimum over  all affine changes of coordinates of Ld over sigma.  Okay?  Otherwise you can always take an affine scaling of your norm.  You see what I mean?  So whatever you do, if you want to be optimal, you need to be affine invariant.  And it's easier to look first for affine invariance.  That's the reason why I talk so much about affine invariance.  In the end, the real goal is to find, of course, the optimal bound for Nestero's method in  a principled way.  So in a way that tells you exactly how to select the norm and how to select the pox.  I agree with you that this doesn't solve the problem of computing the corresponding pox  and solving the projection steps.  But I guess that we'll have to wait until we solve this problem first, I guess, no?  So I agree with you, but my message is that getting the optimal bound in itself is not  a resolved issue at this point yet.  Thank you.  So let's thank Alex again.  Thank you.  grandstandive.
Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_0_1043.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_1044_1979.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_1980_4991.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_4992_5219.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_5220_5855.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_5856_5939.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_5940_5999.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_6000_6299.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_6300_6575.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_6576_6707.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_6708_7271.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_7272_7319.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_7320_7847.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_7848_8087.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_8088_8495.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_8496_8723.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_8724_8819.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_8820_8891.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_8892_9131.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_9132_9443.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_9444_11387.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_11388_11951.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_11952_12179.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_12180_18803.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_18804_19727.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_19728_19835.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_19836_24083.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_24084_29039.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_29040_29375.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_29376_34439.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_34440_34607.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_34608_35507.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_35508_36431.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_36432_36911.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_36912_37895.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_37896_40967.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_40968_43487.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_43488_44135.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_44136_46451.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_46452_47975.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_47976_49763.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_49764_55331.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_55332_56471.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_56472_57275.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_57276_58691.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_58692_59327.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_59328_59555.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_59556_60023.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_60024_60479.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_60480_61931.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_61932_62063.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_62064_62195.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_62196_62303.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_62304_62495.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_62496_62783.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_62784_67511.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_67512_69623.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_69624_74291.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_74292_75191.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_75192_75419.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_75420_76619.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_76620_77003.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_77004_77387.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_77388_80543.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_80544_81131.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_81132_81611.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_81612_81971.png Alexandre_d_Aspremont_-_Renegar_s_Condition_Number_and_Compressed_Sensing_Performance__1080p_25fps_H_81972_94703.png