טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentKaplan Atara
SubjectEfficient Algorithms for Low Rank Optimization Problems
DepartmentDepartment of Applied Mathematics
Supervisors Assistant Professor Shoham Sabach
Dr. Dan Garber


Abstract

Continuous optimization problems over matrices, which include a low-rank promoting term, such as a nuclear-norm regularizer or constraint, have important applications in machine learning, signal processing and more. Yet, such problems are highly challenging to solve in large-scale. On one hand, the low-rank promoting term prohibits efficient implementations of classical proximal based methods and even of simple subgradient methods. On the other hand, methods which are tailored for low-rank optimization, such as conditional gradient-type methods, and avoid expensive matrix decompositions, suffer from slow convergence rates.


In this work, we present new algorithms and results for general strongly-convex composite optimization problems, which obtain faster convergence rates than those attainable via standard methods, while avoiding expensive matrix decompositions. In particular, our methods are appealing for matrix recovery problems with low-rank penalties where avoiding prohibitive full-rank singular value decompositions, which are required by most standard methods, is most desirable.


At the heart of our results lies the concept of a weak-proximal oracle. This oracle replaces the standard proximal oracle used in many methods. In the context of low-

rank matrix optimization problems, a weak-proximal oracle merely requires computing a low-rank singular value decomposition of the rank of the optimal solution, which can be done more efficiently than computing a full-rank singular value decomposition, as the standard proximal oracle requires.


We use a weak-proximal oracle in designing and analyzing two algorithms for tackling two classes of optimization problems. The first one is a stochastic optimization problem, which consists of minimizing a strongly-convex objective that includes both a non-smooth term and a low-rank promoting term. This can be used, for example, in low-rank and sparse matrix recovery problems. The second one is a minimization of a deterministic smooth and strongly convex objective function applied to the sum of two blocks of variables, where each block of variables is constrained or regularized individually. For example, this applies to matrix problems in which one of the blocks corresponds to a low-rank matrix, such as Robust PCA.