5 ms·

Agree with the gist but with some reservations. Small correction to what I said: srean> I was deliberately harsh on stats in my comment to offset some of the w

by srean 9y ago

Agree with the gist but with some reservations. Small correction to what I said: srean> I was deliberately harsh on stats in my comment to offset some of the wrong things you mentioned about stats. Replace 'stats' with ML in my comment above. You are spot on regarding stats part, regarding ML not so much. In fact I have great respect for you as a applied mathematician and frequently learn something from these exchange of comments. graycat> Moreover, the situation is reversed: Columbus brought better ship, etc. technology to the Americas than the Americas had, but CS AL/ML are bringing nearly all highly inferior technology to statistics, pure/applied math, etc. This is unfair to the point of being absurd. Have you looked at stats software ? or compute infrastructure built by statisticians ? I can say more, but that would be below the belt. CS/ML has infused new blood in this area augmenting the capabilities of what can be done on a machine or cloud) 3 orders of magnitude or more. Part of it is advances in CS and software systems, but that is not all. One of the other parts is advances in algorithms. I am sure you would not scoff at ML pedigreed algorithms that run way faster than CPLEX. Many would not have the context, but I am sure you do. Of course these algorithms are not fr any LP, but a class of huge LPs that show up in graphical models. These belief propagation based algorithms outperform not only vanilla simplex algorithms but also the state of the at ones on these problems. Then there is culture. ML algorithms are more likely to be open sourced so that people try it, criticize it and that is how progress is made. In stats locking it behind some proprietary stuff is the norm. R is an exception, but as a piece of software I would keep it light years away from the money. Let me move on. graycat> The asymptotic stuff is mostly okay: Can't figure out precisely what the darned thing will do for case n so let n go to infinity and maybe can see what happens. Then say, "for large n, this is about what happens" -- crude but better than nothing. Yeah n is indeed very large in most data sets, but p the dimension is often larger. All hell breaks lose in this situation when you go by classic theory of statistical inference. This quandary applies to deep neural nets also. The number of parameters way exceeds the training data points it yet generalizes well to unseen data. WTF is going on ! Classic prob/stats have no answers. Forget classic, even modern prob stats is struggling to explain this. A good fight is being fought to characterize their behavior. New mathematical arguments are being developed but this is clearly a work in progress, an open problem. You have a chip on your shoulder of sorts regarding ML. That's fine, nothing wrong with that. What is wrong, however, is when you mischaracterize it because you are not reading the right material. You have to read those books and journal publications that are the moral equivalent of the prob/stats library you have. Its not fair to compare two languages when you quote from corny porn in one but high literature from the other. May I say Vapnik again :) And checkout the main publication s from COLT (computational learning theory), ICML, NIPS etc. I am sure you have heard of the multi-armed bandit problem. Gittins index and all that. Now solve it for the distribution free case. Even that leaves something to be desired because rewards may not be governed by a stochastic process. Give guarantees for arbitrary but bounded reward sequences. Stats literature had no answer for these cases. These are just a glimpse of the tools and results that have come from ML. You observe some noisy entries from a huge matrix that is low-rank. Now fill the unseen entries and give guarantees on performance. ML has the tools here. A biggie is analysis of causality thanks to Judea Pearl. Some still dont get it that conditioning and causality are fundamentally different. Just regressing Y over X will not cut it. ML has the tools here. Anyways... Oh Jesus! not ANOVA again. Its a cute toy, that's all. The assumptions it needs are rarely met in the datasets we want to analyze today. Visionaries like Tukey had figured that out 3 decades ago. Why do statisticians to this day keep using parametric tools in situations where we are drowning in data. I agree that its not entirely the fault of statistics that people do the above. Stats really has to shed a lot of baggage that made sense a century ago but does not make sense now. Given your experience I am sure you know that things are rarely ever Gaussian. Central limit theorem often does not apply in this popular form because of distributions with ginormous variance. Why use tools based on that. Classic parameter estimation guarantees are all fine in the toy 'spherical cow' world but where in stats are the non-asymptotic guarantees on prediction performance in a distribution free setting. This is precisely the raison d'être for ML. Not that there are no statisticians who have gone this route (Dawid would be one who needs mention), but way too few. ML does indeed have a lot to offer. To be cute I would leave it at what I said before: > non-asymptotic guarantees on prediction in a distribution free / nonparametric setting. That is what ML does. The newer developments aim at situations where the number of parameters in the model far exceed the data. What guarantees can you give in such situations. Surprisingly quite a bit, and contrary to what text books have said over the century, you can give guarantees. The algorithms work magically well, but of course you would need some (realistic assumptions). ML is an applied science so it borrows from and (crucially) adds to mathematics all the time. This particular line of work borrows a lot from the geometry of high dimensional random convex bodies, and Banach spaces. The most exciting part I see is the melding of the good parts of ML and stats and a good deal of communication across the Stats and ML community lines. They collaborate, they publish in the same conferences and that's just freaking fantastic. This is what we need not some stupid fights over which is better or is it applied science or not. Parting word, dont get an idea of ML from ML porn and spread untruths like, graycat> ML is .... short on math guarantees. build a library just like you did for stats.

