國立虎尾科技大學 |

Structure-Driven Algorithm Design in Optimization and Machine Learning.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Structure-Driven Algorithm Design in Optimization and Machine Learning./
Author:	Lin, Tianyi.
Description:	1 online resource (418 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-03, Section: B.
Contained By:	Dissertations Abstracts International85-03B.
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9798380381161

Structure-Driven Algorithm Design in Optimization and Machine Learning.
Lin, Tianyi.

Structure-Driven Algorithm Design in Optimization and Machine Learning. - 1 online resource (418 pages)

Source: Dissertations Abstracts International, Volume: 85-03, Section: B.

Thesis (Ph.D.)--University of California, Berkeley, 2023.

Includes bibliographical references

A textbook property of optimization algorithms is their ability to solve the problems under generic regularity conditions. Two examples are simplex method and gradient descent (GD) method. However, the performance of these fundamental and general-purpose optimization algorithms is often unsatisfactory; they often run slowly and perhaps return the suboptimal solutions in generic settings. In my view, this is the price of their generality; indeed, the generic algorithms are an achievement, but for many problems, the gains from leveraging special structure can be huge. A basic question then arises: how can we harness problem-specific structure within our algorithms to obtain fast, practical algorithms with strong performance guarantees? As more structured data-driven decision-making models emerge, this question has become increasingly pressing and relevant to practitioners.For example, the GD is known to get stuck at a suboptimal saddle points in nonconvex optimization. Nonetheless, a line of recent works have shown that random initialization or perturbation changes the dynamics of GD and makes it provably converge to a global optimal solution. In addition, both Markov decision process (MDP) and discrete optimal transport (OT) problems can be solved using large-scale linear programs. Rather than using generic LP algorithms, the policy iteration and the Sinkhorn iteration exploit special structures in MDP and OT and thus perform better in practice. Adapting algorithms to problem-specific structure is generally referred to as structure-driven algorithm design. Although this line of research - which has been studied extensively for over 70 years - has enjoyed widespread success, the machine-learning success stories have introduced new formulations ripe for deep theoretical analysis and remarkable practical impact. My research pushes this frontier by identifying special structure of reliable machine learning (minimax optimization) and multi-agent machine learning (high-order optimization and beyond) and design optimal algorithms for computing the appropriately defined optimal solutions; and other structured problems, such as efficient entropic regularized optimal transport, gradient-free nonsmooth nonconvex optimization, and adaptive and doubly optimal learning in games.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798380381161Subjects--Topical Terms:

573171
Computer science.
Subjects--Index Terms:

Algorithm designIndex Terms--Genre/Form:

554714
Electronic books.

Structure-Driven Algorithm Design in Optimization and Machine Learning.
LDR:03691ntm a22003977 4500 001 1147634
005 20240916065421.5
006 m o d
007 cr bn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798380381161
035 $a (MiAaPQ)AAI30490479
035 $a AAI30490479
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Lin, Tianyi. $3 1473393
245 1 0 $a Structure-Driven Algorithm Design in Optimization and Machine Learning.
264 0 $c 2023
300 $a 1 online resource (418 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-03, Section: B.
500 $a Advisor: Jordan, Michael I.
502 $a Thesis (Ph.D.)--University of California, Berkeley, 2023.
504 $a Includes bibliographical references
520 $a A textbook property of optimization algorithms is their ability to solve the problems under generic regularity conditions. Two examples are simplex method and gradient descent (GD) method. However, the performance of these fundamental and general-purpose optimization algorithms is often unsatisfactory; they often run slowly and perhaps return the suboptimal solutions in generic settings. In my view, this is the price of their generality; indeed, the generic algorithms are an achievement, but for many problems, the gains from leveraging special structure can be huge. A basic question then arises: how can we harness problem-specific structure within our algorithms to obtain fast, practical algorithms with strong performance guarantees? As more structured data-driven decision-making models emerge, this question has become increasingly pressing and relevant to practitioners.For example, the GD is known to get stuck at a suboptimal saddle points in nonconvex optimization. Nonetheless, a line of recent works have shown that random initialization or perturbation changes the dynamics of GD and makes it provably converge to a global optimal solution. In addition, both Markov decision process (MDP) and discrete optimal transport (OT) problems can be solved using large-scale linear programs. Rather than using generic LP algorithms, the policy iteration and the Sinkhorn iteration exploit special structures in MDP and OT and thus perform better in practice. Adapting algorithms to problem-specific structure is generally referred to as structure-driven algorithm design. Although this line of research - which has been studied extensively for over 70 years - has enjoyed widespread success, the machine-learning success stories have introduced new formulations ripe for deep theoretical analysis and remarkable practical impact. My research pushes this frontier by identifying special structure of reliable machine learning (minimax optimization) and multi-agent machine learning (high-order optimization and beyond) and design optimal algorithms for computing the appropriately defined optimal solutions; and other structured problems, such as efficient entropic regularized optimal transport, gradient-free nonsmooth nonconvex optimization, and adaptive and doubly optimal learning in games.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
650 4 $a Industrial engineering. $3 679492
650 4 $a Mathematics. $3 527692
653 $a Algorithm design
653 $a Game theory
653 $a Machine learning
653 $a Optimization algorithms
653 $a Gradient descent
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
690 $a 0546
690 $a 0405
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Berkeley. $b Electrical Engineering & Computer Sciences. $3 845564
773 0 $t Dissertations Abstracts International $g 85-03B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30490479 $z click for full text (PQDT)