The overall performance or expected excess risk of an iterative machine learning algorithm can be decomposed into training error and generalization error. While the former is controlled by its convergence analysis, the latter can be tightly handled by algorithmic stability. The machine learning community has a rich history investigating convergence and stability separately. However, the question about the trade-off between these two quantities remains open. In this paper, we show that for any iterative algorithm at any iteration, the overall performance is lower bounded by the minimax statistical error over an appropriately chosen loss function class. This implies an important trade-off between convergence and stability of the algorithm -- a faster converging algorithm has to be less stable, and vice versa. As a direct consequence of this fundamental tradeoff, new convergence lower bounds can be derived for classes of algorithms constrained with different stability bounds. In particular, when the loss function is convex (or strongly convex) and smooth, we discuss the stability upper bounds of gradient descent (GD) and stochastic gradient descent and their variants with decreasing step sizes. For Nesterov's accelerated gradient descent (NAG) and heavy ball method (HB), we provide stability upper bounds for the quadratic loss function. Applying existing stability upper bounds for the gradient methods in our trade-off framework, we obtain lower bounds matching the well-established convergence upper bounds up to constants for these algorithms and conjecture similar lower bounds for NAG and HB. Finally, we numerically demonstrate the tightness of our stability bounds in terms of exponents in the rate and also illustrate via a simulated logistic regression problem that our stability bounds reflect the generalization errors better than the simple uniform convergence bounds for GD and NAG.

This paper studies the complexity of the stochastic gradient algorithm for PCA when the data are observed in a streaming setting. We also propose an online approach for selecting the learning rate. Simulation experiments confirm the practical relevance of the plain stochastic gradient approach and that drastic improvements can be achieved by learning the learning rate.

A key challenge in complex visuomotor control is learning abstract representations that are effective for specifying goals, planning, and generalization. To this end, we introduce universal planning networks (UPN). UPNs embed differentiable planning within a goal-directed policy. This planning computation unrolls a forward model in a latent space and infers an optimal action plan through gradient descent trajectory optimization. The plan-by-gradient-descent process and its underlying representations are learned end-to-end to directly optimize a supervised imitation learning objective. We find that the representations learned are not only effective for goal-directed visual imitation via gradient-based trajectory optimization, but can also provide a metric for specifying goals using images. The learned representations can be leveraged to specify distance-based rewards to reach new target states for model-free reinforcement learning, resulting in substantially more effective learning when solving new tasks described via image-based goals. We were able to achieve successful transfer of visuomotor planning strategies across robots with significantly different morphologies and actuation capabilities.

We present a neurosymbolic approach to the lifelong learning of algorithmic tasks that mix perception and procedural reasoning. Reusing highlevel concepts across domains and learning complex procedures are two key challenges in lifelong learning. We show that a combination of gradientbased learning and symbolic program synthesis can be a more effective response to these challenges than purely neural methods. Concretely, our approach, called HOUDINI, represents neural networks as strongly typed, end-to-end differentiable functional programs that use symbolic higher-order combinators to compose a library of neural functions. Our learning algorithm consists of: (1) a program synthesizer that performs a type-directed search over programs in this language, and decides on the library functions that should be reused and the architectures that should be used to combine them; and (2) a neural module that trains synthesized programs using stochastic gradient descent. We evaluate our approach on three algorithmic tasks. Our experiments show that our type-directed search technique is able to significantly prune the search space of programs, and that the overall approach transfers high-level concepts more effectively than monolithic neural networks as well as traditional transfer learning.

Gradient-based Monte Carlo algorithms are useful tools for sampling posterior distributions. Similar to gradient descent algorithms, gradient-based Monte Carlo generates posterior samples iteratively using the gradient of loglikelihood. Langevin dynamics (LD) and Hamiltonian Monte Carlo (HMC) [Duane et al., 1987, Neal et al., 2011] are two important examples of gradient-based Monte Carlo sampling algorithms that are widely used in Bayesian inference. Since calculating likelihood on large datasets is expensive, people use stochastic gradients [Robbins and Monro, 1951] in place of full gradient, and have, for both Langevin dynamics and Hamiltonian Monte Carlo, developed their stochastic gradient counterparts[Welling and Teh, 2011, Chen et al., 2014]. Stochastic gradient Hamiltonian Monte Carlo (SGHMC) usually converges faster than stochastic gradient Langevin dynamics (SGLD) in practical machine learning tasks like covariance estimation of bivariate Gaussian and Bayesian neural networks for classification on MNIST dataset, as demonstrated in [Welling and Teh, 2011]. Similar phenomenon was also observed in [Chen et al., 2015] where SGHMC and SGLD were compared on both synthetic and real-world datasets. Intuitively speaking, comparing against SGLD, SGHMC has a momentum term that enables it to explore the parameter space of posterior distribution much faster when the gradient of log-likelihood becomes smaller. Very recently, [Dubey et al., 2016] borrowed the standard variance reduction techniques from the stochastic optimization literature [Johnson and Zhang, 2013, Defazio et al., 2014] and applied them on SGLD to obtain two variancereduced SGLD algorithms (called SAGA-LD and SVRG-LD) with improved theoretical results and practical performance. Because of the superiority of SGHMC over SGLD in terms of convergence rate in a wide range of machine learning tasks, it would be a natural question whether such variance reduction techniques can be applied on SGHMC to achieve better results than variance-reduced SGLD.

