LightOn Cloud 2.0 featuring LightOn Aurora OPUs

** Nuit Blanche is now on Twitter: @NuitBlog **

At LightOn, we just launched LightOn Cloud 2.0 that feature several Aurora Optical Processing Unit for use by the Machine Learning Community. the blog post about this can be found here. You can request access to the Cloud at https://cloud.lighton.ai/

We are also having a LightOn Cloud for Research program: https://cloud.lighton.ai/lighton-research/

• [En] Press Release: LightOn launches LightOn Cloud 2.0 featuring Aurora OPUs, April 7th, 2020 
• [Fr] Communiqué de presse: LightOn lance le LightOn Cloud 2.0 avec des OPUs Aurora, 7 Avril 2020 

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup
About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Accelerating SARS-COv2 Molecular Dynamics Studies with Optical Random Features

** Nuit Blanche is now on Twitter: @NuitBlog **

We just published a new blog post at LightOn. This time, we used LightOn's Optical Processing Unit to show how our hardware can help in speeding up global sampling studies that are using Molecular Dynamics simulations, such as in the case of metadynamics. Our engineer, Amélie Chatelain wrote a blog post about it and it is here: Accelerating SARS-COv2 Molecular Dynamics Studies with Optical Random Features

We showed that LightOn's OPU, in tandem with the NEWMA algorithm, becomes very interesting (compared to CPU implementations of Random Fourier Features and FastFood) for simulations featuring more than 4 000 atoms.

  

Because building computational hardware makes no sense if we don't have a community that lifts us, the code used to generate the plots in that blog post is publicly available at the following link: https://github.com/lightonai/newma-md.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:

Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup< br/> About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog

About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

LightOn’s AI Research Workshop — FoRM #4: The Future of Random Matrices. Thursday, December 19th

** Nuit Blanche is now on Twitter: @NuitBlog **

Tomorrow we will feature LightOn’s 4th AI Research workshop on the Future of Random Matrices (FoRM). It starts at 2pm on Thursday, December 19th (That’s 2pm CET/Paris, 1pm GMT/UTC/London, 8am EST/NY-Montreal, 5am PST/California, 9pm UTC+8/ Shenzhen). We have an exciting and diverse line-up with talks on compressive learning, binarized neural networks, particle physics, and matrix factorization.

Feel free to join us, or to catch the event livestream — link to be available on this page on the day of the event.

Without further ado, here is the program:

Program

• 1:45pm — Welcome coffee and opening. A short introduction about LightOn, Igor Carron
• 2:00pm — Compressive Learning with Random Projections, Ata Kaban
• 2:45pm — Medical Applications of Low Precision Neuromorphic Systems, Bodgan Penkovsky
• 3:30pm — Comparing Low Complexity Linear Transforms, Gavin Gray4:00pm — Coffee break and discussions
• 4:20pm —LightOn’s OPU+Particle Physics, David Rousseau, Aishik Ghosh, Laurent Basara, Biswajit Biswas
• 5:00pm — Accelerated Weighted (Nonnegative) Matrix Factorization with Random Projections, Matthieu Puigt
• 5:45pm — Wrapping-up and beers on our rooftop

Talks and abstracts

Ata Kaban, University of Birmingham.
Compressive Learning with Random Projections

By direct analogy to compressive sensing, compressive learning has been originally coined to mean learning efficiently from random projections of high dimensional massive data sets that have a sparse representation. In this talk we discuss compressive learning without the sparse representation requirement, where instead we exploit the

natural structure of learning problems.

Bodgan Penkovsky, Paris-Sud University.
Medical Applications of Low Precision Neuromorphic Systems

The advent of deep learning has considerably accelerated machine learning development, but its development at the edge is limited by its high energy cost and memory requirement. With new memory technology available, emerging Binarized Neural Networks (BNNs) are promising to reduce the energy impact of the forthcoming machine learning hardware generation, enabling machine learning on the edge devices and avoiding data transfer over the network. In this talk we will discuss strategies to apply BNNs to biomedical signals such as electrocardiography and electroencephalography, without sacrificing accuracy and improving energy use. The ultimate goal of this research is to enable smart autonomous healthcare devices.

