In the context of Computer Science and Optimization, I have heard that different problems can be classified using the "P vs NP" framework. Essentially, there is a hierarchy of problems based on the inherent complexity of the problem itself. For example, a problem like "multiplying numbers" is considered as "P" and is considered fundamentally easier to solve than a problem like "solving a sudoku" which is "NP".
In most Statistical and Machine Learning Models, there is usually an optimization problem "nested" within the model that is required to solve. For example:
- Regression Models: In a standard regression model, we try to find the value of the "beta coefficients" that either minimize the error between the (candidate) model's prediction of the response variable and true values of the response variable (Ordinary Least Squares - OLS), or we try to find the "beta coefficients" such that probability of reproducing the observed response values is maximized (Maximum Likelihood Estimation - MLE). For simple regression models, there exists "exact solutions" to the OLS and MLE optimization problems and we can calculate these "beta coefficients" analytically - but in more sophisticated regression models such as Logistic Regression or Regularized Regression (e.g. LASSO, RIDGE), the corresponding optimization problem is usually solved using some approximate and iterative algorithm such as the "Newton-Raphson" Method.
- Decision Trees: A Decision Tree (e.g. CART) is formed by "splitting" variables into smaller subsets (i.e. "nodes") such that "purity" increases in each subsequent subset; "purity" is often measured through some sort of "Information Gain" that is based on measures such as "Gini Index" or "Entropy". Thus, Decision Trees can be interpreted as an optimization problem where "Information Gain" has to be optimized. I have heard that since Decision Trees often have different variable types (e.g. continuous and categorial), searching for the optimal variable splits that optimize "Information Gain" is a Mixed Integer Optimization Problem having an enormous Combinatorial Search Space. For the interest of creating a decent Decision Tree in a reasonable amount of time, "Information Gain" is optimized using a "Greedy Search Algorithm," and as a result, the final Decision Tree (i.e. the answer to this Mixed Integer Optimization Problem) is almost certainly unlikely to be the optimal Decision Tree (as there is very high probability that a better Decision Tree likely exists in this large Combinatorial Search Space, but finding this Decision Tree would take too much time):
- Neural Networks: Successful Neural Networks are largely attributed to the effectiveness of Optimization Algorithms (e.g. Stochastic Gradient Descent) to optimize (i.e. determine the "neuron weights") notoriously complicated, high dimensional and non-convex Loss Functions:
My Question: Is it possible to categorize the optimization problems corresponding to Statistical and Machine Learning Models such as Regression Models, Decision Trees, and Neural Networks as "P" vs "NP"?
I am aware that categorizing these problems wont really have any effect on solving them, but I have the following guess: When provided with a candidate solution to any of these optimization problems (e.g. Regression beta coefficients, a particular Decision Tree, Neural Network Weights), we have no real way of checking whether this candidate solution is indeed the optimal solution (unlike a sudoku, in which even for an enormous "n x n" sudoku, we can instantly check if a candidate solution violates the rules or not). Thus, my guess is that many of these above optimization problems are likely either NP-Complete or NP-Hard.
Is this correct?
Note: I have often heard of Machine Learning Optimization Problems being described as "Ill-Posed Problems", implying that they are inherently more difficult than "Well-Posed Problems" (Why is pattern recognition often defined as an ill-posed problem?). This is due to factors such as solutions to these optimization problems "may not exist" and "may not be unique". However, I am not sure if "Ill-Posed Problems" automatically leave the "N" and "NP" complexity classes.
