Optimization in Data Science

Decentralized Stochastic Bilevel Optimization with Improved Per-Iteration Complexity

  • Xuxing Chen
  • Minhui Huang
  • Shiqian Ma
  • Krishnakumar Balasubramanian
    • Categories Nonlinear Optimization, Optimization in Data Science, Stochastic Programming

    Bilevel optimization recently has received tremendous attention due to its great success in solving important machine learning problems like meta learning, reinforcement learning, and hyperparameter optimization. Extending single-agent training on bilevel problems to the decentralized setting is a natural generalization, and there has been a flurry of work studying decentralized bilevel optimization algorithms. However, it … Read more

    Wasserstein Regularization for 0-1 Loss

  • Rui Gao
    • Categories Data Science Theory, Robust Optimization, Stochastic Programming

    Wasserstein distributionally robust optimization (DRO) finds robust solutions by hedging against data perturbation specified by distributions in a Wasserstein ball. The robustness is linked to the regularization effect, which has been studied for continuous losses in various settings. However, existing results cannot be simply applied to the 0-1 loss, which is frequently seen in uncertainty … Read more

    Decision-making with Side Information: A Causal Transport Robust Approach

  • Jincheng Yang
  • Luhao Zhang
  • Ningyuan Chen
  • Rui Gao
  • Ming Hu
    • Categories Optimization in Data Science, Robust Optimization, Stochastic Programming Tags , , ,

    We consider stochastic optimization with side information where, prior to decision making, covariate data are available to inform better decisions. In particular, we propose to consider a distributionally robust formulation based on causal transport distance. Compared with divergence and Wasserstein metric, the causal transport distance is better at capturing the information structure revealed from the conditional distribution … Read more

    Behind the Scenes of Gradient Descent: A Trajectory Analysis via Basis Function Decomposition

  • Jianhao Ma
  • Lingjun Guo
  • Salar Fattahi
    • Categories Optimization in Data Science

    This work analyzes the solution trajectory of gradient-based algorithms via a novel basis function decomposition. We show that, although solution trajectories of gradient-based algorithms may vary depending on the learning task, they behave almost monotonically when projected onto an appropriate orthonormal function basis. Such projection gives rise to a basis function decomposition of the solution … Read more

    Sparse PCA With Multiple Components

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Data Science Theory, Data-Mining, Semi-definite Programming

    Sparse Principal Component Analysis (sPCA) is a cardinal technique for obtaining combinations of features, or principal components (PCs), that explain the variance of high-dimensional datasets in an interpretable manner. This involves solving a sparsity and orthogonality-constrained convex maximization problem, which is extremely computationally challenging. Most existing works address sparse PCA via methods—such as iteratively computing … Read more

    Fixed-Point Automatic Differentiation of Forward–Backward Splitting Algorithms for Partly Smooth Functions

  • Sheheryar Mehmood
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

    A large class of non-smooth practical optimization problems can be written as minimization of a sum of smooth and partly smooth functions. We consider such structured problems which also depend on a parameter vector and study the problem of differentiating its solution mapping with respect to the parameter which has far reaching applications in sensitivity … Read more

    On polynomial time solvability of combinatorial Markov random fields

  • Shaoning Han
  • Andrés Gómez
  • Jong-Shi Pang
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Applications

    The problem of inferring Markov random fields (MRFs) with a sparsity or robustness prior can be naturally modeled as a mixed-integer program. This motivates us to study a general class of convex submodular optimization problems with indicator variables, which we show to be polynomially solvable in this paper. The key insight is that, possibly after … Read more

    Optimized convergence of stochastic gradient descent by weighted averaging

  • Melinda Hagedorn
  • Florian Jarre
    • Categories Convex Optimization, Data Science Theory, Stochastic Approaches Tags , , , , ,

    Under mild assumptions stochastic gradient methods asymptotically achieve an optimal rate of convergence if the arithmetic mean of all iterates is returned as an approximate optimal solution. However, in the absence of stochastic noise, the arithmetic mean of all iterates converges considerably slower to the optimal solution than the iterates themselves. And also in the … Read more

    Submodularity, pairwise independence and correlation gap

  • Arjun Ramachandra
  • Karthik Natarajan
    • Categories Optimization in Data Science, Robust Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we provide a characterization of the expected value of monotone submodular set functions with $n$ pairwise independent random inputs. Inspired by the notion of “correlation gap”, we study the ratio of the maximum expected value of a function with arbitrary dependence among the random inputs with given marginal probabilities to the maximum … Read more

    A Simplified Convergence Theory for Byzantine Resilient Stochastic Gradient Descent

  • Lindon Roberts
    • Categories Optimization in Data Science, Stochastic Programming Tags , ,

    In distributed learning, a central server trains a model according to updates provided by nodes holding local data samples. In the presence of one or more malicious servers sending incorrect information (a Byzantine adversary), standard algorithms for model training such as stochastic gradient descent (SGD) fail to converge. In this paper, we present a simplified … Read more