PaperlayerView exact revision on arXiv

Source-linked AI summary

Mathematical Programming in Machine Learning and Artificial Intelligence: A Unified Taxonomy of Models and Applications

Chaosheng Dong

arXiv:2609.07254v1math.OCcs.AI

TL;DR

ML/AI predictions often feed decisions coupled by budgets, assignments, diversity, dynamics, or adversaries. This paper organizes those decisions across mathematical-programming paradigms and compares their modeling consequences, presenting mathematical programming as a disciplined interface between predictions and constrained decisions.

  • Problem

    ML/AI outputs often feed decisions coupled by budgets, assignments, diversity, dynamics, or adversaries, so the decision must account for constraints linking predictions to actions.

    Source: §1 · p. 1

  • Method

    The paper builds a taxonomy across mathematical-programming paradigms, normalizes application formulations, distinguishes their relationships to prior work, and compares computational properties.

    Source: §1 · p. 2

  • Results

    The cross-paradigm comparison identifies no universally preferable paradigm and notes that systems can combine approaches across prediction and decision stages.

    Source: §13 · p. 28

  • Takeaways & Limitations

    Mathematical programming makes explicit which guarantees survive when learned quantities enter constrained optimization models.

    Source: §1 · p. 1

    When inner learning is nonconvex, hypergradient procedures need not solve the global bilevel problem.

    Source: §7 · p. 19

Abstract

from arXiv · show

Mathematical programming provides a common language for many decisions embedded in modern machine-learning (ML) and artificial-intelligence (AI) systems: selecting retrieval context, routing tokens, allocating inference compute, fitting structured predictors, protecting against distribution shift, and balancing competing objectives. However, the relevant literature is fragmented across optimization, information retrieval, recommendation, natural-language processing, computer vision, and learning theory. This paper organizes various applications under common mathematical programming paradigms: linear, quadratic, binary and mixed-integer, conic, bilevel, multi-objective, inverse, distributionally robust, submodular, and min--max optimization. We normalize the models with a mostly unified notation and, for every application, identify inputs, decision variables, a principal formulation, structural properties, solution strategies, and limitations. Across paradigms, we compare tractability, relaxation quality, decomposition, approximation guarantees, and scalability bottlenecks. The paper shows that mathematical programming is most useful not as a claim that all learning is LP or MIP, but as a disciplined interface between predictions and constrained decisions.

1 Introduction

The paper frames mathematical programming as a way to make constraints coupling ML/AI predictions and decisions explicit. It organizes applications across optimization paradigms, standardizes their formulations, and compares their structural and computational properties.

1 Introduction

  • Mathematical programming makes explicit how budgets, assignments, diversity, dynamics, or adversaries couple predictions to decisions.The paper presents it as an interface between learned quantities and constrained decisions.Source: §1 · p. 1
  • The paper contributes a taxonomy, mostly unified formulations, distinctions among MP relationships, and a comparison of tractability, relaxations, decomposition, approximation, and scalability.It distinguishes explicit, equivalent, and natural reformulations, including cases where a formulation guides a heuristic rather than a solved program.Source: §1 · p. 2

2 Scope, Taxonomy, and Mathematical Programming Preliminaries

  • The paper's broad scope includes LP, QP, MIP, conic, bilevel, multi-objective, inverse, distributionally robust, submodular, and min–max optimization.These classes share explicit decisions, feasible sets, and objectives, without implying efficient reduction to LP or MIP.Source: §2 · p. 2
  • The paper distinguishes explicit formulations, mathematically equivalent formulations, and natural MP reformulations that translate an algorithm or system description without claiming the source solved that program.These labels clarify the relationship between each displayed model and its cited work.Source: §2 · p. 2

2.1 Taxonomy at a Glance

  • The taxonomy table organizes applications by paradigm, application, main decision variable, principal constraint or structure, representative citation, and MP relationship.The paper identifies Table 1 as its unified taxonomy.Source: §2.1 · pp. 2, 5

