PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimization Problems for Machine Learning: A Survey

Claudio Gambella, Bissan Ghaddar, Joe Naoum-Sawaya

arXiv:1901.05331v5math.OCcs.LG

TL;DR

Machine learning seeks models that learn from experience to solve complex problems, but model complexity, noisy data, and decision-making requirements create important optimization challenges. This paper surveys machine learning approaches through mathematical optimization models, discusses their strengths and shortcomings, and highlights research directions and open problems.

  • Problem

    Machine learning must learn models that generalize beyond training data despite overfitting and noisy observations, while also supporting reliable predictions and optimal decision making.

  • Method

    The paper surveys regression, classification, clustering, deep learning, adversarial learning, and emerging paradigms using mathematical optimization formulations and solution approaches.

  • Results

    The survey presents and discusses optimization models across a wide range of machine learning models, including emerging applications in machine teaching and empirical model learning.

  • Takeaways & Limitations

    Large-scale optimization formulations and model-specific solution approaches, supported by commercial optimization software, are identified as an important research direction.

  • Takeaways & Limitations

    Mixed-integer deep neural network formulations can have weak continuous relaxations, making tight bounds crucial for their effectiveness.

Abstract

from arXiv · show

This paper surveys the machine learning literature and presents in an optimization framework several commonly used machine learning approaches. Particularly, mathematical optimization models are presented for regression, classification, clustering, deep learning, and adversarial learning, as well as new emerging applications in machine teaching, empirical model learning, and Bayesian network structure learning. Such models can benefit from the advancement of numerical optimization techniques which have already played a distinctive role in several machine learning settings. The strengths and the shortcomings of these models are discussed and potential research directions and open problems are highlighted.

1 Introduction

Machine learning seeks to enable machines to learn from experience and make predictions or decisions under varying conditions. This survey frames machine learning approaches as optimization problems, reviews their applications and limitations, and identifies research directions at the interface with operations research.

  • Machine learning aims to make intelligent decisions by learning from past experiences and solving complex problems under changing conditions.
  • Supervised learning fits models from input-output pairs, whereas unsupervised learning explores data distributions to identify distinguishing features and associations.
  • Empirical-risk minimization uses independent and identically distributed training samples because the true data distribution is unknown.
  • Model complexity, overfitting, and outliers create a tension between fitting training data and preserving predictive generalization.
  • Operations research intersects machine learning through applying learning to management decisions, solving hard optimization problems, and formulating learning itself as optimization.
  • The survey organizes machine learning around optimization formulations spanning regression, classification, clustering, dimension reduction, deep learning, adversarial learning, and emerging paradigms.

2 Regression Models

Regression models estimate relationships between predictors and quantitative responses, with optimization formulations supporting fitting, robustness, feature selection, and sparsity. The surveyed alternatives trade bias, flexibility, interpretability, and computational difficulty against prediction quality.

  • Linear regression represents a quantitative response as a linear function of predictors and remains attractive for simplicity, applications, and interpretability.
  • Least-squares fitting minimizes residual sum of squares and has a closed-form solution, but can produce high variance and many non-zero coefficients.
  • Robust regression models account for feature noise through an uncertainty set whose characterization influences optimization complexity.
  • Mixed-integer formulations can jointly model sparsity, selective feature inclusion, noisy-data robustness, outlier stability, expertise, significance, and multicollinearity.
  • Shrinkage methods reduce coefficient magnitudes to improve interpretability, while lasso can force coefficients exactly to zero when λ is sufficiently large.
  • Best-subset selection is NP-hard, and its prediction accuracy depends strongly on input noise without a guaranteed dominance over lasso or forward selection.
  • Nonlinear and piecewise-affine models increase flexibility, while generalized additive models retain interpretability but assume additive feature effects.

3 Classification

Classification assigns unlabeled observations to classes using a labeled training dataset. The survey introduces binary and multiclass approaches including logistic regression, linear discriminant analysis, decision trees, and support vector machines.

  • Classification predicts the class membership of an unlabeled item from training observations whose class memberships are known.
  • The surveyed classification approaches include logistic regression, linear discriminant analysis, decision trees, and support vector machines.

3.1 Logistic Regression

