## Submodular maximization and its generalization through an intersection cut lens

 We study a mixed-integer set $$\mathcal{S}:=\{(x,t) \in \{0,1\}^n \times \mathbb{R}: f(x) \ge t\}$$ arising in the submodular maximization problem, where $$f$$ is a submodular function defined over $$\{0,1\}^n$$. We use intersection cuts to tighten a polyhedral outer approximation of $$\mathcal{S}$$. We construct a continuous extension $$\mathsf{F}$$ of $$f$$, which is convex and defined over … Read more

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

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

## Relatively-Smooth Convex Optimization by First-Order Methods, and Applications

The usual approach to developing and analyzing first-order methods for smooth convex optimization assumes that the gradient of the objective function is uniformly smooth with some Lipschitz constant L. However, in many settings the differentiable convex function f(.) is not uniformly smooth — for example in D-optimal design where f(x):=-ln det(HXH^T), or even the univariate … Read more

## Duality of ellipsoidal approximations via semi-infinite programming

In this work, we develop duality of the minimum volume circumscribed ellipsoid and the maximum volume inscribed ellipsoid problems. We present a unified treatment of both problems using convex semi–infinite programming. We establish the known duality relationship between the minimum volume circumscribed ellipsoid problem and the optimal experimental design problem in statistics. The duality results … Read more