2.2 Unified Notation

  • Notation uses bold lowercase for vectors, bold uppercase for matrices, calligraphic letters for sets, and ordinary lowercase for scalars.Symbols may take specialized meanings when defined next to their equations.Source: §2.2 · p. 6

3 Linear Programming

The section presents linear programming as useful for continuous decisions and structured combinatorial models. It illustrates equivalent LP formulations for sparse recovery and integral network-flow optimization for multi-object tracking, while identifying the assumptions and structures that shape their use.

3 Linear Programming

  • LP is attractive for continuous learning-system decisions or integral combinatorial models with exact LP relaxations, offering global optimality certificates and mature decomposition methods.LP optimizes a linear objective subject to linear equalities and inequalities.Source: §3 · p. 6

3.1 Compressed Sensing

  • Basis pursuit reconstructs a signal consistent with linear measurements by minimizing its ℓ1 norm, with auxiliary-variable bounds yielding an equivalent LP that encourages sparsity.LP optimality alone does not establish statistical identifiability; exact sparsest-signal recovery depends on conditions on the sensing matrix.Source: §3.1 · p. 6

3.2 LP with Network-Flow Structure

  • Multi-object tracking represents detection use, transitions, source flow, and sink flow in a min-cost network-flow model that constructs a specified number of trajectories.Flow conservation and unit capacities constrain detection participation.Source: §3.2 · p. 6, §3.2.1 · pp. 6–8
  • With integral supplies and capacities, the network-flow incidence matrix is totally unimodular, so an extreme optimal LP solution is integral.General pairwise exclusions or higher-order occlusion constraints can destroy this property.Source: §3.2.1 · p. 8
  • Successive shortest paths, network simplex, specialized graph algorithms, and generic LP solvers can solve the flow model, which presumes calibrated local costs, a chosen transition graph, and fixed track count.Long-range interactions, identity ambiguity, and detection errors are represented only through supplied arcs and costs.Source: §3.2.1 · p. 8

4 Quadratic Programming

This section surveys quadratic-programming formulations for constrained decisions across learning and AI, spanning reconstruction, resource allocation, prediction, retrieval, recommendation, clustering, and video-frame selection. It covers how Hessian curvature determines convexity, the global-solution challenges of exact clustering formulations, and frame selection under compute and temporal constraints.

4.1 Local Reconstruction Weights in Locally Linear Embedding

  • LLE’s convex, observation-wise QP learns neighborhood reconstruction weights with sum-to-one invariance; KKT systems solve each problem, though fixed neighborhoods and singular covariance can limit reliability.Diagonal regularization can stabilize nearly singular neighborhoods, and parallel solution across observations is immediate.Source: §4 · p. 8, §4.1 · p. 9

5.1 RAG Context Selection under a Token Budget

  • RAG context selection is an NP-hard multidimensional multiple-choice knapsack: Pareto-pruned dynamic programming is one approach, but additive utilities may miss passage interactions [25].The model treats estimated evidential value as additive and enforces resource budgets and group-choice constraints.Source: §5.1 · pp. 9–10

5.2 Mixture-of-Experts Routing

  • Mixture-of-experts routing is a capacitated bipartite assignment; pure transportation structure gives an integral LP relaxation, while production routers often use top-k or local balancing.Expert-choice routing fixes expert bucket sizes while allowing heterogeneous token multiplicity.Source: §5.2 · p. 10

5.3 Tool or Agent-Component Selection; 5.5 Test-Time Reasoning and Exploration-Budget Allocation

  • Agent-component selection and test-time compute allocation are knapsack-style BIPs that trade predicted utility against costs or budgets, with noisy estimates and omitted interactions limiting their scope.Agent choices can include incompatibility and prerequisite constraints; compute allocation assigns one inference level per query under a batch-wide budget.Source: §5.3 · pp. 10–11, §5.5 · p. 12

5.4 Notification/Email Allocation and Frequency Optimization

  • Notification allocation is a large BIP coupling user-frequency limits, campaign quotas, and shared budgets; distributed and primal–dual methods can scale it, but are not universally exact.The model abstracts additive predicted effects and omits causal carryover, fatigue, content safety, and consent semantics.Source: §5.4 · p. 12

