Stackelberg Games with k-Submodular Function under Distributional Risk-Receptiveness and Robustness

\(\) We study submodular optimization in adversarial context, applicable to machine learning problems such as feature selection using data susceptible to uncertainties and attacks. We focus on Stackelberg games between an attacker (or interdictor) and a defender where the attacker aims to minimize the defender’s objective of maximizing a k-submodular function. We allow uncertainties arising … Read more

Exploiting Overlap Information in Chance-constrained Program with Random Right-hand Side

We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In … Read more

Optimization without Retraction on the Random Generalized Stiefel Manifold

\(\) Optimization over the set of matrices \(X\) that satisfy \(X^\top B X = I_p\), referred to as the generalized Stiefel manifold, appears in many applications involving sampled covariance matrices such as the canonical correlation analysis (CCA), independent component analysis (ICA), and the generalized eigenvalue problem (GEVP). Solving these problems is typically done by iterative … Read more

A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Set

The state-of-the-art methods for estimating high-dimensional covariance matrices all shrink the eigenvalues of the sample covariance matrix towards a data-insensitive shrinkage target. The underlying shrinkage transformation is either chosen heuristically – without compelling theoretical justification – or optimally in view of restrictive distributional assumptions. In this paper, we propose a principled approach to construct covariance … Read more

Subgradient Convergence Implies Subdifferential Convergence on Weakly Convex Functions: With Uniform Rates Guarantees

In nonsmooth, nonconvex stochastic optimization, understanding the uniform convergence of subdifferential mappings is crucial for analyzing stationary points of sample average approximations of risk as they approach the population risk. Yet, characterizing this convergence remains a fundamental challenge. This work introduces a novel perspective by connecting the uniform convergence of subdifferential mappings to that of subgradient … Read more

Multistage Stochastic Facility Location under Facility Disruption Uncertainty

We consider a multistage variant of the classical stochastic capacitated facility location problem under facility disruption uncertainty. Two solution algorithms for this problem class are presented: (1) stochastic dual dynamic integer programming (SDDiP), the state-of-the-art algorithm for solving multistage stochastic integer programs, and (2) shadow price approximation (SPA), an algorithm utilizing trained parameters of the … Read more

A computational study of cutting-plane methods for multi-stage stochastic integer programs

We report a computational study of cutting plane algorithms for multi-stage stochastic mixed-integer programming models with the following cuts: (i) Benders’, (ii) Integer L-shaped, and (iii) Lagrangian cuts. We first show that Integer L-shaped cuts correspond to one of the optimal solutions of the Lagrangian dual problem, and, therefore, belong to the class of Lagrangian … Read more

Applying random coordinate descent in a probability maximization scheme

Gradient computation of multivariate distribution functions calls for considerable effort. A standard procedure is component-wise computation, hence coordinate descent is an attractive choice. This paper deals with constrained convex problems. We apply random coordinate descent in an approximation scheme that is an inexact cutting-plane method from a dual viewpoint. We present convergence proofs and a … Read more

Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation

\(\) We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any stochastic gradient method which makes sufficient progress in expectation. The proof, which proceeds using the estimating sequences framework, applies to both convex and strongly convex functions and is easily specialized to … Read more

Similarity-based Decomposition Algorithm for Two-stage Stochastic Scheduling

This paper presents a novel decomposition method for two-stage stochastic mixed-integer optimization problems. The algorithm builds upon the idea of similarity between finite sample sets to measure how similar the first-stage decisions are among the uncertainty realization scenarios. Using such a Similarity Index, the non-anticipative constraints are removed from the problem formulation so that the … Read more