UCLA

In many engineering and machine learning applications, we often encounter optimization problems (e.g., resource allocation, clustering) for which finding the exact solution is computationally intractable. In such problems, ad-hoc approximate solutions are often used, which have no performance guarantees. Our goal is to develop approximate optimization methods with the following features a) provable performance guarantees, and b) computational tractability. In this dissertation, we focus on several challenging problems in resource allocation and machine learning and develop optimization methods for the same.

In the first part of this dissertation, we develop optimization methods to solve fundamental resource allocation problems encountered in the design of different systems, namely wireless networks, crowdsourcing systems, and healthcare systems.

Dense deployment of heterogeneous small cells (e.g., picocells, femtocells) is becoming the most effective way to combat the exploding demand for the wireless spectrum. Given the large-scale nature of these deployments, developing resource sharing policies using a centralized system can be computationally and communicationally prohibitive. To this end, we propose a general framework for distributed multi-agent resource sharing. We show that the proposed framework significantly outperforms the state-of-the-art. We prove quite general constant factor approximation guarantees with respect to the optimal solutions.

Matching platforms for freelancing (e.g., Upwork) are becoming mainstream. These platforms are faced with the challenging task of allocating workers to clients in order to generate maximum revenues, taking into consideration that both sides are self-interested, have limited information about the other, and desire to be matched with the best possible partners. We propose a dynamic matching mechanism that takes these challenges into account and achieves many of the aforesaid properties.

Screening plans are used for the early detection of several diseases, such as breast cancer and colon cancer. These screening plans are not personalized to the history and demographics of the subject and can often lead to a delay in the detection of the disease and in other cases cause unnecessary invasive tests such as biopsies. We show that constructing exactly optimal personalized screening plans that minimize the number of screens given a tolerance on the delay is computationally intractable. We develop a framework to solve the proposed problem approximately. We establish general performance guarantees and show that the proposed solution is computationally tractable. We apply the framework to breast cancer screening and establish its utility in comparison to the existing clinical guidelines.

In the second part of this dissertation, we develop optimization methods useful for machine learning applications. Machine learning models are increasingly becoming a part of many of the decision making systems, for instance, clinical decision support systems. Many of the machine learning models are hard to interpret and thus are often called "black-box" models. We propose a method that approximates the black-box models using piecewise-linear approximations. This approach helps explain the model using linear models in different regions of the feature space. We provide provable fidelity, i.e., how well does approximation reflect the black-box, guarantees and show that the method is computationally tractable. We carry out experiments on different datasets and establish the utility of our approach.

Kullback-Leibler divergence is a fundamental quantity used in many disciplines, such as machine learning, statistics, and information theory. We develop an optimization-based approach to estimate the Kullback-Leibler divergence, which relies on the Donsker-Varadhan representation. The state-of-the-art estimator based on this representation relies on solving a non-convex optimization problem and hence, is not consistent. We propose a convex reformulation to construct an estimator, which we show is consistent. We also carry out experiments to show that the proposed estimator is better than the competing estimator.