Sparse coding is a basic task in many fields including signal processing, neuroscience and machine learning where the goal is to learn a basis that enables a sparse representation of a given set of data, if one exists. Its standard formulation is as a non-convex optimization problem which is solved in practice by heuristics based on alternating minimization. Re- cent work has resulted in several algorithms for sparse coding with provable guarantees, but somewhat surprisingly these are outperformed by the simple alternating minimization heuristics. Here we give a general framework for understanding alternating minimization which we leverage to analyze existing heuristics and to design new ones also with provable guarantees. Some of these algorithms seem implementable on simple neural architectures, which was the original motivation of Olshausen and Field (1997a) in introducing sparse coding. We also give the first efficient algorithm for sparse coding that works almost up to the information theoretic limit for sparse recovery on incoherent dictionaries. All previous algorithms that approached or surpassed this limit run in time exponential in some natural parameter. Finally, our algorithms improve upon the sample complexity of existing approaches. We believe that our analysis framework will have applications in other settings where simple iterative algorithms are used.

When applying machine learning to problems in NLP, there are many choices to make about how to represent input texts. These choices can have a big effect on performance, but they are often uninteresting to researchers or practitioners who simply need a module that performs well. We propose an approach to optimizing over this space of choices, formulating the problem as global optimization. We apply a sequential model-based optimization technique and show that our method makes standard linear models competitive with more sophisticated, expensive state-of-the-art methods based on latent variable models or neural networks on various topic classification and sentiment analysis problems. Our approach is a first step towards black-box NLP systems that work with raw text and do not require manual tuning.

A natural way to characterize the cluster structure of a dataset is by finding regions containing a high density of data. This can be done in a nonparametric way with a kernel density estimate, whose modes and hence clusters can be found using mean-shift algorithms. We describe the theory and practice behind clustering based on kernel density estimates and mean-shift algorithms. We discuss the blurring and non-blurring versions of mean-shift; theoretical results about mean-shift algorithms and Gaussian mixtures; relations with scale-space theory, spectral clustering and other algorithms; extensions to tracking, to manifold and graph data, and to manifold denoising; K-modes and Laplacian K-modes algorithms; acceleration strategies for large datasets; and applications to image segmentation, manifold denoising and multivalued regression.

Saving energy is a major concern. Hence, it is fundamental to design and construct buildings that are energy-efficient. It is known that the early stage of architectural design has a significant impact on this matter. However, it is complex to create designs that are optimally energy efficient, and at the same time balance other essential criterias such as economics, space, and safety. One state-of-the art approach is to create parametric designs, and use a genetic algorithm to optimize across different objectives. We further improve this method, by aggregating the solutions of multiple agents. We evaluate diverse teams, composed by different agents; and uniform teams, composed by multiple copies of a single agent. We test our approach across three design cases of increasing complexity, and show that the diverse team provides a significantly larger percentage of optimal solutions than single agents.

Vehicle-sharing (ex: bike sharing, car sharing) is widelyadopted in many cities of the world due to concernsassociated with extensive private vehicle usage, whichhas led to increased carbon emissions, traffic conges-tion and usage of non-renewable resources. In vehicle-sharing systems, base stations are strategically placedthroughout a city and each of the base stations containa pre-determined number of vehicles at the beginningof each day. Due to the stochastic and individualisticmovement of customers, typically, there is either con-gestion (more than required) or starvation (fewer thanrequired) of vehicles at certain base stations. As demon-strated in our experimental results, this happens oftenand can cause a significant loss in demand. We proposeto dynamically redeploy idle vehicles using carriers soas to minimize lost demand or alternatively maximizerevenue of the vehicle sharing company. To that end,we contribute an optimization formulation to jointly ad-dress the redeployment (of vehicles) and routing (of car-riers) problems and provide two approaches that rely ondecomposability and abstraction of problem domains toreduce the computation time significantly. Finally, wedemonstrate the utility of our approaches on two realworld data sets of bike-sharing companies.

