Optimization in Data Science

Almost-sure convergence of iterates and multipliers in stochastic sequential quadratic optimization

  • Frank E. Curtis
  • Xin Jiang
  • Qi Wang
    • Categories Constrained Nonlinear Optimization, Data Science Applications, Stochastic Programming Tags , , ,

    Stochastic sequential quadratic optimization (SQP) methods for solving continuous optimization problems with nonlinear equality constraints have attracted attention recently, such as for solving large-scale data-fitting problems subject to nonconvex constraints. However, for a recently proposed subclass of such methods that is built on the popular stochastic-gradient methodology from the unconstrained setting, convergence guarantees have been … Read more

    Solution Path of Time-varying Markov Random Fields with Discrete Regularization

  • Salar Fattahi
  • Andrés Gómez
    • Categories Dynamic Programming, Integer Programming, Optimization in Data Science

    \(\) We study the problem of inferring sparse time-varying Markov random fields (MRFs) with different discrete and temporal regularizations on the parameters. Due to the intractability of discrete regularization, most approaches for solving this problem rely on the so-called maximum-likelihood estimation (MLE) with relaxed regularization, which neither results in ideal statistical properties nor scale to … Read more

    Inexact Direct-Search Methods for Bilevel Optimization Problems

  • Youssef Diouane
  • Vyacheslav Kungurtsev
  • Francesco Rinaldi
  • Damiano Zeffiro
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization in Data Science

    In this work, we introduce new direct search schemes for the solution of bilevel optimization (BO) problems. Our methods rely on a fixed accuracy black box oracle for the lower-level problem, and deal both with smooth and potentially nonsmooth true objectives. We thus analyze for the first time in the literature direct search schemes in … Read more

    Structured Pruning of Neural Networks for Constraints Learning

  • Matteo Cacciola
  • Andrea Lodi
  • Antonio Frangioni
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Optimization in Data Science Tags , ,

    In recent years, the integration of Machine Learning (ML) models with Operation Research (OR) tools has gained popularity across diverse applications, including cancer treatment, algorithmic configuration, and chemical process optimization. In this domain, the combination of ML and OR often relies on representing the ML model output using Mixed Integer Programming (MIP) formulations. Numerous studies … Read more

    Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recovery

  • Lijun Ding
  • Alex L. Wang
    • Categories Nonsmooth Optimization, Optimization in Data Science, Statistics Tags , , , , ,

    \(\) We study a sample complexity vs. conditioning tradeoff in modern signal recovery problems where convex optimization problems are built from sampled observations. We begin by introducing a set of condition numbers related to sharpness in \(\ell_p\) or Schatten-p norms (\(p\in[1,2]\)) based on nonsmooth reformulations of a class of convex optimization problems, including sparse recovery, … Read more

    Shattering Inequalities for Learning Optimal Decision Trees

  • Justin Boutilier
  • Carla Michini
  • Zachary Zhou
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science

    Recently, mixed-integer programming (MIP) techniques have been applied to learn optimal decision trees. Empirical research has shown that optimal trees typically have better out-of-sample performance than heuristic approaches such as CART. However, the underlying MIP formulations often suffer from weak linear programming (LP) relaxations. Many existing MIP approaches employ big-M constraints to ensure observations are … Read more

    Stability-Adjusted Cross-Validation for Sparse Linear Regression

  • Ryan Cory-Wright
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms

    Given a high-dimensional covariate matrix and a response vector, ridge-regularized sparse linear regression selects a subset of features that explains the relationship between covariates and the response in an interpretable manner. To select the sparsity and robustness of linear regressors, techniques like k-fold cross-validation are commonly used for hyperparameter tuning. However, cross-validation substantially increases the … Read more

    A new upper bound of the Euclidean TSP constant

  • Julien Yu
  • John Carlsson
    • Categories Data Science Applications, Transportation Tags , ,

    Let X1, X2, . . . , Xn be n independent and uniformly distributed random points in a compact region R ⊂ R2 of area 1. Let TSP(X1, . . . , Xn) denote the length of the optimal Euclidean traveling salesman tour that traverses all these points. The classical Beardwood-Halton-Hammersley theorem proves the existence … Read more

    Nonlinear Distributionally Robust Optimization

  • Rayyan
  • Peyman Mohajerin Esfahani
    • Categories Infinite Dimensional Optimization, Optimization in Data Science, Robust Optimization Tags , ,

    This article focuses on a class of distributionally robust optimization (DRO) problems where, unlike the growing body of the literature, the objective function is potentially non-linear in the distribution. Existing methods to optimize nonlinear functions in probability space use the Frechet derivatives, which present both theoretical and computational challenges. Motivated by this, we propose an … Read more