conftrace_

2006 NeurIPS NeurIPS 2006

Randomized PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension

Abstract

We design an on-line algorithm for Principal Component Analysis. In each trial the current instance is projected onto a probabilistically chosen low dimensional subspace. The total expected quadratic approximation error equals the total quadratic approximation error of the best subspace chosen in hindsight plus some additional term that grows linearly in dimension of the subspace but logarithmically in the dimension of the instances.

🚀 Conference Pioneer - NeurIPS 2006

📈 Trend Setter - Online Algorithms

🐣 Hot Topic Early Bird - regret bound

Authors

Manfred K. Warmuth, Dima Kuzmin

Topics

Machine Learning > Core Methods > Representation Learning Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Optimization Machine Learning > Core Methods > Dimensionality Reduction Machine Learning > Learning Types > Online Learning Machine Learning > Optimization & Theory > Online Algorithms Machine Learning > Core Methods > Kernel Methods

Keywords

dimensionality reduction online learning principal component analysis matrix factorization regret bound online algorithm randomized algorithm subspace projection kernel methods quadratic approximation error

More from NeurIPS 2006

All NeurIPS 2006 papers →

Correcting Sample Selection Bias by Unlabeled Data

A Nonparametric Approach to Bottom-Up Visual Saliency

Computation of Similarity Measures for Sequential Data using Generalized Suffix Trees

Efficient Structure Learning of Markov Networks using L_1-Regularization

Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions

Mixture Regression for Covariate Shift