Data-Mining

A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization

  • Stephen Wright
  • Cong Han Lim
  • Ching-pei Lee
    • Categories Data-Mining, Nonlinear Optimization, Parallel Algorithms Tags , , , , , , ,

    We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving ERM problems with a nonsmooth regularization term. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or work only for specific regularizers. Our algorithm uses successive quadratic approximations, and we describe how to … Read more

    Cut-Pursuit Algorithm for Regularizing Nonsmooth Functionals with Graph Total Variation

  • Landrieu Loïc
  • Hugo Raguet
    • Categories Biomedical Applications, Data-Mining, Nonsmooth Optimization

    We present an extension of the cut-pursuit algorithm, introduced by Landrieu and Obozinski (2017), to the graph total-variation regularization of functions with a separable nondifferentiable part. We propose a modified algorithmic scheme as well as adapted proofs of convergence. We also present a heuristic approach for handling the cases in which the values associated to … Read more

    Smart “Predict, then Optimize”

  • Adam N. Elmachtoub
  • Paul Grigas
    • Categories Applications - OR and Management Sciences, Data-Mining, Statistics

    Many real-world analytics problems involve two significant challenges: prediction and optimization. Due to the typically complex nature of each challenge, the standard paradigm is to predict, then optimize. By and large, machine learning tools are intended to minimize prediction error and do not account for how the predictions will be used in a downstream optimization … Read more

    Forecasting Solar Flares using magnetogram-based predictors and Machine Learning

  • Federico Benvenuto
  • Manolis K. Georgoulis
  • D. Shaun Bloomfield
  • Kostas Florios
  • Jordan A. Guerra
  • Ioannis Kontogiannis
  • Sung-Hong Park
    • Categories Basic Sciences Applications, Data-Mining, Statistics Tags ,

    We propose a forecasting approach for solar flares based on data from Solar Cycle 24, taken by the Helioseismic and Magnetic Imager (HMI) on board the Solar Dynamics Observatory (SDO) mission. In particular, we use the Space-weather HMI Active Region Patches (SHARP) product that facilitates cut-out magnetograms of solar active regions (AR) in the Sun … Read more

    Approximate Positively Correlated Distributions and Approximation Algorithms for D-optimal Design

  • Mohit Singh
  • Weijun Xie
    • Categories Approximation Algorithms, Data-Mining Tags , , ,

    Experimental design is a classical problem in statistics and has also found new applications in machine learning. In the experimental design problem, the aim is to estimate an unknown vector x in m-dimensions from linear measurements where a Gaussian noise is introduced in each measurement. The goal is to pick k out of the given … Read more

    Sparse principal component analysis and its l1-relaxation

  • Santanu S. Dey
  • Rahul Mazumder
  • Marco Molinaro
  • Guanyi Wang
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining

    Principal component analysis (PCA) is one of the most widely used dimensionality reduction methods in scientific data analysis. In many applications, for additional interpretability, it is desirable for the factor loadings to be sparse, that is, we solve PCA with an additional cardinality (l0) constraint. The resulting optimization problem is called the sparse principal component … Read more

    Weak Stability of $\ell_1hBcminimization Methods in Sparse Data Reconstruction

  • H. Jiang
  • Zhi-Quan Luo
  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization, Data-Mining, Linear Programming Tags , , , , ,

    As one of the most plausible convex optimization methods for sparse data reconstruction, $\ell_1$-minimization plays a fundamental role in the development of sparse optimization theory. The stability of this method has been addressed in the literature under various assumptions such as restricted isometry property (RIP), null space property (NSP), and mutual coherence. In this paper, … Read more

    Estimating L1-Norm Best-Fit Lines for Data

  • J. Paul Brooks
  • JH Dulá
    • Categories Applications - OR and Management Sciences, Data-Mining, Statistics Tags , , ,

    The general formulation for finding the L1-norm best-fit subspace for a point set in $m$-dimensions is a nonlinear, nonconvex, nonsmooth optimization problem. In this paper we present a procedure to estimate the L1-norm best-fit one-dimensional subspace (a line through the origin) to data in $\Re^m$ based on an optimization criterion involving linear programming but which … Read more

    Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Kilian Schindler
  • Wolfram Wiesemann
    • Categories Approximation Algorithms, Data-Mining, Linear, Cone and Semidefinite Programming Tags , , ,

    Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset. We cast this problem as a mixed-integer … Read more

    Decomposition Algorithms for Distributionally Robust Optimization using Wasserstein Metric

  • Fengqiao Luo
  • Sanjay Mehrotra
    • Categories Data-Mining, Robust Optimization, Semi-infinite Programming Tags , , , ,

    We study distributionally robust optimization (DRO) problems where the ambiguity set is de ned using the Wasserstein metric. We show that this class of DRO problems can be reformulated as semi-in nite programs. We give an exchange method to solve the reformulated problem for the general nonlinear model, and a central cutting-surface method for the convex case, … Read more