graycat 9y ago
Part I Beating linear programming as in C-PLEX on networks? In some cases, that's easy: On a lot of networks, the simplex algorithm specializes in an amazing way: A basic solution corresponds to a spanning tree. To consider adding a variable to the basis, just add an arc to the tree, get a circuit, run one unit of flow around the circuit and see if can save money, and if so run the flow around until hit a flow capacity constraint on one of the arcs in the circuit, remove that arc from the basis, and, presto, have a simplex pivot. If use the W. Cunningham (one of my profs) modification of strongly feasible bases, then are guaranteed won't cycle. It's easy to program and just blindingly fast -- e.g., the arithmetic is all just addition and subtraction. It's still the simplex algorithm so that C-PLEX could have been used, but for a big network problem will likely run ballpark thousands of times faster than C-PLEX. For more particular cases, maybe more can be done. Bertsekas has a polynomial algorithm for that problem. It may get applied to that wacko in Ping Pong Yang. Network flows is a an old, big, deep field e.g., Ravindra K.\ Ahuja, Thomas L.\ Magnanti, James B.\ Orlin {\it Network Flows: Theory, Algorithms, and Applications,\/} ISBN 0-13-617549-X, Prentice Hall, New Jersey, 1993.\ \ Mokhtar S.\ Bazaraa and John J.\ Jarvis, {\it Linear Programming and Network Flows,\/} ISBN 0-471-06015-1, John Wiley and Sons, New York, 1977.\ \ For analysis of variance, there is, e.g., George W.\ Snedecor and William G.\ Cochran, {\it Statistical Methods, Sixth Edition,\/} ISBN 0-8138-1560-6, The Iowa State University Press, Ames, Iowa, 1971.\ \ No joke it's from Iowa since it's long been important in agriculture research and testing and in experimental design and analysis much more generally. E.g., people who propose new ways to do K-12 education commonly use these techniques to good advantage. Sure, first cut, it's regression analysis again, but with its special discreteness really it's quite different. It's powerful stuff. For the Gaussian assumptions in regression, don't get too concerned: The normal equations remain and don't need a Gaussian assumption -- there's still a projection and still get the Pythagorean theorem -- total sum of squares = regression sum of squares + error sum of squares. The Gaussian assumption yields F ratio and t-tests, and ballpark in practice those remain robust mostly ignoring the Gaussian assumption. In some wild, edge cases, might want to check the robust claim, but otherwise do get some good information about the fit.
- srean 9y ago
  Totally agreed. The algorithm that I was talking about is a rather curious one. It neither does vertex hopping like simplex, nor interior point iterations. It works with a factorized representation of the Lagrangian and then updates parts of the in a fixed point iteration that if converges would satisfy KKT. What is strange is that this is not monotonic in the dual cost (neither the primal). As long as there is no more than 1 loop in the original problem the convergence is guaranteed. Otherwise no guarantee holds but it often does converge.

by srean 9y ago

graycat 9y ago

Part I Beating linear programming as in C-PLEX on networks? In some cases, that's easy: On a lot of networks, the simplex algorithm specializes in an amazing way: A basic solution corresponds to a spanning tree. To consider adding a variable to the basis, just add an arc to the tree, get a circuit, run one unit of flow around the circuit and see if can save money, and if so run the flow around until hit a flow capacity constraint on one of the arcs in the circuit, remove that arc from the basis, and, presto, have a simplex pivot. If use the W. Cunningham (one of my profs) modification of strongly feasible bases, then are guaranteed won't cycle. It's easy to program and just blindingly fast -- e.g., the arithmetic is all just addition and subtraction. It's still the simplex algorithm so that C-PLEX could have been used, but for a big network problem will likely run ballpark thousands of times faster than C-PLEX. For more particular cases, maybe more can be done. Bertsekas has a polynomial algorithm for that problem. It may get applied to that wacko in Ping Pong Yang. Network flows is a an old, big, deep field e.g., Ravindra K.\ Ahuja, Thomas L.\ Magnanti, James B.\ Orlin {\it Network Flows: Theory, Algorithms, and Applications,\/} ISBN 0-13-617549-X, Prentice Hall, New Jersey, 1993.\ \ Mokhtar S.\ Bazaraa and John J.\ Jarvis, {\it Linear Programming and Network Flows,\/} ISBN 0-471-06015-1, John Wiley and Sons, New York, 1977.\ \ For analysis of variance, there is, e.g., George W.\ Snedecor and William G.\ Cochran, {\it Statistical Methods, Sixth Edition,\/} ISBN 0-8138-1560-6, The Iowa State University Press, Ames, Iowa, 1971.\ \ No joke it's from Iowa since it's long been important in agriculture research and testing and in experimental design and analysis much more generally. E.g., people who propose new ways to do K-12 education commonly use these techniques to good advantage. Sure, first cut, it's regression analysis again, but with its special discreteness really it's quite different. It's powerful stuff. For the Gaussian assumptions in regression, don't get too concerned: The normal equations remain and don't need a Gaussian assumption -- there's still a projection and still get the Pythagorean theorem -- total sum of squares = regression sum of squares + error sum of squares. The Gaussian assumption yields F ratio and t-tests, and ballpark in practice those remain robust mostly ignoring the Gaussian assumption. In some wild, edge cases, might want to check the robust claim, but otherwise do get some good information about the fit.

srean 9y ago
Totally agreed. The algorithm that I was talking about is a rather curious one. It neither does vertex hopping like simplex, nor interior point iterations. It works with a factorized representation of the Lagrangian and then updates parts of the in a fixed point iteration that if converges would satisfy KKT. What is strange is that this is not monotonic in the dual cost (neither the primal). As long as there is no more than 1 loop in the original problem the convergence is guaranteed. Otherwise no guarantee holds but it often does converge.