Unlike matrix completion, tensor completion does not have an algorithm that is known to achieve the information-theoretic sample complexity rate. This paper develops a new algorithm for the special case of completion for nonnegative tensors. We prove that our algorithm converges in a linear (in numerical tolerance) number of oracle steps, while achieving the information-theoretic rate. Our approach is to define a new norm for nonnegative tensors using the gauge of a particular 0-1 polytope; integer linear programming can, in turn, be used to solve linear separation problems over this polytope. We combine this insight with a variant of the Frank-Wolfe algorithm to construct our numerical algorithm, and we demonstrate its effectiveness and scalability through computational experiments using a laptop on tensors with up to one-hundred million entries.

Though there is a growing literature on fairness for supervised learning, incorporating fairness into unsupervised learning has been less well-studied. This paper studies fairness in the context of principal component analysis (PCA). We first define fairness for dimensionality reduction, and our definition can be interpreted as saying a reduction is fair if information about a protected class (e.g., race or gender) cannot be inferred from the dimensionality-reduced data points. Next, we develop convex optimization formulations that can improve the fairness (with respect to our definition) of PCA and kernel PCA. These formulations are semidefinite programs, and we demonstrate their effectiveness using several datasets. We conclude by showing how our approach can be used to perform a fair (with respect to age) clustering of health data that may be used to set health insurance rates.

Drug resistance in breast cancer cell populations has been shown to arise through phenotypic transition of cancer cells to a drug-tolerant state, for example through epithelial-to-mesenchymal transition or transition to a cancer stem cell state. However, many breast tumors are a heterogeneous mixture of cell types with numerous epigenetic states in addition to stem-like and mesenchymal phenotypes, and the dynamic behavior of this heterogeneous mixture in response to drug treatment is not well-understood. Recently, we showed that plasticity between differentiation states, as identified with intracellular markers such as cytokeratins, is linked to resistance to specific targeted therapeutics. Understanding the dynamics of differentiation-state transitions in this context could facilitate the development of more effective treatments for cancers that exhibit phenotypic heterogeneity and plasticity. In this work, we develop computational models of a drug-treated, phenotypically heterogeneous triple-negative breast cancer (TNBC) cell line to elucidate the feasibility of differentiation-state transition as a mechanism for therapeutic escape in this tumor subtype. Specifically, we use modeling to predict the changes in differentiation-state transitions that underlie specific therapy-induced changes in differentiation-state marker expression that we recently observed in the HCC1143 cell line. We report several statistically significant therapy-induced changes in transition rates between basal, luminal, mesenchymal, and non-basal/non-luminal/non-mesenchymal differentiation states in HCC1143 cell populations. Moreover, we validate model predictions on cell division and cell death empirically, and we test our models on an independent data set. Overall, we demonstrate that changes in differentiation-state transition rates induced by targeted therapy can provoke distinct differentiation-state aggregations of drug-resistant cells, which may be fundamental to the design of improved therapeutic regimens for cancers with phenotypic heterogeneity.

[This corrects the article DOI: 10.1371/journal.pcbi.1006840.].

Classifiers and rating scores are prone to implicitly codifying biases, which may be present in the training data, against protected classes (i.e., age, gender, or race). So it is important to understand how to design classifiers and scores that prevent discrimination in predictions. This paper develops computationally tractable algorithms for designing accurate but fair support vector machines (SVM’s). Our approach imposes a constraint on the covariance matrices conditioned on each protected class, which leads to a nonconvex quadratic constraint in the SVM formulation. We develop iterative algorithms to compute fair linear and kernel SVM’s, which solve a sequence of relaxations constructed using a spectral decomposition of the nonconvex constraint. Its effectiveness in achieving high prediction accuracy while ensuring fairness is shown through numerical experiments on several data sets.

On-policy imitation learning algorithms such as Dagger evolve a robot control policy by executing it, measuring performance (loss), obtaining corrective feedback from a supervisor, and generating the next policy. As the loss between iterations can vary unpredictably, a fundamental question is under what conditions this process will eventually achieve a converged policy. If one assumes the underlying trajectory distribution is static (stationary), it is possible to prove convergence for Dagger. Cheng and Boots (2018) consider the more realistic model for robotics where the underlying trajectory distribution, which is a function of the policy, is dynamic and show that it is possible to prove convergence when a condition on the rate of change of the trajectory distributions is satisfied. In this paper, we reframe that result using dynamic regret theory from the field of Online Optimization to prove convergence to locally optimal policies for Dagger, Imitation Gradient, and Multiple Imitation Gradient. These results inspire a new algorithm, Adaptive On-Policy Regularization (AOR), that ensures the conditions for convergence. We present simulation results with cart-pole balancing and walker locomotion benchmarks that suggest AOR can significantly decrease dynamic regret and chattering. To our knowledge, this the first application of dynamic regret theory to imitation learning.

