Gradijentne metode bezuvjetne minimizacije

undergraduate thesis

• Title (english): Gradient-based algorithms for unconstrained minimization
• Author: Karlo Hubak
• Mentor: Josipa Pina Milišić (mentor)
• Committee member: Josipa Pina Milišić (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Anamari Nakić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2020-09-15, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Gradijentni algoritmi su često korištene metode prilikom riješavanja problema bezuvjetne minimizacije. Poznavajući gradijent funkcije koja je objekt optimizacije, svaka iteracija gradijentnog algoritma teži minimumu dane funkcije. U vrijeme kada algoritmi koji služe za predviđanje (u koje se ubrajaju i gradijentni algoritmi) često trebaju baratati s količinama podataka na razini web-a, mnogi algoritmi mogu postati neprikladni, no, kako raste količina podataka, tako raste i naša sposobnost da ih precizno interpretiramo.
Najprije, dana je matematička osnova gradijentnih metoda, a zatim su pokazane performanse dva različita gradijentna algoritma: gradijentni spust (GS) i stohastički gradijentni spust (SGS). Razmotren je sintetizirani model linearne regresije. Performanse algoritama su evaluirane procjenom najveće izglednosti. Nakon toga, analiza konvergencije je prikazana. Na kraju, SGS je pokretan nad sve većim podskupovima podataka. Takvi podskupovi se nazivaju mini-grupe.
U slučaju linearne regresije, pokazano je da SGS ima bolje performanse od GS-a kako se količina podataka povećava. Nadalje, kako se povećava veličina mini-grupa, preciznost SGS-a ne raste značajno.

Abstract (english)

Gradient-based algorithms are popular when solving unconstrained optimization problems. By exploiting knowledge of the gradient of the objective function to optimize, each iteration of a gradient-based algorithm aims at approaching the minimizer of said function. In this age, when prediction algorithms (of which gradient-based algorithms are a part of), many algorithms may encounter difficulties. However, as the data sets grow larger, so does our capability to interpret them.
Firstly, the basis of mathematics background is covered concerning gradient optimization, after that the performance of two different gradient-based algorithms, Gradient Descent (GD) and Stochastic Gradient Descent (SGD) is presented. A synthetic linear regression model is considered. Performance of the algorithms are evaluated by comparison with the maximum likelihood estimator (MLE). Thereafter, a convergence study is presented. Lastly, SGD is evaluated over increasingly large, random subsets of the data. Such a subset is known as a mini-batch. In the case of linear regression, it is found that SGD outperforms GD as the data sets grow larger. Furthermore, the precision of SGD does not necessarily improve when increasing the mini-batch size.

• Keywords: bezuvjetna optimizacija; gradijentni spust; stohastički gradijentni spust; stohastički gradijentni spust s mini-grupama
• Keywords (english): unconstrained minimization; gradient descent; stohastic gradient descent; stohastic gradient descent with mini-batches
• Language: croatian
• URN:NBN: urn:nbn:hr:168:288150
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 10:04:04