5.6 Optimal Decision-Tree Construction; 5.7 Best Subset Selection

  • Optimal-tree MILPs jointly choose splits and predictions, while best-subset selection is a convex MIQP whose binary feature choices make the full problem nonconvex.Big-M constraints can weaken relaxations in both settings; solver bounds, rather than heuristic incumbents alone, certify global gaps for subset selection.Source: §5.6 · pp. 13–14, §5.7 · p. 14

5.8 Constrained Maximum-Inner-Product Retrieval; 5.10 Diversity-Aware Recommendation

  • Constrained MIPS uses binary selection for fairness or coverage bounds, while diversity-aware recommendation adds pairwise similarity penalties, producing binary quadratic models.The retrieval model optimizes only over supplied candidates; recommendation’s scalar trade-off parameter may obscure user-specific preferences.Source: §5.8 · pp. 14–15, §5.10 · p. 16

5.9 Mixed-Precision Neural-Network Quantization; 5.11 Globally Optimized 𝑘-Means or Minimum Sum-of-Squares Clustering

  • Mixed-precision quantization uses a multiple-choice multidimensional integer program for layerwise resource budgets, while global k-means models jointly assign observations and estimate centroids [27].Layerwise sensitivity proxies neglect cross-layer interactions; the supplied k-means passage introduces a mixed-integer quadratic-constraint formulation and its assignment interpretation.Source: §5.9 · p. 15, §5.11 · pp. 16–17

5.11 Globally Optimized 𝑘-Means or Minimum Sum-of-Squares Clustering

  • Globally optimized k-means may be a MINLP or, with valid bounds and reformulations, a convex quadratic-constraint, MIQP, or MILP model,.Spatial branch-and-bound, branch-and-cut, symmetry breaking, bound tightening, relaxations, and local-clustering incumbents support solution, but global certification remains difficult.Source: §5.11 · p. 17
  • Global clustering methods scale to far smaller instances than local heuristics, while squared Euclidean distance favors spherical clusters and outliers can dominate.The number of clusters K is fixed.Source: §5.11 · p. 17

5.12 Video Frame or Keyframe Selection

  • Video keyframe selection balances query relevance and diversity under a frame budget, using an NP-hard integer quadratic model that can be linearized or approximated.MILP linearization adds an auxiliary product variable per retained pair; sparsifying similarities reduces memory and solve time, while greedy search, local swaps, temporal segmentation, and candidate pruning support longer videos. Framewise relevance may miss actions requiring temporal context; pairwise redundancy does not ensure narrative continuity, and generated narratives can introduce unmodeled errors.Source: §5.12 · p. 17

6 Conic Programming

Conic programming represents convex constraints through cone membership; the section applies SOCPs to group sparsity and SDPs to sparse PCA. These formulations expose tractable relaxations and scalable alternatives, but each has practical limits.

6 Conic Programming

  • Conic programs optimize linear objectives over linear constraints and convex-cone membership, with SOCPs modeling norm epigraphs and SDPs modeling positive-semidefinite constraints.Conic duality supplies strong bounds, while generic SDP scaling is less favorable than LP or SOCP scaling.Source: §6 · p. 18

6.1 Group Lasso as SOCP

  • Group Lasso uses an equivalent convex SOCP whose group-norm constraints induce block sparsity without integrality.Interior-point solvers suit moderate scale; block coordinate descent, proximal gradient, and screening exploit separability for larger designs. Specified groups can over-shrink large or correlated groups, and overlap or hierarchy requires additional variables.Source: §6.1 · p. 18

6.2 Sparse PCA as SDP

  • Sparse PCA maximizes explained variance under a sparsity budget; dropping rank one yields an SDP upper bound, but its solution may not be rank one.Eigenvector or randomized rounding recovers an approximate loading; the d × d lift has quadratic storage, and noisy covariance estimates can dominate optimization guarantees.Source: §6.2 · p. 19

