Low-Rank Riemannian Optimization for Graph-Based Clustering Applications.

With the abundance of data, machine learning applications engaged increased attention in the last decade. An attractive approach to robustify the statistical analysis is to preprocess the data through clustering. This paper develops a low-complexity Riemannian optimization framework for solving optimization problems on the set of positive semidefinite stochastic matrices. The low-complexity feature of the proposed algorithms stems from the factorization of the optimization variable X=YYT and deriving conditions on the number of columns of Y under which the factorization yields a satisfactory solution. The paper further investigates the embedded and quotient geometries of the resulting Riemannian manifolds. In particular, the paper explicitly derives the tangent space, Riemannian gradients and Hessians, and a retraction operator allowing the design of efficient first and second-order optimization methods for the graph-based clustering applications of interest. The numerical results reveal that the resulting algorithms present a clear complexity advantage as compared with state-of-the-art euclidean and Riemannian approaches for graph clustering applications.

How to Query an Oracle? Efficient Strategies to Label Data.

We consider the basic problem of querying an expert oracle for labeling a dataset in machine learning. This is typically an expensive and time consuming process and therefore, we seek ways to do so efficiently. The conventional approach involves comparing each sample with (the representative of) each class to find a match. In a setting with N equally likely classes, this involves N/2 pairwise comparisons (queries per sample) on average. We consider a k-ary query scheme with k ≥ 2 samples in a query that identifies (dis)similar items in the set while effectively exploiting the associated transitive relations. We present a randomized batch algorithm that operates on a round-by-round basis to label the samples and achieves a query rate of [Formula: see text]. In addition, we present an adaptive greedy query scheme, which achieves an average rate of ≈ 0.2N queries per sample with triplet queries. For the proposed algorithms, we investigate the query rate performance analytically and with simulations. Empirical studies suggest that each triplet query takes an expert at most 50% more time compared with a pairwise query, indicating the effectiveness of the proposed k-ary query schemes. We generalize the analyses to nonuniform class distributions when possible.

Stochastic Mirror Descent on Overparameterized Nonlinear Models.

Most modern learning problems are highly overparameterized, i.e., have many more model parameters than the number of training data points. As a result, the training loss may have infinitely many global minima (parameter vectors that perfectly "interpolate" the training data). It is therefore imperative to understand which interpolating solutions we converge to, how they depend on the initialization and learning algorithm, and whether they yield different test errors. In this article, we study these questions for the family of stochastic mirror descent (SMD) algorithms, of which stochastic gradient descent (SGD) is a special case. Recently, it has been shown that for overparameterized linear models, SMD converges to the closest global minimum to the initialization point, where closeness is in terms of the Bregman divergence corresponding to the potential function of the mirror descent. With appropriate initialization, this yields convergence to the minimum-potential interpolating solution, a phenomenon referred to as implicit regularization. On the theory side, we show that for sufficiently-overparameterized nonlinear models, SMD with a (small enough) fixed step size converges to a global minimum that is "very close" (in Bregman divergence) to the minimum-potential interpolating solution, thus attaining approximate implicit regularization. On the empirical side, our experiments on the MNIST and CIFAR-10 datasets consistently confirm that the above phenomenon occurs in practical scenarios. They further indicate a clear difference in the generalization performances of different SMD algorithms: experiments on the CIFAR-10 dataset with different regularizers, l1 to encourage sparsity, l2 (SGD) to encourage small Euclidean norm, and l∞ to discourage large components, surprisingly show that the l∞ norm consistently yields better generalization performance than SGD, which in turn generalizes better than the l1 norm.

A Silicon Photonics Computational Lensless Active-Flat-Optics Imaging System.

The need for lightweight, miniature imaging systems is becoming increasingly prevalent in light of the development of wearable electronics, IoT devices, and drones. Computational imaging enables new types of imaging systems that replace standard optical components like lenses with cleverly designed computational processes. Traditionally, many of these types of systems use conventional complementary metal oxide semiconductor (CMOS) or charge coupled device (CCD) sensors for data collection. While this allows for rapid development of large-scale systems, the lack of system-sensor co-design limits the compactness and performance. Here we propose integrated photonics as a candidate platform for the implementation of such co-integrated systems. Using grating couplers and co-designed computational processing in lieu of a lens, we demonstrate the use of silicon photonics as a viable platform for computational imaging with a prototype lensless imaging device. The proof-of-concept device has 20 sensors and a 45-degree field of view, and its optics and sensors are contained within a 2,000 µm × 200 µm × 20 µm volume.

Multiplexed identification, quantification and genotyping of infectious agents using a semiconductor biochip.

The emergence of pathogens resistant to existing antimicrobial drugs is a growing worldwide health crisis that threatens a return to the pre-antibiotic era. To decrease the overuse of antibiotics, molecular diagnostics systems are needed that can rapidly identify pathogens in a clinical sample and determine the presence of mutations that confer drug resistance at the point of care. We developed a fully integrated, miniaturized semiconductor biochip and closed-tube detection chemistry that performs multiplex nucleic acid amplification and sequence analysis. The approach had a high dynamic range of quantification of microbial load and was able to perform comprehensive mutation analysis on up to 1,000 sequences or strands simultaneously in <2 h. We detected and quantified multiple DNA and RNA respiratory viruses in clinical samples with complete concordance to a commercially available test. We also identified 54 drug-resistance-associated mutations that were present in six genes of Mycobacterium tuberculosis, all of which were confirmed by next-generation sequencing.

FRET-based real-time DNA microarrays.

We present a quantification method for affinity-based DNA microarrays which is based on the real-time measurements of hybridization kinetics. This method, i.e., real-time DNA microarrays, enhances the detection dynamic range of conventional systems by being impervious to probe saturation, washing artifacts, microarray spot-to-spot variations, and other intensity-affecting impediments. We demonstrate in both theory and practice that the time-constant of target capturing is inversely proportional to the concentration of the target analyte, which we take advantage of as the fundamental parameter to estimate the concentration of the analytes. Furthermore, to experimentally validate the capabilities of this method in practical applications, we present a FRET-based assay which enables the real-time detection in gene expression DNA microarrays.

Real-time DNA microarray analysis.

We present a quantification method for affinity-based DNA microarrays which is based on the real-time measurements of hybridization kinetics. This method, i.e. real-time DNA microarrays, enhances the detection dynamic range of conventional systems by being impervious to probe saturation in the capturing spots, washing artifacts, microarray spot-to-spot variations, and other signal amplitude-affecting non-idealities. We demonstrate in both theory and practice that the time-constant of target capturing in microarrays, similar to all affinity-based biosensors, is inversely proportional to the concentration of the target analyte, which we subsequently use as the fundamental parameter to estimate the concentration of the analytes. Furthermore, to empirically validate the capabilities of this method in practical applications, we present a FRET-based assay which enables the real-time detection in gene expression DNA microarrays.