Paper Group ANR 559
Comments on the proof of adaptive submodular function minimization. Statistical inference for high dimensional regression via Constrained Lasso. Deep Ordinal Ranking for Multi-Category Diagnosis of Alzheimer’s Disease using Hippocampal MRI data. Minimum Energy Quantized Neural Networks. A description length approach to determining the number of k-m …
Comments on the proof of adaptive submodular function minimization
| Title | Comments on the proof of adaptive submodular function minimization |
| Authors | Feng Nan, Venkatesh Saligrama |
| Abstract | We point out an issue with Theorem 5 appearing in “Group-based active query selection for rapid diagnosis in time-critical situations”. Theorem 5 bounds the expected number of queries for a greedy algorithm to identify the class of an item within a constant factor of optimal. The Theorem is based on correctness of a result on minimization of adaptive submodular functions. We present an example that shows that a critical step in Theorem A.11 of “Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization” is incorrect. |
| Tasks | Active Learning, Stochastic Optimization |
| Published | 2017-05-10 |
| URL | http://arxiv.org/abs/1705.03771v1 |
| http://arxiv.org/pdf/1705.03771v1.pdf | |
| PWC | https://paperswithcode.com/paper/comments-on-the-proof-of-adaptive-submodular |
| Repo | |
| Framework | |
Statistical inference for high dimensional regression via Constrained Lasso
| Title | Statistical inference for high dimensional regression via Constrained Lasso |
| Authors | Yun Yang |
| Abstract | In this paper, we propose a new method for estimation and constructing confidence intervals for low-dimensional components in a high-dimensional model. The proposed estimator, called Constrained Lasso (CLasso) estimator, is obtained by simultaneously solving two estimating equations—one imposing a zero-bias constraint for the low-dimensional parameter and the other forming an $\ell_1$-penalized procedure for the high-dimensional nuisance parameter. By carefully choosing the zero-bias constraint, the resulting estimator of the low dimensional parameter is shown to admit an asymptotically normal limit attaining the Cram'{e}r-Rao lower bound in a semiparametric sense. We propose a tuning-free iterative algorithm for implementing the CLasso. We show that when the algorithm is initialized at the Lasso estimator, the de-sparsified estimator proposed in van de Geer et al. [\emph{Ann. Statist.} {\bf 42} (2014) 1166–1202] is asymptotically equivalent to the first iterate of the algorithm. We analyse the asymptotic properties of the CLasso estimator and show the globally linear convergence of the algorithm. We also demonstrate encouraging empirical performance of the CLasso through numerical studies. |
| Tasks | |
| Published | 2017-04-17 |
| URL | http://arxiv.org/abs/1704.05098v1 |
| http://arxiv.org/pdf/1704.05098v1.pdf | |
| PWC | https://paperswithcode.com/paper/statistical-inference-for-high-dimensional |
| Repo | |
| Framework | |
Deep Ordinal Ranking for Multi-Category Diagnosis of Alzheimer’s Disease using Hippocampal MRI data
| Title | Deep Ordinal Ranking for Multi-Category Diagnosis of Alzheimer’s Disease using Hippocampal MRI data |
| Authors | Hongming Li, Mohamad Habes, Yong Fan |
| Abstract | Increasing effort in brain image analysis has been dedicated to early diagnosis of Alzheimer’s disease (AD) based on neuroimaging data. Most existing studies have been focusing on binary classification problems, e.g., distinguishing AD patients from normal control (NC) elderly or mild cognitive impairment (MCI) individuals from NC elderly. However, identifying individuals with AD and MCI, especially MCI individuals who will convert to AD (progressive MCI, pMCI), in a single setting, is needed to achieve the goal of early diagnosis of AD. In this paper, we propose a deep ordinal ranking model for distinguishing NC, stable MCI (sMCI), pMCI, and AD at an individual subject level, taking into account the inherent ordinal severity of brain degeneration caused by normal aging, MCI, and AD, rather than formulating the classification as a multi-category classification problem. The proposed deep ordinal ranking model focuses on the hippocampal morphology of individuals and learns informative and discriminative features automatically. Experiment results based on a large cohort of individuals from the Alzheimer’s Disease Neuroimaging Initiative (ADNI) indicate that the proposed method can achieve better performance than traditional multi-category classification techniques using shape and radiomics features from structural magnetic resonance imaging (MRI) data. |
| Tasks | |
| Published | 2017-09-05 |
| URL | http://arxiv.org/abs/1709.01599v2 |
| http://arxiv.org/pdf/1709.01599v2.pdf | |
| PWC | https://paperswithcode.com/paper/deep-ordinal-ranking-for-multi-category |
| Repo | |
| Framework | |
Minimum Energy Quantized Neural Networks
| Title | Minimum Energy Quantized Neural Networks |
| Authors | Bert Moons, Koen Goetschalckx, Nick Van Berckelaer, Marian Verhelst |
| Abstract | This work targets the automated minimum-energy optimization of Quantized Neural Networks (QNNs) - networks using low precision weights and activations. These networks are trained from scratch at an arbitrary fixed point precision. At iso-accuracy, QNNs using fewer bits require deeper and wider network architectures than networks using higher precision operators, while they require less complex arithmetic and less bits per weights. This fundamental trade-off is analyzed and quantified to find the minimum energy QNN for any benchmark and hence optimize energy-efficiency. To this end, the energy consumption of inference is modeled for a generic hardware platform. This allows drawing several conclusions across different benchmarks. First, energy consumption varies orders of magnitude at iso-accuracy depending on the number of bits used in the QNN. Second, in a typical system, BinaryNets or int4 implementations lead to the minimum energy solution, outperforming int8 networks up to 2-10x at iso-accuracy. All code used for QNN training is available from https://github.com/BertMoons. |
| Tasks | |
| Published | 2017-11-01 |
| URL | http://arxiv.org/abs/1711.00215v2 |
| http://arxiv.org/pdf/1711.00215v2.pdf | |
| PWC | https://paperswithcode.com/paper/minimum-energy-quantized-neural-networks |
| Repo | |
| Framework | |
A description length approach to determining the number of k-means clusters
| Title | A description length approach to determining the number of k-means clusters |
| Authors | Hiromitsu Mizutani, Ryota Kanai |
| Abstract | We present an asymptotic criterion to determine the optimal number of clusters in k-means. We consider k-means as data compression, and propose to adopt the number of clusters that minimizes the estimated description length after compression. Here we report two types of compression ratio based on two ways to quantify the description length of data after compression. This approach further offers a way to evaluate whether clusters obtained with k-means have a hierarchical structure by examining whether multi-stage compression can further reduce the description length. We applied our criteria to determine the number of clusters to synthetic data and empirical neuroimaging data to observe the behavior of the criteria across different types of data set and suitability of the two types of criteria for different datasets. We found that our method can offer reasonable clustering results that are useful for dimension reduction. While our numerical results revealed dependency of our criteria on the various aspects of dataset such as the dimensionality, the description length approach proposed here provides a useful guidance to determine the number of clusters in a principled manner when underlying properties of the data are unknown and only inferred from observation of data. |
| Tasks | Dimensionality Reduction |
| Published | 2017-02-28 |
| URL | http://arxiv.org/abs/1703.00039v1 |
| http://arxiv.org/pdf/1703.00039v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-description-length-approach-to-determining |
| Repo | |
| Framework | |
A Note on Nesting in Dyadic Deontic Logic
| Title | A Note on Nesting in Dyadic Deontic Logic |
| Authors | Agneau Belanyek, Davide Grossi, Wiebe van der Hoek |
| Abstract | The paper reports on some results concerning Aqvist’s dyadic logic known as system G, which is one of the most influential logics for reasoning with dyadic obligations (“it ought to be the case that … if it is the case that …"). Although this logic has been known in the literature for a while, many of its properties still await in-depth consideration. In this short paper we show: that any formula in system G including nested modal operators is equivalent to some formula with no nesting; that the universal modality introduced by Aqvist in the first presentation of the system is definable in terms of the deontic modality. |
| Tasks | |
| Published | 2017-10-10 |
| URL | http://arxiv.org/abs/1710.03481v1 |
| http://arxiv.org/pdf/1710.03481v1.pdf | |
| PWC | https://paperswithcode.com/paper/a-note-on-nesting-in-dyadic-deontic-logic |
| Repo | |
| Framework | |
Partially Occluded Leaf Recognition via Subgraph Matching and Energy Optimization
| Title | Partially Occluded Leaf Recognition via Subgraph Matching and Energy Optimization |
| Authors | Ayan Chaudhury, John L. Barron |
| Abstract | We present an approach to match partially occluded plant leaves with databases of full plant leaves. Although contour based 2D shape matching has been studied extensively in the last couple of decades, matching occluded leaves with full leaf databases is an open and little worked on problem. Classifying occluded plant leaves is even more challenging than full leaf matching because of large variations and complexity of leaf structures. Matching an occluded contour with all the full contours in a database is an NP-hard problem [Su et al. ICCV2015], so our algorithm is necessarily suboptimal. |
| Tasks | |
| Published | 2017-04-28 |
| URL | http://arxiv.org/abs/1704.08778v2 |
| http://arxiv.org/pdf/1704.08778v2.pdf | |
| PWC | https://paperswithcode.com/paper/partially-occluded-leaf-recognition-via |
| Repo | |
| Framework | |
Tangent Cones to TT Varieties
| Title | Tangent Cones to TT Varieties |
| Authors | Benjamin Kutschan |
| Abstract | As already done for the matrix case for example in [Joe Harris, Algebraic Geometry - A first course, p.256] we give a parametrization of the Bouligand tangent cone of the variety of tensors of bounded TT rank. We discuss how the proof generalizes to any binary hierarchical format. The parametrization can be rewritten as an orthogonal sum of TT tensors. Its retraction onto the variety is particularly easy to compose. We also give an implicit description of the tangent cone as the solution of a system of polynomial equations. |
| Tasks | |
| Published | 2017-05-29 |
| URL | http://arxiv.org/abs/1705.10152v1 |
| http://arxiv.org/pdf/1705.10152v1.pdf | |
| PWC | https://paperswithcode.com/paper/tangent-cones-to-tt-varieties |
| Repo | |
| Framework | |
Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe
| Title | Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfe |
| Authors | Quentin Berthet, Vianney Perchet |
| Abstract | We consider the problem of bandit optimization, inspired by stochastic optimization and online learning problems with bandit feedback. In this problem, the objective is to minimize a global loss function of all the actions, not necessarily a cumulative loss. This framework allows us to study a very general class of problems, with applications in statistics, machine learning, and other fields. To solve this problem, we analyze the Upper-Confidence Frank-Wolfe algorithm, inspired by techniques for bandits and convex optimization. We give theoretical guarantees for the performance of this algorithm over various classes of functions, and discuss the optimality of these results. |
| Tasks | Stochastic Optimization |
| Published | 2017-02-22 |
| URL | http://arxiv.org/abs/1702.06917v2 |
| http://arxiv.org/pdf/1702.06917v2.pdf | |
| PWC | https://paperswithcode.com/paper/fast-rates-for-bandit-optimization-with-upper |
| Repo | |
| Framework | |
First Draft on the xInf Model for Universal Physical Computation and Reverse Engineering of Natural Intelligence
| Title | First Draft on the xInf Model for Universal Physical Computation and Reverse Engineering of Natural Intelligence |
| Authors | Hongbo Jia |
| Abstract | Turing Machines are universal computing machines in theory. It has been a long debate whether Turing Machines can simulate the consciousness mind behaviors in the materialistic universe. Three different hypotheses come out of such debate, in short:(A) Can; (B) Cannot; (C) Super-Turing machines can. Because Turing Machines or other kinds of theoretical computing models are abstract objects while behaviors are real observables, this debate involves at least three distinct fields of science and technology: physics, computer engineering, and experimental neuroscience. However, the languages used in these different fields are highly heterogeneous and not easily interpretable for each other, making it very difficult to reach partial agreements regarding this debate, Therefore, the main goal of this manuscript is to establish a proper language that can translate among those different fields. First, I propose a theoretical model for analyzing how theoretical computing machines would physically run in physical time. This model, termed as the xInf, is at first place Turing-complete in theory, and depending on the properties of physical time, it can be either Turing-equivalent or Super-Turing in the physical universe. The xInf Model is demonstrated to be a suitable universal language to translate among physics, computer engineering, and neuroscience. Finally, I propose a conjecture that there exists a Minimal Complete Set of rules in the xInf Model that enables the construction of a physical machine using inorganic materials that can pass the Turing Test in physical time. I cannot demonstrate whether such a conjecture to be testified or falsified on paper using finite-order logic, my only solution is physical time itself, i.e. an evolutionary competition will eventually tell the conclusion. |
| Tasks | |
| Published | 2017-12-26 |
| URL | http://arxiv.org/abs/1712.10280v1 |
| http://arxiv.org/pdf/1712.10280v1.pdf | |
| PWC | https://paperswithcode.com/paper/first-draft-on-the-xinf-model-for-universal |
| Repo | |
| Framework | |
Avoiding Communication in Proximal Methods for Convex Optimization Problems
| Title | Avoiding Communication in Proximal Methods for Convex Optimization Problems |
| Authors | Saeed Soori, Aditya Devarakonda, James Demmel, Mert Gurbuzbalaban, Maryam Mehri Dehnavi |
| Abstract | The fast iterative soft thresholding algorithm (FISTA) is used to solve convex regularized optimization problems in machine learning. Distributed implementations of the algorithm have become popular since they enable the analysis of large datasets. However, existing formulations of FISTA communicate data at every iteration which reduces its performance on modern distributed architectures. The communication costs of FISTA, including bandwidth and latency costs, is closely tied to the mathematical formulation of the algorithm. This work reformulates FISTA to communicate data at every k iterations and reduce data communication when operating on large data sets. We formulate the algorithm for two different optimization methods on the Lasso problem and show that the latency cost is reduced by a factor of k while bandwidth and floating-point operation costs remain the same. The convergence rates and stability properties of the reformulated algorithms are similar to the standard formulations. The performance of communication-avoiding FISTA and Proximal Newton methods is evaluated on 1 to 1024 nodes for multiple benchmarks and demonstrate average speedups of 3-10x with scaling properties that outperform the classical algorithms. |
| Tasks | |
| Published | 2017-10-24 |
| URL | http://arxiv.org/abs/1710.08883v1 |
| http://arxiv.org/pdf/1710.08883v1.pdf | |
| PWC | https://paperswithcode.com/paper/avoiding-communication-in-proximal-methods |
| Repo | |
| Framework | |
Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation
| Title | Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation |
| Authors | Matthias Hein, Maksym Andriushchenko |
| Abstract | Recent work has shown that state-of-the-art classifiers are quite brittle, in the sense that a small adversarial change of an originally with high confidence correctly classified input leads to a wrong classification again with high confidence. This raises concerns that such classifiers are vulnerable to attacks and calls into question their usage in safety-critical systems. We show in this paper for the first time formal guarantees on the robustness of a classifier by giving instance-specific lower bounds on the norm of the input manipulation required to change the classifier decision. Based on this analysis we propose the Cross-Lipschitz regularization functional. We show that using this form of regularization in kernel methods resp. neural networks improves the robustness of the classifier without any loss in prediction performance. |
| Tasks | |
| Published | 2017-05-23 |
| URL | http://arxiv.org/abs/1705.08475v2 |
| http://arxiv.org/pdf/1705.08475v2.pdf | |
| PWC | https://paperswithcode.com/paper/formal-guarantees-on-the-robustness-of-a |
| Repo | |
| Framework | |
Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: II Wireless Networks with Interference
| Title | Throughput Optimal Decentralized Scheduling of Multi-Hop Networks with End-to-End Deadline Constraints: II Wireless Networks with Interference |
| Authors | Rahul Singh, P. R. Kumar, Eytan Modiano |
| Abstract | Consider a multihop wireless network serving multiple flows in which wireless link interference constraints are described by a link interference graph. For such a network, we design routing-scheduling policies that maximize the end-to-end timely throughput of the network. Timely throughput of a flow $f$ is defined as the average rate at which packets of flow $f$ reach their destination node $d_f$ within their deadline. Our policy has several surprising characteristics. Firstly, we show that the optimal routing-scheduling decision for an individual packet that is present at a wireless node $i\in V$ is solely a function of its location, and “age”. Thus, a wireless node $i$ does not require the knowledge of the “global” network state in order to maximize the timely throughput. We notice that in comparison, under the backpressure routing policy, a node $i$ requires only the knowledge of its neighbours queue lengths in order to guarantee maximal stability, and hence is decentralized. The key difference arises due to the fact that in our set-up the packets loose their utility once their “age” has crossed their deadline, thus making the task of optimizing timely throughput much more challenging than that of ensuring network stability. Of course, due to this key difference, the decision process involved in maximizing the timely throughput is also much more complex than that involved in ensuring network-wide queue stabilization. In view of this, our results are somewhat surprising. |
| Tasks | |
| Published | 2017-09-06 |
| URL | http://arxiv.org/abs/1709.01672v2 |
| http://arxiv.org/pdf/1709.01672v2.pdf | |
| PWC | https://paperswithcode.com/paper/throughput-optimal-decentralized-scheduling |
| Repo | |
| Framework | |
Deep-LK for Efficient Adaptive Object Tracking
| Title | Deep-LK for Efficient Adaptive Object Tracking |
| Authors | Chaoyang Wang, Hamed Kiani Galoogahi, Chen-Hsuan Lin, Simon Lucey |
| Abstract | In this paper we present a new approach for efficient regression based object tracking which we refer to as Deep- LK. Our approach is closely related to the Generic Object Tracking Using Regression Networks (GOTURN) framework of Held et al. We make the following contributions. First, we demonstrate that there is a theoretical relationship between siamese regression networks like GOTURN and the classical Inverse-Compositional Lucas & Kanade (IC-LK) algorithm. Further, we demonstrate that unlike GOTURN IC-LK adapts its regressor to the appearance of the currently tracked frame. We argue that this missing property in GOTURN can be attributed to its poor performance on unseen objects and/or viewpoints. Second, we propose a novel framework for object tracking - which we refer to as Deep-LK - that is inspired by the IC-LK framework. Finally, we show impressive results demonstrating that Deep-LK substantially outperforms GOTURN. Additionally, we demonstrate comparable tracking performance to current state of the art deep-trackers whilst being an order of magnitude (i.e. 100 FPS) computationally efficient. |
| Tasks | Object Tracking |
| Published | 2017-05-19 |
| URL | http://arxiv.org/abs/1705.06839v2 |
| http://arxiv.org/pdf/1705.06839v2.pdf | |
| PWC | https://paperswithcode.com/paper/deep-lk-for-efficient-adaptive-object |
| Repo | |
| Framework | |
Multi-Advisor Reinforcement Learning
| Title | Multi-Advisor Reinforcement Learning |
| Authors | Romain Laroche, Mehdi Fatemi, Joshua Romoff, Harm van Seijen |
| Abstract | We consider tackling a single-agent RL problem by distributing it to $n$ learners. These learners, called advisors, endeavour to solve the problem from a different focus. Their advice, taking the form of action values, is then communicated to an aggregator, which is in control of the system. We show that the local planning method for the advisors is critical and that none of the ones found in the literature is flawless: the egocentric planning overestimates values of states where the other advisors disagree, and the agnostic planning is inefficient around danger zones. We introduce a novel approach called empathic and discuss its theoretical aspects. We empirically examine and validate our theoretical findings on a fruit collection task. |
| Tasks | |
| Published | 2017-04-03 |
| URL | http://arxiv.org/abs/1704.00756v2 |
| http://arxiv.org/pdf/1704.00756v2.pdf | |
| PWC | https://paperswithcode.com/paper/multi-advisor-reinforcement-learning |
| Repo | |
| Framework | |