We are concerned with controlling dynamical systems, such as self-driving cars and smart buildings, in a manner that guarantees that they satisfy complex task specifications. Mixed integer linear programming has recently proven to be a powerful tool for such problems, enabling the computation of optimal plans that satisfy complex temporal constraints for high-dimensional, dynamical systems. These optimization-based approaches find solutions quickly for challenging (and previously unsolvable) planning problems. Framing temporal logic planning as constrained optimization also presents exciting new areas of research.

Residential and commercial buildings are responsible for about 40% of primary energy consumption in the United States, hence improving their energy efficiency could have important sustainability benefits. The design of a building has tremendous effect on its energy profile, and recently there has been an increased interest in developing optimization methods that support the design of high performance buildings. Previous approaches are either based on simulation optimization or on training an accurate predictive model that is queried during the optimization. We propose a method that more tightly integrates the machine learning and optimization components, by employing active learning during optimization. In particular, we use a Gaussian Process (GP) model for the prediction and active learning and multi-objective genetic algorithm NSGA-II for the optimization. We develop a comprehensive and publicly available benchmark for building design optimization. We evaluate 5 machine learning approaches on our dataset, and show that the GP model is competitive, in addition to being well-suited for the active learning setting. We compare our optimization approach against the 2-stage approach and simulation optimization. Our results show that our approach produces solutions at the Pareto frontier compared to the other two approaches, while using only a fraction of the simulations and time.

One approach to conserving endangered species is to purchase and protect a set of land parcels in a way that maximizes the expected future population spread. Unfortunately, an ideal set of parcels may have a cost that is beyond the immediate budget constraints and must thus be purchased incrementally. This raises the challenge of deciding how to schedule the parcel purchases in a way that maximizes the flexibility of budget usage while keeping population spread loss in control. In this paper, we introduce a formulation of this scheduling problem that does not rely on knowing the future budgets of an organization. In particular, we consider scheduling purchases in a way that achieves a population spread no less than desired but delays purchases as long as possible. Such schedules offer conservation planners maximum flexibility and use available budgets in the most efficient way. We develop the problem formally as a stochastic optimization problem over a network cascade model describing a commonly used model of population spread. Our solution approach is based on reducing the stochastic problem to a novel variant of the directed Steiner tree problem, which we call the set-weighted directed Steiner graph problem. We show that this problem is computationally hard, motivating the development of a primal-dual algorithm for the problem that computes both a feasible solution and a bound on the quality of an optimal solution. We evaluate the approach on both real and synthetic conservation data with a standard population spread model. The algorithm is shown to produce near optimal results and is much more scalable than more generic off-the-shelf optimizers. Finally, we evaluate a variant of the algorithm to explore the trade-offs between budget savings and population growth.

Saving energy is a major concern. Hence, it is fundamental to design and construct buildings that are energy-efficient. It is known that the early stage of architectural design has a significant impact on this matter. However, it is complex to create designs that are optimally energy efficient, and at the same time balance other essential criterias such as economics, space, and safety. One state-of-the art approach is to create parametric designs, and use a genetic algorithm to optimize across different objectives. We further improve this method, by aggregating the solutions of multiple agents. We evaluate diverse teams, composed by different agents; and uniform teams, composed by multiple copies of a single agent. We test our approach across three design cases of increasing complexity, and show that the diverse team provides a significantly larger percentage of optimal solutions than single agents.

Many recent planning heuristics are based on LP optimization. However, planning experts mostly use LP solvers as a black box and it is often not obvious to them which LP techniques would be most suitable for their specific applications.To foster the communication between the planning and the optimization community, this paper gives an easily accessible overview over these recent LP-based heuristics, namely the optimal cost partitioning heuristic for abstractions, the post-hoc optimization heuristic, a landmark heuristic, the state-equation heuristic, and a delete relaxation heuristic. All these heuristics fit the framework of so-called operator counting constraints, which we also present.