Gavin Gray, Edinburgh University.
Comparing Low Complexity Linear Transforms

In response to the development of recent efficient dense layers, this talk discusses replacing linear components in pointwise convolutions with structured linear decompositions for substantial gains in the efficiency/accuracy tradeoff. Pointwise convolutions are fully connected layers and are thus prepared for replacement by structured transforms. Networks using such layers are able to learn the same tasks as those using standard convolutions, and provide Pareto-optimal benefits in efficiency/accuracy, both in terms of computation (mult-adds) and parameter count (and hence memory).

David Rousseau, Aishik Ghosh, Laurent Basara, Biswajit Biswas. LAL Orsay, LRI Orsay, BITS University.

OPU+Particle Physics

LightOn’s OPU is opening a new machine learning paradigm. Two use cases have been selected to investigate the potentiality of OPU for particle physics:

• End-to-End learning: high energy proton collision at the Large Hadron Collider have been simulated, each collision being recorded as an image representing the energy flux in the detector. Two classes of events have been simulated: signal are created by a hypothetical supersymmetric particle, and background by known processes. The task is to train a classifier to separate the signal from the background. Several techniques using the OPU will be presented, compared with more classical particle physics approaches.
• Tracking: high energy proton collisions at the LHC yield billions of records with typically 100,000 3D points corresponding to the trajectory of 10,000 particles. Various investigations of the potential of the OPU to digest this high dimensional data will be reported.

Matthieu Puigt, Université du Littoral Côte d’Opale.

Accelerated Weighted (Nonnegative) Matrix Factorization with Random Projections

Random projections belong to the major techniques used to process big data. They have been successfully applied to, e.g., (Nonnegative) Matrix Factorization ((N)MF). However, missing entries in the matrix to factorize (or more generally weights which model the confidence in the entries of the data matrix) prevent their use. In this talk, I will present the framework that we recently proposed to solve this issue, i.e., to apply random projections to weighted (N)MF. We experimentally show the proposed framework to significantly speed-up state-of-the-art weighted NMF methods under some mild conditions.

The workshop will take place at IPGG, 6 Rue Jean Calvin, 75005 Paris. The location is close to both the Place Monge and the Censier-Daubenton subway stations on line7. it is also close to the Luxembourg station on the RER B line. The location is close to bus stops on the 21, 24, 27, 47, and 89 routes. Note that strikes are still ongoing, and some of these options may not be available.

We will be in the main amphitheater, downstairs on your right when you enter the building. Please register in advance on our meetup group so as to help us in the organization of the workshop.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup
 About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Asymmetric Random Projections

** Nuit Blanche is now on Twitter: @NuitBlog **

It is interesting that much of the literature about random projections is to make them less data oblivious. That goal is in large part driven by our stinginess on the complexity of computing these Random Projections. What if the number of Random Projections were not capped? What if, instead of metering the number of random projections to get the most out of it, one were given plenty of them in one fell swoop? This is what we are trying to do at LightOn: use Light to provide plenty of random projections. How much is plenty? Let's put it this way, having a Random Projection of size 1 or 1 million using our OPU requires the same effort. We are running a Cloud service where you can try our technology, it's here: https://www.lighton.ai/lighton-cloud/ 

In the meantime, let us take a look at these interesting asymmetric RPs:

Asymmetric Random Projections by Nick Ryder, Zohar Karnin, Edo Liberty

Random projections (RP) are a popular tool for reducing dimensionality while preserving local geometry. In many applications the data set to be projected is given to us in advance, yet the current RP techniques do not make use of information about the data. In this paper, we provide a computationally light way to extract statistics from the data that allows designing a data dependent RP with superior performance compared to data-oblivious RP. We tackle scenarios such as matrix multiplication and linear regression/classification in which we wish to estimate inner products between pairs of vectors from two possibly different sources. Our technique takes advantage of the difference between the sources and is provably superior to oblivious RPs. Additionally, we provide extensive experiments comparing RPs with our approach showing significant performance lifts in fast matrix multiplication, regression and classification problems.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:

Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup< br/> About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog

