TY - GEN
T1 - Importance sampling strategy for non-convex randomized block-coordinate descent
AU - Flamary, Rémi
AU - Rakotomamonjy, Alain
AU - Gasso, Gilles
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - As the number of samples and dimensionality of optimization problems related to statistics and 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.
AB - As the number of samples and dimensionality of optimization problems related to statistics and 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.
U2 - 10.1109/CAMSAP.2015.7383796
DO - 10.1109/CAMSAP.2015.7383796
M3 - Conference contribution
AN - SCOPUS:84963865436
T3 - 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015
SP - 301
EP - 304
BT - 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 6th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2015
Y2 - 13 December 2015 through 16 December 2015
ER -