2018/09/27 by Dan Garber, Garber, Dan
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and ELM #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1809.10491
openalex publication_date 2018/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we focus on the problem of Online Principal Component Analysis\nin the regret minimization framework. For this problem, all existing regret\nminimization algorithms for the fully-adversarial setting are based on a\npositive semidefinite convex relaxation, and hence require quadratic memory and\nSVD computation (either thin of full) on each iteration, which amounts to at\nleast quadratic runtime per iteration. This is in stark contrast to a\ncorresponding stochastic i.i.d. variant of the problem, which was studied\nextensively lately, and admits very efficient gradient ascent algorithms that\nwork directly on the natural non-convex formulation of the problem, and hence\nrequire only linear memory and linear runtime per iteration. This raises the\nquestion: can non-convex online gradient ascent algorithms be shown to minimize\nregret in online adversarial settings? In this paper we take a step forward\ntowards answering this question. We introduce an\n\adversarially-perturbed spiked-covariance model in which, each data\npoint is assumed to follow a fixed stochastic distribution with a non-zero\nspectral gap in the covariance matrix, but is then perturbed with some\nadversarial vector. This model is a natural extension of a well studied\nstandard stochastic setting that allows for non-stationary (adversarial)\npatterns to arise in the data and hence, might serve as a significantly better\napproximation for real-world data-streams. We show that in an interesting\nregime of parameters, when the non-convex online gradient ascent algorithm is\ninitialized with a "warm-start" vector, it provably minimizes the regret with\nhigh probability. We further discuss the possibility of computing such a\n"warm-start" vector, and also the use of regularization to obtain fast regret\nrates. Our theoretical findings are supported by empirical experiments on both\nsynthetic and real-world data.\n