About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Distributed Learning with Random Features

** Nuit Blanche is now on Twitter: @NuitBlog **

Distributed Learning with Random Features by Jian Li, Yong Liu, Weiping Wang

Distributed learning and random projections are the most common techniques in large scale nonparametric statistical learning. In this paper, we study the generalization properties of kernel ridge regression using both distributed methods and random features. Theoretical analysis shows the combination remarkably reduces computational cost while preserving the optimal generalization accuracy under standard assumptions. In a benign case, O(N−−√)partitions and O(N−−√) random features are sufficient to achieve O(1/N) learning rate, where N is the labeled sample size. Further, we derive more refined results by using additional unlabeled data to enlarge the number of partitions and by generating features in a data-dependent way to reduce the number of random features.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup< br/> About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Random Projections for Quadratic Programs over a Euclidean Ball

** Nuit Blanche is now on Twitter: @NuitBlog ** 

Using random projections to shrink Linear and Quadratic programs!

From presentation Random projections for Quadratic Programming over a Euclidean ball

Random Projections for Quadratic Programs over a Euclidean Ball by Vu Khac Ky, Pierre-Louis Poirion, Claudia D’Ambrosio, Leo Liberti

Random projections are used as dimensional reduction techniques in many situations. They project a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Usually, random projections are applied to numerical data. In this paper, however, we present a successful application of random projections to quadratic programming problems subject to polyhedral and a Euclidean ball constraint. We derive approximate feasibility and optimality results for the lower dimensional problem. We then show the practical usefulness of this idea on many random instances, as well as on two portfolio optimization instances with over 25M nonzeros in the (quadratic) risk term.

Gaussian random projections for Euclidean membership problems by Vu Khac Ky, Pierre-Louis Poirion, Leo Liberti

We discuss the application of Gaussian random projections to the fundamental problem of deciding whether a given point in a Euclidean space belongs to a given set. In particular, we consider the two cases, when the target set is either at most countable or of low doubling dimension. We show that, under a number of different assumptions, the feasibility (or infeasibility) of this problem is preserved almost surely when the problem data is projected to a lower dimensional space. We also consider the threshold version of this problem, in which we require that the projected point and the projected set are separated by a certain distance error. As a consequence of these results, we are able to improve the bound of Indyk-Naor on the Nearest Neigbour preserving embeddings. Our results are applicable to any algorithmic setting which needs to solve Euclidean membership problems in a high-dimensional space. 

Solving LP using random projections by Vu Khac Ky, Pierre-Louis Poirion, Leo Liberti

A celebrated result of Johnson and Lindenstrauss asserts that, in high enough dimensional spaces, Euclidean distances defined by a finite set of points are approximately preserved when these points are projected to a certain lower dimensional space. We show that the distance from a point to a convex set is another approximate invariant, and leverage this result to approximately solve linear programs with a logarithmic number of rows.

Random projections for linear programming by Vu Khac Ky, Pierre-Louis Poirion, Leo Liberti

 Random projections are random linear maps, sampled from appropriate distributions, that approximately preserve certain geometrical invariants so that the approximation improves as the dimension of the space grows. The well-known Johnson-Lindenstrauss lemma states that there are random matrices with surprisingly few rows that approximately preserve pairwise Euclidean distances among a set of points. This is commonly used to speed up algorithms based on Euclidean distances. We prove that these matrices also preserve other quantities, such as the distance to a cone. We exploit this result to devise a probabilistic algorithm to solve linear programs approximately. We show that this algorithm can approximately solve very large randomly generated LP instances. We also showcase its application to an error correction coding problem.

And a thesis:  Random projections for high-dimensional optimization problems by Vu Khac Ky

