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.

Q: Common activation functions used in neural networks can yield to training difficulties due to the saturation behavior of the activation function, which may hide dependencies which are not visible to first order (using only gradients). Gating mechanisms that use softly saturating activation functions to emulate the discrete switching of digital logic circuits are good examples of this. We propose to exploit the injection of appropriate noise so that some gradients may sometimes flow, even if the noiseless application of the activation function would yield zero gradient. Large noise will dominate the noise-free gradient and allow stochastic gradient descent to be more exploratory. By adding noise only to the problematic parts of the activation function we allow the optimization procedure to explore the boundary between the degenerate (saturating) and the well-behaved parts of the activation function. We also establish connections to simulated annealing, when the amount of noise is annealed down, making it easier to optimize hard objective functions. We find experimentally that replacing such saturating activation functions by by noisy variants helps training in many contexts, yielding state-of-the-art results on several datasets, especially when training seems to be the most difficult, e.g., when curriculum learning is necessary to obtain good results.

A: Noisy Activation Functions
****
Q: We present a method for solving implicit (factored) Markov decision processes (MDPs) with very large state spaces. We intro­ duce a property of state space partitions which we call f-homogeneity. Intuitively, an f-homogeneous partition groups together states that behave approximately the same under all or some subset of policies. Borrow­ ing from recent work on model minimization in computer-aided software verification, we present an algorithm that takes a factored representation of an MDP and an 0 � f � I and computes a factored f-homogeneous par­ tition of the state space. This partition defines a family of related MOPs-those MOP's with state space equal to the blocks of the partition, and transition probabilities "appro:X:imately" like those of any (original MDP) state in the source block. To formally study such families of MDPs, we introduce the new notion of a "bounded parameter MDP" (BMDP), which is a fam­ ily of (traditional) MOPs defined by speci­ fying upper and lower bounds on the transi­ tion probabilities and rewards. We describe algorithms that operate on BMDPs to find policies that are approximately optimal with respect to the original MDP. In combination, our method for reducing a large implicit MDP to a possibly much smaller BMDP using an f-homogeneous par­ tition, and our methods for selecting actions in BMDP's constitute a new approach for an­ alyzing large implicit MOP's. Among its ad­ vantages, this new approach provides insight into existing algorithms to solving implicit MDPs, provides useful connections to work in automata theory and model minimization, and suggests methods, which involve vary­ ing f, to trade time and space (specifically in terms of the size of the corresponding state space) for solution quality.

A: Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes
****
Q: In this paper, we address learning problems for high dimensional data. Previously, oblivious random projection based approaches that project high dimensional features onto a random subspace have been used in practice for tackling highdimensionality challenge in machine learning. Recently, various non-oblivious randomized reduction methods have been developed and deployed for solving many numerical problems such as matrix product approximation, low-rank matrix approximation, etc. However, they are less explored for the machine learning tasks, e.g., classification. More seriously, the theoretical analysis of excess risk bounds for risk minimization, an important measure of generalization performance, has not been established for non-oblivious randomized reduction methods. It therefore remains an open problem what is the benefit of using them over previous oblivious random projection based approaches. To tackle these challenges, we propose an algorithmic framework for employing non-oblivious randomized reduction method for general empirical risk minimizing in machine learning tasks, where the original high-dimensional features are projected onto a random subspace that is derived from the data with a small matrix approximation error. We then derive the first excess risk bound for the proposed non-oblivious randomized reduction approach without requiring strong assumptions on the training data. The established excess risk bound exhibits that the proposed approach provides much better generalization performance and it also sheds more insights about different randomized reduction approaches. Finally, we conduct extensive experiments on both synthetic and real-world benchmark datasets, whose dimension scales to O(10), to demonstrate the efficacy of our proposed approach. Introduction Recently, the scale and dimensionality of data associated with machine learning and data mining applications have seen unprecedented growth, spurring the BIG DATA research and development. Learning from largescale ultrahigh-dimensional data remains a computationally challenging problem. The big size of data not only increases the memory footprint but also increases the computational costs pertaining to optimization. A popular approach for addressing the high-dimensionality challenge is Copyright c © 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. to perform dimensionality reduction. Nowadays, randomized reduction methods are emerging to be attractive for dimensionality reduction. Compared with traditional dimensionality reduction methods (e.g., PCA and LDA), randomized reduction methods (i) can lead to simpler algorithms that are easier to analyze (Mahoney 2011); (ii) can often be organized to exploit modern computational architectures better than classical dimensional reduction methods (Halko, Martinsson, and Tropp 2011); (iii) can be more efficient without loss in efficacy (Paul et al. 2013). Generally, randomized reduction methods can be cast into two types: the first type of methods reduces a set of high-dimensional vectors into a low dimensional space independent of each other. These methods usually sample a random matrix independent of the data and then use it to reduce the dimensionality of the data. The second type of methods projects a set of vectors (in the form of a matrix) onto a subspace such that the original matrix can be well reconstructed from the projected matrix and the subspace. Therefore, the subspace to which the data is projected depends on the original data. These methods have been deployed for solving many numerical problems related to matrices, e.g., matrix product approximation, low-rank matrix approximation, approximate singular value decomposition (Boutsidis and Gittens 2013a; Halko, Martinsson, and Tropp 2011). To differentiate these two types of randomized reduction methods, we refer to the first type as oblivious randomized reduction, and refer to the second type as non-oblivious randomized reduction. We note that in literature oblivious and non-oblivious are used interchangeably with data-independent and data-dependent. Here, we use the terminology commonly appearing in matrix analysis and numerical linear algebra due to that the general excess risk bound depends on the matrix approximation error. However, we have not seen any comprehensive study on the statistical property (in particular the excess risk bound) of these randomized reduction methods applied to risk minimization in machine learning. The excess risk bound measures the generalization performance of a learned model compared to the optimal model from a class that has the best generalization performance. The excess risk bounds facilitate a better understanding of different learning algorithms and have the potential to guide us to design better algorithms (Kukliansky and Shamir 2015). It is worth noting that several studies have been devoted to understanding the theoretical properties of oblivious randomized reduction methods applied to classification and regression problems. For example, (Blum 2005; Shi et al. 2012; Paul et al. 2013) analyzed the preservation of the margin of SVM based classification methods with randomized dimension reduction. (Zhang et al. 2014; Yang et al. 2015; Pilanci and Wainwright 2015) studied the problem from the perspective of optimization. Nonetheless, these results are limited in the sense that (i) they focus on only oblivious randomized reduction where the data is projected onto a random subspace independent of the data; (ii) they depend heavily on strong assumptions of the training data or the problem, e.g., low-rank of the data matrix, linear separability of training examples, or the sparsity of optimal solution, and (iii) some of these results do not directly carry over to the excess risk bounds. To tackle the above challenges, we propose an algorithmic framework for employing non-oblivious randomized reduction (NOR) method to project the original high-dimensional features onto a random subspace that is derived from the original data. We study and establish the excess risk bound of the presented randomized algorithms for risk minimization. Different from previous results for oblivious randomized reduction methods, our theoretical analysis does not require assumptions of the training data or the problem, such as low-rank of the data matrix, linear separability of training examples, and the sparsity of optimal solution. When the data matrix is of low-rank or has a fast spectral decay, the excess risk bound of NOR is much better than that of oblivious randomized reduction based methods. Empirical studies on synthetic and real data sets corroborate the theoretical results and demonstrate the effectiveness of the proposed methods.

A:
Efficient Non-oblivious Randomized Reduction for Risk Minimization with Improved Excess Risk Guarantee
****