Search

We consider the problem of finding a two-layer neural network with sigmoid, rectified linear unit, or binary step activation functions that “fits” a training data set as accurately as possible as quantified by the training error; and study the following question: does a low training error guarantee that the norm of the output layer (outer norm) itself is small? We address this question for the case of non-negative output weights. Using a simple covering number argument, we establish that under quite mild distributional assumptions on the input/label pairs; any such network achieving a small training error on polynomially many data necessarily has a well-controlled outer norm. Notably, our results (a) have a good sample complexity, (b) are independent of the number of hidden units, (c) are oblivious to the training algorithm; and (d) require quite mild assumptions on the data (in particular the input vector $X$ ∊ Rd need not have independent coordinates). We then show how our bounds can be leveraged to yield generalization guarantees for such networks.

We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions. Such problems arise widely in the theory of random graphs, theoretical computer science, and statistical physics. Two concrete problems we consider are (a) optimizing the Hamiltonian of a spherical or Ising p-spin glass model, and (b) finding a large independent set in a sparse Erdos-Renyi graph. Two families of algorithms are considered: (a) low-degree polynomials of the input—a general framework that captures methods such as approximate message passing and local algorithms on sparse graphs, among others; and (b) the Langevin dynamics algorithm, a canonical Monte Carlo analogue of the gradient descent algorithm (applicable only for the spherical p-spin glass Hamiltonian). We show that neither family of algorithms can produce nearly optimal solutions with high probability. Our proof uses the fact that both models are known to exhibit a variant of the overlap gap property (OGP) of near-optimal solutions. Specifically, for both models, every two solutions whose objective values are above a certain threshold are either close or far from each other. The crux of our proof is the stability of both algorithms: a small perturbation of the input induces a small perturbation of the output. By an interpolation argument, such a stable algorithm cannot overcome the OGP barrier. The stability of the Langevin dynamics is an immediate consequence of the well-posedness of stochastic differential equations. The stability of low-degree polynomials is established using concepts from Gaussian and Boolean Fourier analysis, including noise sensitivity, hypercontractivity, and total influence.

We establish the average-case hardness of the algorithmic problem of exactly computing the partition function of the Sherrington-Kirkpatrick model of spin glasses with Gaussian couplings. In particular, we establish that unless P=#P, there does not exist a polynomial-time algorithm to exactly compute this object on average. This is done by showing that if there exists a polynomial-time algorithm exactly computing the partition function for a certain fraction of all inputs, then there is a polynomial-time algorithm exactly computing this object for all inputs, with high probability, yielding P =#P. Our results cover both finite-precision arithmetic as well as the real-valued computational models. The ingredients of our proofs include Berlekamp-Welch algorithm, a list-decoding algorithm by Sudan for reconstructing a polynomial from its noisy samples, near-uniformity of log-normal distribution modulo a large prime; and a control over total variation distance for log-normal distribution under convex perturbation. To the best of our knowledge, this is the first average-case hardness result pertaining a statistical physics model with random parameters.

We study high-dimensional linear regression problem without sparsity, and address the question of efficient recovery with small number of measurements. We propose an algorithm which efficiently recovers an unknown feature vector β∗ ∈ ℝp from its linear measurements Y = Xβ∗ in polynomially many steps, with high probability (as p → ∞), even with a single measurement, provided elements of β∗ are supported on a rationally independent set of at most polynomial in p size known to learner. We use a combination of PSLQ integer relation and LLL lattice basis reduction algorithms to achieve our goal. We then apply our ideas to develop an efficient, single-sample algorithm for the phase retrieval problem, where ${\beta ^ * } \in {\mathbb{C}^p}$ is to be recovered from magnitude-only observations Y = |〈X, β∗〉|.

Today, echocardiography is regarded as the clinical gold standard for evaluation of left ventricular (LV) dysfunction. Although a number of quantitative metrics are commonly used in conjunction with specific criteria to diagnose and prognosticate the disease state, part of the assessment of LV function is still qualitative and performed visually. Subjectively derived indices such as the wall motion score index are subject to significant inter-observer variability. Ultrasound- based measures of myocardial deformation (strain) have been available for several years, even in commercially distributed packages, and have the potential to offer a quantitative, objective, and more operator-independent assessment of LV function. However, despite growing evidence on the clinical utility of deformation imaging, a consensus on the meaning, interpretation, and normal ranges of myocardial strain is still lacking, thus preventing routine use of such estimates in clinical practice. In this article, we outline the current status of myocardial strain estimation and address the existing hurdles that must be overcome in order to incorporate this powerful technique into standard clinical assessment of LV function. I. INTRODUCTION