Logistic regression models binary class membership probabilistically and estimates parameters for a linear decision boundary. Its convex differentiable optimization enables global optimization methods, while variable selection helps control overfitting.

  • Logistic regression models binary labels through the posterior probability P(y|x), estimated from predictor variables and regression parameters.
  • The binary decision boundary is the hyperplane β0+β⊤x = 0, where both class probabilities equal 0.5.
  • Because the logistic-regression problem is convex and differentiable, gradient descent and Newton’s method can find a global optimum.
  • Variable selection can reduce overfitting by retaining only relevant predictors, whereas interaction terms increase flexibility at additional overfitting risk.

3.2 Linear Discriminant Analysis

LDA performs classification and dimensionality reduction by projecting labeled data into a lower-dimensional space. Its optimization minimizes within-class scatter while maximizing between-class scatter, commonly through the Fisher criterion.

  • LDA reduces feature dimensionality while using class labels to support robust classification.It is often applied when data contains many features, such as image data.
  • The linear transformation qi = G⊤xi maps each p-dimensional sample into an r-dimensional space with r < p.
  • Within-class scatter measures spread around class means, whereas between-class scatter measures spread of class means around the global mean.
  • LDA minimizes within-class scatter and maximizes between-class scatter through the Fisher criterion.The Fisher criterion is the ratio of between-class to within-class scatters.
  • Assuming Sw is invertible and non-singular, the Fisher criterion selects the r largest eigenvalues of S−1w Sb and corresponding eigenvectors.
  • Large margin linear discriminant analysis maximizes the minimum distance between class centers and the total class center but requires non-convex optimization.A proposed solution solves a series of convex quadratic optimization problems.

3.3 Decision Trees

Decision trees partition predictor space through hierarchical splitting rules for regression or classification. Optimization formulations balance misclassification loss and tree complexity, but globally optimal binary-tree construction is computationally difficult.

  • Decision trees partition predictor space into sub-regions and predict using statistical indicators of the resulting training-data segments.They are non-parametric models used for both regression and classification.
  • Regression trees use top-down recursive binary splitting to divide the training data into distinct regions.A univariate cut separates observations according to a feature-specific cutpoint.
  • Classical greedy recursive splitting does not guarantee a globally optimal classification tree, and optimal binary-tree construction is NP-hard.Linear, continuous, and dynamic-programming optimization heuristics have therefore been proposed.
  • A mixed integer programming formulation seeks provably optimal trees but has exponential complexity in tree depth.For fixed depth D, the maximum number of nodes is T = 2^D+1 −1.
  • The optimization objective combines normalized total misclassification loss with decision-tree complexity.The complexity term counts split branch nodes and is controlled by tuning parameter α.
  • For categorical features, an alternative formulation exploits combinatorial structure to strengthen the optimal-tree model and improve computational performance.
  • Bagging, random forests, and boosting improve accuracy by combining multiple decision trees, while single trees are often preferred for interpretability.

3.4 Support Vector Machines

SVMs learn separating hyperplanes by maximizing classification margins, with optimization formulations extended to nonseparable data, nonlinear kernels, regression, and ordinal outcomes. The survey also highlights trade-offs involving sparsity, interpretability, and modeling assumptions.

  • SVM classification identifies a hyperplane that separates binary classes while maximizing the margin to the closest data points.
  • Hard-margin SVM assumes perfect linear separability, a condition that often fails in practice.When the data is not linearly separable, the hard-margin optimization problem is infeasible.
  • Soft-margin SVM introduces slack variables ξi ≥ 0 and penalizes constraint violations to relax perfect separability.
  • Replacing the 2-norm with the 1-norm yields a linear optimization problem, generally at the expense of a higher misclassification rate.
  • The 1-norm can sparsify w by reducing the number of features used in classification, while elastic net combines 1-norm and 2-norm penalties.
  • Kernel mappings produce nonlinear separation in the original space while requiring only kernel evaluations in the dual formulation.The explicit feature mapping φ is not needed.
  • Support vector regression approximates real-valued targets within tolerance ϵ and penalizes deviations outside that tolerance.The ϵ-insensitive loss is zero within tolerance and positive beyond it.
  • Ordinal SVM models ordered categories with r −1 separating parallel hyperplanes rather than transforming ranks into numerical distances.Direct numerical transformation can be challenging, while binary encoding increases problem scale.

4 Clustering

