Gözde Özcan PhD Dissertation Defense

Name:
Gözde Özcan

Title:
Learning and Optimizing Set Functions

Date:
8/12/2024

Time:
10:00:00 AM

Location:
EXP 601
Committee Members:
Prof. Stratis Ioannidis (Advisor)
Prof. Jennifer Dy
Prof. Evimaria Terzi

Abstract:
Learning and optimizing set functions play a crucial role in the artificial intelligence research as various problems of interest can be characterized with set inputs and/or outputs. Submodular functions, i.e., set functions with a diminishing returns property, are an important subcategory of such functions. They naturally present themselves in applications such as sensor placement, data summarization, feature selection, influence maximization, hyper-parameter optimization, and facility location, to name a few. In a lot of these compelling problems, the objective is to maximize a submodular function subject to matroid constraints, which is known to be NP-hard. For problems of this nature, the continuous greedy algorithm provides a (1 − 1/e)-approximation guarantee in polynomial-time. It does so by estimating the gradient of the so-called multilinear relaxation of the objective function via sampling. However, for the general class of submodular functions, the number of samples required to achieve this theoretical guarantee can be computationally prohibitive.

In this dissertation, we address deterministic submodular maximization problems with matroid constraints, specifically those with objectives expressed through compositions of analytic and multilinear functions. We introduce a novel polynomial series estimator to approximate the multilinear relaxation of such functions and demonstrate that the sub-optimality introduced by our polynomial expansion can be minimized by increasing the polynomial order. By utilizing this estimator, a variant of the continuous greedy algorithm achieves an approximation ratio close to (1 − 1/e) ≈ 0.63 through deterministic gradient estimation. In numerical experiments, our polynomial estimator outperforms the sampling estimator, offering reduced errors in less time.

We extend our study to the stochastic submodular maximization setting with general matroid constraints, where objectives are defined as expectations over submodular functions with an unknown distribution. Adapting polynomial estimators to this context reduces the variance of the gradient estimation while introducing a controlled bias term. For several notable stochastic submodular maximization problems, we demonstrate that this bias decays exponentially with the degree of our polynomial approximators. Furthermore, for monotone functions, a stochastic variant of the continuous greedy algorithm attains an approximation ratio (in expectation) close to (1 − 1/e) ≈ 0.63 using these polynomial estimators. Our experimental results validate the advantages of our approach across synthetic and real-life datasets.

Finally, we turn our attention to the learning set functions under a so-called optimal subset oracle setting. A recent approach approximates the underlying utility function with an energy-based model. Approximating this energy-based model yields iterations of fixed-point update steps during mean-field variational inference. However, these fixed-point iterations are not guaranteed to converge and as the number of iterations increases, automatic differentiation quickly becomes computationally prohibitive due to the size of the Jacobians that are stacked during backpropagation. We address these challenges by examining the convergence conditions for the fixed-point iterations and utilizing implicit differentiation over automatic differentiation. We empirically demonstrate the efficiency of our method on synthetic and real-world subset selection applications.