Are Machine Learning Optimization Problem ever Categorized as "P" or "NP"?

Question

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, non-deterministic (i.e. the loss function is dependent on the observed data), 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?

Thanks!

Note: I have often heard of Pattern Recognition and Machine Learning Optimization Problems being described as "Ill-Posed Problems", implying that they are inherently more difficult than "Well-Posed Problems" This is due to factors such as:

• solutions to these optimization problems "may not exist"
• solutions "may not be unique".
• slight perturbations to the function/solution can cause large changes within the system
• it is impossible to determine whether the final solution to the optimization problem is in fact the "true optimal" solution - in Machine Learning, we often settle for a "good enough" solution

I would imagine that many "ill-posed" machine learning optimization problems would generally fall under the designation of "NP" , "NP-Complete" or "NP-Hard" compared to simply "P". However, I not sure about this.

Answer 1

When talking about statistical learning we generally don't talk too much about P vs. NP complexity (which usually is more associated with decision problems than optimization problems anyway - there are many optimization problems that are much 'harder' than P or NP). There are some exceptions, such as decision trees - it's know that finding a minimal optimal binary decision tree is NP (cf. Laurent).

What is generally more interesting is PAC learnability, which looks at the learning problem itself rather than any optimization algorithms we might use to approximate a solution. PAC learning asks the following question: can an algorithm given a subset of labelled examples from an instance set $X$ probably produce an approximately correct classifier for the entire set $X$? Here, 'probably' means with probability at least $1-\delta$ and 'approximately' means with average error $\leq \epsilon$ over $X$ (the Wikipedia page for PAC learning is useful for the full definitions). Essentially, PAC learning gets at the complexity of the actual learning problem in terms of sample complexity than computational complexity, which is somewhat detached from the learning problem itself. In practice, since we are going to rely on approximations most of the time anyway, guarantees on error given sample sizes are generally more interesting from a learning standpoint.