Hessian matrix | EPFL Graph Search

In mathematics, the Hessian matrix, Hessian or (less commonly) Hesse matrix is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named after him. Hesse originally used the term "functional determinants". Definitions and properties Suppose f : \R^n \to \R is a function taking as input a vector \mathbf{x} \in \R^n and outputting a scalar f(\mathbf{x}) \in \R. If all second-order partial derivatives of f exist, then the Hessian matrix \mathbf{H} of f is a square n \times n matrix, usually defined and arranged as \mathbf H_f= \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1,\partial x_2} & \cdots & \dfr

A Distributed Second-Order Algorithm You Can Trust

Matilde Gargiani, Thomas Hofmann, Martin Jaggi, Aurélien Lucchi

Due to the rapid growth of data and computational resources, distributed optimization has become an active research area in recent years. While first-order methods seem to dominate the field, second-order methods are nevertheless attractive as they potentially require fewer communication rounds to converge. However, there are significant drawbacks that impede their wide adoption, such as the computation and the communication of a large Hessian matrix. In this paper we present a new algorithm for distributed training of generalized linear models that only requires the computation of diagonal blocks of the Hessian matrix on the individual workers. To deal with this approximate information we propose an adaptive approach that - akin to trust-region methods - dynamically adapts the auxiliary model to compensate for modeling errors. We provide theoretical rates of convergence for a wide class of problems including L1-regularized objectives. We also demonstrate that our approach achieves state-of-the-art results on multiple large benchmark datasets.

2018

The double exponential runtime is tight for 2-stage stochastic ILPs

Klaus Jansen, Kim-Manuel Klein, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = b, l

SPRINGER HEIDELBERG2022

The stochastic heat equation: hitting probabilities and the probability density function of the supremum via Malliavin calculus

Fei Pu

In this thesis, we study systems of linear and/or non-linear stochastic heat equations and fractional heat equations in spatial dimension

1

driven by space-time white noise. The main topic is the study of hitting probabilities for the solutions to these systems. We first study the properties of the probability density functions of the solution to non-linear systems of stochastic fractional heat equations driven by multiplicative space-time white noise. Using the techniques of Malliavin calculus, we prove that the one-point probability density function of the solution is infinitely differentiable, uniformly bounded and positive everywhere. Moreover, a Gaussian-type upper bound on the two-point probability density function is obtained by a detailed analysis of the small eigenvalues of the Malliavin matrix. We establish an optimal lower bound on hitting probabilities for the (non-Gaussian) solution, which is as sharp as that for the Gaussian solution to a system of linear equations. We develop a new method to study the upper bound on hitting probabilities, from the perspective of probability density functions. For the solution to the linear stochastic heat equation, we prove that the random vector, which consists of the solution and the supremum of a linear increment of the solution over a time segment, has an infinitely differentiable probability density function. We derive a formula for this density and establish a Gaussian-type upper bound. The smoothness property and Gaussian-type upper bound for the density of the supremum of the solution over a space-time rectangle touching the

t = 0

axis are also studied. Furthermore, we extend these results to the solutions of systems of linear stochastic fractional heat equations. For a system of linear stochastic heat equations with Dirichlet boundary conditions, we present a sufficient condition for certain sets to be hit with probability one.

EPFL2018

The stochastic heat equation: hitting probabilities and the probability density function of the supremum via Malliavin calculus

Fei Pu

In this thesis, we study systems of linear and/or non-linear stochastic heat equations and fractional heat equations in spatial dimension

1

t = 0

EPFL2018