7
$\begingroup$

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".

enter image description here

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.

enter image description here

  • 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):

enter image description here

  • 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:

enter image description here

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.

$\endgroup$
6
  • 1
    $\begingroup$ First comment: the precise definitions of NP and NP-whatever are fairly picky, and in particular there is some difference between "decidable" in polynomial time (the computer science version of NP-whatever, which came first) and "solvable" in polynomial time (the optimization version, which came later). Second comment: NP-Hard is not the hardest problem level out there. Being in NP (including NP-Hard) requires that (somewhat loosely speaking) answers can be verified in polynomial time. There could conceivably be problems where even that is not true. $\endgroup$
    – prubin
    Feb 7 at 1:54
  • $\begingroup$ @ prubin: thank you for your reply! i was interested in this idea in a very general sense. For instance - if you take the problem of optimizing the loss function of a neural network. Could we assign some "designation" to this general problem (e.g. P, NP, NP-Hard, etc.)? $\endgroup$
    – stats_noob
    Feb 7 at 5:22
  • 1
    $\begingroup$ Note that, as your diagram correctly shows, P is a subset of NP. So, if a problem is in P, then it is also in NP. Also note that we don't know whether there exist problems that are in NP but not in P. $\endgroup$
    – Stef
    Feb 7 at 11:50
  • $\begingroup$ No, it's not typical for traditional analyses of neural-networks to discuss complexity-classes. $\endgroup$
    – Nat
    Feb 7 at 12:26
  • $\begingroup$ Sorry, I don't know enough about loss functions used to train neural nets to say whether the problems fall into P, NP or some other category. $\endgroup$
    – prubin
    Feb 7 at 16:49

1 Answer 1

9
$\begingroup$

No. There are optimization problems that are strictly in EXPTIME or other complexity higher complexity. Picking the optimal move in a Go game on a $n\times n$ grid is EXPTIME in $n$. MaxSAT on QBF (quantified boolean formulas) is in PSPACE. Those examples are of harder complexity classes then NP and because of that the P vs NP distinction is irrelevant for them.

$\endgroup$
4
  • $\begingroup$ Optimal move in Go is definitely in PSpace. Specifically, it can be done with something like n^4 space and (n^2)^(n^2) time. $\endgroup$ Feb 7 at 19:05
  • $\begingroup$ @OscarSmith You need to assume a bound on the maximum number of moves to get an estimate like that. The number of spaces on the board is not a maximum for the number of moves, a game can take much longer than that. As far as I know there is no straight forward answer to the question of the maximum number of moves on a given board size. $\endgroup$
    – quarague
    Feb 7 at 19:14
  • 1
    $\begingroup$ More specifically, the computational complexity hinges in part on the "ko rule" which does not permit repeated configurations. With such a rule in place, the "state" of the board involves all previous states, which may be exponential. The computational complexity of Go is unknown under these circumstances. (With no ko rule, then as Oscar Smith states, it's readily seen to be in PSPACE.) en.wikipedia.org/wiki/Go_and_mathematics $\endgroup$
    – SamM
    Feb 7 at 19:56
  • 2
    $\begingroup$ I assumed japanese KO rules which are given as an example on the EXPTIME Wikipedia page. $\endgroup$ Feb 7 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.