Parallel and Hybrid Soft-Thresholding Algorithms with Line Search for Sparse Nonlinear Regression. Yang, Y., Pesavento, M., Chatzinotas, S., & Ottersten, B. In 2018 26th European Signal Processing Conference (EUSIPCO), pages 1587-1591, Sep., 2018. Paper doi abstract bibtex In this paper, we propose a convergent iterative algorithm for nondifferentiable nonconvex nonlinear regression problems. The proposed parallel algorithm consists in optimizing a sequence of successively refined approximate functions. Compared with the popular iterative soft-thresholding algorithm commonly known as ISTA, which is the benchmark algorithm for such problems, it has two attractive features which lead to a notable reduction in the algorithm's complexity: the proposed approximate function does not have to be a global upper bound of the original function, and the stepsize can be efficiently computed by the line search scheme which is carried out over a properly constructed differentiable function. Furthermore, when the parallel algorithm cannot be fully parallelized due to memory/processor constraints, we propose a hybrid updating scheme that divides the whole set of variables into blocks which are updated sequentially. Since the stepsize is obtained by performing the line search along the coordinate of each block variable, the proposed hybrid algorithm converges faster than state-of-the-art hybrid algorithms based on constant stepsizes and/or decreasing stepsizes. Finally, the proposed algorithms are numerically tested.
@InProceedings{8553274,
author = {Y. Yang and M. Pesavento and S. Chatzinotas and B. Ottersten},
booktitle = {2018 26th European Signal Processing Conference (EUSIPCO)},
title = {Parallel and Hybrid Soft-Thresholding Algorithms with Line Search for Sparse Nonlinear Regression},
year = {2018},
pages = {1587-1591},
abstract = {In this paper, we propose a convergent iterative algorithm for nondifferentiable nonconvex nonlinear regression problems. The proposed parallel algorithm consists in optimizing a sequence of successively refined approximate functions. Compared with the popular iterative soft-thresholding algorithm commonly known as ISTA, which is the benchmark algorithm for such problems, it has two attractive features which lead to a notable reduction in the algorithm's complexity: the proposed approximate function does not have to be a global upper bound of the original function, and the stepsize can be efficiently computed by the line search scheme which is carried out over a properly constructed differentiable function. Furthermore, when the parallel algorithm cannot be fully parallelized due to memory/processor constraints, we propose a hybrid updating scheme that divides the whole set of variables into blocks which are updated sequentially. Since the stepsize is obtained by performing the line search along the coordinate of each block variable, the proposed hybrid algorithm converges faster than state-of-the-art hybrid algorithms based on constant stepsizes and/or decreasing stepsizes. Finally, the proposed algorithms are numerically tested.},
keywords = {approximation theory;computational complexity;convergence of numerical methods;iterative methods;optimisation;parallel algorithms;regression analysis;search problems;iterative soft-thresholding algorithm;differentiable function;hybrid algorithm;hybrid updating scheme;line search scheme;approximate function;parallel algorithm;nondifferentiable nonconvex nonlinear regression problems;convergent iterative algorithm;sparse nonlinear regression;soft-thresholding algorithms;Signal processing algorithms;Convergence;Approximation algorithms;Complexity theory;Search problems;Linear programming;Upper bound;Big Data;Block Coordinate Descent;Line Search;Linear Regression;Nonlinear Regression;Successive Convex Approximation},
doi = {10.23919/EUSIPCO.2018.8553274},
issn = {2076-1465},
month = {Sep.},
url = {https://www.eurasip.org/proceedings/eusipco/eusipco2018/papers/1570437101.pdf},
}
Downloads: 0
{"_id":"M7ZzWtu6cCT9dgWYW","bibbaseid":"yang-pesavento-chatzinotas-ottersten-parallelandhybridsoftthresholdingalgorithmswithlinesearchforsparsenonlinearregression-2018","authorIDs":[],"author_short":["Yang, Y.","Pesavento, M.","Chatzinotas, S.","Ottersten, B."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Y."],"propositions":[],"lastnames":["Yang"],"suffixes":[]},{"firstnames":["M."],"propositions":[],"lastnames":["Pesavento"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Chatzinotas"],"suffixes":[]},{"firstnames":["B."],"propositions":[],"lastnames":["Ottersten"],"suffixes":[]}],"booktitle":"2018 26th European Signal Processing Conference (EUSIPCO)","title":"Parallel and Hybrid Soft-Thresholding Algorithms with Line Search for Sparse Nonlinear Regression","year":"2018","pages":"1587-1591","abstract":"In this paper, we propose a convergent iterative algorithm for nondifferentiable nonconvex nonlinear regression problems. The proposed parallel algorithm consists in optimizing a sequence of successively refined approximate functions. Compared with the popular iterative soft-thresholding algorithm commonly known as ISTA, which is the benchmark algorithm for such problems, it has two attractive features which lead to a notable reduction in the algorithm's complexity: the proposed approximate function does not have to be a global upper bound of the original function, and the stepsize can be efficiently computed by the line search scheme which is carried out over a properly constructed differentiable function. Furthermore, when the parallel algorithm cannot be fully parallelized due to memory/processor constraints, we propose a hybrid updating scheme that divides the whole set of variables into blocks which are updated sequentially. Since the stepsize is obtained by performing the line search along the coordinate of each block variable, the proposed hybrid algorithm converges faster than state-of-the-art hybrid algorithms based on constant stepsizes and/or decreasing stepsizes. Finally, the proposed algorithms are numerically tested.","keywords":"approximation theory;computational complexity;convergence of numerical methods;iterative methods;optimisation;parallel algorithms;regression analysis;search problems;iterative soft-thresholding algorithm;differentiable function;hybrid algorithm;hybrid updating scheme;line search scheme;approximate function;parallel algorithm;nondifferentiable nonconvex nonlinear regression problems;convergent iterative algorithm;sparse nonlinear regression;soft-thresholding algorithms;Signal processing algorithms;Convergence;Approximation algorithms;Complexity theory;Search problems;Linear programming;Upper bound;Big Data;Block Coordinate Descent;Line Search;Linear Regression;Nonlinear Regression;Successive Convex Approximation","doi":"10.23919/EUSIPCO.2018.8553274","issn":"2076-1465","month":"Sep.","url":"https://www.eurasip.org/proceedings/eusipco/eusipco2018/papers/1570437101.pdf","bibtex":"@InProceedings{8553274,\n author = {Y. Yang and M. Pesavento and S. Chatzinotas and B. Ottersten},\n booktitle = {2018 26th European Signal Processing Conference (EUSIPCO)},\n title = {Parallel and Hybrid Soft-Thresholding Algorithms with Line Search for Sparse Nonlinear Regression},\n year = {2018},\n pages = {1587-1591},\n abstract = {In this paper, we propose a convergent iterative algorithm for nondifferentiable nonconvex nonlinear regression problems. The proposed parallel algorithm consists in optimizing a sequence of successively refined approximate functions. Compared with the popular iterative soft-thresholding algorithm commonly known as ISTA, which is the benchmark algorithm for such problems, it has two attractive features which lead to a notable reduction in the algorithm's complexity: the proposed approximate function does not have to be a global upper bound of the original function, and the stepsize can be efficiently computed by the line search scheme which is carried out over a properly constructed differentiable function. Furthermore, when the parallel algorithm cannot be fully parallelized due to memory/processor constraints, we propose a hybrid updating scheme that divides the whole set of variables into blocks which are updated sequentially. Since the stepsize is obtained by performing the line search along the coordinate of each block variable, the proposed hybrid algorithm converges faster than state-of-the-art hybrid algorithms based on constant stepsizes and/or decreasing stepsizes. Finally, the proposed algorithms are numerically tested.},\n keywords = {approximation theory;computational complexity;convergence of numerical methods;iterative methods;optimisation;parallel algorithms;regression analysis;search problems;iterative soft-thresholding algorithm;differentiable function;hybrid algorithm;hybrid updating scheme;line search scheme;approximate function;parallel algorithm;nondifferentiable nonconvex nonlinear regression problems;convergent iterative algorithm;sparse nonlinear regression;soft-thresholding algorithms;Signal processing algorithms;Convergence;Approximation algorithms;Complexity theory;Search problems;Linear programming;Upper bound;Big Data;Block Coordinate Descent;Line Search;Linear Regression;Nonlinear Regression;Successive Convex Approximation},\n doi = {10.23919/EUSIPCO.2018.8553274},\n issn = {2076-1465},\n month = {Sep.},\n url = {https://www.eurasip.org/proceedings/eusipco/eusipco2018/papers/1570437101.pdf},\n}\n\n","author_short":["Yang, Y.","Pesavento, M.","Chatzinotas, S.","Ottersten, B."],"key":"8553274","id":"8553274","bibbaseid":"yang-pesavento-chatzinotas-ottersten-parallelandhybridsoftthresholdingalgorithmswithlinesearchforsparsenonlinearregression-2018","role":"author","urls":{"Paper":"https://www.eurasip.org/proceedings/eusipco/eusipco2018/papers/1570437101.pdf"},"keyword":["approximation theory;computational complexity;convergence of numerical methods;iterative methods;optimisation;parallel algorithms;regression analysis;search problems;iterative soft-thresholding algorithm;differentiable function;hybrid algorithm;hybrid updating scheme;line search scheme;approximate function;parallel algorithm;nondifferentiable nonconvex nonlinear regression problems;convergent iterative algorithm;sparse nonlinear regression;soft-thresholding algorithms;Signal processing algorithms;Convergence;Approximation algorithms;Complexity theory;Search problems;Linear programming;Upper bound;Big Data;Block Coordinate Descent;Line Search;Linear Regression;Nonlinear Regression;Successive Convex Approximation"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/Roznn/EUSIPCO/main/eusipco2018url.bib","creationDate":"2021-02-13T15:38:40.360Z","downloads":0,"keywords":["approximation theory;computational complexity;convergence of numerical methods;iterative methods;optimisation;parallel algorithms;regression analysis;search problems;iterative soft-thresholding algorithm;differentiable function;hybrid algorithm;hybrid updating scheme;line search scheme;approximate function;parallel algorithm;nondifferentiable nonconvex nonlinear regression problems;convergent iterative algorithm;sparse nonlinear regression;soft-thresholding algorithms;signal processing algorithms;convergence;approximation algorithms;complexity theory;search problems;linear programming;upper bound;big data;block coordinate descent;line search;linear regression;nonlinear regression;successive convex approximation"],"search_terms":["parallel","hybrid","soft","thresholding","algorithms","line","search","sparse","nonlinear","regression","yang","pesavento","chatzinotas","ottersten"],"title":"Parallel and Hybrid Soft-Thresholding Algorithms with Line Search for Sparse Nonlinear Regression","year":2018,"dataSources":["yiZioZximP7hphDpY","iuBeKSmaES2fHcEE9"]}