This talk will present reachability analysis as a tool for model checking and controller synthesis for dynamic systems. We will consider the problem of guaranteeing reachability to a given desired subset of the state space while satisfying a safety property defined in terms of state constraints. We allow for nonlinear and hybrid dynamics, and possibly nonconvex state constraints. We use these results to synthesize controllers that ensure safety and reachability properties under bounded model disturbances that vary continuously.

In this paper, we present details of the real time implementation onboard a quadrotor helicopter of learning-based model predictive control (LBMPC). LBMPC rigorously combines statistical learning with control engineering, while providing levels of guarantees about safety, robustness, and convergence. Experimental results show that LBMPC can learn physically based updates to an initial model, and how as a result LBMPC improves transient response performance. We demonstrate robustness to mis-learning. Finally, we show the use of LBMPC in an integrated robotic task demonstration-The quadrotor is used to catch a ball thrown with an a priori unknown trajectory.

Heating, ventilation, and air conditioning (HVAC) systems are an important target for efficiency improvements through new equipment and retrofitting because of their large energy footprint. One type of equipment that is common in homes and some offices is an electrical, single-stage heat pump air conditioner (AC). To study this setup, we have built the Berkeley Retrofitted and Inexpensive HVAC Testbed for Energy Efficiency (BRITE) platform. This platform allows us to actuate an AC unit that controls the room temperature of a computer laboratory on the Berkeley campus that is actively used by students, while sensors record room temperature and AC energy consumption. We build a mathematical model of the temperature dynamics of the room, and combining this model with statistical methods allows us to compute the heating load due to occupants and equipment using only a single temperature sensor. Next, we implement a control strategy that uses learning-based model-predictive control (MPC) to learn and compensate for the amount of heating due to occupancy as it varies throughout the day and year. Experiments on BRITE show that our techniques result in a 30%-70% reduction in energy consumption as compared to two-position control, while still maintaining a comfortable room temperature. The energy savings are due to our control scheme compensating for varying occupancy, while considering the transient and steady state electrical consumption of the AC. Our techniques can likely be generalized to other HVAC systems while still maintaining these energy saving features.

BACKGROUND: The correlation between the expression levels of transcription factors and their target genes can be used to infer interactions within animal regulatory networks, but current methods are limited in their ability to make correct predictions. RESULTS: Here we describe a novel approach which uses nonparametric statistics to generate ordinary differential equation (ODE) models from expression data. Compared to other dynamical methods, our approach requires minimal information about the mathematical structure of the ODE; it does not use qualitative descriptions of interactions within the network; and it employs new statistics to protect against over-fitting. It generates spatio-temporal maps of factor activity, highlighting the times and spatial locations at which different regulators might affect target gene expression levels. We identify an ODE model for eve mRNA pattern formation in the Drosophila melanogaster blastoderm and show that this reproduces the experimental patterns well. Compared to a non-dynamic, spatial-correlation model, our ODE gives 59% better agreement to the experimentally measured pattern. Our model suggests that protein factors frequently have the potential to behave as both an activator and inhibitor for the same cis-regulatory module depending on the factors' concentration, and implies different modes of activation and repression. CONCLUSIONS: Our method provides an objective quantification of the regulatory potential of transcription factors in a network, is suitable for both low- and moderate-dimensional gene expression datasets, and includes improvements over existing dynamic and static models.

Local linearization techniques are an important class of nonparametric system identification. Identifying local linearizations in practice involves solving a linear regression problem that is ill-posed. The problem can be ill-posed either if the dynamics of the system lie on a manifold of lower dimension than the ambient space or if there are not enough measurements of all the modes of the dynamics of the system. We describe a set of linear regression estimators that can handle data lying on a lower-dimension manifold. These estimators differ from previous estimators, because these estimators are able to improve estimator performance by exploiting the sparsity of the system - the existence of direct interconnections between only some of the states - and can work in the ldquolarge p, small nrdquo setting in which the number of states is comparable to the number of data points. We describe our system identification procedure, which consists of a pre smoothing step and a regression step, and then we apply this procedure to data taken from a quadrotor helicopter. We use this data set to compare our procedure with existing procedures.