A level set-based method for tracking the endocardium from 3D ultrasound images is presented. The tracking process is initialized by a manual delineation and performed automatically. The method does not use a shape prior model, removing the requirement of acquiring large sets of training data, and providing adaptivity for abnormal cases. At each image frame, the edge strength is estimated and locations with strong edges are used to compute the region-based surface deformation, which is then propagated to the rest of the image volume. The approach is evaluated with 10 sequences of canine subjects including 5 ischemic image sequences. The results show that the method performs with error values below the interobserver variability of manual segmentation, and is able to robustly follow the cardiac wall movement.

There currently exist a variety of methods for evaluating movement in patients suffering from neuromuscular diseases (NMD). These tests are primarily performed in the clinical setting and evaluated by highly trained individuals, rather than evaluating patient in their natural environments (i.e., home or school). Currently available automated motion capture modalities offer a highly accurate means of assessing general motion, but are also limited to a highly controlled setting. Recent advances in MEMS technology have introduced the possibility of robust motion capture in uncontrolled environments, while minimizing user interference with self-initiated motion, especially in weaker subjects. The goal of this study is to design and evaluate a MEMS-sensor-based system for motion capture in the NMD patient population. The highly interdisciplinary effort has led to significant progress toward the implementation of a new device, which is accurate, clinically relevant, and highly affordable.

Echocardiography is the most prevalent imaging modalities in clinical cardiology. However, current diagnostic techniques rely on qualitative image analysis, ignoring the quantitative data inherent to this modality. We seek to develop a quantitative system for analyzing echocardiographic images. In this study, the performance of myocardial elastography was tested under motion-induced decorrelation noise using a tissue- mimicking phantom of the human left ventricle (LV) that underwent physiologic, cardiac motion configurations. A Terason system (Teratech Corp., Burlington, MA, USA.) with a phased array transducer (128 elements, 3.5 MHz) was utilized to acquire radiofrequency (RF) data in a short-axis view of a cylindrical polyacrylamide phantom with geometric (Ro = 28 mm, Ri = 15 mm, L = 15 cm) and mechanical properties (Ewall = 50 kPa + agar scatterers; Ecore = 10 kPa) similar to those of an adult, healthy LV. The phantom underwent two motion configurations - either pure rotation, with the non-rotating end of the phantom being free, or torsion with the non-rotating end being fixed; the latter in order to simulate the "wringing" action of the LV. This provided a realistic motion pattern for decorrelation noise and rotational motion analysis. RF data were acquired at multiple slices to assess differential displacements under these motion configurations. In-plane (lateral and axial) displacements were iteratively estimated using a 1D cross-correlation and recorrelation technique in a 2D search (4.10 mm window with 75% overlap) and then radial, circumferential, and angular displacements were calculated via a coordinate transformation. Second, in-plane strains were calculated using a least-squares strain estimator. Radial and circumferential strains were then computed based on a similar coordinate transformation. The observed displacement estimates were in accordance with the theoretically predicted results. During pure rotation, all regions of the phantom exhibited similar displacements and minute strains. In the case of torsion, in-plane strains were again insignificant, but analysis of multiple slices revealed differential motion resulting from the imposed constraint on rotation. Ongoing studies aim at investigating the reproducibility of the measurements as well as studying more complex motion configurations, including simultaneous radial deformation and flow.

We propose asymptotically optimal algorithms for job shop scheduling. We propose a fluid relaxation for the job shop scheduling problem, in which we replace discrete jobs with the flow of a continuous fluid. We compute an optimal solution of the fluid relaxation in closed form, obtain a lower bound C/sub max/ to the job shop scheduling problem, and construct a feasible schedule from the fluid relaxation with objective value at most C/sub max/+O(/spl radic/C/sub max/), where the constant in the O(/spl middot/) notation is independent of the number of jobs. However, it depends on the processing times of the jobs, thus producing an asymptotically optimal schedule as the total number of jobs tends to infinity. If the initially present jobs increase proportionally, then our algorithm produces a schedule with value at most C/sub max/+O(1). In computational experiments our algorithms produce schedules which are within 1% of optimality even for moderately sized problems.

We study the distribution of steady-state queue lengths in multiclass queueing networks under a stable policy. We propose a general methodology based on Lyapunov functions, for the performance analysis of infinite state Markov chains and apply it specifically to Markovian multiclass queueing networks. We establish a deeper connection between stability and performance of such networks by showing that if there exist linear and piecewise linear Lyapunov functions that show stability, then these Lyapunov functions can be used to establish geometric type lower and upper bounds on the tail probabilities, and thus bounds on the expectation of the queue lengths. As an example of our results, for a reentrant line queueing network with two processing stations operating under a work-conserving policy we show that E[L]=O (1/(1-/spl rho/*)2), where L is the total number of customers in the system, and /spl rho/* is the maximal actual or virtual traffic intensity in the network. This extends a recent result by Dai and Vande-Vate, which states that a re-entrant line queueing network with two stations is globally stable if /spl rho/*