The capacitated P-median problem (CPMP) is an NPcomplete problem which investigates the problem of partitioning a set of N nodes into M different disjoint clusters, each represented by a certain node that is designed as concentrator. The NM nodes that are not chosen as concentrators are referred as terminals. The partitioning of the initial N nodes must be performed in such a way that a measure of total distance between the terminals and their corresponding concentrators is minimized. In addition, a capacity constraint imposed on the concentrators must be met, in order to obtain feasible solutions to the problem [1-4]. A direct application of the CPMP is in the context of communication networks deployment, where a set of terminals in the network must be assigned to the corresponding concentrator in order to compose access networks that satisfy the rate requirements of such terminals [5]. In this context, most of the efforts so far has focused on the topological design of communication networks (e.g. Wireless Sensor Networks (WSN), backbone networks or mobile networks [6-8]) since many of the processes involved in such networks can be approached as a CPMP problem, e.g.

Yoshua Bengio Université de Montréal CIFAR Fellow Many state-of-the-art results obtained with deep networks are achieved with the largest models that could be trained, and if more computation power was available, we might be able to exploit much larger datasets in order to improve generalization ability. Whereas in learning algorithms such as decision trees the ratio of capacity (e.g., the number of parameters) to computation is very favorable (up to exponentially more parameters than computation), the ratio is essentially 1 for deep neural networks. Conditional computation has been proposed as a way to increase the capacity of a deep neural network without increasing the amount of computation required, by activating some parameters and computation "on-demand", on a per-example basis. In this note, we propose a novel parametrization of weight matrices in neural networks which has the potential to increase up to exponentially the ratio of the number of parameters to computation. The proposed approach is based on turning on some parameters (weight matrices) when specific bit patterns of hidden unit activations are obtained. In order to better control for the overfitting that might result, we propose a parametrization that is tree-structured, where each node of the tree corresponds to a prefix of a sequence of sign bits, or gating units, associated with hidden units.

