The Living Thing / Notebooks :

Randomised regression

Usefulness: 🔧
Novelty: 💡
Uncertainty: 🤪 🤪 🤪
Incompleteness: 🚧 🚧 🚧

Tackling your regression, by using random projections of the predictors.

Usually this means using those projections to reduce the dimensionality of a high dimensional regression. In this case it is not far from compressed sensing, except in how we handle noise. In this linear model case, this is of course random linear algebra, and may be a randomised matrix factorisation.

Occasionally we might use non-linear projections to increase the dimensionality of our data in the hope of making a non-linear regression approximately linear, which dates back to Cover (Cove65).

I am especially interested in seeing how this might be useful for dependent data, especially time series.

Brian McWilliams, Gabriel Krummenacher and Mario Lučić, Randomized Linear Regression: A brief overview and recent results. Gabriel implemented some of the algorithms mentioned, e.g.

Martin Wainright, Statistics meets Optimization: Randomization and approximation for high-dimensional problems.

In the modern era of high-dimensional data, the interface between mathematical statistics and optimization has become an increasingly vibrant area of research. In this course, we provide some vignettes into this interface, including the following topics:


Bahmani, Sohail, and Justin Romberg. 2017. “Anchored Regression: Solving Random Convex Equations via Convex Programming,” February.

Choromanski, Krzysztof, Mark Rowland, and Adrian Weller. 2017. “The Unreasonable Effectiveness of Random Orthogonal Embeddings,” March.

Cover, T. M. 1965. “Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition.” IEEE Transactions on Electronic Computers EC-14 (3): 326–34.

Dhillon, Paramveer, Yichao Lu, Dean P. Foster, and Lyle Ungar. 2013. “New Subsampling Algorithms for Fast Least Squares Regression.” In Advances in Neural Information Processing Systems, 360–68. Curran Associates, Inc.

Gilbert, Anna C., Yi Zhang, Kibok Lee, Yuting Zhang, and Honglak Lee. 2017. “Towards Understanding the Invertibility of Convolutional Neural Networks,” May.

Gribonval, Rémi, Gilles Blanchard, Nicolas Keriven, and Yann Traonmilin. 2017. “Compressive Statistical Learning with Random Feature Moments,” June.

Gupta, Pawan, and Marianna Pensky. 2016. “Solution of Linear Ill-Posed Problems Using Random Dictionaries,” May.

Heinze, Christina, Brian McWilliams, and Nicolai Meinshausen. 2016. “DUAL-LOCO: Distributing Statistical Estimation Using Random Projections.” In, 875–83.

Heinze, Christina, Brian McWilliams, Nicolai Meinshausen, and Gabriel Krummenacher. 2014. “LOCO: Distributing Ridge Regression with Random Projections,” June.

Krummenacher, Gabriel, Brian McWilliams, Yannic Kilcher, Joachim M Buhmann, and Nicolai Meinshausen. 2016. “Scalable Adaptive Stochastic Optimization Using Random Projections.” In Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 1750–8. Curran Associates, Inc.

McWilliams, Brian, David Balduzzi, and Joachim M Buhmann. 2013. “Correlated Random Features for Fast Semi-Supervised Learning.” In Advances in Neural Information Processing Systems 26, edited by C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, 1050:440–48. Curran Associates, Inc.

McWilliams, Brian, Gabriel Krummenacher, Mario Lucic, and Joachim M. Buhmann. 2014. “Fast and Robust Least Squares Estimation in Corrupted Linear Models.” In Advances in Neural Information Processing Systems, 415–23.

Rosenfeld, Amir, and John K. Tsotsos. 2018. “Intriguing Properties of Randomly Weighted Networks: Generalizing While Learning Next to Nothing.”

Scardapane, Simone, and Dianhui Wang. 2017. “Randomness in Neural Networks: An Overview.” Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 7 (2).

Soni, Akshay, and Yashar Mehdad. 2017. “RIPML: A Restricted Isometry Property Based Approach to Multilabel Learning,” February.

Thanei, Gian-Andrea, Christina Heinze, and Nicolai Meinshausen. 2017. “Random Projections for Large-Scale Regression,” January.

Wang, HaiYing, Rong Zhu, and Ping Ma. 2017. “Optimal Subsampling for Large Sample Logistic Regression,” February.

Zhang, Xiao, Lingxiao Wang, and Quanquan Gu. 2017. “Stochastic Variance-Reduced Gradient Descent for Low-Rank Matrix Recovery from Linear Measurements,” January.