Research
Research
My research is primarily focused on exploiting (combinatorial) structures present in optimization and machine learning problems to (i) develop novel and efficient algorithms with provable theoretical guarantees; (ii) speed-up existing methods and draw connections between them. In particular, my work integrates the theory of approximation algorithms, combinatorial optimization and submodular functions, iterative first-order optimization methods and smarter warm-start solutions.
Publications:
Publications:
Trust-MAPS: Projections-based Data Correction of EMRs for Superior ML on Temporal Clinical Diseases
To soon be submitted to PNAS
Abstract
Clinicians look at Electronic Medical Record (EMR) data, composed of charts and lab tests, to aid them in their decision making process, and can detect errors or discount untrustworthy lab tests. There has been a recent emphasis on using machine learning models to automate clinical decision making; however, all these works look at EMR data without incorporating context or clinical expertise to detect untrustworthy data. This work is the first to translate clinical domain knowledge into high-dimensional mathematical constraints and project EMR data of ICU patients onto those clinical domain constraints. These projections are used to correct inconsistencies in the patient data and to obtain "trust-scores" that improve prediction power. In this paper, we apply our projections-based data correction techniques to the automate the early detection of Sepsis. Sepsis is a life-threatening condition that occurs when the body's extreme response to an infection damages its own tissues, and is fatal if it is not diagnosed early. We test our algorithm on the PhysioNet dataset consisting of a total of 40,000 patients and achieve high predictive accuracy within a 6 hour time window before the onset of sepsis. We show that incorporating our novel projection pipeline significantly improves the performance of the machine learning prediction model, increasing both the precision and AUC by a factor of approximately 1.5 compared to baselines of ML models trained without using projections, and predicting sepsis using SOFA scores. We outperform the precision state of the art for the early detection of sepsis.
Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes
Under submission to Math of Operations Research
[PDF] | [Code] | [Poster]
Abstract
Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing "projections'' in potentially each iteration (e.g., O(T^{1/2}) regret of online mirror descent). On the other hand, conditional gradient variants solve a linear optimization in each iteration, but result in suboptimal rates (e.g., O(T^{3/4}) regret of online Frank-Wolfe). Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points over widely-prevalent submodular base polytopes B(f). We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives. We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination. For the special case of cardinality based submodular polytopes, we improve the runtime of computing certain Bregman projections by a factor of \omega(n/log(n)). Our theoretical results show orders of magnitude reduction in runtime in preliminary computational experiments.
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
Major Revision at Math of OR
[PDF] | [Code] | [Poster] | [Video]
Abstract
Descent directions such as movement towards Frank-Wolfe vertices, away steps, in-face away steps and pairwise directions have been an important design consideration in conditional gradient descent (CGD) variants. In this work, we attempt to demystify the impact of movement in these directions towards attaining constrained minimizers. The best local direction of descent is the directional derivative of the projection of the gradient, which we refer to as the shadow of the gradient. We show that the continuous time dynamics of moving in the shadow are equivalent to those of PGD however non-trivial to discretize. By projecting gradients in PGD, one not only ensures feasibility but also is able to “wrap” around the convex region. We show that Frank-Wolfe(FW) vertices in fact recover the maximal wrap one can obtain by projecting gradients, thus providing a new perspective to these steps. We also claim that the shadow steps give the best direction of descent emanating from the convex hull of all possible away-vertices. Opening up the PGD movements in terms of shadow steps gives linear convergence, dependent on thecnumber of faces. We combine these insights into a novel Shadow-CG method that uses FW steps (i.e., wrap around the polytope) and shadow steps (i.e., optimal local descent direction),while enjoying linear convergence. Our analysis develops properties of directional derivatives of projections (which may be of independent interest), while providing a unifying view of variousdescent directions in the CGD literature.
Electrical Flows Over Spanning Trees
[PDF] | [Code] | [Video]
Abstract
The network reconfiguration problem seeks to find a rooted tree T such that the energy of the (unique) feasible electrical flow over T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from $\min\{O(m-n), O(n)\}$ for general graphs, to $O(\sqrt{n})$ over grids with uniform resistances on edges, and $O(1)$ for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. \sg{Using insights from our theoretical results}, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance.
Conditional Value-at-Risk Assortment Optimization Under the Multinomial-Logit Model
[PDF]
Abstract
Assortment optimization is a significant problem that arises in many revenue management and marketing applications like retailing and online advertising. In an assortment optimization problem, the goal is to select a subset of items that maximize some notion of revenue in the presence of the substitution behavior of consumers specified by a choice model. Previously, the assortment optimization problem was studied from the expected revenue perspective, where the goal was to find the assortment that maximizes the expected revenue. In this paper, we consider constrained and unconstrained assortment optimization problems from a risk perspective, where the goal is to nd a subset of items that maximizes the revenue conditional value-at-Risk, assuming that customers select according to the multinomial-logit model (MNL). We show that this problem could be formulated as an integer program. In addition, we show that in the unconstrained problem, an assortment that maximizes CVaR will always be nested by revenue and accordingly provide a direct algorithm that finds the optimal assortment. We use this result to further show that an assortment that maximizes expected revenue will always be a subset of an assortment that maximizes CVaR, and that the optimal CVaR assortment includes more items.
Recent and Upcoming Talks:
Recent and Upcoming Talks:
Reusing Combinatorial Structure: Faster Projections on Submodular Base Polytopes
Reusing Combinatorial Structure: Faster Projections on Submodular Base Polytopes
Reusing Combinatorial Structure: Faster Projections on Submodular Base Polytopes
Reusing Combinatorial Structure: Faster Projections on Submodular Base Polytopes
Electrical Flows Over Spanning Trees
Reusing Combinatorial Structure: Faster Projections on Submodular Base Polytopes
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
Electrical Flows Over Spanning Trees to Minimize Power Losses in Electricity Distribution Networks
Electrical Flows Over Spanning Trees