Abstract In this thesis, we will use random projection to reduce either the number of variables or the number of constraints (or both in some cases) in some well-known optimization problems. By projecting data into lower dimensional spaces, we obtain new problems with similar structures, but much easier to solve. Moreover, we try to establish conditions such that the two problems (original and projected) are strongly related (in probability sense). If it is the case, then by solving the projected problem, we can either find approximate solutions or approximate objective value for the original one. We will apply random projection to study a number of important optimization problems, including linear and integer programming (Chapter 2), convex optimization with linear constraints (Chapter 3), membership and approximate nearest neighbor (Chapter 4) and trustregion subproblems (Chapter 5). All these results are taken from the papers that I am co-authored with [26, 25, 24, 27]. This thesis will be constructed as follows. In the first chapter, we will present some basic concepts and results in probability theory. Since this thesis extensively uses elementary probability, this informal introduction will make it easier for readers with little background on this field to follow our works. In Chapter 2, we will briefly introduce to random projection and the Johnson-Lindenstrauss lemma. We will present several constructions of random projectors and explain the reason why they work. In particular, sub-gaussian random matrices will be treated in details, together with some discussion on fast and sparse random projections. In Chapter 3, we study optimization problems in their feasibility forms. In particular, we study the so-called restricted linear membership problem, which asks for the feasibility of the system {Ax = b, x ∈ C} where C is some set that restricts the choice of parameters x. This class contains many important problems such as linear and integer feasibility. We propose to apply a random projection T to the linear constraints and obtain the corresponding projected problem: {T Ax = T b, x ∈ C}. We want to find conditions on T, so that the two feasibility 4 problems are equivalent with high probability. The answer is simple when C is finite and bounded by a polynomial (in n). In that case, any random projection T with O(log n) rows is sufficient. When C = R n +, we use the idea of separating hyperplane to separate b from the cone {Ax | x ≥ 0} and show that T b is still separated from the projected cone {T Ax | x ≥ 0} under certain conditions. If these conditions do not hold, for example when the cone {Ax | x ≥ 0} is non-pointed, we employ the idea in the Johnson-Lindenstrauss lemma to prove that, if b /∈ {Ax | x ≥ 0}, then the distance between b and that cone is slightly distorted under T, thus still remains positive. However, the number of rows of T depends on unknown parameters that are hard to estimate. In Chapter 4, we continue to study the above problem in the case when C is a convex set. Under that assumption, we can define a tangent cone K of C at x ∗ ∈ arg minx∈C kAx − bk. We establish the relations between the original and projected problems based on the concept of Gaussian width, which is popular in compressed sensing. In particular, we prove that the two problems are equivalent with high probability as long as the random projection T is sampled from sub-gaussian distributions and has at least O(W2 (AK)) rows, where W(AK) is the Gaussian-width of AK. We also extend this result to the case when T is sampled from randomized orthonormal systems in order to exploit its fast matrix-vector multiplication. Our results are similar to those in [21], however they are more useful in privacy-preservation applications when the access to the original data A, b is limited or unavailable. In Chapter 5, we study the Euclidean membership problem: “Given a vector b and a closed set X in R n , decide whether b ∈ X or not”. This is a generalization of the restricted linear membership problem considered previously. We employ a Gaussian random projection T to embed both b and X into a lower dimension space and study the corresponding projected version: “Decide whether T b ∈ T(X) or not”. When X is finite or countable, using a straightforward argument, we prove that the two problems are equivalent almost surely regardless the projected dimension. However, this result is only of theoretical interest, possibly due to round-off errors in floating point operations which make its practical application difficult. We address this issue by introducing a threshold τ > 0 and study the corresponding “thresholded” problem: “Decide whether dist (T b, T(X)) ≥ τ”. In the case when X may be uncountable, we prove that the original and projected problems are also equivalent if the projected dimension d is proportional to some intrinsic dimension of the set X. In particular, we employ the definition of doubling dimension to prove that, if b /∈ X, then Sb /∈ S(X) almost surely as long as d = Ω(ddim(X)). Here, ddim(X) is the doubling dimension of X, which is defined as the smallest number such that each ball in X can be covered by at most 2 dd(X) balls of half the radius. We extend this result to the thresholded case, and obtain a more useful bound for d. It turns out that, as a consequence of that result, we are able to 5 improve a bound of Indyk-Naor on the Nearest Neigbour Preserving embeddings by a factor of log(1/δ) ε . In Chapter 6, we propose to apply random projections for the trust-region subproblem, which is stated as min{c >x + x >Qx | Ax ≤ b, kxk ≤ 1}. These problems arise in trust-region methods for dealing with derivative-free optimization. Let P ∈ R d×n be a random matrix sampled from Gaussian distribution, we then consider the following “projected” problem: min{c >P >P x + x >P >P QP >P x | AP >P x ≤ b, kP xk ≤ 1}, which can be reduced to min{(P c) >u + u >(P QP >)u | AP >u ≤ b, kuk ≤ 1} by setting u := P x. The latter problem is of low dimension and can be solved much faster than the original. However, we prove that, if u ∗ is its optimal solution, then with high probability, x ∗ := P >u ∗ is a (1 + O(ε))-approximation for the original problem. This is done by using recent results about the “concentration of eigenvalues” of Gaussian matrices. 

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup< br/> About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

