Stochastic gradient descent(SGD)methods have gained widespread popularity for solving large-scale optimization problems.However,the inherent variance in SGD often leads to slow convergence rates.We introduce a family ...Stochastic gradient descent(SGD)methods have gained widespread popularity for solving large-scale optimization problems.However,the inherent variance in SGD often leads to slow convergence rates.We introduce a family of unbiased stochastic gradient estimators that encompasses existing estimators from the literature and identify a gradient estimator that not only maintains unbiasedness but also achieves minimal variance.Compared with the existing estimator used in SGD algorithms,the proposed estimator demonstrates a significant reduction in variance.By utilizing this stochastic gradient estimator to approximate the full gradient,we propose two mini-batch stochastic conjugate gradient algorithms with minimal variance.Under the assumptions of strong convexity and smoothness on the objective function,we prove that the two algorithms achieve linear convergence rates.Numerical experiments validate the effectiveness of the proposed gradient estimator in reducing variance and demonstrate that the two stochastic conjugate gradient algorithms exhibit accelerated convergence rates and enhanced stability.展开更多
The generalized likelihood ratio(GLR)method is a recently introduced gradient estimation method for handling discontinuities in a wide range of sample performances.We put the GLR methods from previous work into a sing...The generalized likelihood ratio(GLR)method is a recently introduced gradient estimation method for handling discontinuities in a wide range of sample performances.We put the GLR methods from previous work into a single framework,simplify regularity conditions to justify the unbiasedness of GLR,and relax some of those conditions that are difficult to verify in practice.Moreover,we combine GLR with conditional Monte Carlo methods and randomized quasi-Monte Carlo methods to reduce the variance.Numerical experiments show that variance reduction could be significant in various applications.展开更多
基金supported by the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27010101)the Beijing Natural Science Foundation(Grant No.Z220004)+1 种基金the Chinese NSF(Grant No.12021001)the Fundamental Research Funds for the Central Universities(Grant No.2023ZCJH02)。
文摘Stochastic gradient descent(SGD)methods have gained widespread popularity for solving large-scale optimization problems.However,the inherent variance in SGD often leads to slow convergence rates.We introduce a family of unbiased stochastic gradient estimators that encompasses existing estimators from the literature and identify a gradient estimator that not only maintains unbiasedness but also achieves minimal variance.Compared with the existing estimator used in SGD algorithms,the proposed estimator demonstrates a significant reduction in variance.By utilizing this stochastic gradient estimator to approximate the full gradient,we propose two mini-batch stochastic conjugate gradient algorithms with minimal variance.Under the assumptions of strong convexity and smoothness on the objective function,we prove that the two algorithms achieve linear convergence rates.Numerical experiments validate the effectiveness of the proposed gradient estimator in reducing variance and demonstrate that the two stochastic conjugate gradient algorithms exhibit accelerated convergence rates and enhanced stability.
基金the National Natural Science Foundation of China(NSFC)under Grant 72022001,92146003,71901003the Air Force Office of Scientific Research under Grant FA95502010211by Discover GrantRGPIN-2018-05795fromNSERCCanada.
文摘The generalized likelihood ratio(GLR)method is a recently introduced gradient estimation method for handling discontinuities in a wide range of sample performances.We put the GLR methods from previous work into a single framework,simplify regularity conditions to justify the unbiasedness of GLR,and relax some of those conditions that are difficult to verify in practice.Moreover,we combine GLR with conditional Monte Carlo methods and randomized quasi-Monte Carlo methods to reduce the variance.Numerical experiments show that variance reduction could be significant in various applications.
