A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 6 Issue 1
Jan.  2019

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 11.8, Top 4% (SCI Q1)
    CiteScore: 17.6, Top 3% (Q1)
    Google Scholar h5-index: 77, TOP 5
Turn off MathJax
Article Contents
Jonathan Tuck, David Hallac and Stephen Boyd, "Distributed Majorization-Minimization for Laplacian Regularized Problems," IEEE/CAA J. Autom. Sinica, vol. 6, no. 1, pp. 45-52, Jan. 2019. doi: 10.1109/JAS.2019.1911321
Citation: Jonathan Tuck, David Hallac and Stephen Boyd, "Distributed Majorization-Minimization for Laplacian Regularized Problems," IEEE/CAA J. Autom. Sinica, vol. 6, no. 1, pp. 45-52, Jan. 2019. doi: 10.1109/JAS.2019.1911321

Distributed Majorization-Minimization for Laplacian Regularized Problems

doi: 10.1109/JAS.2019.1911321
More Information
  • We consider the problem of minimizing a block separable convex function (possibly nondifferentiable, and including constraints) plus Laplacian regularization, a problem that arises in applications including model fitting, regularizing stratified models, and multi-period portfolio optimization. We develop a distributed majorization-minimization method for this general problem, and derive a complete, self-contained, general, and simple proof of convergence. Our method is able to scale to very large problems, and we illustrate our approach on two applications, demonstrating its scalability and accuracy.


  • loading
  • [1]
    S. Boyd, E. Busseti, S. Diamond, R. N. Kahn, K. Koh, P. Nystrup, and J. Speth, "Multi-period trading via convex optimization, " Foundations and Trends in Optimization, vol. 3, no. 1, pp. 1- 76, Apr. 2017.
    D. Hallac, Y. Park, S. Boyd, and J. Leskovec, "Network inference via the time-varying graphical lasso, " in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 205-213, 2017.
    M. Yin, J. Gao, and Z. Lin, "Laplacian regularized low-rank representation and its applications, " IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 3, pp. 504-517, Mar. 2016. http://www.ncbi.nlm.nih.gov/pubmed/27046494
    J. Pang and G. Cheung, "Graph laplacian regularization for image denoising: Analysis in the continuous domain, " IEEE Transactions on Image Processing, vol. 26, no. 4, pp. 1770- 1785, April 2017.[Online]. Available: doi: https://doi.org/10.1109/TIP.2017.2651400
    D. Slepcev and M. Thorpe, "Analysis of p-laplacian regularization in semi-supervised learning, " ArXiV preprint, Oct. 2017.
    R. K. Ando and T. Zhang, "Learning on graph with Laplacian regularization, " Conference on Neural Information Processing Systems, 2006. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&tp=&arnumber=6287089
    S. Melacci and M. Belkin, "Laplacian support vector machines trained in the primal, " Journal of Machine Learning Research, vol. 12, pp. 1149-1184, Jul. 2011.
    K. Lange, MM Optimization Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2016.
    Y. Sun, P. Babu, and D. Palomar, "Majorization-minimization algorithms in signal processing, communications, and machine learning."IEEE Transactions in Signal Processing, vol. 65, no. 3, pp. 794-816, 2017.
    S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, "Distributed optimization and statistical learning via the Alternating Direction Method of Multipliers, " Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1-122, Jan. 2011. http://imaiai.oxfordjournals.org/external-ref?access_num=10.1561/2200000016&link_type=DOI
    J. de Leeuw and K. Lange, "Sharp quadratic majorization in one dimension, " Computational Statistics & Data Analysis, vol. 53, no. 7, pp. 2471-2484, 2009.[Online]. Available: doi: 10.1016/j.csda.2009.01.002
    C. Zhang, D. Florencio, and P. Chou, "Graph signal processing-a probabilistic framework, " Tech. Rep., April 2015. [Online]. Available: https://www.microsoft.com/en-us/research/publication/graph-signal-processing-a-probabilistic-framework/
    X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, "Learning laplacian matrix in smooth graph signal representations, " IEEE Transactions on Signal Processing, vol. 64, no. 23, pp. 6160-6173, Dec. 2016.[Online]. Available: doi: 10.1109/TSP.2016.2602809
    H. E. Egilmez, E. Pavez, and A. Ortega, "Graph learning from data under laplacian and structural constraints, " IEEE Journal of Selected Topics in Signal Processing, vol. 11, no. 6, pp. 825-841, Sept 2017. http://ieeexplore.ieee.org/document/7979524/
    C. Godsil and G. Royle, The Laplacian of a Graph. Springer, 2001.
    K. Q. Weinberger, F. Sha, Q. Zhu, and L. K. Saul, "Graph Laplacian regularization for large-scale semidefinite programming, " in Advances in Neural Information Processing Systems 19. MIT Press, 2007, pp. 1489-1496.
    M. Razaviyayn, M. Hong, and Z. Luo, "A unified convergence analysis of block successive minimization methods for nonsmooth optimization, " SIAM Journal on Optimization, vol. 23, no. 2, pp. 1126-1153, 2013. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_1209.2385
    D. Hallac, C. Wong, S. Diamond, A. Sharang, R. Sosic, S. Boyd, and J. Leskovec, "SnapVX: A network-based convex optimization solver." Journal of Machine Learning Research, vol. 18, 2017. http://europepmc.org/abstract/MED/29599649
    D. R. Hunter and K. Lange, "A tutorial on mm algorithms, " The American Statistician, vol. 58, no. 1, pp. 30-37, 2004.[Online]. Available: https://doi.org/10.1198/0003130042836
    M. W. Jacobson and J. A. Fessler, "An expanded theoretical treatment of iteration-dependent majorize-minimize algorithms, " IEEE Transactions on Image Processing, vol. 16, no. 10, pp. 2411-2422, Oct 2007.
    A. L. Yuille and A. Rangarajan, "The concave-convex procedure, " Neural Computing, vol. 15, no. 4, pp. 915-936, Apr. 2003.
    T. T. Wu and K. Lange, "The MM alternative to EM, " Statistical Science, vol. 25, no. 4, pp. 492-505, 11 2010. doi: 10.1214/08-STS264
    R. Almgren and N. Chriss, "Optimal execution of portfolio transactions, " Journal of Risk, pp. 5-39, 2000. http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_0908.1211
    J. Skaf and S. Boyd, "Multi-period portfolio optimization with constraints and transaction costs, " 2009.
    J. Friedman, T. Hastie, and R. Tibshirani, "Sparse inverse covariance estimation with the graphical lasso, " Biostatistics, vol. 9, no. 3, pp. 432-441, Aug. 2008.
    P. Danaher, P. Wang, and D. Witten, "The joint graphical lasso for inverse covariance estimation across multiple classes, " Journal of the Royal Statistical Society, vol. 76, no. 2, pp. 373-397, 2014. doi: 10.1111/rssb.2014.76.issue-2
    O. Banerjee, L. El Ghaoui, and A. d'Aspremont, "Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data, " Journal of Machine Learning Research, vol. 9, pp. 485-516, 2008. http://d.old.wanfangdata.com.cn/Periodical/dlxtzdh201313010
    I. Soloveychik and A. Wiesel, "Joint estimation of inverse covariance matrices lying in an unknown subspace, " IEEE Transactions on Signal Processing, vol. 65, no. 9, pp. 2379-2388, 2017. doi: 10.1109/TSP.2017.2652358
    E. Levitan and G. T. Herman, "A maximum a posteriori probability expectation maximization algorithm for image reconstruction in emission tomography, " IEEE Transactions on Medical Imaging, vol. 6, no. 3, pp. 185-192, Sept 1987.
    R. T. Rockafellar, Convex Analysis, ser. Princeton Mathematical Series. Princeton University Press, 1970.
    J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization, Theory and Examples. Springer, 2000.
    L. C. Evans, Partial differential equations. Providence, R.I.: American Mathematical Society, 2010.
    S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.
    J. Nocedal and S. J. Wright, Numerical Optimization. Springer, 2006.
    F. H. Clarke, Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics, 1990. http://d.old.wanfangdata.com.cn/Periodical/dzkxxk201708024
    N. Parikh and S. Boyd, "Proximal algorithms, " Foundations and Trends in Optimization, vol. 1, no. 3, pp. 127-239, Jan. 2014.
    B. Bollob'as, Modern Graph Theory, ser. Graduate Texts in Mathematics. Heidelberg: Springer, 1998.
    P. Combettes and J. Pesquet, Proximal Splitting Methods in Signal Processing. New York, NY: Springer New York, 2011, pp. 185-212.[Online]. Available: https://doi.org/10.1007/978-1-4419-9569-8_10.
    M. Burger, A. Sawatzky, and G. Steidl, First Order Algorithms in Variational Image Processing. Cham: Springer International Publishing, 2016, pp. 345-407.[Online]. Available: https://doi.org/10.1007/978-3-319-41589-5_10.
    E. Yildirim and S. Wright, "Warm-start strategies in interiorpoint methods for linear programming, " SIAM Journal on Optimization, vol. 12, no. 3, pp. 782-810, 2002.[Online]. Available: https://doi.org/10.1137/S1052623400369235 http://dl.acm.org/citation.cfm?id=589134
    Y. Wang and S. Boyd, "Fast model predictive control using online optimization, " IEEE Transactions on Control Systems Technology, vol. 18, no. 3, pp. 267-278, March 2010. http://www.sciencedirect.com/science/article/pii/S1474667016400662
    D. Kim, D. Pal, J.-B. Thibault, and J. A. Fessler, "Accelerating ordered subsets image reconstruction for X-ray CT using spatially non-uniform optimization transfer, " IEEE Transactions on Medical Imaging, vol. 32, no. 11, pp. 1965-78, Nov. 2013. http://med.wanfangdata.com.cn/Paper/Detail/PeriodicalPaper_PM23751959
    M. J. Muckley, D. C. Noll, and J. A. Fessler, "Fast parallel MR image reconstruction via B1-based, adaptive restart, iterative soft thresholding algorithms (BARISTA), " IEEE Transactions on Medical Imaging, vol. 34, no. 2, pp. 578-88, Feb. 2015.
    M. McKerns, "Pathos multiprocessing, " July 2017.[Online]. Available: https://pypi.python.org/pypi/pathos
    S. Boyd, M. T. Mueller, B. O'Donoghue, and Y. Wang, "Performance bounds and suboptimal policies for multi-period investment, " Foundations and Trends in Optimization, vol. 1, no. 1, pp. 1-72, Jan. 2014. http://dl.acm.org/citation.cfm?id=2693591.2693592
    G. Chamberlain and M. Rothschild, "Arbitrage, factor structure, and mean-variance analysis on large asset markets, " Econometrica, vol. 51, no. 5, pp. 1281-1304, 1983. [Online]. Available: http://www.jstor.org/stable/1912275 http://www.jstor.org/stable/1912275
    S. Diamond and S. Boyd, "CVXPY: A Python-embedded modeling language for convex optimization, " Journal of Machine Learning Research, vol. 17, no. 83, pp. 1-5, 2016. http://www.ncbi.nlm.nih.gov/pubmed/27375369
    B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, "OSQP: An operator splitting solver for quadratic programs, " ArXiv e-prints, Nov. 2017.
    D. M. Witten and R. Tibshirani, "Covariance-regularized regression and classification for high dimensional problems, " Journal of the Royal Statistical Society, vol. 71, no. 3, pp. 615-636, 2009. doi: 10.1111/rssb.2009.71.issue-3
    B. O' Donoghue, E. Chu, N. Parikh, and S. Boyd, "Conic optimization via operator splitting and homogeneous self-dual embedding, " Journal of Optimization Theory and Applications, vol. 169, no. 3, pp. 1042-1068, June 2016.


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(3)  / Tables(1)

    Article Metrics

    Article views (1642) PDF downloads(80) Cited by()


    DownLoad:  Full-Size Img  PowerPoint