Тупица Назарий Константинович Методы решения задач, допускающих альтернативную минимизацию / Methods for Solving Problems That Allow Alternating Minimization

brief description

Тупица Назарий Константинович Методы решения задач, допускающих альтернативную минимизацию / Methods for Solving Problems That Allow Alternating Minimization
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Тупица Назарий Константинович
Table of Contents

Contents Page

Acknowledgments ii

List of Figures iv

List of Tables v

0 Introduction

1 Alternating Minimization

1.1 Optimal Transport

1.2 Wasserstein barycenters

1.3 Multimarginal Optimal Transport

1.3.1 Algorithm Design Based on the Alternating Minimization Approach

1.4 Alternating Least Squares

1.4.1 Matrix Completion

1.4.2 Tensor Decomposition

2 Simple Alternating Minimization Algorithm Analysis

2.1 Notation

2.2 Proximal Polyak-Lojasiewicz condition

2.3 Linear Convergence of Simple Alternating Minimization Algorithm

2.3.1 Example with ||x||A = ^J(Ax,x)

2.3.2 General Convex Constraint Sets

2.4 Polynomial Convergence of Simple Alternating Minimization Algorithm

3 Adaptive Accelerated Gradient Method

3.1 Linear Convergence of AGMsDR

4 Accelerated Alternating Minimization

4.1 AGMsDR Modification for Alternating Minimization

5 Primal Dual Analysis for Multimarginal Optimal Transport

5.1 General Primal-Dual Accelerated Alternating Minimization

5.1.1 Bound for L

5.1.2 Bound for R

5.1.3 Projection on the Feasible Set

5.2 Complexity of Multimarginal OT

6 Numerical Results

6.1 Optimal Transport

6.2 Multimarginal Optimal Transport

6.3 Alternating Least Squares

6.3.1 Matrix Completion

6.3.2 Tensor decomposition

7 Appendix

7.1 Fixed-Step Accelerated Alternating Minimization

7.1.1 Primal-Dual Extension for Fixed Step Accelerated Alternating

Minimization

References

List of Figures

6.1 The results of Algorithm 9 (AAM) and Algorithm 5 (AGM), with different values of e

6.2 The results of Algorithms 9 (AAM) and Algorithm 5 (AGM), with different values of e

6.3 Performance comparison between on the MNIST dataset. Filled in area corresponds to 1 standard deviation

6.4 Performance comparison between multimarginal Sinkhorn's algorithm and Algorithm 8 (n = 15, m = 4)

6.5 Performance comparison between multimarginal Sinkhorn's algorithm and Algorithm 8 (m = 4, e = 0.05)

6.6 Performance of the Algorithm 3 and Algorithm 5 applied to the problem (1.20)

6.7 Performance of the Algorithm 3 and Algorithm 5 applied to the problem (1.21)

List of Tables

4.1 Summary of literature