On Random Deep Weight-Tied Autoencoders: Exact Asymptotic Analysis, Phase Transitions, and Implications to Training

On Random Deep Weight-Tied Autoencoders: Exact Asymptotic Analysis, Phase Transitions, and Implications to Training by Ping Li, Phan-Minh Nguyen

Abstract: We study the behavior of weight-tied multilayer vanilla autoencoders under the assumption of random weights. Via an exact characterization in the limit of large dimensions, our analysis reveals interesting phase transition phenomena when the depth becomes large. This, in particular, provides quantitative answers and insights to three questions that were yet fully understood in the literature. Firstly, we provide a precise answer on how the random deep weight-tied autoencoder model performs “approximate inference” as posed by Scellier et al. (2018), and its connection to reversibility considered by several theoretical studies. Secondly, we show that deep autoencoders display a higher degree of sensitivity to perturbations in the parameters, distinct from the shallow counterparts. Thirdly, we obtain insights on pitfalls in training initialization practice, and demonstrate experimentally that it is possible to train a deep autoencoder, even with the tanh activation and a depth as large as 200 layers, without resorting to techniques such as layer-wise pre-training or batch normalization. Our analysis is not specific to any depths or any Lipschitz activations, and our analytical techniques may have broader applicability.

The attendant video at ICLR is here and it starts at 52 minutes.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

A New Theory for Sketching in Linear Regression -implementation-

A New Theory for Sketching in Linear Regression by Edgar Dobriban, Sifan Liu

Large datasets create opportunities as well as analytic challenges. A recent development is to use random projection or sketching methods for dimension reduction in statistics and machine learning. In this work, we study the statistical performance of sketching algorithms for linear regression. Suppose we randomly project the data matrix and the outcome using a random sketching matrix reducing the sample size, and do linear regression on the resulting data. How much do we lose compared to the original linear regression? The existing theory does not give a precise enough answer, and this has been a bottleneck for using random projections in practice.
In this paper, we introduce a new mathematical approach to the problem, relying on very recent results from asymptotic random matrix theory and free probability theory. This is a perfect fit, as the sketching matrices are random in practice. We allow the dimension and sample sizes to have an arbitrary ratio. We study the most popular sketching methods in a unified framework, including random projection methods (Gaussian and iid projections, uniform orthogonal projections, subsampled randomized Hadamard transforms), as well as sampling methods (including uniform, leverage-based, and greedy sampling). We find precise and simple expressions for the accuracy loss of these methods. These go beyond classical Johnson-Lindenstrauss type results, because they are exact, instead of being bounds up to constants. Our theoretical formulas are surprisingly accurate in extensive simulations and on two empirical datasets.

Implementation is here: https://github.com/liusf15/Sketching-lr

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Projecting "better than randomly": How to reduce the dimensionality of very large datasets in a way that outperforms random projections

