Stochastic Optimization Algorithms for Problems with Controllable Biased Oracles
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911432341192704 |
|---|---|
| author | Liu, Yin Tajbakhsh, Sam Davanloo |
| author_facet | Liu, Yin Tajbakhsh, Sam Davanloo |
| contents | Motivated by emerging applications in machine learning, we consider an optimization problem in a general form where the gradient of the objective function is available through a biased stochastic oracle. We assume a bias-control parameter can reduce the bias magnitude; however, a lower bias requires more computation/samples. For instance, in two applications on stochastic composition optimization and policy optimization for infinite-horizon Markov decision processes, we show that the bias follows a power law and exponential decay, respectively, as functions of their corresponding bias control parameters. For problems with such gradient oracles, the paper proposes stochastic algorithms that adjust the bias-control parameter throughout the iterations. We analyze the nonasymptotic performance of the proposed algorithms in the nonconvex regime and establish their sample or bias-control computational complexities to obtain a stationary point in expectation or with high probability. Finally, we numerically evaluate the performance of the proposed algorithms over three applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_07810 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Stochastic Optimization Algorithms for Problems with Controllable Biased Oracles Liu, Yin Tajbakhsh, Sam Davanloo Optimization and Control Motivated by emerging applications in machine learning, we consider an optimization problem in a general form where the gradient of the objective function is available through a biased stochastic oracle. We assume a bias-control parameter can reduce the bias magnitude; however, a lower bias requires more computation/samples. For instance, in two applications on stochastic composition optimization and policy optimization for infinite-horizon Markov decision processes, we show that the bias follows a power law and exponential decay, respectively, as functions of their corresponding bias control parameters. For problems with such gradient oracles, the paper proposes stochastic algorithms that adjust the bias-control parameter throughout the iterations. We analyze the nonasymptotic performance of the proposed algorithms in the nonconvex regime and establish their sample or bias-control computational complexities to obtain a stationary point in expectation or with high probability. Finally, we numerically evaluate the performance of the proposed algorithms over three applications. |
| title | Stochastic Optimization Algorithms for Problems with Controllable Biased Oracles |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2306.07810 |