Clustering groups unlabeled observations into homogeneous, well-separated subsets and connects naturally to operations-research formulations. The survey covers centroid-, capacity-, and hyperplane-based models alongside heuristic and mathematical-optimization solution methods.

  • Clustering seeks K homogeneous and well-separated subsets of unlabeled observations.Homogeneity concerns similarity within clusters, while separation concerns differences between clusters.
  • Euclidean clustering can be modeled as a network problem with similarities to the classical p-median problem.
  • K-means minimizes distances to cluster centroids with an a-priori fixed number of clusters.The number of clusters is commonly selected using an elbow curve or similarity indicators such as silhouette measures.
  • Mixed integer nonlinear and linearized formulations represent cluster assignments and centroid distances explicitly to minimize within-cluster variance.
  • The standard iterative heuristic alternates assigning points to their nearest centroids and recomputing centroids until within-cluster variance is sufficiently low.Because results depend on initial centroids, the procedure is typically repeated with different starts.
  • Capacitated centered clustering limits cluster capacity while measuring homogeneity through similarity to cluster centers.With distance-based similarity and equal capacities, the formulation also models facility location.
  • K-hyperplane clustering assigns observations to hyperplanes and minimizes squared orthogonal distances, targeting collinearity or coplanarity rather than similarity.
  • A distance-based reassignment heuristic for K-hyperplane clustering outperforms spatial branch-and-bound solvers.The underlying formulation is non-convex because of one constraint.

5 Linear Dimension Reduction

Linear dimension-reduction methods replace the original predictors with fewer linear combinations to retain informative variation. PCA maximizes variance without using responses, whereas PLS seeks directions that also correlate with the response.

  • Principal Components: PCA finds a low-dimensional representation whose ordered principal components retain progressively quantified amounts of the original features’ variance.The first component captures the largest variability, while later components are constrained to be uncorrelated with earlier ones.
  • Principal Components: Principal Components Regression uses the first principal components as predictors, reducing predictor count while retaining dataset variability.Its limitation is that variance-maximizing components may not be relevant to the response variables.
  • Principal Components: PCA can also support unsupervised learning, including k-means clustering, because its components do not require response information.A single-step quadratic program can combine the regression loss and PCA objectives when selecting components for regression.
  • Partial Least Squares: PLS projects predictors and responses into latent features, targeting directions with both high predictor variance and high response correlation.It is particularly suited to settings with many features relative to observations and iteratively orthogonalizes subsequent directions.

6 Deep Learning

Deep learning models use layered transformations with weights, biases, and activation functions to learn complex regression and classification relationships. The surveyed optimization formulations cover training, regularization, mixed-integer representations, pooling, activation maximization, and adversarial-example search.

  • Network Architecture: Deep feedforward networks propagate inputs through successive weighted layers, biases, and activation functions to produce the output vector.A three-layer example has 3 input units, 5 hidden units, and 2 output units, with fully connected adjacent layers.
  • Network Architecture: Activation functions enable nonlinear learning; ReLU is commonly preferred because gradient methods optimize it and it tends to produce sparse networks.For classification, final-layer logits can be converted into class probabilities using logistic-sigmoidal or softmax functions.
  • Training: DNN training determines weights and biases by minimizing losses such as sum-of-squared errors for regression and cross-entropy for classification.Gradient descent, called back-propagation in this setting, is an effective approach, while regularization can limit weight growth and overfitting.
  • Mixed-Integer Formulations: A trained ReLU DNN can be modeled as a mixed-integer linear program using layer outputs, binary activation variables, continuous slacks, and fixed weights.The formulation can incorporate pooling operations and support optimization tasks such as maximizing unit activations.
  • Mixed-Integer Formulations: Mixed-integer formulations can search for adversarial perturbations, but the described restrictions neither guarantee an adversarial solution nor prove that none exists.Their continuous relaxation is weak, making tight activation bounds crucial for computational effectiveness.
  • Training Limitations: A hybrid constraint-programming and mixed-integer approach for training binary neural networks produced better generalization than common gradient-descent solvers, especially on small datasets.Gradient descent generally guarantees only local optimality unless early stopping is used.

7 Adversarial Learning

