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

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2019  >  6(1): 45-52
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
shu

Distributed Majorization-Minimization for Laplacian Regularized Problems

doi: 10.1109/JAS.2019.1911321

  • Department of Electrical Engineering, Stanford University, Stanford, CA 94305 USA

More Information
    Abstract
  • 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.

     

    • FullText(HTML)
  • loading
    • References(50)
  • [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.
    [2]
    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.
    [3]
    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
    [4]
    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
    [5]
    D. Slepcev and M. Thorpe, "Analysis of p-laplacian regularization in semi-supervised learning, " ArXiV preprint, Oct. 2017.
    [6]
    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
    [7]
    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.
    [8]
    K. Lange, MM Optimization Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2016.
    [9]
    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.
    [10]
    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
    [11]
    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
    [12]
    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/
    [13]
    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
    [14]
    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/
    [15]
    C. Godsil and G. Royle, The Laplacian of a Graph. Springer, 2001.
    [16]
    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.
    [17]
    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
    [18]
    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
    [19]
    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
    [20]
    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.
    [21]
    A. L. Yuille and A. Rangarajan, "The concave-convex procedure, " Neural Computing, vol. 15, no. 4, pp. 915-936, Apr. 2003.
    [22]
    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
    [23]
    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
    [24]
    J. Skaf and S. Boyd, "Multi-period portfolio optimization with constraints and transaction costs, " 2009.
    [25]
    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.
    [26]
    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
    [27]
    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
    [28]
    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
    [29]
    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.
    [30]
    R. T. Rockafellar, Convex Analysis, ser. Princeton Mathematical Series. Princeton University Press, 1970.
    [31]
    J. M. Borwein and A. S. Lewis, Convex Analysis and Nonlinear Optimization, Theory and Examples. Springer, 2000.
    [32]
    L. C. Evans, Partial differential equations. Providence, R.I.: American Mathematical Society, 2010.
    [33]
    S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.
    [34]
    J. Nocedal and S. J. Wright, Numerical Optimization. Springer, 2006.
    [35]
    F. H. Clarke, Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics, 1990. http://d.old.wanfangdata.com.cn/Periodical/dzkxxk201708024
    [36]
    N. Parikh and S. Boyd, "Proximal algorithms, " Foundations and Trends in Optimization, vol. 1, no. 3, pp. 127-239, Jan. 2014.
    [37]
    B. Bollob'as, Modern Graph Theory, ser. Graduate Texts in Mathematics. Heidelberg: Springer, 1998.
    [38]
    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.
    [39]
    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.
    [40]
    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
    [41]
    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
    [42]
    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
    [43]
    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.
    [44]
    M. McKerns, "Pathos multiprocessing, " July 2017.[Online]. Available: https://pypi.python.org/pypi/pathos
    [45]
    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
    [46]
    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
    [47]
    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
    [48]
    B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, "OSQP: An operator splitting solver for quadratic programs, " ArXiv e-prints, Nov. 2017.
    [49]
    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
    [50]
    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.
    • Related Articles
    • Supplements(0)

Catalog

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

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

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

    Figures(3)  / Tables(1)

    Get Citation
    PDF
    XML

    Article Metrics

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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return