2019/06/07 by Jules Depersin, Guillaume Lecué, Depersin, Jules +1 · 2 citations
Computer Science · Engineering · Decision Sciences · #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #Risk and Portfolio Optimization
paper · pdf · doi:10.48550/arxiv.1906.03058
We construct an algorithm, running in time \mathcal O(N d + uK d), which is robust to outliers and heavy-tailed data and which achieves the subgaussian rate from [Lugosi, Mendelson] √\frac\rm Tr(Σ)N+√\frac||Σ||opKNwith probability at least 1-exp(-c0K)-exp(-c1 u) where Σ is the covariance matrix of the informative data, K∈\1, …, K\ is some parameter (number of block means) and u>0 is another parameter of the algorithm. This rate is achieved when K≥ c1 |\mathcal O| where |\mathcal O| is the number of outliers in the database and under the only assumption that the informative data have a second moment. The algorithm is fully data-dependent and does not use in its construction the proportion of outliers nor the rate above. Its construction combines recently developed tools for Median-of-Means estimators and covering-Semi-definite Programming [Chen, Diakonikolas, Ge] and [Peng, Tangwongsan, Zhang].