Adversarial learning formulates attacks and defenses as optimization problems, including targeted and untargeted perturbations, robust training, and poisoning in streaming settings. These formulations expose computational challenges and limits on robustness guarantees.

  • Motivation: Adversarial examples exploit perturbed inputs to cause classification errors, creating security concerns for machine-learning classifiers.The literature models these concerns using min-max, Stackelberg, or Nash formulations depending on the relationship between learner and attacker losses.
  • Targeted attacks: Targeted attacks seek a perturbation r such that f(x + r) = y′, while keeping the perturbed input close to x.If the target label equals the original label, r = 0 is a trivial solution and does not misclassify the input.
  • Computational challenges: The computational difficulty of finding optimal adversarial perturbations depends on classifier complexity and the feasible input set, especially for neural networks.This makes exact optimization challenging in general.
  • Untargeted attacks: Untargeted attacks seek nearby inputs whose classified label differs from the original, without specifying the replacement class.Their formulations use scoring functions and distance metrics such as the 1-, 2-, and ∞-norms, and can be represented as bilevel optimization problems.
  • Adversarial robustness: Adversarial training uses robust optimization to train neural networks against all perturbations in a specified class, formalized as an outer minimization over an inner attack maximization.The resulting objective also quantifies robustness for the chosen perturbation class.
  • Data poisoning: Semi-online and fully-online poisoning attacks modify streaming training data, but online learning makes the weights complex functions of the data stream and complicates gradient computation.In this setting, the KKT conditions do not hold, motivating convex surrogates and other simplifications.

8 Emerging Paradigms

Emerging paradigms extend optimization-based machine learning beyond conventional predictive tasks to teaching learners, embedding learned models in combinatorial decisions, and learning Bayesian-network structures. Their formulations introduce bilevel, mixed-integer, constraint-programming, and structural restrictions that affect tractability.

  • Machine teaching: The teaching dimension problem seeks the minimum training-set size needed to correctly teach a model.It has been studied for linear learners including Ridge regression, SVM, and logistic regression.
  • Machine teaching: Machine teaching jointly specifies teaching risk, teaching cost, a learner, and a regularization factor within a bilevel optimization problem.The teacher solves the upper problem while the learner solves the lower machine-learning problem.
  • Machine teaching: Machine-teaching problems are generally challenging, but convex learners can sometimes replace the lower problem with KKT conditions and reduce the formulation to one level.Discrete teaching sets may also permit submodularity analysis or mixed-integer formulations for small sets.
  • Empirical model learning: Empirical model learning integrates machine-learning models into combinatorial optimization to support prescriptive analytics and decision-making in high-complexity systems.Its framework includes decision variables, an encoded machine-learning model, observables, logical predicates, and a cost function.
  • Empirical model learning: Embedding neural networks and decision trees into combinatorial problems can use mixed-integer nonlinear programming, constraint programming, SAT Modulo Theories, and local search.The combinatorial structure and the embedded empirical model are represented separately in the formulation.
  • Bayesian-network structure learning: Bayesian-network structure learning represents variables as nodes and causal relations as directed edges in a directed acyclic graph.Restricting the network to bounded small tree width makes the structure-learning case computationally tractable but limits exact representation of the underlying data distribution.
  • Bayesian-network structure learning: The bounded-tree-width formulation maximizes a decomposable graph score while enforcing tree-width, acyclicity, variable relationships, and binary or bounded variable conditions.Parent sets are enumerated beforehand, and auxiliary variables enforce the structural constraints.

9 Conclusions

The survey frames machine learning training as large-scale optimization and identifies model-specific opportunities, limitations, and open problems across established and emerging paradigms. It emphasizes scalability, uncertainty, nonlinearity, and unresolved performance guarantees as central challenges.

  • The survey presents optimization models for regression, classification, clustering, deep learning, machine teaching, and empirical model learning.It also discusses adversarial learning and related emerging formulations.
  • Regression: Regression models address overfitting and uncertainty, but globally solving non-convex sparsity regularization remains computationally challenging.Tighter relaxations and exact solution approaches remain active research directions.
  • Classification: Classification optimization supports sparsity and uncertainty handling, while exploiting kernel tricks in sparse SVM models remains unclear.Robust and stochastic optimization approaches are being investigated for inaccurate data.
  • Clustering: Clustering formulations are generally hard-to-solve MINLPs because of non-convexity and large-scale instances, so heuristics are commonly used.Exact clustering approaches have received comparatively less attention.
  • Deep and adversarial learning: Deep-network optimization has mainly been demonstrated on relatively small datasets, while adversarial misclassification modeling and training-data uncertainty remain open problems.Adversarial robustness and data poisoning also involve bilevel or two-player formulations whose solution approaches remain under investigation.
  • Emerging directions: Further directions include tractable single-level machine-teaching formulations, prescriptive empirical model learning, and optimization-based hyperparameter selection.The survey also notes stochastic-gradient methods' role in large-scale learning and excludes a detailed review of numerical optimization techniques.
Loading 1901.05331v5…