# Can OLS be considered an optimization technique?

Can ordinary least squares estimation be considered an optimization technique? If so, how can I explain this?

Note:

From an AI perspective, supervised learning involves finding a hypothesis function $h_\vec{w}(\vec{x})$ that approximates the true nature between predictor variables and the predicted variable. Let some set of functions with the same model representation define the hypothesis space $\mathbb{H}$ (That is we hypothesise the true relationship to be a linear function of inputs or a quadratic function of inputs and so forth). The objective is to find the model $h\in\mathbb{H}$ that optimally maps inputs to outputs. This is done by application of some technique to finds optimal values for the adjustable parameters $\vec{w}$ that defines the function $h_w(\vec{x})$. In AI we call this parameter optimization. A parameter optimization technique/model inducer/learning algorithm would for example be the back propagation algorithm.

OLS is used to find/estimate for $\beta$ parameters that defines the linear regression line that optimally maps predictor variables to output variables. This would be parameter optimization in the scenario above.

-
Can you please clarify what you mean by "optimization technique"? That phrase would usually refer to something like this section of the wikipedia page on optimization but, based on the answers you've received, others are interpreting it another way. Just to clarify, if you mean it in the way asserted by the link, then the answer is certainly "No"; OLS is an estimation technique. –  Macro Jan 6 '13 at 23:55
I dunno. All optimization techniques minimize functions of a particular form. So simplex won't minimize non-linear functions and Nelder-Mead won't minimize various horrible functions. Under a strained reading of the word "optimize", OLS is an optimization technique for a very particular class of functions. –  Patrick Caldon Jan 7 '13 at 1:43
@Entropy Because the ambiguity in your question is leading to controversy, please edit it to clarify your meaning of "optimization technique." Some kind of improvement of this nature is needed so that we can keep this thread open. –  whuber Jan 7 '13 at 14:36
I have upvoted the question as a positive response to the substantial edit. However, it strikes me that the question now contains its own answer: the edit appears to argue that essentially all parameter-fitting exercises are "optimization techniques"--we could almost take this as an (idiosyncratic) definition--and thus it concludes that OLS, as a parameter-fitting technique, is one of them. This appears to leave us either with nothing to say or to argue about what "optimization technique" ought to mean. Alas, neither of these is a constructive activity. Should we just close this question? –  whuber Jan 10 '13 at 14:48
I believe @Macro has outlined the distinction in comments elsewhere in this thread: parameter fitting uses optimization but is not an optimization technique in its own right. But arguing over this is not the sort of thing that is appropriate for this site, which is why I am leaning towards closing the question. –  whuber Jan 10 '13 at 18:01

Yes, it is. In OLS, you are looking for the linear model that provides the "best" fit to the data. Implementation requires specifying some notion of what you mean by "best". OLS works by defining the "best" model as the one that minimizes a certain measure of model error -- in this case, the sum of the squares of the model residuals. The residuals are the part of the data that aren't explained by the model: OLS seeks to give the best description of the data, by minimizing the "total amount" of unexplained variation in the data.

Formally, any operaton in which you are solving for the minimum or maximum of some function can be interpreted as an optimization.

-
I think "optimization technique" is generally interpreted as referring to a method that can be used to optimize a given function. Yes, you are doing optimization when you solve for the OLS estimator but I don't see how that makes it an optimization technique. The Simplex algorithm, Newton's method, Conjugate-Gradient, etc... are optimization techniques. –  Macro Jan 6 '13 at 21:59
@Macro is correct. OLS is (the solution to) an optimization problem. But given any optimization problem, there are a variety of techniques that one might use for solving it. –  Dapz Jan 7 '13 at 6:00

I would have said that OLS is an optimization problem rather than an optimisation technique, as there are many optimization techniques/algorithms that can be used to solve OLS problems (e.g. analytical solutions for [ridge] regression, IRWLS for logistic regression, scaled conjugate gradients for neural nets, etc.). There is no reason why you can't fit an OLS regression model by simple gradient descent, the reason we generally don't is there are more efficient algorithms.

OLS specifies what you are optimising, but you get the same solution from any suitable optimisation technique.

-

Given explanatory variable $x_i$ and observed variable $y_i$, and a linear regression model $y = a + b x$, OLS is the minimum of: $$\sum_i (y_i - b x_i - a)^2$$ over all $a,b$.

In contrast to this, quantile regression is the minimum of: $$\sum_i |y_i - b x_i - a|$$ over all $a,b$.

EDIT As a minimum, the parameter estimates for $a$ and $b$ are some kind of optimum. And the calculation method, i.e. solving the normal equations, to actually find the estimates can be considered as technique.

So I vote for yes, OLS is a kind of optimization technique. If someone says "I solved the problem using OLS" I would conclude he used the euclidean norm and a linear solver on the normal equations formulation of the problem. I do not know which solver, though.

So the term "OLS" is more similar to "MLE" than to numerical methods like "Simplex algorithm" or "Conjugate Gradient method".

-
Sorry, I should be clearer. I think the original question should be parsed as "is OLS a technique which employs optimization", rather than "is OLS a general technique for optimization". The first is true, and if the first expression of KW's answer when reexpressed as a function is minimised by an optimizer the coefficent values will be identical to OLS estimation but for possible numerical issues. –  Patrick Caldon Jan 7 '13 at 1:37
@Patrick, It seems that an unconventional definition of "optimzation technique" is held by several people in this thread - I don't think you'll see anyone (e.g. wikipedia, a statistics textbook, etc.) referring to OLS or MLE as optimization techniques - you'll see them referred to as estimation techniques. We'll have to wait for clarification from the OP but I have a hard time seeing this as asking the first interpretation you gave, partially because "is OLS a technique which employs optimization" seems trivially true based on the name alone ("least squares"!!!). –  Macro Jan 7 '13 at 1:59
@Marco: I don't think that your thread-brothers are trafficking in unconventional definitions. Rather, we are trying to provide what we understand the questioner is probably after. –  Arthur Small Jan 7 '13 at 3:56
@entropy, I'm not really following your reasoning but, FYI, you could also calculate the OLS estimator by using gradient descent (or any other optimization technique - just pick one) so don't let the fact that the OLS estimator happens to have a closed-form solution confuse the issue for you. –  Macro Jan 10 '13 at 14:34
@entropy the technique of setting partial derivatives equal to zero is not OLS, just a method of solving a subset of OLS problems. There are other optimisation problems you can solve by setting partial derivatives to zero and there are OLS problems that you can't solve this way (i.e. problems that are not linear in the parameters). –  Dikran Marsupial Jan 10 '13 at 19:20