So, datasets are becoming so large that we now have investigations on the difference between Random Projections and Randomized PCA !

Projecting "better than randomly": How to reduce the dimensionality of very large datasets in a way that outperforms random projections by Michael Wojnowicz, Di Zhang, Glenn Chisholm, Xuan Zhao, Matt Wolff

For very large datasets, random projections (RP) have become the tool of choice for dimensionality reduction. This is due to the computational complexity of principal component analysis. However, the recent development of randomized principal component analysis (RPCA) has opened up the possibility of obtaining approximate principal components on very large datasets. In this paper, we compare the performance of RPCA and RP in dimensionality reduction for supervised learning. In Experiment 1, study a malware classification task on a dataset with over 10 million samples, almost 100,000 features, and over 25 billion non-zero values, with the goal of reducing the dimensionality to a compressed representation of 5,000 features. In order to apply RPCA to this dataset, we develop a new algorithm called large sample RPCA (LS-RPCA), which extends the RPCA algorithm to work on datasets with arbitrarily many samples. We find that classification performance is much higher when using LS-RPCA for dimensionality reduction than when using random projections. In particular, across a range of target dimensionalities, we find that using LS-RPCA reduces classification error by between 37% and 54%. Experiment 2 generalizes the phenomenon to multiple datasets, feature representations, and classifiers. These findings have implications for a large number of research projects in which random projections were used as a preprocessing step for dimensionality reduction. As long as accuracy is at a premium and the target dimensionality is sufficiently less than the numeric rank of the dataset, randomized PCA may be a superior choice. Moreover, if the dataset has a large number of samples, then LS-RPCA will provide a method for obtaining the approximate principal components.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:

Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog

About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Enhanced Expressive Power and Fast Training of Neural Networks by Random Projections

Here is one way random projections can reduce training time in neural networks !

Enhanced Expressive Power and Fast Training of Neural Networks by Random Projections by Jian-Feng Cai, Dong Li, Jiaze Sun, Ke Wang

Random projections are able to perform dimension reduction efficiently for datasets with nonlinear low-dimensional structures. One well-known example is that random matrices embed sparse vectors into a low-dimensional subspace nearly isometrically, known as the restricted isometric property in compressed sensing. In this paper, we explore some applications of random projections in deep neural networks. We provide the expressive power of fully connected neural networks when the input data are sparse vectors or form a low-dimensional smooth manifold. We prove that the number of neurons required for approximating a Lipschitz function with a prescribed precision depends on the sparsity or the dimension of the manifold and weakly on the dimension of the input vector. The key in our proof is that random projections embed stably the set of sparse vectors or a low-dimensional smooth manifold into a low-dimensional subspace. Based on this fact, we also propose some new neural network models, where at each layer the input is first projected onto a low-dimensional subspace by a random projection and then the standard linear connection and non-linear activation are applied. In this way, the number of parameters in neural networks is significantly reduced, and therefore the training of neural networks can be accelerated without too much performance loss.

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv

Book: High-Dimensional Probability An Introduction with Applications in Data Science by Roman Vershynin

Found in the comment section of Terry's blog: Roman Vershynin is writing a book titled: High-Dimensional Probability An Introduction with Applications in Data Science (University of California, Irvine March 25, 2019) 

Here is the table of content:

Preface vi Appetizer: using probability to cover a geometric set 

1 Preliminaries on random variables 6
1 1 Preliminaries on random variables 6
1.1 Basic quantities associated with random variables 6
1.2 Some classical inequalities 7
1.3 Limit theorems 9
1.4 Notes 12

2 Concentration of sums of independent random variables 13 
2.1 Why concentration inequalities? 13
2.2 Hoeffding’s inequality 16
2.3 Chernoff’s inequality 19
2.4 Application: degrees of random graphs 21
2.5 Sub-gaussian distributions 24
2.6 General Hoeffding’s and Khintchine’s inequalities 29
2.7 Sub-exponential distributions 32
2.8 Bernstein’s inequality 37
2.9 Notes 40  

