Universitätsbibliothek Wien

Stochastic primal-dual forward-backward-forward algorithm with applications in machine learning

Kastner, Klaus (2018) Stochastic primal-dual forward-backward-forward algorithm with applications in machine learning.
Masterarbeit, University of Vienna. Fakultät für Mathematik
BetreuerIn: Bot, Radu Ioan

[img] PDF-File
Alle Rechte vorbehalten / All rights reserved

Download (793Kb)
DOI: 10.25365/thesis.53897
URN: urn:nbn:at:at-ubw:1-26054.05614.236860-9

Link zu u:search

Abstract in English

We propose a stochastic primal-dual forward-backward-forward algorithm for solving monotone inclusion problems involving maximally monotone operators, linear compositions of parallel sums of maximally monotone operators and single-valued Lipschitzian monotone operators. The stochastic algorithm is expected to converge faster than its deterministic counterpart, since every iteration computational effort is saved by using a random sweeping strategy. Based on the concept of quasi-Fej\'{e}r monotonicity, we prove the almost sure convergence of the algorithm. In the second half of this thesis, we discuss the employment of the proposed algorithm in context of solving convex minimization problems, arising in the field of Kernel based Machine Learning. We use a pool of hand-written images showing the numbers four or five in order to train a Support Vector Machine, which aims to classify the images correctly. This issue is equivalent to solving a convex minimization problem. By means of this application we test several types of the stochastic algorithm, assess their performances and compare them to the performance of its deterministic counterpart. Finally, we present the according MATLAB-codes.

Schlagwörter in Englisch

arbitrary sampling / block-coordinate algorithm / random variables / stochastic algorithm / stochastic Fejer-monotone sequence / maximally monotone operator / resolvent / convex optimization / subdifferential / kernel-based machine learning / support vector machine / numerical experiments

Abstract in German

Wir präsentieren ein stochastisches Primal-duales Vorwärts-Rückwärts-Vorwärts Verfahren zum Lösen des monotonen Inklusions-Problems, welches maximal- monotone Operatoren, lineare Zusammensetzungen paralleler Summen von maximal- monotonen Operatoren und einzelwertige Lipschitz-stetige monotone Operatoren umfasst. Wir erwarten uns ein besseres Konvergenzverhalten vom stochastischen Algorithmus im Vergleich zu seinem deterministischen Gegenüber, weil ersterer durch zufälliges Aktivieren der Koordinaten in jeder Iteration Rechenaufwand einspart. Basierend auf dem Konzept der quasi-Fejér Monotonie beweisen wir die fast-sicher Konvergenz des Algorithmuses. Im zweiten Teil dieser Arbeit zeigen wir, wie man das stochastische Primal-duale Vorwärts-Rückwärts-Vorwärts Verfahren einerseits zum Lösen allgemeiner konvexer Optimierungsaufgaben und darauf basierend andererseits zum Lösen speziell für das Kernel-basierte Maschinelle Lernen verwenden kann. Konkret benützen wir eine große Auswahl von Bildern, welche die handgeschriebenen Ziffern Vier oder Fünf zeigen, um eine Support Vektor Maschine zu trainieren. Diese zielt darauf ab, die Bilder richtig zu unterscheiden. Abstrakt formuliert gleicht diese Aufgabe einer konvexen Optimierungsaufgabe. Anhand dieser Anwendung testen wir verschiedene Typen des stochastischen Algorithmuses, bewerten deren Leistungsfähigkeiten und vergleichen diese mit der Leistungsfähigkeit seines deterministischen Gegenüber. Zum Schluss präsentieren wir noch die MATLAB-Codes.

Schlagwörter in Deutsch

Zufallsvariablen / stochastische quasi-Fejér monotone Folge / stochastischer Algorithmus / maximal-monotone Operatoren / Resolvente / konvexes Optimierungsproblem / Subdifferential / Kernel-basiertes maschinelles Lernen / Support Vector Maschine / numerische Experimente

Item Type: Hochschulschrift (Masterarbeit)
Author: Kastner, Klaus
Title: Stochastic primal-dual forward-backward-forward algorithm with applications in machine learning
Umfangsangabe: 47 Seiten : Illustrationen
Institution: University of Vienna
Faculty: Fakultät für Mathematik
Studiumsbezeichnung bzw.
Universitätslehrgang (ULG):
Masterstudium Mathematik
Publication year: 2018
Language: eng ... Englisch
Supervisor: Bot, Radu Ioan
Assessor: Bot, Radu Ioan
Classification: 31 Mathematik > 31.46 Funktionalanalysis
31 Mathematik > 31.47 Operatortheorie
31 Mathematik > 31.70 Wahrscheinlichkeitsrechnung
31 Mathematik > 31.76 Numerische Mathematik
31 Mathematik > 31.80 Angewandte Mathematik
31 Mathematik > 31.40 Analysis: Allgemeines
54 Informatik > 54.72 Künstliche Intelligenz
AC Number: AC15425733
Item ID: 53897
(Das PDF-Layout ist ident mit der Druckausgabe der Hochschulschrift.)

Urheberrechtshinweis: Für Dokumente, die in elektronischer Form über Datennetze angeboten werden, gilt uneingeschränkt das österreichische Urheberrechtsgesetz; insbesondere sind gemäß § 42 UrhG Kopien und Vervielfältigungen nur zum eigenen und privaten Gebrauch gestattet. Details siehe Gesetzestext.

Edit item (Administrators only) Edit item (Administrators only)