We are very excited to join forces with MLCommons and OctoML.ai! Contact Grigori Fursin for more details!

Importance sampling strategy for non-convex randomized block-coordinate descent

lib:5055e4e9f8552424 (v1.0.0)

Authors: RĂ©mi Flamary,Alain Rakotomamonjy,Gilles Gasso
ArXiv: 1606.07286
Document:  PDF  DOI 
Abstract URL: http://arxiv.org/abs/1606.07286v1


As the number of samples and dimensionality of optimization problems related to statistics an machine learning explode, block coordinate descent algorithms have gained popularity since they reduce the original problem to several smaller ones. Coordinates to be optimized are usually selected randomly according to a given probability distribution. We introduce an importance sampling strategy that helps randomized coordinate descent algorithms to focus on blocks that are still far from convergence. The framework applies to problems composed of the sum of two possibly non-convex terms, one being separable and non-smooth. We have compared our algorithm to a full gradient proximal approach as well as to a randomized block coordinate algorithm that considers uniform sampling and cyclic block coordinate descent. Experimental evidences show the clear benefit of using an importance sampling strategy.

Relevant initiatives  

Related knowledge about this paper Reproduced results (crowd-benchmarking and competitions) Artifact and reproducibility checklists Common formats for research projects and shared artifacts Reproducibility initiatives

Comments  

Please log in to add your comments!
If you notice any inapropriate content that should not be here, please report us as soon as possible and we will try to remove it within 48 hours!