Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates | PERPUSTAKAAN UNIVERSITAS KATOLIK PARAHYANGAN

Pencarian berdasarkan :

Pencarian terakhir:

Text

Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates

Balasubramanian, Krishnakumar - Nama Orang; Ghadimi, Saeed - Nama Orang; Nguyen, Anthony - Nama Orang;

In this paper, we study smooth stochastic multilevel composition optimization problems, where the objective function is a nested composition of T functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle. For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze their convergence to an ϵ-stationary point of the problem. We show that the first algorithm, which is a generalization of [S. Ghadimi, A. Ruszczynski, and M. Wang, SIAM J. Optim., 30 (2020), pp. 960--979] to the T level case, can achieve a sample complexity of OT(1/ϵ6) by using minibatches of samples in each iteration, where OT hides constants that depend on T. By modifying this algorithm using linearized stochastic estimates of the function values, we improve the sample complexity to OT(1/ϵ4). This modification not only removes the requirement of having a minibatch of samples in each iteration, but also makes the algorithm parameter-free and easy to implement. To the best of our knowledge, this is the first time that such an online algorithm designed for the (un)constrained multilevel setting obtains the same sample complexity of the smooth single-level setting, under standard assumptions (unbiasedness and boundedness of the second moments) on the stochastic first-order oracle.

Ketersediaan

Barcode		Tipe Koleksi	Nomor Panggil	Lokasi	Status
art142438	null	Artikel		Gdg9-Lt3	Tersedia namun tidak untuk dipinjamkan - No Loan

Informasi Detail

Judul Seri: SIAM JOURNAL ON OPTIMIZATION; Vol.32 No.2 April-June 2022
No. Panggil: -
Penerbit: : .,
Deskripsi Fisik: p. 519-544
Bahasa: English
ISBN/ISSN: -
Klasifikasi: NONE
Tipe Isi: -
Tipe Media: -
Tipe Pembawa: -
Edisi: -
Subjek: NONCONVEX OPTIMIZATION
COMPLEXITY BOUNDS
MULTILEVEL STOCHASTIC COMPOSITION
LEVEL-INDEPENDENT CONVERGENCE RATE
Info Detail Spesifik: https://doi.org/10.1137/21M1406222
Pernyataan Tanggungjawab: Krishnakumar Balasubramanian, Saeed Ghadimi, Anthony Nguyen

Versi lain/terkait

Tidak tersedia versi lain

Lampiran Berkas

Tidak Ada Data

Komentar

Anda harus masuk sebelum memberikan komentar