Optimal order of accuracy of search algorithms in stochastic optimization

B. T. Polyak; A. B. Tsybakov

Optimal order of accuracy of search algorithms in stochastic optimization

B. T. Polyak
, A. B. Tsybakov

Research output: Contribution to journal › Article › peer-review

Abstract

Let f: R^N → R¹ be an unknown function with a unique minimum at the point x^*. The problem of estimating x^* from the observations y_n = f(X_n) + ξ_n, n = 1,2,..., where ξ_n are independent random errors and x_n are observations points, is considered in the minimax setting. The best attainable characteristics of stochastic optimization algorithms are investigated, and algorithms with optimal order of accuracy are proposed.

Original language	English
Pages (from-to)	126-133
Number of pages	8
Journal	Problems of Information Transmission
Volume	26
Issue number	2
Publication status	Published - 1 Oct 1990

Cite this

@article{305f68217eda4a75ba029fcac8a12407,

title = "Optimal order of accuracy of search algorithms in stochastic optimization",

abstract = "Let f: RN → R1 be an unknown function with a unique minimum at the point x*. The problem of estimating x* from the observations yn = f(Xn) + ξn, n = 1,2,..., where ξn are independent random errors and xn are observations points, is considered in the minimax setting. The best attainable characteristics of stochastic optimization algorithms are investigated, and algorithms with optimal order of accuracy are proposed.",

author = "Polyak, \{B. T.\} and Tsybakov, \{A. B.\}",

year = "1990",

month = oct,

day = "1",

language = "English",

volume = "26",

pages = "126--133",

journal = "Problems of Information Transmission",

issn = "0032-9460",

number = "2",

}

TY - JOUR

T1 - Optimal order of accuracy of search algorithms in stochastic optimization

AU - Polyak, B. T.

AU - Tsybakov, A. B.

PY - 1990/10/1

Y1 - 1990/10/1

N2 - Let f: RN → R1 be an unknown function with a unique minimum at the point x*. The problem of estimating x* from the observations yn = f(Xn) + ξn, n = 1,2,..., where ξn are independent random errors and xn are observations points, is considered in the minimax setting. The best attainable characteristics of stochastic optimization algorithms are investigated, and algorithms with optimal order of accuracy are proposed.

AB - Let f: RN → R1 be an unknown function with a unique minimum at the point x*. The problem of estimating x* from the observations yn = f(Xn) + ξn, n = 1,2,..., where ξn are independent random errors and xn are observations points, is considered in the minimax setting. The best attainable characteristics of stochastic optimization algorithms are investigated, and algorithms with optimal order of accuracy are proposed.

M3 - Article

AN - SCOPUS:0025496781

SN - 0032-9460

VL - 26

SP - 126

EP - 133

JO - Problems of Information Transmission

JF - Problems of Information Transmission

IS - 2

ER -

Optimal order of accuracy of search algorithms in stochastic optimization

Abstract

Fingerprint

Cite this