Convex and Nonconvex Formulations for Mixed Regression With Two Components: Minimax Optimal Rates

被引:11
作者
Chen, Yudong [1 ]
Yi, Xinyang [2 ]
Caramanis, Constantine [2 ]
机构
[1] Cornell Univ, Sch Operat Res & Informat Engn, Ithaca, NY 14850 USA
[2] Univ Texas Austin, Dept Elect & Comp Engn, Austin, TX 78712 USA
基金
美国国家科学基金会;
关键词
Mixture models; statistical learning; minimax techniques; information theory; MATRIX RECOVERY; CONVERGENCE;
D O I
10.1109/TIT.2017.2773474
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider the mixed regression problem with two components, under adversarial and stochastic noise. We give a convex optimization formulation that provably recovers the true solution, as well as a nonconvex formulation that works under more general settings and remains tractable. Upper bounds are provided on the recovery errors for both arbitrary noise and stochastic noise models. We also give matching minimax lower bounds (up to log factors), showing that our algorithm is information-theoretical optimal in a precise sense. Our results represent the first tractable algorithm guaranteeing successful recovery with tight bounds on recovery errors and sample complexity. Moreover, we pinpoint the statistical cost of mixtures: our minimax-optimal results indicate that the mixture poses a fundamentally more difficult problem in the low-SNR regime, where the learning rate changes.
引用
收藏
页码:1738 / 1766
页数:29
相关论文
共 38 条
  • [1] FAST GLOBAL CONVERGENCE OF GRADIENT METHODS FOR HIGH-DIMENSIONAL STATISTICAL RECOVERY
    Agarwal, Alekh
    Negahban, Sahand
    Wainwright, Martin J.
    [J]. ANNALS OF STATISTICS, 2012, 40 (05) : 2452 - 2482
  • [2] Anandkumar A, 2014, J MACH LEARN RES, V15, P2773
  • [3] [Anonymous], 2015, Solving random quadratic systems of equations is nearly as easy as solving linear systems
  • [4] [Anonymous], 2012, ELEMENTS INFORM THEO
  • [5] [Anonymous], 2015, ADV NEURAL INFORM PR
  • [6] [Anonymous], 2013, P 4 C INNOVATIONS TH
  • [7] [Anonymous], SERIES PROBABILITY S
  • [8] Assouad B. Yu., 1997, Festschrift for Lucien Le Cam, P423
  • [9] Azizyan Martin, 2013, MINIMAX THEORY HIGH
  • [10] Birge Lucien, 1983, Zeitschrift fur Wahrscheinlichkeitstheorie und Verwandte Gebiete, V65, P181