5 ms·

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

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.
- srean 9y ago
  Ok did not agree :) on the Gaussian part. Yeah sure its a projection but so what. Why and when should a L2 norm projection be useful. It would when the tails of the residuals are Gaussian like. Otherwise things will and do go haywire. L2 loss is too sensitive at the tails. This observation is nothing new though. What is new however are the near magical guarantees you can get (literally rabbit out of a hat) when you use L1 projection instead. It comes at a computational cost but solves a problem that cannot be efficiently solved otherwise: Xw = y + noise. X is a random matrix woefully rank deficient. Exponentially more columns than rows. w \in R^n but has very few non zeros. Now find that w. This needs rather deep tools from asymptotic geometry and Banach spaces. Its an area that's quite active on stas / ML / signal processing right now.
  - graycat 9y ago
    > Yeah sure its a projection but so what. Why and when should a L2 norm projection be useful. We want the answer, and more generally a predictive model. We use the data we have to define a vector subspace. We use that subspace to creep up on the answer we want. Finally to get the answer, we project onto the subspace we have settled on. We CAN do the projection even though we don't have the answer. We take that projection on to the subspace, that point in that subspace, as our approximation to the answer. We use L^2 because that projection, with the Pythagorean theorem, is the closest in L^2. Being close in L^2 is a good thing: L^2 is a Hilbert space, and being Cauchy convergent means being convergent in L^2, and then there is a subsequence that converges almost surely, with probability 1, exactly, etc., and in practice it's exactly. A sequence that converges in L^2 but not exactly is pathological. Then as we use more variables, the vector subspace gets closer to the answer and we get a better projection although maybe not a better fitting model. To me, tails of distributions have next to nothing to do with it or the use of L^2. In particular, the basic regression math, the normal equations, the Pythagorean theorem total sum of squares = regression sum of squares + error sum of squares makes no assumptions at all about distributions (might want to argue that need to be in L^2, that is, for each random variable X have E[X^2] finite, or maybe at least E[|X|] finite, that is, L^1) certainly does not assume a Gaussian. Moreover the matrix in the normal equations has variances and covariances, but these are close to just the inner product in the Hilbert space L^2 and do NOT assume a Gaussian or anything about a distribution except merely that the expectations exist which in practice is a meager assumption, essentially always the case. Just because are working with variances and covariance does NOT mean that are assuming a Gaussian. Also notice that nowhere do we need to assume that our data is not discrete. Discrete data is still fine. If in addition do have an appropriate Gaussian assumption, then at the end of the usual normal equations stuff, can get an F ratio and some t-tests that usually can help evaluate the quality of the fitting and the importance of the coefficients. And for the model, we can get confidence intervals on the predicted values -- sure, will need a Gaussian assumption here, but there might be other approaches and otherwise we can hope or look for robust estimators. L^2's fine with me. More can be done, but the above is the first cut reason for using subspaces and L^2 projections although this explanation is rarely taught to students. When ordinary regression doesn't work very well, then I'm reluctant to strain with much more. I might be willing in some circumstances to use what L. Breiman (I respect Breiman, Loeve student) has in his Classification and Regression Trees.

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.

srean 9y ago
Ok did not agree :) on the Gaussian part. Yeah sure its a projection but so what. Why and when should a L2 norm projection be useful. It would when the tails of the residuals are Gaussian like. Otherwise things will and do go haywire. L2 loss is too sensitive at the tails. This observation is nothing new though. What is new however are the near magical guarantees you can get (literally rabbit out of a hat) when you use L1 projection instead. It comes at a computational cost but solves a problem that cannot be efficiently solved otherwise: Xw = y + noise. X is a random matrix woefully rank deficient. Exponentially more columns than rows. w \in R^n but has very few non zeros. Now find that w. This needs rather deep tools from asymptotic geometry and Banach spaces. Its an area that's quite active on stas / ML / signal processing right now.
- graycat 9y ago
  > Yeah sure its a projection but so what. Why and when should a L2 norm projection be useful. We want the answer, and more generally a predictive model. We use the data we have to define a vector subspace. We use that subspace to creep up on the answer we want. Finally to get the answer, we project onto the subspace we have settled on. We CAN do the projection even though we don't have the answer. We take that projection on to the subspace, that point in that subspace, as our approximation to the answer. We use L^2 because that projection, with the Pythagorean theorem, is the closest in L^2. Being close in L^2 is a good thing: L^2 is a Hilbert space, and being Cauchy convergent means being convergent in L^2, and then there is a subsequence that converges almost surely, with probability 1, exactly, etc., and in practice it's exactly. A sequence that converges in L^2 but not exactly is pathological. Then as we use more variables, the vector subspace gets closer to the answer and we get a better projection although maybe not a better fitting model. To me, tails of distributions have next to nothing to do with it or the use of L^2. In particular, the basic regression math, the normal equations, the Pythagorean theorem total sum of squares = regression sum of squares + error sum of squares makes no assumptions at all about distributions (might want to argue that need to be in L^2, that is, for each random variable X have E[X^2] finite, or maybe at least E[|X|] finite, that is, L^1) certainly does not assume a Gaussian. Moreover the matrix in the normal equations has variances and covariances, but these are close to just the inner product in the Hilbert space L^2 and do NOT assume a Gaussian or anything about a distribution except merely that the expectations exist which in practice is a meager assumption, essentially always the case. Just because are working with variances and covariance does NOT mean that are assuming a Gaussian. Also notice that nowhere do we need to assume that our data is not discrete. Discrete data is still fine. If in addition do have an appropriate Gaussian assumption, then at the end of the usual normal equations stuff, can get an F ratio and some t-tests that usually can help evaluate the quality of the fitting and the importance of the coefficients. And for the model, we can get confidence intervals on the predicted values -- sure, will need a Gaussian assumption here, but there might be other approaches and otherwise we can hope or look for robust estimators. L^2's fine with me. More can be done, but the above is the first cut reason for using subspaces and L^2 projections although this explanation is rarely taught to students. When ordinary regression doesn't work very well, then I'm reluctant to strain with much more. I might be willing in some circumstances to use what L. Breiman (I respect Breiman, Loeve student) has in his Classification and Regression Trees.