7 Bilevel Programming

Bilevel programming nests an inner optimization under an outer objective, as in model training or candidate search followed by validation or evaluation. The applications range from hyperparameter and architecture search to data selection, scientific discovery, and diffusion tuning, with nonconvexity and approximation limiting guarantees.

7 Bilevel Programming

  • Bilevel programming nests an inner optimization within an outer one; nonunique inner solutions create optimistic and pessimistic conventions, and nonconvex inner learning can prevent hypergradient procedures from solving the global problem.Hypergradients may use unrolling, implicit differentiation, or approximation.Source: §7 · p. 19

7.1 Hyperparameter Optimization

  • Hyperparameter optimization trains with proposed settings at the inner level and measures held-out performance at the outer level, but validation reuse and approximate inner training limit reliability.Hypergradient quality depends on optimizer dynamics, stopping rules, and Hessian approximations.Source: §7.1 · pp. 19–20

7.2 Neural Architecture Search

  • Neural architecture search relaxes discrete operation choices into continuous simplex weights, but the relaxed optimum may differ from the discretized architecture.Weight sharing biases architecture comparisons, and selected designs require retraining for independent evaluation.Source: §7.2 · p. 20

7.3 Coreset Selection and Data Subsampling

  • Coreset selection uses probabilistic sample weights to define inner training data under an expected-size constraint, but the realized subset is not guaranteed to be high quality.Unbiased score-function gradients can have high variance, and repeated inner training is expensive.Source: §7.3 · p. 21

7.4 Autonomous Scientific Discovery and AI Scientist Systems

  • Autonomous scientific discovery can be represented as an outer loop revising a criterion and an inner loop searching candidates, but this need not be conventional differentiable bilevel optimization.Scientific objectives may be incomplete proxies, simulators misspecified, and experiments costly; solver convergence applies only to the solved subproblem, not open-ended scientific validity.Source: §7.4 · pp. 21–22

7.5 Diffusion-Model Hyperparameter and Noise-Schedule Optimization

  • Diffusion schedule optimization trains a denoiser inside and scores generated validation samples or a quality surrogate outside, while stochastic iterative sampling makes implicit differentiation costly.Finite-sample and finite-inner-work approximations can be used, and an optimized schedule may not transfer across data distributions, samplers, or compute budgets.Source: §7.5 · p. 22

8 Multi-Objective Optimization

Multi-objective optimization retains competing objectives rather than collapsing them immediately into one scalar. In multi-task learning, a small convex QP combines task gradients to seek a common descent direction, but one trajectory does not describe the full Pareto front.

8 Multi-Objective Optimization

  • Multi-objective optimization uses dominance and Pareto stationarity instead of a unique total order, with scalarization or common-descent subproblems providing computational steps.In multi-task learning, a nonzero minimum-norm convex combination of task gradients gives a common descent direction, while zero indicates first-order Pareto stationarity under standard regularity.Source: §8 · p. 22, §8.1 · p. 23

8.1 Multi-Task Learning

  • Multi-task learning combines task losses through a common parameterization, and its common-descent subproblem is a convex QP in the number of tasks, even for large parameter dimension.One QP yields one Pareto-stationary trajectory, not the entire Pareto front; stationarity is not global Pareto optimality in nonconvex models, and gradient scales influence trade-offs.Source: §8.1 · pp. 22–23

9 Inverse Optimization

Inverse optimization infers objective parameters that make observed decisions optimal or nearly optimal, with identifiability central because many objectives can explain the same behavior. In inverse reinforcement learning, a soft-margin Bellman QP encodes demonstrated policy optimality, but reward ambiguity and imperfect demonstrations constrain interpretation.

9 Inverse Optimization

  • Inverse optimization infers objective parameters that rationalize observed decisions, but many objectives may explain the same behavior, making identifiability central.The inferred reward in inverse reinforcement learning may be nonidentifiable up to transformations, and inferred intent need not match ethically acceptable goals.Source: §9 · p. 23, §9.1 · p. 24

