This paper focuses on finite sample analysis for stochastic gradient algorithms. The motivation stems from a vast varieties of applications. In particular, the recent advances on stochastic optimization in conjunction with machine learning have opened up new domains. A particular emphasis of the learning community requires us taking a careful look at of the finite sample analysis. Well, it is well known that stochastic gradient algorithms or stochastic approximation algorithms are normally concentrated on dealing with asymptotic properties of the recursive algorithms. However, the learning community placed more effort for carrying out analysis of finite sample properties of the recursive algorithms; see for example,... and references therein.

Mean field theory has been successfully used to analyze deep neura l networks (DNN) in the infinite size limit. Given the finite size of realistic D NN, we utilize the large deviation theory and path integral analysis to study the deviation of functions represented by DNN from their typical mean field solution s. The parameter perturbations investigated include weight sparsification (dilution) a nd binarization, which are commonly used in model simplification, for both ReLU and sign activation functions. We find that random networks with ReLU activation are m ore robust to parameter perturbations with respect to their counterparts wit h sign activation, which arguably is reflected in the simplicity of the functions they generate . Keywords: large deviation theory, path integral, deep neural networks, fu nction sensitivity 1. Introduction Learning machines realized by deep neural networks (DNN) have ac hieved impressive success in performing various machine learning tasks, such as spee ch recognition, image classification and natural language processing [1].

Consider the problem of finding a population amongst many with the largest mean when these means are unknown but population samples can be generated via simulation. Typically, by selecting a population with the largest sample mean, it can be shown that the false selection probability decays at an exponential rate. Lately researchers have sought algorithms that guarantee that this probability is restricted to a small $\delta$ in order $\log(1/\delta)$ computational time by estimating the associated large deviations rate function via simulation. We show that such guarantees are misleading. Enroute, we identify the large deviations principle followed by the empirically estimated large deviations rate function that may also be of independent interest. Further, we show a negative result that when populations have unbounded support, under mild restrictions, any policy that asymptotically identifies the correct population with probability at least $1-\delta$ for each problem instance requires more than $O(\log(1/\delta))$ samples in making such a determination in any problem instance. This suggests that some restrictions are essential on populations to devise $O(\log(1/\delta))$ algorithms with $1 - \delta$ correctness guarantees. We note that under restriction on population moments, such methods are easily designed. We also observe that sequential methods from stochastic multi-armed bandit literature can be adapted to devise such algorithms.

Learning in neural networks poses peculiar challenges when using discretized rather then continuous synaptic states. The choice of discrete synapses is motivated by biological reasoning and experiments, and possibly by hardware implementation considerations as well. In this paper we extend a previous large deviations analysis which unveiled the existence of peculiar dense regions in the space of synaptic states which accounts for the possibility of learning efficiently in networks with binary synapses. We extend the analysis to synapses with multiple states and generally more plausible biological features. The results clearly indicate that the overall qualitative picture is unchanged with respect to the binary case, and very robust to variation of the details of the model. We also provide quantitative results which suggest that the advantages of increasing the synaptic precision (i.e.~the number of internal synaptic states) rapidly vanish after the first few bits, and therefore that, for practical applications, only few bits may be needed for near-optimal performance, consistently with recent biological findings. Finally, we demonstrate how the theoretical analysis can be exploited to design efficient algorithmic search strategies.