Réduction de la variance

La réduction de la variance regroupe l'ensemble des techniques, plus ou moins simples, qui permettent de réduire la variance des estimateurs de Monte-Carlo. En voici une courte liste :

Variable antithétique : on introduit une seconde variable aléatoire très fortement négativement corrélée avec la première, permettant de réduire la variance. L'élément clef est la formule suivante, valable pour deux variables X,Y: :\mathrm{Var}(X+Y) = \mathrm{Var}(X) + \mathrm{Var}(Y) + 2 \mathrm{Cov}(X,Y)
Variable de contrôle : on introduit une variable tierce, dite variable de contrôle, et on construit une nouvelle classe d'estimateurs, dépendant d'un paramètre c. On cherche la valeur du paramètre c permettant de réaliser une réduction de variance, par rapport à l'estimation Monte-Carlo de base ;
L'échantillonnage préférentiel (ou importance sampling en anglais) : lors du tirage de données aléatoires, certaines valeurs ont plus d'importance que d'autres dans l'évaluat

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (16)

Publications associées

Chargement

Personnes associées (2)

Personnes associées

Chargement

Unités associées (2)

Unités associées

Chargement

Concepts associés (2)

Concepts associés

Chargement

Cours associés (5)

Cours associés

Chargement

Séances de cours associées (13)

Séances de cours associées

Chargement

Tensor-Based Numerical Method For Stochastic Homogenization

This paper addresses the complexity reduction of stochastic homogenization of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is obtained using a method designed to exploit quasi-periodicity. Accuracy and cost reduction are investigated for local perturbations or small transformations of periodic materials as well as for materials with no periodicity but a mesoscopic structure, for which the limitations of the method are shown. Finally, for materials outside the scope of this method, we propose to use the approximation of homogenized quantities as control variates for variance reduction of a more accurate and costly Monte Carlo estimator (using a multifidelity Monte Carlo method). The resulting cost reduction is illustrated in a numerical experiment and compared with a control variate method from weakly stochastic homogenization. The limits of this variance reduction technique are tested on materials without periodicity or mesoscopic structure.

SIAM PUBLICATIONS2022

Chargement

Stochastic Zeroth-Order Optimisation Algorithms with Variance Reduction

Ahmad Ajalloeian

Introduction of optimisation problems in which the objective function is black box or obtaining the gradient is infeasible, has recently raised interest in zeroth-order optimisation methods. As an example finding adversarial examples for Deep Learning models (Chen et al. (2017); Moosavi-Dezfooli et al. (2016)) is one of the most common applications in which zeroth-order methods could be used. These optimisation methods use only function values at certain points to estimate the gradient. Most current approaches iteratively sample a random search direction along which they compute an estimation of the gradient (Nesterov and Spokoiny (2017); Conn et al. (2009); Wibisono et al. (2012)). However, due to the high variance in the search direction, these methods usually need d times more iterations than the standard gradient methods, where d is the dimensionality of the problem. So it seems that the main effort for improving the zeroth-order methods should be in reducing the variance of the gradient estimate. In this work we will analyse the gradient-free oracle which uses random directions sampled form a Gaussian distribution. Our analysis shows that in smooth and strongly convex setting, we have a convergence rate of O( d/T) which clearly shows the dependency to the dimension of the problem. Furthermore we propose some variance reduction methods to make the zeroth-order optimisation faster. We experiment our proposed methods in Python to compare their convergence in stochastic and non-stochastic setting. Our empirical results show that in a setting that number of allowed function evaluation is fixed, using a variance reduction method (e.g. momentum) can make the convergence of zeroth-order methods happen faster.

2019

Chargement

Robust Maximization of Non-Submodular Objectives

Ilija Bogunovic, Volkan Cevher, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exist constant-factor guarantees when the function is submodular [1, 2], there are no guarantees for non-submodular objectives. In this work, we present a new algorithm Oblivious-Greedy and prove the first constant-factor approximation guarantees for a wider class of non-submodular objectives. The obtained theoretical bounds are the first constant-factor bounds that also hold in the linear regime, i.e. when the number of deletions is linear in k. Our bounds depend on established parameters such as the submodularity ratio and some novel ones such as the inverse curvature. We bound these parameters for two important objectives including support selection and variance reduction. Finally, we numerically demonstrate the robust performance of Oblivious-Greedy for these two objectives on various datasets.

2018

Chargement

MATH-414: Stochastic simulation

The student who follows this course will get acquainted with computational tools used to analyze systems with uncertainty arising in engineering, physics, chemistry, and economics. Focus will be on sampling methods as Monte Carlo, quasi Monte Carlo, Markov Chain Monte Carlo.

MATH-600: Optimization and simulation

Master state-of-the art methods in optimization with heuristics and simulation. Work involves:

reading the material beforehand
class hours to discuss the material and solve problems
homework

CS-439: Optimization for machine learning

This course teaches an overview of modern optimization methods, for applications in machine learning and data science. In particular, scalability of algorithms to large datasets will be discussed in theory and in implementation.

Méthode de Monte-Carlo

Une méthode de Monte-Carlo, ou méthode Monte-Carlo, est une méthode algorithmique visant à calculer une valeur numérique approchée en utilisant des procédés aléatoires, c'est-à-dire des techniques p

Échantillonnage préférentiel

L'échantillonnage préférentiel, en anglais importance sampling, est une méthode de réduction de la variance qui peut être utilisée dans la méthode de Monte-Carlo. L'idée sous-jacente à l'échantillonna