Publication

Cover: A Cluster-Based Variance Reduced Method For Online Learning

Ali H. Sayed, Bicheng Ying, Kun Yuan
2019
Conference Papers

Abstract

In this paper, we develop a stochastic-gradient learning algorithm for situations involving streaming data that arise from an underlying clustered structure. In such settings, the variance of gradient noise can be decomposed into the in-cluster variance sigma(2)(in) in plus the between-cluster variance sigma(2)(bet). We develop a cluster-based online variance-reduced method (COVER) to eliminate sigma(2)(bet) and improve the MSD performance of stochastic- gradient descent (SGD) to the order of O(sigma(2)(in)). We establish the convergence property of COVER and derive a tight closed-form mean-square deviation (MSD) performance expression. Our simulations illustrate the improved performance of COVER in terms of steady- state performance.

Official source

https://infoscience.epfl.ch/entities/publication/bc77b04e-8fe4-4220-87de-a9d4f441b1a4

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Ali H. Sayed, Bicheng Ying, Kun Yuan
2019
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/bc77b04e-8fe4-4220-87de-a9d4f441b1a4

About this result

Related concepts (25)

Stochastic gradient descent

Stochastic gradient descent (often abbreviated SGD) is an iterative method for optimizing an objective function with suitable smoothness properties (e.g. differentiable or subdifferentiable). It can be regarded as a stochastic approximation of gradient descent optimization, since it replaces the actual gradient (calculated from the entire data set) by an estimate thereof (calculated from a randomly selected subset of the data).

Standard deviation

In statistics, the standard deviation is a measure of the amount of variation or dispersion of a set of values. A low standard deviation indicates that the values tend to be close to the mean (also called the expected value) of the set, while a high standard deviation indicates that the values are spread out over a wider range. Standard deviation may be abbreviated SD, and is most commonly represented in mathematical texts and equations by the lower case Greek letter σ (sigma), for the population standard deviation, or the Latin letter s, for the sample standard deviation.

Chi-squared distribution

In probability theory and statistics, the chi-squared distribution (also chi-square or -distribution) with degrees of freedom is the distribution of a sum of the squares of independent standard normal random variables. The chi-squared distribution is a special case of the gamma distribution and is one of the most widely used probability distributions in inferential statistics, notably in hypothesis testing and in construction of confidence intervals.

Related publications (31)

Imitation Learning in Discounted Linear MDPs without exploration assumptions

Volkan Cevher, Luca Viano, Efstratios Panteleimon Skoulakis

We present a new algorithm for imitation learning in infinite horizon linear MDPs dubbed ILARL which greatly improves the bound on the number of trajectories that the learner needs to sample from the environment. In particular, we re- move exploration assu ...

2024

Anthony C Davison and Igor Rodionov's contribution to the Discussion of 'Estimating means of bounded random variables by betting' by Waudby-Smith and Ramdas

Anthony Christopher Davison, Igor Rodionov

We derive confidence intervals (CIs) and confidence sequences (CSs) for the classical problem of estimating a bounded mean. Our approach generalizes and improves on the celebrated Chernoff method, yielding the best closed-form "empirical-Bernstein" CSs and ...

Oxford Univ Press2024

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Anastasiia Koloskova

Distributed learning is the key for enabling training of modern large-scale machine learning models, through parallelising the learning process. Collaborative learning is essential for learning from privacy-sensitive data that is distributed across various ...

EPFL2024