Numerous decision problems reveal noisy, corrupt or otherwise partial feedback on choices. The Bandit Convex Optimization framework is a general methodology for tackling such missing-feedback problems, including the famed multi-armed-bandit problem and its generalizations. Applications include online routing, rank aggregation, matrix completion and more. Our research addresses efficient algorithms for bandit convex optimization, both in the form of general methodologies for exploration, as well as new techniques from optimization, and variance exploitation.
Inferring and Enforcing Security Policies in Web Applications
The Liberty Computer Architecture Research Group exploits unique opportunities exposed by considering the interaction of compilers and architectures to increase performance, to improve reliability, to reduce cost, to lower power, and to shorten the time to market of microprocessor systems. This objective is accomplished by providing critical computer architecture and compiler research, expertise, and prototypes to the community.
For much of my professional life, designing algorithms had been my thing. Then, one day, I watched a majestic flock of geese fly over Carnegie Lake and it dawned upon me that it had been their thing, too. Having been at it for 100 million years, even longer than I had, naturally their algorithmic genius surpassed mine. Undaunted, I resolved to catch up. The premise of my current research is that interpreting biological or social self-organized systems as "natural algorithms" brings upon them a fresh, new perspective ripe for inquiry. I believe that only the algorithm has the expressive power to model complex self-adaptive systems at the right levels of abstraction. Algorithms are the differential equations of the 21st century. Beyond its trite catchiness, this line serves to remind us that mankind's grasp of PDEs vastly exceeds its mastery of algorithms. The first order of business, therefore, is to build new analytical tools for natural algorithms.
In recent years convex optimization and the notion of regret minimization in games have been combined and applied to machine learning in a general framework called online convex optimization. For more information see the survey on the convex optimization approach to regret minimization, or this draft of a course book on online convex optimization in machine learning.
Although vector graphics offer a number of benefits, conventional vector painting programs offer only limited support for the traditional painting metaphor. We propose a new algorithm that translates a user’s mouse motion into a triangle mesh representation. This triangle mesh can then be composited onto a canvas containing an existing mesh representation of earlier strokes. This representation allows the algorithm to render solid colors and linear gradients. It also enables painting at any resolution. This paradigm allows artists to create complex, multi-scale drawings with gradients and sharp features while avoiding pixel sampling artifacts.
The Princeton Application Repository for Shared-Memory Computers (PARSEC) is a benchmark suite composed of multithreaded programs. The suite focuses on emerging workloads and was designed to be representative of next-generation shared-memory programs for chip-multiprocessors.
The PlanetLab Consortium is a collection of academic, industrial, and government institutions cooperating to support and enhance the PlanetLab overlay network. It is responsible for overseeing the long-term growth of PlanetLab's hardware infrastructure; designing and evolving its software architecture; providing day-to-day operational support; and defining policies that govern appropriate use. The PlanetLab Consortium is managed by Princeton University, the University of California at Berkeley, and the University of Washington. Princeton currently hosts the Consortium.
Matthew Stephens and I considered the problem of identifying latent structure in a population of individuals. We considered the two methods most commonly applied to this problem, namely, admixture models and principal components analysis (PCA), in the framework of matrix factorization methods with different matrix constraints. Within this framework, we described a sparse factor analysis model (SFA) that encouraged sparsity on the factor loadings through an automatic relevance determination prior. Results from SFA bridged the gap between admixture models and PCA: SFA did not over-regularize the data like admixture models tend to do, but, unlike PCA, sparsity enabled well-separated populations to each be associated with a single factor, making the results interpretable as with admixture models. However, we found that the methods produced similar results for continuous populations; a sample of 1387 individuals with approximately 200,000 SNPs from Europe mapped to two factors captured the geography of the sample well in all three methods. We are currently developing factor analysis models that have effective sparsity-inducing priors that go beyond automatic relevance determination priors and have better conjugacy properties the traditional spike-slab type priors.
The Princeton S* Network Systems (SNS) group within Princeton’s Computer Science Department. The undefined S* — Scalable, Secure, Self-Organizing, Self-Managing, Service-centric, Storage-based — characterizes the broad scope of our research.
Prof. Martonosi and her group engage in a range of computer architecture research projects in the areas of Heterogeneous Parallelism, Verifiable and Translatable Memory Models, and Power-Efficient Computing. Their work has led to the top-cited papers in several major conferences, as well as real-world impact through deployments.
The computational bottleneck in applying state-of-the-art iterative methods to ML/optimization is often the so-called "projection step". We design projection-free optimization algorithms that replaces projections by more efficient linear optimization steps. Recent results include a projection-free algorithm for online learning and the first linearly convergent projection-free algorithm.
As a graduate student with Dr. Michael Jordan, collaborating with Dr. Steven Brenner, I created a statistical methodology, SIFTER (Statistical Inference of Function Through Evolutionary Relationships), to capture how protein molecular function evolves within a phylogeny in order to accurately predict function for unannotated proteins, improving over existing methods that use pairwise sequence comparisons. We relied on the assumption that function evolves in parallel with sequence evolution, implying that phylogenetic distance is the natural measure of functional divergence. In SIFTER, molecular function evolves as a first-order Markov chain within a phylogenetic tree. Posterior probabilities are computed exactly using message-passing, with an approximate method for large or functionally diverse protein families; model parameters are estimated using generalized expectation maximization. Functional predictions are extracted from protein-specific posterior probabilities for each function. I applied SIFTER to a genome-scale fungal data set, which included families of proteins from 46 fully-sequenced fungal genomes, and SIFTER substantially outperformed state-of-the-art methods in producing correct and specific predictions.
The color of composited pigments in digital painting is generally computed one of two ways: either alpha blending in RGB, or the Kubelka-Munk equation (KM). The former fails to reproduce paint like appearances, while the latter is difficult to use. We present a data-driven pigment model that reproduces arbitrary compositing behavior by interpolating sparse samples in a high dimensional space. The input is an of a color chart, which provides the composition samples. We propose two different prediction algorithms, one doing simple interpolation using radial basis functions (RBF), and another that trains a parametric model based on the KM equation to compute novel values. We show that RBF is able to reproduce arbitrary compositing behaviors, even non-paint-like such as additive blending, while KM compositing is more robust to acquisition noise and can generalize results over a broader range of values.
Multi-tenant resource fairness for shared datacenter services
SEEK: Search Engine for Heterogeneous Human Gene-Expression Compendia
SEEK: Search Engine for Heterogeneous Human Gene-Expression Compendia
Service-centric networking with Serval
Survey-based GWAS. Genome-wide association studies (GWAS) identify genetic variants that are associated with the occurrence of a complex phenotype or disease in a set of individuals. Many phenotypes are difficult to quantify with a single measure. I am building methods for conducting GWAS using survey data as the phenotype. Standard dimensionality reduction techniques are not effective for scaling down the size of the data because the resulting phenotype summaries were not interpretable. In prior work, we applied SFA and found that the sparse solution had phenotypic interpretations for all of the factors, and genetic associatons for a number of phenotypes. Our current work goes well beyond this model for greater robustness and inference of the number of factors from the underlyng data.
Prevalent computer architecture modeling methodologies are prone to error, make design-space exploration slow, and create barriers to collaboration. The Structural Modeling Project addresses these issues by providing viable structural modeling methodologies to the community. The Liberty Simulation Environment showcases this approach and serves as the core of a new international standardization effort called Fraternité.