0

In Iterative Reweighted Least Squares (IRLS) algorithm, an optimization problem with the weight treated as known is solved in each iteration during solving the main optimization problem. For instance, when solving $\min Q(\beta,V(\beta,\gamma))=\min(y-X\beta)'V(\beta,\gamma)(y-X\beta)$, the IRLS solves $\min Q(\beta,V(\bar{\beta},\bar{\gamma}))$ where $\bar{\beta}$ and $\bar{\gamma}$ are the value of $\beta$ and $\gamma$ in the previous step, which has a closed form solution for $\beta$.

My question is that why do I need to solve this problem in each iteration, or what is the role of this sub-optimization problem in the context of $\min Q(\beta,\gamma)$? More generally, why do I need to solve additional optimization problem when solving an optimization problem?

user0131
  • 357

1 Answers1

2

Iterative reweighted least squares composes (on the fly) a series of quadratic approximations of nonlinear optimization problems, which can be solved by linear methods (specifically, via weighted least squares). At each step it makes a new approximate but easy-to-solve problem based on the local behavior of the function.

At each stage the solution to the weighted least squares problem is not an exact solution to the nonlinear target problem, only an approximate one. Nevertheless (under some conditions) the approximation improves as the optimum is approached and convergence toward the solution of the original problem is often quite rapid, in many cases requiring only a handful of steps; naturally, it helps to have a good starting approximation.

Sadly the current Wikipedia page on IRLS is misleading about the nature of problems that can be solved by this method, implying that it's limited to problems of minimizing p-norms. It isn't.

Glen_b
  • 282,281
  • Many thanks. I think I got the idea. I'm wondering if there are any books/papers that describes the details of IRLS... – user0131 Sep 25 '23 at 06:56
  • Many resources, no doubt. I don't have any to suggest, sorry; after hearing of it in an undergrad class I may have originally pursued it in Thisted's book on Statistical Computing or Gentle's book Computational Statistics - albeit certainly among other resources - but those would be quite old now. You may also find Fisher Scoring of interest: https://en.wikipedia.org/wiki/Scoring_algorithm ... which for some models, including GLMs, is a form of IRLS. For example, see https://stats.stackexchange.com/questions/485975/show-that-each-iteration-of-fisher-scoring-for-glm-is-least-squares-for-working – Glen_b Sep 25 '23 at 08:51
  • Many thanks. I shall look for the material. – user0131 Sep 25 '23 at 10:36