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.
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.
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.
Yes Pythagorean identity, or Pythagorean decomposition, whatever you want to call it, the orthogonality properties etc etc make L2 super convenient to apply and reason about, but that does not mean it is a suitable performance metric to use. This is again the phenomena of searching for the answer where its well lit vs where the answer lies.
The problem really lies in the tails of the errors, although it might not be immediately apparent. You say variance covariance etc etc, but it does not take much for RVs not to possess them. Think about it, Chebyshev's inequality will make it clear what decay you need for those to exist.
Yes you are right choice of L_2 by itself makes no assumptions. But once you start analyzing the performance of the estimator it will show up, particularly when Fisher information is no longer strongly convex. Cramer Rao becomes a vacuous bound in this case. The other problem is L2 balls become infinitely larger than say the L1 ball as dimensionality increases. So L2 error stops being very good at localizing a vector.
The problem is L_2 is not a good metric to measure inaccuracy with, it is super convenient to use though.
Let me demonstrate one of its well known problems. Say the error residual has tails that does not decay as fast as an exponential (MGF does not exist around 0). You can then show that the accuracy can be arbitrarily bad. No need for super ugly densities, something as benign as just a mixture of two Gaussians with the same expectation will break it. I am just restating Huber's robustness argument here in a different way.
Gauss himself was well aware of the problem and chose it for convenience. Even his peers were well aware of situations when L1 made more sense than L2. Unfortunately optimization theory was not well developed at that time to use L1 based methods. But now we can.
BTW you might find it interesting that the Pythagorean property is not limited to L2 squared. The set of all 'divergences' for which it holds is the Bregman divergence family. Its an if and only if condition. This is a result that came from the ML community. One side of the implication was known though. Bregman divergences are again the likelihood ratios of exponential family densities, (also called Darmois Koopman family in older literature), hence has strong connections with NP lemma as well. What I find mind boggling is that Bregman divergence had its origin in convex optimization literature ! Its origins had absolutely nothing, nothing to do with probability and stats. Its amazing when two separate fields of Math make contact in these ways.
BTW if you dont mind sharing your suitably anonymized mail, I am srean.list at gmail. It will be pleasure to discuss math with you. I find it very helpful when i can stress test an idea aginst a human oracle. HN might not be a forum well suited for this.
You bring up a lot of stuff I've never reviewed.
> but that does not mean it is a suitable performance metric to use.
If the plane do the L^2 projection on is really close, then the error is really small, and what's not to like? Really close is good enough for me.
Right, there are three biggie choices, L^1 (minimize the sum of absolute values of the errors), L^2 (minimize the sum of squared errors), and L^infinity (minimize the worst error).
L^2's fine with me, good enough for government work, okay first cut, day in and day out.
If in some particular case L^2 has some problems, then maybe something like regression is not the right tool for the problem.
Gee, we do a lot of L^2: We get orthogonal components so that we can get L^2 cafeteria style, just pick the components we want. E.g., in filtering stochastic processes, we take a Fourier transform -- that is finding the coefficients of the sample path on the sine-cosine orthogonal components. Or we do a convolution, which is the same thing in the end. The approximation we get is an L^2 approximation.
So, with JPG -- sure, it's L^2. Right, JPG does funny stuff nearly lines. Life's not perfect!
For some things, sure we want L^infinity: E.g., if we want to use a quotient of polynomials to approximate the usual special functions, then we want to minimize the worst error and do what is called Chebyshev approximation, but this is very specialized.
Indeed it is. Lets catchup more sometime. Here's my email again srean.list on gmail
Totally agreed there is lot to like about L2 but there are plenty situations where it is terrible (in fact some of them are on one topic of your interest: monitoring server farms). In some of those situations L1 or a combination of L1 and L2 helps a lot.
In practice, essentially always, for real random variables X, Y, all of the following exist and are finite:
E[X], E[|X|], E[X^2], E[XY]
Var(X) = E[(X - E[X])^2]
Std(X) = Var(X)^(1/2)
Cov(X,Y) = E[(X - E[X]) (Y - E[Y])]
Cor(X,Y) = Cov(X,Y)/(Std(X) Std(Y))
E[Y|X]
E[X] and Std(X)are useful quite broadly and that we find/estimate them does not mean that we are working with a Gaussian distribution.
If the above is not true, then there is something bizarre and/or pathological, the ultimate edge case, and we need to review what we are doing.
All you need is the tail to fall slower than a quadratic.
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.