9.1 Inverse Reinforcement Learning

  • Inverse reinforcement learning can use a convex QP with linear Bellman inverse-optimality constraints, asking demonstrated actions to beat alternatives by a unit margin softened by slack variables.Regularization selects among scale-ambiguous rewards; approximate dynamics and large state spaces require sampling or function approximation.Source: §9.1 · p. 24

10 Distributionally Robust Optimization

Distributionally robust optimization models decisions against probability laws near an empirical distribution, with the ambiguity set determining which shifts are protected. The section applies this approach to contrastive learning and LLM preference alignment, while noting that robustness depends on the chosen ambiguity geometry and its fit to the target shift.

10 Distributionally Robust Optimization

  • The ambiguity set determines which distribution shifts are protected, and duality can replace the inner distribution problem with a finite-dimensional regularized loss.Divergence balls reweight probability, whereas Wasserstein balls transport probability mass.Source: §10 · p. 24

10.1 Contrastive Learning as DRO

  • Contrastive DRO upweights challenging negatives within a divergence neighborhood, but large sets can emphasize false negatives and finite-batch dual estimates can be biased or unstable.The radius controls conservatism; neural dependence makes the outer problem nonconvex, so representative approaches include adversarial reweighting and stochastic gradient descent–ascent.Source: §10.1 · p. 25

10.2 Distributionally Robust DPO for LLM Alignment

  • DRO for DPO concentrates on high-loss preference examples under a chosen divergence or transport ambiguity set, with KL reweighting and Wasserstein geometric movement.Dual approximations and stochastic gradients support scalable approximate minimax optimization; Xu et al. develop Wasserstein DPO and KL-DPO and derive scalable approximations.Source: §10.2 · p. 25
  • Preference-label errors, a mismatched transport cost, or conservatism that reduces average utility limit what robust DPO can protect; robustness to represented shifts is not universal alignment.The protected shift depends on the ambiguity set, not only its radius.Source: §10.2 · p. 25

11 Submodular Optimization

Submodular optimization represents selection problems where additional choices can have diminishing returns, enabling approximation guarantees under stated constraints. The section applies this structure to data selection, document summarization, and dynamic KV-cache eviction, while emphasizing that guarantees concern the modeled objective and assumptions.

11 Submodular Optimization

  • For normalized monotone submodular maximization under a cardinality constraint, greedy selection achieves 1 − 1/e of the optimum; other constraints require different guarantees.Submodularity means diminishing returns: adding an item gives at least as much gain to a smaller set as to a larger one.Source: §11 · p. 26

11.1 Data Subset Selection and Active Learning

  • Facility-location selection credits each data point through its most similar selected representative, and greedy achieves a 1 − 1/e guarantee under nonnegative similarities and a cardinality constraint.The guarantee concerns the chosen set function, not downstream test accuracy; similarity and uncertainty calibration constrain what the selection represents.Source: §11.1 · p. 26

11.2 Document Summarization

  • Budgeted summarization combines concept coverage with topic diversity under sentence-length costs, forming a monotone submodular objective for which modified greedy or enumeration methods have constant-factor guarantees under appropriate assumptions.The guarantee does not prevent incoherent extracted sentences, missed factual dependencies, or redundancy beyond the selected features.Source: §11.2 · p. 27

11.3 KV-Cache Eviction for LLM Inference

  • Dynamic KV-cache eviction balances historical attention heavy hitters with a reserved recent window, allowing at most the arriving token to enter under the cache budget.Greedy eviction is not static top-k: scores and feasible candidates evolve, and attention-score collection can offset memory savings; past attention may not predict future need.Source: §11.3 · p. 27

12 Min–Max and Saddle-Point Optimization

Min–max optimization models strategic or adversarial interaction, but neural games are generally nonconvex–nonconcave and lack the guarantees available for convex–concave games. GANs instantiate this structure as generator–discriminator training, with practical updates that are not exact saddle solvers.

