It is shown that, by pilot-estimating these model quantities using a negligible fraction of the simulation budget, substantial robustness is attained in the resulting FD estimators, and how such an approach is competitive against any choices of prescribed perturbation size, even if they are designed to be minimax-optimal over reasonable classes of target functions and FD schemes.
Abstract
We study stochastic gradient estimation in black-box environments where only noisy simulation observations of function values are available. Finite-difference (FD) methods are among the most widely used zeroth-order gradient estimators in such settings, by measuring the change in function values against a perturbation size. While the optimal order in choosing this perturbation size with respect to the simulation budget is well understood, the optimal constant factor relies on model characteristics that are typically unknown and viewed to be as difficult to estimate as the gradient itself. Consequently, FD estimators are often based on ad hoc tuning of the perturbation size, which may exhibit highly unstable performance across problem instances. In this paper, we challenge this conventional wisdom from both theoretical and practical perspectives. We show that, by pilot-estimating these model quantities using a negligible fraction of the simulation budget, substantial robustness is attained in the resulting FD estimators. Theoretically, we show that using a perturbation size governed by this pilot estimation can already achieve an MSE that is first-order identical to the ``oracle"MSE as if the optimal perturbation size is known in advance. Moreover, we show how such an approach is competitive against any choices of prescribed perturbation size, even if they are designed to be minimax-optimal over reasonable classes of target functions and FD schemes. Our proposed pilot estimation is practically easy to run, and a variety of numerical experiments demonstrate both the robustness and near-oracle optimality of our estimator relative to conventional FD schemes based on ad hoc tuning.
In sampling problems, gradient-based schemes such as Langevin Monte Carlo (LMC) mix faster than non-gradient-based methods, but their applicability is limited by access to the gradient of the target log-density. In practice, gradients are often unavailable and function evaluations are noisy, e.g., stochastic simulators or black-box simulators, so we propose LMC-SPSA with noise, which approximates the gradient of the target log-density using two noisy function evaluations per iteration. We prove, under noisy gradient estimates, that LMC-SPSA converges in distribution by proving the convergence in Wasserstein distance. Furthermore, we construct a diminishing step-size schedule that still drives the Wasserstein error bound to convergence, extending convergence guarantees beyond the constant-step setting. Further, we sharpen the dominant dimension dependence of the Wasserstein error from $O(p^4)$ to $O(p^2)$ (with $p$ denoting the dimension), and support this analysis with numerical results. We show that LMC-SPSA achieves $W_2$-accuracy $\varepsilon$ with total noisy-oracle complexity of $O(p/\varepsilon^2+\delta^2p^3/\varepsilon^3)$, where $\delta$ is the paired-noise level. This improves the noise-dependent accuracy scaling relative to the ZO-LMC method of Roy et al. We further establish asymptotically vanishing Wasserstein error as the number of iterations $\to\infty$ under diminishing step-size and perturbation sequences and derive an explicit convergence rate for a balanced schedule under noisy zeroth-order feedback. Empirical experiments are conducted to verify the performance of LMC-SPSA with noise. We provide an oracle-budget-matched comparison with the ZO-LMC method, showing smaller empirical sampling errors under the same function-evaluation budget.
This paper proposes a tractable stochastic approach based on an entropic regularization of the distributionally robust value function, which makes it possible to compute stochastic gradient estimators, and the combination of these estimators with a stochastic Frank-Wolfe algorithm, allowing us to optimize the regularized robust objective while naturally handling constraints.
This paper investigates stochastic approximation methods based on finite differences for the minimization of quasiconvex functions. Traditional approaches to convex optimization problems primarily rely on exact or stochastic subgradients. However, in many practical situations, only noisy information about function values is available. In such cases, stochastic quasi-gradient schemes constructed using randomized finite-difference estimators are considered. In particular, we study batch two-point schemes that provide unbiased approximations of the gradient of a smoothed objective function. Variance bounds are established for these estimators, which enable a rigorous convergence analysis of projected stochastic descent methods.
The paper considers the minimization problem of functions of the form $f(x) = \max_{i \in I} f_i(x),$ where each function $f_i(x),$ $i \in I,$ is quasiconvex and has a Lipschitz-continuous gradient on a convex compact set. The main result of the paper is the derivation of convergence rate estimates for stochastic finite-difference methods in the quasiconvex setting. It is shown that the expected suboptimality decreases at the rate $O\!\left(1/\sqrt{k}\right).$ The obtained results significantly broaden the applicability of stochastic finite-difference methods to nonsmooth quasiconvex optimization problems and provide a rigorous theoretical justification of the algorithm in black-box settings where only noisy function evaluations are available.
Rafik A. Khachatryan· Russian Universities Reports...· 0 citations
This paper studies the convergence of stochastic gradient descent when the implemented updates are subject to a persistent and state-dependent bias, in which the desired update is scaled by response functions component-wise, and proposes a gradient-based algorithm, termed Residual Learning.
Zhaoxian Wu, Quan Xiao, Tayfun Gokmen et al.· 0 citations
Motivated by batch and semi-batch process operation, we study finite-horizon open-loop dynamic optimization problems with uncertain parameters. A common computational approach replaces the expected performance criterion by an average over finitely many sampled parameter realizations. We develop a statistical theory for the resulting sample-based optimal value as an estimator of the population optimal value. The analysis is based on a stability estimate showing that terminal losses depend Lipschitz continuously on the time-integrated control, which records the cumulative input delivered up to each time. This estimate yields a functional central limit theorem for the sample-based objective and a statistical limit theorem for the corresponding optimal value error. As a consequence, we obtain confidence intervals for the population optimal value. When the population optimizer is unique, the limit is Gaussian and leads to a plug-in confidence interval. When multiple optimal policies may exist, we use a subsampling confidence interval that does not require uniqueness. The methodology is illustrated on two fed-batch case studies in which feed-rate profiles are optimized under parametric uncertainty.
It is obvious to say that an adequate estimation of the autocorrelation function is central in time series analysis. In this paper, we propose three new robust estimators based on ratios of observations, which offer strong resistance against outliers. While the first estimator, which is based on the median, is not efficient, the second is a Quasi Maximum Likelihood (QML) estimator with better efficiency properties. The third estimator is a plug-in estimator, which does not require numerical optimization and, consequently, is extremely simple from a computationally point of view, having similar efficiency to that of the ML estimator. We derive the asymptotic distribution of the first two estimators, when the true autocorrelations are zero. Furthermore, we also show that the asymptotic distribution of the plug-in estimator is rather close to that of the QML estimator, allowing for inference and, in particular, for the construction of point-wise significance bands for the autocorrelations. Using Monte Carlo simulations, we analyse the finite sample properties of the proposed estimators and compare them with those of the sample autocorrelations and alternative extant robust estimators based on ranks. Although the proposed estimators have larger dispersion than the sample autocorrelations in uncontaminated time series, they are highly robust in the presence of outliers. Also, they have better properties than popular alternative robust estimators based on ranks when estimating autocorrelations of order larger than one. The results are illustrated by estimating the correlogram of daily IBEX35 returns, quarterly US economic growth and monthly US inflation.