The authors propose a new approach for solving constraint satisfaction problems (CSPs) in a neural architecture. While previous attempts in this direction have largely relied on stochastic neuron models to prevent a neural network from getting stuck in local optima (e.g. through the use of Boltzmann machines), the proposed architecture is capable of finding optimal solutions to problems using purely deterministic network dynamics. This is achieved by coupling oscillator modules such that the strength of their mutual interaction depends on their phase difference. Although the paper does not provide a rigorous theoretical explanation for it, these phase differences are observed to vary irregularly in simulations, thus providing sufficient exploratory drive to escape local optima. In small simulations of a CSP with ten binary variables and nine tertiary constraints the network is observed to find either of the two correct solutions (which satisfy all constraints) in each trial.

We investigate three related and important problems connected to machine learning: approximating a submodular function everywhere, learning a submodular function (in a PAC-like setting [28]), and constrained minimization of submodular functions. We show that the complexity of all three problems depends on the "curvature" of the submodular function, and provide lower and upper bounds that refine and improve previous results [2, 6, 8, 27]. Our proof techniques are fairly generic. We either use a black-box transformation of the function (for approximation and learning), or a transformation of algorithms to use an appropriate surrogate function (for minimization). Curiously, curvature has been known to influence approximations for submodular maximization [3, 29], but its effect on minimization, approximation and learning has hitherto been open. We complete this picture, and also support our theoretical claims by empirical results.

We consider the problem of reinforcement learning over episodes of a finitehorizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization.

Nonnegative matrix factorization (NMF) is a popular data analysis method, the objective of which is to approximate a matrix with all nonnegative components into the product of two nonnegative matrices. In this work, we describe a new simple and efficient algorithm for multi-factor nonnegative matrix factorization (mfNMF) problem that generalizes the original NMF problem to more than two factors. Furthermore, we extend the mfNMF algorithm to incorporate a regularizer based on the Dirichlet distribution to encourage the sparsity of the components of the obtained factors. Our sparse mfNMF algorithm affords a closed form and an intuitive interpretation, and is more efficient in comparison with previous works that use fix point iterations. We demonstrate the effectiveness and efficiency of our algorithms on both synthetic and real data sets.

Many real-world problems have complicated objective functions. To optimize such functions, humans utilize sophisticated sequential decision-making strategies. Many optimization algorithms have also been developed for this same purpose, but how do they compare to humans in terms of both performance and behavior? We try to unravel the general underlying algorithm people may be using while searching for the maximum of an invisible 1D function. Subjects click on a blank screen and are shown the ordinate of the function at each clicked abscissa location.

We consider the general problem of Multiple Model Learning (MML) from data, from the statistical and algorithmic perspectives; this problem includes clustering, multiple regression and subspace clustering as special cases. A common approach to solving new MML problems is to generalize Lloyd's algorithm for clustering (or Expectation-Maximization for soft clustering). However this approach is unfortunately sensitive to outliers and large noise: a single exceptional point may take over one of the models. We propose a different general formulation that seeks for each model a distribution over data points; the weights are regularized to be sufficiently spread out. This enhances robustness by making assumptions on class balance. We further provide generalization bounds and explain how the new iterations may be computed efficiently. We demonstrate the robustness benefits of our approach with some experimental results and prove for the important case of clustering that our approach has a non-trivial breakdown point, i.e., is guaranteed to be robust to a fixed percentage of adversarial unbounded outliers.

Paper 1279 – Optimizing Instructional Policies In this paper, the authors adapt an optimization technique based on Gaussian process regression to select the parameters of experiments or teaching regime, which will optimize human performance. They evaluate their method in two behavioral experiments (one on the presentation rate of studied items and another on the ordering of examples while learning a novel concept), demonstrating that it is vastly more efficient than traditional methods in psychology for exploring a continuous space of conditions. Note: I have revised my score to reflect the author feedback's assurance that the starting point of Experiment 1 wasn't the optimum. However, I still don't fully understand how what they wrote in the feedback connects to what they wrote in the paper. I implore the authors to make sure it is clear in the final version of their paper.

Psychologists are interested in developing instructional policies that boost student learning. An instructional policy specifies the manner and content of instruction. For example, in the domain of concept learning, a policy might specify the nature of exemplars chosen over a training sequence. Traditional psychological studies compare several hand-selected policies, e.g., contrasting a policy that selects only difficult-to-classify exemplars with a policy that gradually progresses over the training sequence from easy exemplars to more difficult (known as fading). We propose an alternative to the traditional methodology in which we define a parameterized space of policies and search this space to identify the optimal policy.

The control variate is a vector which hopefully has high correlation with the noisy gradient but for which the expectation is easier to compute. Standard convergence rates for stochastic gradient optimization depend on the variance of the gradient estimates, and thus a variance reduction technique should yield an acceleration of convergence. The authors give examples of control variates by using Taylor approximations of the gradient estimate for the optimization problem arising in regularized logistic regression as well as for MAP estimation for the latent Dirichlet Allocation (LDA) model. They compare constant step-size SGD with and without variance reduction for logistic regression on the covtype dataset, claiming that the variance reduction allows to use bigger step-sizes without having the problem of high variance and thus yields faster empirical convergence. For LDA, they compare the adaptive step-size version of the stochastic optimization method of [10] with and without variance reduction, showing a faster convergence on the held-out test log-likelihood on three large corpora. EVALUATION: Pros: - I like the general idea of variance reduction for SGD using control variates -- it could have a big impact given the popularity of SGD. - The motivation is compelling; the concrete examples of control variates are convincing; and the the general idea (Taylor approximation to define them) seems generalizable - The paper is fairly easy to read. Cons: - The experiments are somewhat weak: only one dataset for logistic regression; and a lack of standardized setup for LDA. - The related work is not covered. QUALITY: The theoretical motivation for the approach is compelling (reducing the variance of the gradient estimates reduces the constant in the convergence rate), but the execution in the empirical section is fairly weak.

We propose a boosting method, DirectBoost, a greedy coordinate descent algorithm that builds an ensemble classifier of weak classifiers through directly minimizing empirical classification error over labeled training examples; once the training classification error is reduced to a local coordinatewise minimum, Direct-Boost runs a greedy coordinate ascent algorithm that continuously adds weak classifiers to maximize any targeted arbitrarily defined margins until reaching a local coordinatewise maximum of the margins in a certain sense.