3 Random vectors in high dimensions 42
3.1 Concentration of the norm 43
3.2 Covariance matrices and principal component analysis 45
3.3 Examples of high-dimensional distributions 50
3.4 Sub-gaussian distributions in higher dimensions 56
3.5 Application: Grothendieck’s inequality and semidefinite programming 60
3.6 Application: Maximum cut for graphs 66
3.7 Kernel trick, and tightening of Grothendieck’s inequality 70
3.8 Notes 74  

4 Random matrices 76 
4.1 Preliminaries on matrices 76
4.2 Nets, covering numbers and packing numbers 81
4.3 Application: error correcting codes 86
4.4 Upper bounds on random sub-gaussian matrices 89
4.5 Application: community detection in networks 93
4.6 Two-sided bounds on sub-gaussian matrices 97 iii iv Contents
4.7 Application: covariance estimation and clustering 99
4.8 Notes 103 

5 Concentration without independence 105
5.1 Concentration of Lipschitz functions on the sphere 105
5.2 Concentration on other metric measure spaces 112
5.3 Application: Johnson-Lindenstrauss Lemma 118
5.4 Matrix Bernstein’s inequality 121
5.5 Application: community detection in sparse networks 129
5.6 Application: covariance estimation for general distributions 129
5.7 Notes 133

6 Quadratic forms, symmetrization and contraction 135 
6.1 Decoupling 135
6.2 Hanson-Wright Inequality 139
6.3 Concentration of anisotropic random vectors 142
6.4 Symmetrization 145
6.5 Random matrices with non-i.i.d. entries 147
6.6 Application: matrix completion 148
6.7 Contraction Principle 151 6.8 Notes 154 

7 Random processes 156 
7.1 Basic concepts and examples 156
7.2 Slepian’s inequality 160
7.3 Sharp bounds on Gaussian matrices 167
7.4 Sudakov’s minoration inequality 170
7.5 Gaussian width 172
7.6 Stable dimension, stable rank, and Gaussian complexity 178
7.7 Random projections of sets 181
7.8 Notes 185 

8 Chaining 187 
8.1 Dudley’s inequality 187
8.2 Application: empirical processes 195
8.3 VC dimension 200
8.4 Application: statistical learning theory 212
8.5 Generic chaining 219
8.6 Talagrand’s majorizing measure and comparison theorems 223
8.7 Chevet’s inequality 225
8.8 Notes 227 

9 Deviations of random matrices and geometric consequences 229 
9.1 Matrix deviation inequality 229
9.2 Random matrices, random projections and covariance estimation 235
9.3 Johnson-Lindenstrauss Lemma for infinite sets 238
9.4 Random sections: M∗ bound and Escape Theorem 240
9.5 Notes 

10 Sparse Recovery 246 
10.1 High-dimensional signal recovery problems 246
10.2 Signal recovery based on M∗ bound 248
10.3 Recovery of sparse signals 250
10.4 Low-rank matrix recovery 254
10.5 Exact recovery and the restricted isometry property 256
10.6 Lasso algorithm for sparse regression 262
10.7 Notes 267

11 Dvoretzky-Milman’s Theorem 269
11.1 Deviations of random matrices with respect to general norms 269
11.2 Johnson-Lindenstrauss embeddings and sharper Chevet inequality 272
11.3 Dvoretzky-Milman’s Theorem 274
11.4 Notes 279

Bibliography 280
Index

Follow @NuitBlog or join the CompressiveSensing Reddit, the Facebook page, the Compressive Sensing group on LinkedIn  or the Advanced Matrix Factorization group on LinkedIn

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email.

Other links:
Paris Machine Learning: Meetup.com||@Archives||LinkedIn||Facebook|| @ParisMLGroup About LightOn: Newsletter ||@LightOnIO|| on LinkedIn || on CrunchBase || our Blog
About myself: LightOn || Google Scholar || LinkedIn ||@IgorCarron ||Homepage||ArXiv