Stochastic gradient descent (SGD) and its variations, e.g., SGD with either classic or Nesterov momentum, RMSProp, Adam, adaptive learning rates, etc., are popular in diverse stochastic optimization problems, e.g., machine learning and online signal processing [1]-[6]. Off-the-shelf methods from convex optimizations, e.g., the quasi-Newton method, conjugate gradient method and truncated Newton method, i.e., the Hessian-free optimization, are attracting more attentions [7]-[10], and find many successful applications in stochastic optimizations as well. At the same time, searchings for new optimization theories and learning rules are always active, and methods like natural gradient descent, relative gradient descent, and equilibrated SGD (ESGD) [11]-[13], provide us with great insight into the properties of the parameter spaces and cost function surfaces in stochastic optimizations. This paper studies the performance of preconditioned SGD (PSGD) [14], a method which explicitly considers the non-convexity and gradient noises in stochastic optimizations. We consider preconditioners in several forms, i.e., dense preconditioner, diagonal preconditioner, Kronecker product preconditioner and more flexible forms. ESGD and batch normalization [18] are shown to be PSGDs with specific forms of preconditioners. We also consider different ways to evaluate the Hessianvector product, an important measurement that helps PSGD to adaptively extract the curvature information of cost surfaces. Our benchmark problems have synthetic and real world data, and involves most commonly used neural network models, e.g., recurrent and convolutional networks. We argue that Kronecker product preconditioners are particularly suitable for training neural networks since affine transformations are their basic building blocks.

Population risk---the expectation of the loss over the sampling mechanism---is always of primary interest in machine learning. However, learning algorithms only have access to empirical risk, which is the average loss over training examples. Although the two risks are typically guaranteed to be pointwise close, for applications with nonconvex nonsmooth losses (such as modern deep networks), the effects of sampling can transform a well-behaved population risk into an empirical risk with a landscape that is problematic for optimization. The empirical risk can be nonsmooth, and it may have many additional local minima. This paper considers a general optimization framework which aims to find approximate local minima of a smooth nonconvex function $F$ (population risk) given only access to the function value of another function $f$ (empirical risk), which is pointwise close to $F$ (i.e., $\|F-f\|_{\infty} \le \nu$). We propose a simple algorithm based on stochastic gradient descent (SGD) on a smoothed version of $f$ which is guaranteed to find an $\epsilon$-second-order stationary point if $\nu \le O(\epsilon^{1.5}/d)$, thus escaping all saddle points of $F$ and all the additional local minima introduced by $f$. We also provide an almost matching lower bound showing that our SGD-based approach achieves the optimal trade-off between $\nu$ and $\epsilon$, as well as the optimal dependence on problem dimension $d$, among all algorithms making a polynomial number of queries. As a concrete example, we show that our results can be directly used to give sample complexities for learning a ReLU unit, whose empirical risk is nonsmooth.

Recent advances in policy gradient methods and deep learning have demonstrated their applicability for complex reinforcement learning problems. However, the variance of the performance gradient estimates obtained from the simulation is often excessive, leading to poor sample efficiency. In this paper, we apply the stochastic variance reduced gradient descent (SVRG) to model-free policy gradient to significantly improve the sample-efficiency. The SVRG estimation is incorporated into a trust-region Newton conjugate gradient framework for the policy optimization. On several Mujoco tasks, our method achieves significantly better performance compared to the state-of-the-art model-free policy gradient methods in robotic continuous control such as trust region policy optimization (TRPO)

Our aim is to study gradient descent in such loss functions or energy landscapes and compare it to results obtained from real high-dimensional optimization problems such as encountered in deep learning. In particular, we analyze the distribution of the improved loss function after a step of gradient descent, provide analytic expressions for the moments as well as prove asymptotic normality as the dimension of the parameter space becomes large. Moreover, we compare this with the expectation of the global minimum of the landscape obtained by means of the Euler characteristic of excursion sets. Besides complementing our analytical findings with numerical results from simulated Gaussian random fields, we also compare it to loss functions obtained from optimisation problems on synthetic and real data sets by proposing a "black box" random field toy-model for a deep neural network loss function.

We propose three new robust aggregation rules for distributed synchronous Stochastic Gradient Descent (SGD) under a general Byzantine failure model. The attackers can arbitrarily manipulate the data transferred between the servers and the workers in the parameter server (PS) architecture. We prove the Byzantine resilience properties of these aggregation rules. Empirical analysis shows that the proposed techniques outperform current approaches for realistic use cases and Byzantine attack scenarios.