12 Min–Max and Saddle-Point Optimization

  • Convex–concave games admit strong saddle theory, whereas neural games are usually nonconvex–nonconcave and alternating gradients can cycle or lack equilibrium guarantees.These limitations qualify the use of min–max optimization for strategic or adversarial interactions.Source: §12 · p. 28

12.1 Generative Adversarial Networks

  • In the ideal unrestricted GAN game, the generated law matches the data law and the discriminator outputs one half, but neural parameterizations remove classical minimax and global-convergence guarantees.Alternating stochastic gradients and related updates address numerical behavior as practical game-optimization methods, not exact saddle solvers.Source: §12.1 · p. 28

13 Cross-Paradigm Comparison and Practical Considerations

The comparison treats mathematical-programming paradigms as modeling choices rather than universally ranked alternatives. It connects formulation and guarantees to estimated inputs, relaxations, decomposition opportunities, scale, and the decision being made.

13 Cross-Paradigm Comparison and Practical Considerations

  • Table 3 compares modeling consequences rather than declaring one paradigm universally preferable; a system can cross paradigms, such as training with DRO and consuming predictions in an MILP.An SDP can bound a discrete model, while a Lagrangian dual can decompose a BIP into per-request decisions.Source: §13 · p. 28

13.1 From Predictions to Coefficients

  • Optimization treats estimated scores, sensitivities, costs, and similarities as data, so biased or shifted coefficients can still yield poor decisions even with a perfect solver.Calibration, uncertainty sets, causal evaluation, and post-decision monitoring are part of the optimization pipeline.Source: §13.1 · p. 28

13.2 Relaxations, Certificates, and Approximation

  • LP and SDP relaxations provide bounds rather than necessarily deployable or optimal recovered decisions, while submodular guarantees apply to the specified set function rather than validating its proxy for human utility.For nonconvex bilevel and min–max learning, a stationary point is weaker than a global certificate.Source: §13.2 · pp. 28–29

13.3 Decomposition and Scale

  • Lagrangian multipliers turn shared budgets into prices that expose parallel subproblems, while column generation helps when feasible actions are numerous.Retrieval candidate generation is indispensable, but its recall ceiling is distinct from the optimizer’s gap on the reduced set.Source: §13.3 · pp. 29–30

13.4 Choosing a Formulation

  • Choose a formulation from the decision and guarantee required: use MIP for logical feasibility and certificates at manageable scale, and convex representations when their geometry is useful.The paper also recommends network LP for genuine incidence structure, bilevel models for conditional learned responses, DRO for distributional uncertainty, submodularity for diminishing-return coverage, and min–max models for opposed players.Source: §13.4 · p. 30

14 Research Challenges and Opportunities

The section identifies challenges in propagating uncertainty and differentiating through optimization, alongside needs for scalable certificates and dynamic formulations. It also calls for outcome-grounded diversity and fairness, auditable agentic optimization, and benchmarks that isolate sources of error.

14 Research Challenges and Opportunities

  • Uncertainty in relevance, cost, and response models must reach decisions without making robust formulations unusably conservative.Source: §14 · p. 30
  • End-to-end learning needs gradients through discrete or approximate solvers while managing discontinuity, bias, memory, tolerances, and feasibility.Source: §14 · p. 30
  • Billions of candidate actions motivate decompositions, learned primal heuristics, safe screening, and distributed bounds, with exact pruning protected from heuristic invalidation.Source: §14 · p. 30
  • Nonstationary systems need online or dynamic formulations with regret or stability guarantees aligned to feedback loops, since actions can change future data, preferences, or goals.Source: §14 · p. 30
  • Diversity and fairness proxies such as similarity, quotas, and coverage need links to user outcomes, intersectional constraints, and causal exposure effects while remaining scalable.Source: §14 · p. 30
  • Agentic optimization calls for versioned objectives, constraint provenance, solver status, and approximation traces, with provenance and safety conditions modeled as constraints.Source: §14 · p. 30
  • Benchmarks should separate coefficient error, candidate-generation loss, relaxation and optimization gaps, and execution drift because final task quality alone obscures failure sources.Source: §14 · p. 30
Loading 2609.07254v1…