Determinantal point process have recently been used as models in machine learning and this has raised questions regarding the characterizations of conditional independence. In this paper we investigate characterizations of conditional independence. We describe some conditional independencies through the conditions on the kernel of a determinantal point process, and show many can be obtained using the graph induced by a kernel of the L-ensemble. In recent years there have been several machine learning papers about the applications of determinantal point processes (DPP's) [4], [7], [8], [9]... An overview of theory, recent applications and problems in learning DPP's is given in a recent extensive survey [6] by Kulesza and Taskar. In a private communication with Ben Taskar, one of the questions from survey [6] (see §7.3), that remains for future research, was brought to author's attention: - Is there a simple characterization of the conditional independence relations encoded by a DPP? This question arises naturally having in mind conditional independence structure models (see [12]), such as graphical models (see [11]) that are often used. It turns out that, from the mathematical view point, elegant characterizations, similar to those in graphical models, exist. This paper provides two (main) characterizations: - the block in a Schur complement of the kernel has to be a 0-block (Theorem 16, Proposition 17); - we can use the structure of the graph induced by the kernel of the L-ensemble to read many conditional independencies in the process (Theorem 28, Proposition 30).

We consider the problem of learning a forest of nonlinear decision rules with general loss functions. The standard methods employ boosted decision trees such as Adaboost for exponential loss and Friedman's gradient boosting for general loss. In contrast to these traditional boosting algorithms that treat a tree learner as a black box, the method we propose directly learns decision forests via fully-corrective regularized greedy search using the underlying forest structure. Our method achieves higher accuracy and smaller models than gradient boosting (and Adaboost with exponential loss) on many datasets.

Demand response (DR) for residential and small commercial buildings is estimated to account for as much as 65% of the total energy savings potential of DR, and previous work shows that a fully automated Energy Management System (EMS) is a necessary prerequisite to DR in these areas. In this paper, we propose a novel EMS formulation for DR problems in these sectors. Specifically, we formulate a fully automated EMS's rescheduling problem as a reinforcement learning (RL) problem, and argue that this RL problem can be approximately solved by decomposing it over device clusters. Compared with existing formulations, our new formulation (1) does not require explicitly modeling the user's dissatisfaction on job rescheduling, (2) enables the EMS to self-initiate jobs, (3) allows the user to initiate more flexible requests and (4) has a computational complexity linear in the number of devices. We also demonstrate the simulation results of applying Q-learning, one of the most popular and classical RL algorithms, to a representative example.

Assume that each of n voters may or may not approve each of m issues. If an agent (the lobby) may influence up to k voters, then the central question of the NP-hard Lobbying problem is whether the lobby can choose the voters to be influenced so that as a result each issue gets a majority of approvals. This problem can be modeled as a simple matrix modification problem: Can one replace k rows of a binary n x m-matrix by k all-1 rows such that each column in the resulting matrix has a majority of 1s? Significantly extending on previous work that showed parameterized intractability (W[2]-completeness) with respect to the number k of modified rows, we study how natural parameters such as n, m, k, or the "maximum number of 1s missing for any column to have a majority of 1s" (referred to as "gap value g") govern the computational complexity of Lobbying. Among other results, we prove that Lobbying is fixed-parameter tractable for parameter m and provide a greedy logarithmic-factor approximation algorithm which solves Lobbying even optimally if m < 5. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove that Lobbying is LOGSNP-complete for constant values g>0, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.

While the theory of Optimal Control (OC) has become widely used as a framework for studying motor control, the standard framework of OC neglects many essential attributes of biological control [1, 2, 3]. The classic formulation of closed loop OC considers a dynamical system (plant) observed through sensors which transmit their output to a controller, which in turn selects a control law that drives actuators to steer the plant. This standard view, however, ignores the fact that sensors, controllers and actuators are often distributed across multiple subsystems, and disregards the communication channels between these subsystems. While the importance of jointly considering control and communication within a unified framework was already clear to the pioneers of the field of Cybernetics (e.g., Wiener and Ashby), it is only in recent years that increasing effort is being devoted to the formulation of a rigorous systems-theoretic framework for control and communication (e.g., [4]). Since the ultimate objective of an agent is to select appropriate actions, it is clear that sensation and communication must subserve effective control, and should be gauged by their contribution to action selection. In fact, given the communication constraints that plague biological systems (and many current distributed systems, e.g., cellular networks, sensor arrays, power grids, etc.), a major concern of a control design is the optimization of sensory information gathering and communication (consistently with theories of active perception). For example, recent theoretical work demonstrated a sharp communication bandwidth threshold below which control (or even stabilization) cannot be achieved (for a summary of such results see [4]). Moreover, when informational constraints exists within a control setting, even simple (linear and Gaussian) problems become nonlinear and intractable, as exemplified in the famous Witsenhausen counterexample [5]. The interdependence between sensation, communication and control is often overlooked both in control theory and in computational neuroscience, where one assumes that the overall solution to the control problem consists of first estimating the state of the controlled system (without reference to the control task), followed by constructing a controller based on the estimated state.

We consider the problem of dictionary learning under the assumption that the observed signals can be represented as sparse linear combinations of the columns of a single large dictionary matrix. In particular, we analyze the minimax risk of the dictionary learning problem which governs the mean squared error (MSE) performance of any learning scheme, regardless of its computational complexity. By following an established information-theoretic method based on Fanos inequality, we derive a lower bound on the minimax risk for a given dictionary learning problem. This lower bound yields a characterization of the sample-complexity, i.e., a lower bound on the required number of observations such that consistent dictionary learning schemes exist. Our bounds may be compared with the performance of a given learning scheme, allowing to characterize how far the method is from optimal performance.

Methods from algebra and algebraic geometry have been used in various ways to study linkages in kinematics. These methods have failed so far for the study of linkages with helical joints (joints with screw motion), because of the presence of some non-algebraic relations. In this article, we explore a delicate reduction of some analytic equations in kinematics to algebraic questions via a theorem of Ax. As an application, we give a classification of mobile closed 5-linkages with revolute, prismatic, and helical joints.

It is common to find collections/measurements of related objects, such as the same article in different languages, similar talks given by different presenters, similar weather patterns in different years, etc. It remains to determine how much the available big data helps us in statistical analysis; simply throwing every collected dataset into the mix may not yield an optimal output. Thus it is natural and important to understand theoretically when and how additional datasets improve the performance of various statistical analysis tasks such as regression, clustering, classification, etc. This is our motivation to explore the following classification problem.