Optimization in Data Science

A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Data Science Algorithms, Nonlinear Optimization Tags , , , ,

    \(\) A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and the inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative … Read more

    Complexity of Adagrad and other first-order methods for nonconvex optimization problems with bounds constraints

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Data Science Algorithms, Nonlinear Optimization Tags , , , , ,

    A parametric class of trust-region algorithms for constrained nonconvex optimization is analyzed, where the objective function is never computed. By defining appropriate first-order stationarity criteria, we are able to extend the Adagrad method to the newly considered problem and retrieve the standard complexity rate of the projected gradient method that uses both the gradient and … Read more

    Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization

  • Xiangyu Yang
  • Hao Wang
    • Categories Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    \(\) This paper considers the problem of minimizing the sum of a smooth function and the Schatten-\(p\) norm of the matrix. Our contribution involves proposing accelerated iteratively reweighted nuclear norm methods designed for solving the nonconvex low-rank minimization problem. Two major novelties characterize our approach. Firstly, the proposed method possesses a rank identification property, enabling … Read more

    An Extended Validity Domain for Constraint Learning

  • Yilin Zhu
  • Samuel Burer
    • Categories Data Science Algorithms, Optimization in Data Science Tags , , , ,

    We consider embedding a predictive machine-learning model within a prescriptive optimization problem. In this setting, called constraint learning, we study the concept of a validity domain, i.e., a constraint added to the feasible set, which keeps the optimization close to the training data, thus helping to ensure that the computed optimal solution exhibits less prediction … Read more

    A mathematical introduction to SVMs with self-concordant kernel

  • Florian Jarre
    • Categories Data Science Algorithms, Data-Mining, Quadratic Programming Tags , ,

    A derivation of so-called “soft-margin Support Vector Machines with kernel” is presented which does not rely on concepts from functional analysis such as Mercer’s theorem that is frequently cited in this context, and that leads to a new analysis of the continuity properties of the kernel functions such as a new self-concordance condition for the … Read more

    Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances

  • Jie Wang
    • Categories Optimization in Data Science Tags , ,

    Optimal transport has been very successful for various machine learning tasks; however, it is known to suffer from the curse of dimensionality. Hence, dimensionality reduction is desirable when applied to high-dimensional data with low-dimensional structures. The kernel max-sliced (KMS) Wasserstein distance is developed for this purpose by finding an optimal nonlinear mapping that reduces data … Read more

    A graph-structured distance for mixed-variable domains with meta variables

  • Edward HallĂ©-Hannan
  • Charles Audet
  • Youssef Diouane
  • SĂ©bastien Le Digabel
  • Paul Saves
    • Categories Data Science Theory, Optimization in Data Science Tags , , ,

    Heterogeneous datasets emerge in various machine learning and optimization applications that feature different input sources, types or formats. Most models or methods do not natively tackle heterogeneity. Hence, such datasets are often partitioned into smaller and simpler ones, which may limit the generalizability or performance, especially if data is limited. The first main contribution of … Read more

    Mixed-Integer Linear Optimization for Cardinality-Constrained Random Forests

  • Jan Pablo Burgard
  • Maria Eduarda Pinheiro
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science Tags , , , ,

    Random forests are among the most famous algorithms for solving classification problems, in particular for large-scale data sets. Considering a set of labeled points and several decision trees, the method takes the majority vote to classify a new given point. In some scenarios, however, labels are only accessible for a proper subset of the given … Read more

    A Proximal-Gradient Method for Constrained Optimization

  • Daniel P. Robinson
  • Yutong Dai
  • Xiaoyi Qu
    • Categories Nonlinear Optimization, Optimization in Data Science Tags , , , , ,

    We present a new algorithm for solving optimization problems with objective functions that are the sum of a smooth function and a (potentially) nonsmooth regularization function, and nonlinear equality constraints. The algorithm may be viewed as an extension of the well-known proximal-gradient method that is applicable when constraints are not present. To account for nonlinear … Read more