Filip Hanzely
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Filip Hanzely has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Peter Richtárik
King Abdullah University of Science and Technology (KAUST)
5 shared publications - Aritra Dutta
University of Central Florida
4 shared publications - Jingwei Liang
School of Mathematical Sciences Institute of Natural Sciences Shanghai Jiao Tong University 200240 Shanghai CHINA
2 shared publications - Lin Xiao
Microsoft Research, Redmond, USA
2 shared publications - Konstantin Mishchenko
ECE Department CS Department CS Department MSIS Department Laboratory for Information and Decision Systems Rutgers University KAUST University Massachusetts Institute of Technology University of Toronto Rutgers University
1 shared publication Peter Richtàrik
King Abdullah University of Science and Technology
1 shared publication
Latest Publications
- 9 June 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 79 (3) , 717-766
Fastest rates for stochastic mirror descent methods
- 9 June 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 79 (3) , 717-766
Fastest rates for stochastic mirror descent methods
- Open Access
Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. We investigate a triangle scaling property of the Bregman distance generated by the reference convex function and present accelerated Bregman proximal gradient (ABPG) methods that attain an $O(k^{-\gamma})$ convergence rate, where $\gamma\in(0,2]$ is the triangle scaling exponent (TSE) of the Bregman distance. For the Euclidean distance, we have $\gamma=2$ and recover the convergence rate of Nesterov's accelerated gradient methods. For non-Euclidean Bregman distances, the TSE can be much smaller (say $\gamma\leq 1$), but we show that a relaxed definition of intrinsic TSE is always equal to 2. We exploit the intrinsic TSE to develop adaptive ABPG methods that converge much faster in practice. Although theoretical guarantees on a fast convergence rate seem to be out of reach in general, our methods obtain empirical $O(k^{-2})$ rates in numerical experiments on several applications and provide posterior numerical certificates for the fast rates.Open AccessAccelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization
We consider the problem of minimizing the sum of two convex functions: one is differentiable and relatively smooth with respect to a reference convex function, and the other can be nondifferentiable but simple to optimize. We investigate a triangle scaling property of the Bregman distance generated by the reference convex function and present accelerated Bregman proximal gradient (ABPG) methods that attain an $O(k^{-\gamma})$ convergence rate, where $\gamma\in(0,2]$ is the triangle scaling exponent (TSE) of the Bregman distance. For the Euclidean distance, we have $\gamma=2$ and recover the convergence rate of Nesterov's accelerated gradient methods. For non-Euclidean Bregman distances, the TSE can be much smaller (say $\gamma\leq 1$), but we show that a relaxed definition of intrinsic TSE is always equal to 2. We exploit the intrinsic TSE to develop adaptive ABPG methods that converge much faster in practice. Although theoretical guarantees on a fast convergence rate seem to be out of reach in general, our methods obtain empirical $O(k^{-2})$ rates in numerical experiments on several applications and provide posterior numerical certificates for the fast rates. - Top Cited Papers
- 7 April 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 79 (2) , 405-440
Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
- 7 April 2021
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 79 (2) , 405-440
Top Cited PapersAccelerated Bregman proximal gradient methods for relatively smooth convex optimization
- 21 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 68 (1053587X) , 6128-6141
Best Pair Formulation & Accelerated Scheme for Non-Convex Principal Component Pursuit
Given two disjoint sets, the best pair problem aims to find a point in one set and another point in the other set with minimal distance between them. In this paper, we formulate the classical robust principal component analysis (RPCA) problem as a best pair problem and design an accelerated proximal gradient algorithm to solve it. We prove that the method enjoys global convergence with a local linear rate. Our extensive numerical experiments on both real and synthetic data sets suggest that our proposed algorithm outperforms relevant baseline algorithms in the literature.
- 21 July 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 68 (1053587X) , 6128-6141
Best Pair Formulation & Accelerated Scheme for Non-Convex Principal Component Pursuit
Given two disjoint sets, the best pair problem aims to find a point in one set and another point in the other set with minimal distance between them. In this paper, we formulate the classical robust principal component analysis (RPCA) problem as a best pair problem and design an accelerated proximal gradient algorithm to solve it. We prove that the method enjoys global convergence with a local linear rate. Our extensive numerical experiments on both real and synthetic data sets suggest that our proposed algorithm outperforms relevant baseline algorithms in the literature.
- Open Access
A Nonconvex Projection Method for Robust PCA
Robust principal component analysis (RPCA) is a well-studied problem with the goal of decomposing a matrix into the sum of low-rank and sparse components. In this paper, we propose a nonconvex feasibility reformulation of RPCA problem and apply an alternating projection method to solve it. To the best of our knowledge, we are the first to propose a method that solves RPCA problem without considering any objective function, convex relaxation, or surrogate convex constraints. We demonstrate through extensive numerical experiments on a variety of applications, including shadow removal, background estimation, face detection, and galaxy evolution, that our approach matches and often significantly outperforms current state-of-the-art in various ways.
Open AccessA Nonconvex Projection Method for Robust PCA
Robust principal component analysis (RPCA) is a well-studied problem with the goal of decomposing a matrix into the sum of low-rank and sparse components. In this paper, we propose a nonconvex feasibility reformulation of RPCA problem and apply an alternating projection method to solve it. To the best of our knowledge, we are the first to propose a method that solves RPCA problem without considering any objective function, convex relaxation, or surrogate convex constraints. We demonstrate through extensive numerical experiments on a variety of applications, including shadow removal, background estimation, face detection, and galaxy evolution, that our approach matches and often significantly outperforms current state-of-the-art in various ways.
- Open Access
- 17 July 2019
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 33 (01) , 1468-1476
A Nonconvex Projection Method for Robust PCA
Robust principal component analysis (RPCA) is a well-studied problem whose goal is to decompose a matrix into the sum of low-rank and sparse components. In this paper, we propose a nonconvex feasibility reformulation of RPCA problem and apply an alternating projection method to solve it. To the best of our knowledge, this is the first paper proposing a method that solves RPCA problem without considering any objective function, convex relaxation, or surrogate convex constraints. We demonstrate through extensive numerical experiments on a variety of applications, including shadow removal, background estimation, face detection, and galaxy evolution, that our approach matches and often significantly outperforms current state-of-the-art in various ways.
- 17 July 2019
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 33 (01) , 1468-1476
Open AccessA Nonconvex Projection Method for Robust PCA
Robust principal component analysis (RPCA) is a well-studied problem whose goal is to decompose a matrix into the sum of low-rank and sparse components. In this paper, we propose a nonconvex feasibility reformulation of RPCA problem and apply an alternating projection method to solve it. To the best of our knowledge, this is the first paper proposing a method that solves RPCA problem without considering any objective function, convex relaxation, or surrogate convex constraints. We demonstrate through extensive numerical experiments on a variety of applications, including shadow removal, background estimation, face detection, and galaxy evolution, that our approach matches and often significantly outperforms current state-of-the-art in various ways.
- Open Access
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
Many popular distributed optimization methods for training machine learning models fit the following template: a local gradient estimate is computed independently by each worker, then communicated to a master, which subsequently performs averaging. The average is broadcast back to the workers, which use it to perform a gradient-type step to update the local version of the model. It is also well known that many such methods, including SGD, SAGA, and accelerated SGD for over-parameterized models, do not scale well with the number of parallel workers. In this paper we observe that the above template is fundamentally inefficient in that too much data is unnecessarily communicated by the workers, which slows down the overall system. We propose a fix based on a new update-sparsification method we develop in this work, which we suggest be used on top of existing methods. Namely, we develop a new variant of parallel block coordinate descent based on independent sparsification of the local gradient estimates before communication. We demonstrate that with only $m/n$ blocks sent by each of $n$ workers, where $m$ is the total number of parameter blocks, the theoretical iteration complexity of the underlying distributed methods is essentially unaffected. As an illustration, this means that when $n=100$ parallel workers are used, the communication of $99\%$ blocks is redundant, and hence a waste of time. Our theoretical claims are supported through extensive numerical experiments which demonstrate an almost perfect match with our theory on a number of synthetic and real datasets.Open Access99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
Many popular distributed optimization methods for training machine learning models fit the following template: a local gradient estimate is computed independently by each worker, then communicated to a master, which subsequently performs averaging. The average is broadcast back to the workers, which use it to perform a gradient-type step to update the local version of the model. It is also well known that many such methods, including SGD, SAGA, and accelerated SGD for over-parameterized models, do not scale well with the number of parallel workers. In this paper we observe that the above template is fundamentally inefficient in that too much data is unnecessarily communicated by the workers, which slows down the overall system. We propose a fix based on a new update-sparsification method we develop in this work, which we suggest be used on top of existing methods. Namely, we develop a new variant of parallel block coordinate descent based on independent sparsification of the local gradient estimates before communication. We demonstrate that with only $m/n$ blocks sent by each of $n$ workers, where $m$ is the total number of parameter blocks, the theoretical iteration complexity of the underlying distributed methods is essentially unaffected. As an illustration, this means that when $n=100$ parallel workers are used, the communication of $99\%$ blocks is redundant, and hence a waste of time. Our theoretical claims are supported through extensive numerical experiments which demonstrate an almost perfect match with our theory on a number of synthetic and real datasets. - Open Access
Best Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
The best pair problem aims to find a pair of points that minimize the distance between two disjoint sets. In this paper, we formulate the classical robust principal component analysis (RPCA) as the best pair; which was not considered before. We design an accelerated proximal gradient scheme to solve it, for which we show global convergence, as well as the local linear rate. Our extensive numerical experiments on both real and synthetic data suggest that the algorithm outperforms relevant baseline algorithms in the literature.
Open AccessBest Pair Formulation & Accelerated Scheme for Non-convex Principal Component Pursuit
The best pair problem aims to find a pair of points that minimize the distance between two disjoint sets. In this paper, we formulate the classical robust principal component analysis (RPCA) as the best pair; which was not considered before. We design an accelerated proximal gradient scheme to solve it, for which we show global convergence, as well as the local linear rate. Our extensive numerical experiments on both real and synthetic data suggest that the algorithm outperforms relevant baseline algorithms in the literature.