  Online Streaming Feature Selection (OSFS) is a sequential learning problem
where individual features across all samples are made available to algorithms
in a streaming fashion. In this work, firstly, we assert that OSFS's main
assumption of having data from all the samples available at runtime is
unrealistic and introduce a new setting where features and samples are streamed
concurrently called OSFS with Streaming Samples (OSFS-SS). Secondly, the
primary OSFS method, SAOLA utilizes an unbounded mutual information measure and
requires multiple comparison steps between the stored and incoming feature sets
to evaluate a feature's importance. We introduce Geometric Online Adaption, an
algorithm that requires relatively less feature comparison steps and uses a
bounded conditional geometric dependency measure. Our algorithm outperforms
several OSFS baselines including SAOLA on a variety of datasets. We also extend
SAOLA to work in the OSFS-SS setting and show that GOA continues to achieve the
best results. Thirdly, the current paradigm of the OSFS algorithm comparison is
flawed. Algorithms are measured by comparing the number of features used and
the accuracy obtained by the learner, two properties that are fundamentally at
odds with one another. Without fixing a limit on either of these properties,
the qualities of features obtained by different algorithms are incomparable. We
try to rectify this inconsistency by fixing the maximum number of features
available to the learner and comparing algorithms in terms of their accuracy.
Additionally, we characterize the behaviour of SAOLA and GOA on feature sets
derived from popular deep convolutional featurizers.
