TY - CONF AB - The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time. AU - Mohapatra, Pritish AU - Rolinek, Michal AU - Jawahar, C V AU - Kolmogorov, Vladimir AU - Kumar, M Pawan ID - 273 SN - 9781538664209 T2 - 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition TI - Efficient optimization for rank-based loss functions ER - TY - JOUR AB - We report on quantum capacitance measurements of high quality, graphite- and hexagonal boron nitride encapsulated Bernal stacked trilayer graphene devices. At zero applied magnetic field, we observe a number of electron density- and electrical displacement-tuned features in the electronic compressibility associated with changes in Fermi surface topology. At high displacement field and low density, strong trigonal warping gives rise to emergent Dirac gullies centered near the corners of the hexagonal Brillouin and related by three fold rotation symmetry. At low magnetic fields of B=1.25~T, the gullies manifest as a change in the degeneracy of the Landau levels from two to three. Weak incompressible states are also observed at integer filling within these triplets Landau levels, which a Hartree-Fock analysis indicates are associated with Coulomb-driven nematic phases that spontaneously break rotation symmetry. AU - Zibrov, Alexander AU - Peng, Rao AU - Kometter, Carlos AU - Li, Jia AU - Dean, Cory AU - Taniguchi, Takashi AU - Watanabe, Kenji AU - Serbyn, Maksym AU - Young, Andrea ID - 289 IS - 16 JF - Physical Review Letters TI - Emergent dirac gullies and gully-symmetry-breaking quantum hall states in ABA trilayer graphene VL - 121 ER - TY - JOUR AB - In this paper, we discuss biological effects of electromagnetic (EM) fields in the context of cancer biology. In particular, we review the nanomechanical properties of microtubules (MTs), the latter being one of the most successful targets for cancer therapy. We propose an investigation on the coupling of electromagnetic radiation to mechanical vibrations of MTs as an important basis for biological and medical applications. In our opinion, optomechanical methods can accurately monitor and control the mechanical properties of isolated MTs in a liquid environment. Consequently, studying nanomechanical properties of MTs may give useful information for future applications to diagnostic and therapeutic technologies involving non-invasive externally applied physical fields. For example, electromagnetic fields or high intensity ultrasound can be used therapeutically avoiding harmful side effects of chemotherapeutic agents or classical radiation therapy. AU - Salari, Vahid AU - Barzanjeh, Shabir AU - Cifra, Michal AU - Simon, Christoph AU - Scholkmann, Felix AU - Alirezaei, Zahra AU - Tuszynski, Jack ID - 287 IS - 8 JF - Frontiers in Bioscience - Landmark TI - Electromagnetic fields and optomechanics In cancer diagnostics and treatment VL - 23 ER - TY - JOUR AB - We show that the following algorithmic problem is decidable: given a 2-dimensional simplicial complex, can it be embedded (topologically, or equivalently, piecewise linearly) in R3? By a known reduction, it suffices to decide the embeddability of a given triangulated 3-manifold X into the 3-sphere S3. The main step, which allows us to simplify X and recurse, is in proving that if X can be embedded in S3, then there is also an embedding in which X has a short meridian, that is, an essential curve in the boundary of X bounding a disk in S3 \ X with length bounded by a computable function of the number of tetrahedra of X. AU - Matoušek, Jiří AU - Sedgwick, Eric AU - Tancer, Martin AU - Wagner, Uli ID - 425 IS - 1 JF - Journal of the ACM TI - Embeddability in the 3-Sphere is decidable VL - 65 ER - TY - JOUR AB - Maladapted individuals can only colonise a new habitat if they can evolve a positive growth rate fast enough to avoid extinction, a process known as evolutionary rescue. We treat log fitness at low density in the new habitat as a single polygenic trait and thus use the infinitesimal model to follow the evolution of the growth rate; this assumes that the trait values of offspring of a sexual union are normally distributed around the mean of the parents’ trait values, with variance that depends only on the parents’ relatedness. The probability that a single migrant can establish depends on just two parameters: the mean and genetic variance of the trait in the source population. The chance of success becomes small if migrants come from a population with mean growth rate in the new habitat more than a few standard deviations below zero; this chance depends roughly equally on the probability that the initial founder is unusually fit, and on the subsequent increase in growth rate of its offspring as a result of selection. The loss of genetic variation during the founding event is substantial, but highly variable. With continued migration at rate M, establishment is inevitable; when migration is rare, the expected time to establishment decreases inversely with M. However, above a threshold migration rate, the population may be trapped in a ‘sink’ state, in which adaptation is held back by gene flow; above this threshold, the expected time to establishment increases exponentially with M. This threshold behaviour is captured by a deterministic approximation, which assumes a Gaussian distribution of the trait in the founder population with mean and variance evolving deterministically. By assuming a constant genetic variance, we also develop a diffusion approximation for the joint distribution of population size and trait mean, which extends to include stabilising selection and density regulation. Divergence of the population from its ancestors causes partial reproductive isolation, which we measure through the reproductive value of migrants into the newly established population. AU - Barton, Nicholas H AU - Etheridge, Alison ID - 564 IS - 7 JF - Theoretical Population Biology TI - Establishment in a new habitat by polygenic adaptation VL - 122 ER -