Many machine learning problems can be naturally expressed as minimizing the difference of two submodular (DS) functions. Via the Lovász extension, it is well known that minimizing a DS function can be equivalently formulated as minimizing the difference of two convex (DC) functions. While DS minimization has developed theory and algorithms in its own right, it has yet to fully exploit the rich theory and effective algorithms offered by DC programming. To this end, we introduce variants of the well-known DCA (difference of convex functions algorithm) which can be applied to DS minimization. Our results using DCA match the theoretical guarantees satisfied by existing DS algorithms, while providing a more complete characterization of convergence properties. Moreover, numerical results show that our proposed algorithms outperform existing baselines on two applications: speech corpus selection and feature selection.

I will present the framework of slowly varying regression under sparsity, allowing sparse regression models to exhibit slow and sparse variations, through an application in energy consumption prediction. First, I will formulate the problem of parameter estimation as a mixed-integer optimization problem; then, I will demonstrate that it can be precisely reformulated as a binary convex optimization problem through a novel relaxation technique, convexifying the non-convex objective function while matching the original objective on all feasible binary points. I will develop a highly optimized implementation of a cutting plant-type algorithm, a fast regularization-based heuristic method that guarantees a feasible solution, and a practical hyperparamrter tuning procedure relying on binary search that, under certain assumptions, is guaranteed to recover the true model parameters.

We define an online learning and optimization problem that aims to achieve a target coverage level by the end of a finite horizon. At each period, a decision-maker can open new facilities, receives information on the success of each one, and can then update a classification machine learning model to guide future facility location decisions. Irreversible facility opening decisions give rise to an exploration-exploitation trade-off with commitment. We derive an optimal algorithm and a tight lower bound in an asymptotic regime characterized by a large target number of facilities $m\to\infty$ but a fixed planning horizon $T\in\Z_+$. We find that the regret grows sub-linearly at a rate $\Theta\left(m^{\frac{1}{2}\cdot\frac{1}{1-2^{-T}}}\right)$, and therefore converges exponentially fast to $\Theta(\sqrt{m})$ as $T$ increases. These results highlight the benefits of even a few rounds of online learning and optimization, as compared to a no-learning baseline that achieves linear regret. We establish the robustness of these insights in settings with offline data, with imperfect learning, with continuous uncertainty on the performance of each facility, and with heterogeneous facilities in a networked environment. We conclude with a case study in sustainable infrastructure planning using real-world data to show the benefits of the proposed online learning and optimization approach in practice.

Firms wish to learn personalized policies for customers in heterogeneous yet related locations or markets to maximize their monetary gains. To do this, they conduct experiments at each location to estimate the parameters of a customer response function. A crucial decision is which action to assign to each participant in the experiment, especially when a participant can only be assigned one action or there are budget constraints. The existing experimentation methodology considers locations and experiments individually. In this work, we leverage the relationship between locations in the experimentation problem to learn more profitable policies by proposing novel estimators and a semidefinite programming approach.