In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Input: Consider Input: The Augmented Lagragian Method (ALM) and Alternating Direction Method of Multiplier (ADMM) have been powerful optimization methods for general convex programming subject to linear constraint. We consider the convex problem whose objective consists of a smooth part and a nonsmooth but simple part. We propose the Fast Proximal Augmented Lagragian Method (Fast PALM) which achieves the convergence rate O(1/K), compared with O(1/K) by the traditional PALM. In order to further reduce the per-iteration complexity and handle the multi-blocks problem, we propose the Fast Proximal ADMM with Parallel Splitting (Fast PL-ADMM-PS) method. It also partially improves the rate related to the smooth part of the objective function. Experimental results on both synthesized and real world data demonstrate that our fast methods significantly improve the previous PALM and ADMM. Introduction This work aims to solve the following linearly constrained separable convex problem with n blocks of variables min x1, ,xn f(x) = n

Output: Fast Proximal Linearized Alternating Direction Method of Multiplier with Parallel Splitting

Input: Consider Input: We start with an overview of a class of submodular functions called SCMMs (sums of concave composed with non-negative modular functions plus a final arbitrary modular). We then define a new class of submodular functions we call deep submodular functions or DSFs. We show that DSFs are a flexible parametric family of submodular functions that share many of the properties and advantages of deep neural networks (DNNs), including many-layered hierarchical topologies, representation learning, distributed representations, opportunities and strategies for training, and suitability to GPU-based matrix/vector computing. DSFs can be motivated by considering a hierarchy of descriptive concepts over ground elements and where one wishes to allow submodular interaction throughout this hierarchy. In machine learning and data science applications, where there is often either a natural or an automatically learnt hierarchy of concepts over data, DSFs therefore naturally apply. Results in this paper show that DSFs constitute a strictly larger class of submodular functions than SCMMs, thus justifying their mathematical and practical utility. Moreover, we show that, for any integer k > 0, there are k-layer DSFs that cannot be represented by a k-layer DSF for any k < k. This implies that, like DNNs, there is a utility to depth, but unlike DNNs (which can be universally approximated by shallow networks), the family of DSFs strictly increase with depth. Despite this property, however, we show that DSFs, even with arbitrarily large k, do not comprise all submodular functions. We show this using a technique that "backpropagates" certain requirements if it was the case that DSFs comprised all submodular functions. In offering the above results, we also define the notion of an antitone superdifferential of a concave function and show how this relates to submodular functions (in general), DSFs (in particular), negative second-order partial derivatives, continuous submodularity, and concave extensions. To further motivate our analysis, we provide various special case results from matroid theory, comparing DSFs with forms of matroid rank, in particular the laminar matroid. Lastly, we discuss strategies to learn DSFs, and define the classes of deep supermodular functions, deep difference of submodular functions, and deep multivariate submodular functions, and discuss where these can be useful in applications.

Output: Deep Submodular Functions

Input: Consider Input: The Rao-Blackwell theorem is utilized to analyze and improve the scalability of inference in large probabilistic models that exhibit symmetries. A novel marginal density estimator is introduced and shown both analytically and empirically to outperform standard estimators by several orders of magnitude. The developed theory and algorithms apply to a broad class of probabilistic models including statistical relational models considered not susceptible to lifted probabilistic inference. Introduction Many successful applications of artificial intelligence research are based on large probabilistic models. Examples include Markov logic networks (Richardson and Domingos 2006), conditional random fields (Lafferty, McCallum, and Pereira 2001) and, more recently, deep learning architectures (Hinton, Osindero, and Teh 2006; Bengio and LeCun 2007; Poon and Domingos 2011). Especially the models one encounters in the statistical relational learning (SRL) literature often have joint distributions spanning millions of variables and features. Indeed, these models are so large that, at first sight, inference and learning seem daunting. For numerous of these models, however, scalable approximate and, to a lesser extend, exact inference algorithms do exist. Most notably, there has been a strong focus on lifted inference algorithms, that is, algorithms that group indistinguishable variables and features during inference. For an overview we refer the reader to (Kersting 2012). Lifted algorithms facilitate efficient inference in numerous large probabilistic models for which inference is NP-hard in principle. We are concerned with the estimation of marginal probabilities based on a finite number of sample points. We show that the feasibility of inference and learning in large and highly symmetric probabilistic models can be explained with the Rao-Blackwell theorem from the field of statistics. The theory and algorithms do not directly depend on the syntactical nature of the relational models such as arity of predicates and number of variables per formula but only on the given automorphism group of the probabilistic model, and are applicable to classes of probabilistic models much broader than the class of statistical relational models. Copyright c ©️ 2013, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Consider an experiment where a coin is flipped n times. While a frequentist would assume the flips to be i.i.d., a Bayesian typically makes the weaker assumption of exchangeability that the probability of an outcome sequence only depends on the number of "heads" in the sequence and not on their order. Under the non-i.i.d. assumption, a possible corresponding graphical model is the fully connected graph with n nodes and high treewidth. The actual number of parameters required to specify the distribution, however, is only n+1, one for each sequence with 0 k n "heads." Bruno de Finetti was the first to realize that such a sequence of random variables can be (re-)parameterized as a unique mixture of n+1 independent urn processes (de Finetti 1938). It is this notion of a parameterization as a mixture of urn processes that is at the heart of our work. A direct application of de Finetti's results, however, is often impossible since not all variables are exchangeable in realistic probabilistic models. Motivated by the intuition of exchangeability, we show that arbitrary model symmetries allow us to re-paramterize the distribution as a mixture of independent urn processes where each urn consists of isomorphic joint assignments. Most importantly, we develop a novel Rao-Blackwellized estimator that implicitly estimates the fewer parameters of the simpler mixture model and, based on these, computes the marginal densities. We identify situations in which the application of the Rao-Blackwell estimator is tractable. In particular, we show that the Rao-Blackwell estimator is always linear-time computable for single-variable marginal density estimation. By invoking the Rao-Blackwell theorem, we show that the mean squared error of the novel estimator is at least as small as that of the standard estimator and strictly smaller under non-trivial symmetries of the probabilistic model. Moreover, we prove that for estimates based on sample points drawn from a Markov chainM, the bias of the Rao-Blackwell estimator is governed by the mixing time of the quotient Markov chain whose convergence behavior is superior to that ofM. We present empirical results verifying that the RaoBlackwell estimator always outperforms the standard estimator by up to several orders of magnitude, irrespective of the model structure. Indeed, we show that the results of the novel estimator resemble those typically observed in lifted inference papers. For the first time such a performance is shown for an SRL model with a transitivity formula. ar X iv :1 30 4. 26 94 v1 [ cs .A I] 9 A pr 2 01 3
Output: Symmetry-Aware Marginal Density Estimation