Paper Group ANR 444
Stability and Convergence Trade-off of Iterative Optimization Algorithms. Frame-based Sparse Analysis and Synthesis Signal Representations and Parseval K-SVD. Group induced graphical lasso allows for discovery of molecular pathways-pathways interactions. Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization. Erasure coding for dis …
Stability and Convergence Trade-off of Iterative Optimization Algorithms
| Title | Stability and Convergence Trade-off of Iterative Optimization Algorithms |
| Authors | Yuansi Chen, Chi Jin, Bin Yu |
| Abstract | The overall performance or expected excess risk of an iterative machine learning algorithm can be decomposed into training error and generalization error. While the former is controlled by its convergence analysis, the latter can be tightly handled by algorithmic stability. The machine learning community has a rich history investigating convergence and stability separately. However, the question about the trade-off between these two quantities remains open. In this paper, we show that for any iterative algorithm at any iteration, the overall performance is lower bounded by the minimax statistical error over an appropriately chosen loss function class. This implies an important trade-off between convergence and stability of the algorithm – a faster converging algorithm has to be less stable, and vice versa. As a direct consequence of this fundamental tradeoff, new convergence lower bounds can be derived for classes of algorithms constrained with different stability bounds. In particular, when the loss function is convex (or strongly convex) and smooth, we discuss the stability upper bounds of gradient descent (GD) and stochastic gradient descent and their variants with decreasing step sizes. For Nesterov’s accelerated gradient descent (NAG) and heavy ball method (HB), we provide stability upper bounds for the quadratic loss function. Applying existing stability upper bounds for the gradient methods in our trade-off framework, we obtain lower bounds matching the well-established convergence upper bounds up to constants for these algorithms and conjecture similar lower bounds for NAG and HB. Finally, we numerically demonstrate the tightness of our stability bounds in terms of exponents in the rate and also illustrate via a simulated logistic regression problem that our stability bounds reflect the generalization errors better than the simple uniform convergence bounds for GD and NAG. |
| Tasks | |
| Published | 2018-04-04 |
| URL | http://arxiv.org/abs/1804.01619v1 |
| http://arxiv.org/pdf/1804.01619v1.pdf | |
| PWC | https://paperswithcode.com/paper/stability-and-convergence-trade-off-of |
| Repo | |
| Framework | |
Frame-based Sparse Analysis and Synthesis Signal Representations and Parseval K-SVD
| Title | Frame-based Sparse Analysis and Synthesis Signal Representations and Parseval K-SVD |
| Authors | Wen-Liang Hwang, Ping-Tzan Huang, Tai-Lang Jong |
| Abstract | Frames are the foundation of the linear operators used in the decomposition and reconstruction of signals, such as the discrete Fourier transform, Gabor, wavelets, and curvelet transforms. The emergence of sparse representation models has shifted of the emphasis in frame theory toward sparse l1-minimization problems. In this paper, we apply frame theory to the sparse representation of signals in which a synthesis dictionary is used for a frame and an analysis dictionary is used for a dual frame. We sought to formulate a novel dual frame design in which the sparse vector obtained through the decomposition of any signal is also the sparse solution representing signals based on a reconstruction frame. Our findings demonstrate that this type of dual frame cannot be constructed for over-complete frames, thereby precluding the use of any linear analysis operator in driving the sparse synthesis coefficient for signal representation. Nonetheless, the best approximation to the sparse synthesis solution can be derived from the analysis coefficient using the canonical dual frame. In this study, we developed a novel dictionary learning algorithm (called Parseval K-SVD) to learn a tight-frame dictionary. We then leveraged the analysis and synthesis perspectives of signal representation with frames to derive optimization formulations for problems pertaining to image recovery. Our preliminary, results demonstrate that the images recovered using this approach are correlated to the frame bounds of dictionaries, thereby demonstrating the importance of using different dictionaries for different applications. |
| Tasks | Dictionary Learning |
| Published | 2018-01-06 |
| URL | http://arxiv.org/abs/1801.01959v1 |
| http://arxiv.org/pdf/1801.01959v1.pdf | |
| PWC | https://paperswithcode.com/paper/frame-based-sparse-analysis-and-synthesis |
| Repo | |
| Framework | |
Group induced graphical lasso allows for discovery of molecular pathways-pathways interactions
| Title | Group induced graphical lasso allows for discovery of molecular pathways-pathways interactions |
| Authors | Veronica Tozzo, Federico Tomasi, Margherita Squillario, Annalisa Barla |
| Abstract | Complex systems may contain heterogeneous types of variables that interact in a multi-level and multi-scale manner. In this context, high-level layers may considered as groups of variables interacting in lower-level layers. This is particularly true in biology, where, for example, genes are grouped in pathways and two types of interactions are present: pathway-pathway interactions and gene-gene interactions. However, from data it is only possible to measure the expression of genes while it is impossible to directly measure the activity of pathways. Nevertheless, the knowledge on the inter-dependence between the groups and the variables allows for a multi-layer network inference, on both observed variables and groups, even if no direct information on the latter is present in the data (hence groups are considered as latent). In this paper, we propose an extension of the latent graphical lasso method that leverages on the knowledge of the inter-links between the hidden (groups) and observed layers. The method exploits the knowledge of group structure that influence the behaviour of observed variables to retrieve a two layers network. Its efficacy was tested on synthetic data to check its ability in retrieving the network structure compared to the ground truth. We present a case study on Neuroblastoma, which shows how our multi-level inference is relevant in real contexts to infer biologically meaningful connections. |
| Tasks | |
| Published | 2018-11-21 |
| URL | http://arxiv.org/abs/1811.09673v1 |
| http://arxiv.org/pdf/1811.09673v1.pdf | |
| PWC | https://paperswithcode.com/paper/group-induced-graphical-lasso-allows-for |
| Repo | |
| Framework | |
Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
| Title | Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization |
| Authors | Wenjie Huang |
| Abstract | In this paper, we consider the problem of minimizing the average of a large number of nonsmooth and convex functions. Such problems often arise in typical machine learning problems as empirical risk minimization, but are computationally very challenging. We develop and analyze a new algorithm that achieves robust linear convergence rate, and both its time complexity and gradient complexity are superior than state-of-art nonsmooth algorithms and subgradient-based schemes. Besides, our algorithm works without any extra error bound conditions on the objective function as well as the common strongly-convex condition. We show that our algorithm has wide applications in optimization and machine learning problems, and demonstrate experimentally that it performs well on a large-scale ranking problem. |
| Tasks | |
| Published | 2018-05-11 |
| URL | http://arxiv.org/abs/1805.05189v1 |
| http://arxiv.org/pdf/1805.05189v1.pdf | |
| PWC | https://paperswithcode.com/paper/randomized-smoothing-svrg-for-large-scale |
| Repo | |
| Framework | |
Erasure coding for distributed matrix multiplication for matrices with bounded entries
| Title | Erasure coding for distributed matrix multiplication for matrices with bounded entries |
| Authors | Li Tang, Konstantinos Konstantinidis, Aditya Ramamoorthy |
| Abstract | Distributed matrix multiplication is widely used in several scientific domains. It is well recognized that computation times on distributed clusters are often dominated by the slowest workers (called stragglers). Recent work has demonstrated that straggler mitigation can be viewed as a problem of designing erasure codes. For matrices $\mathbf A$ and $\mathbf B$, the technique essentially maps the computation of $\mathbf A^T \mathbf B$ into the multiplication of smaller (coded) submatrices. The stragglers are treated as erasures in this process. The computation can be completed as long as a certain number of workers (called the recovery threshold) complete their assigned tasks. We present a novel coding strategy for this problem when the absolute values of the matrix entries are sufficiently small. We demonstrate a tradeoff between the assumed absolute value bounds on the matrix entries and the recovery threshold. At one extreme, we are optimal with respect to the recovery threshold and on the other extreme, we match the threshold of prior work. Experimental results on cloud-based clusters validate the benefits of our method. |
| Tasks | |
| Published | 2018-11-06 |
| URL | http://arxiv.org/abs/1811.02144v2 |
| http://arxiv.org/pdf/1811.02144v2.pdf | |
| PWC | https://paperswithcode.com/paper/erasure-coding-for-distributed-matrix |
| Repo | |
| Framework | |
Learning Dense Stereo Matching for Digital Surface Models from Satellite Imagery
| Title | Learning Dense Stereo Matching for Digital Surface Models from Satellite Imagery |
| Authors | Wayne Treible, Scott Sorensen, Andrew D. Gilliam, Chandra Kambhamettu, Joseph L. Mundy |
| Abstract | Digital Surface Model generation from satellite imagery is a difficult task that has been largely overlooked by the deep learning community. Stereo reconstruction techniques developed for terrestrial systems including self driving cars do not translate well to satellite imagery where image pairs vary considerably. In this work we present neural network tailored for Digital Surface Model generation, a ground truthing and training scheme which maximizes available hardware, and we present a comparison to existing methods. The resulting models are smooth, preserve boundaries, and enable further processing. This represents one of the first attempts at leveraging deep learning in this domain. |
| Tasks | Self-Driving Cars, Stereo Matching, Stereo Matching Hand |
| Published | 2018-11-08 |
| URL | http://arxiv.org/abs/1811.03535v2 |
| http://arxiv.org/pdf/1811.03535v2.pdf | |
| PWC | https://paperswithcode.com/paper/learning-dense-stereo-matching-for-digital |
| Repo | |
| Framework | |
Keypoint Based Weakly Supervised Human Parsing
| Title | Keypoint Based Weakly Supervised Human Parsing |
| Authors | Zhonghua Wu, Guosheng Lin, Jianfei Cai |
| Abstract | Fully convolutional networks (FCN) have achieved great success in human parsing in recent years. In conventional human parsing tasks, pixel-level labeling is required for guiding the training, which usually involves enormous human labeling efforts. To ease the labeling efforts, we propose a novel weakly supervised human parsing method which only requires simple object keypoint annotations for learning. We develop an iterative learning method to generate pseudo part segmentation masks from keypoint labels. With these pseudo masks, we train an FCN network to output pixel-level human parsing predictions. Furthermore, we develop a correlation network to perform joint prediction of part and object segmentation masks and improve the segmentation performance. The experiment results show that our weakly supervised method is able to achieve very competitive human parsing results. Despite our method only uses simple keypoint annotations for learning, we are able to achieve comparable performance with fully supervised methods which use the expensive pixel-level annotations. |
| Tasks | Human Parsing, Semantic Segmentation |
| Published | 2018-09-14 |
| URL | http://arxiv.org/abs/1809.05285v1 |
| http://arxiv.org/pdf/1809.05285v1.pdf | |
| PWC | https://paperswithcode.com/paper/keypoint-based-weakly-supervised-human |
| Repo | |
| Framework | |
Verification of Markov Decision Processes with Risk-Sensitive Measures
| Title | Verification of Markov Decision Processes with Risk-Sensitive Measures |
| Authors | Murat Cubuktepe, Ufuk Topcu |
| Abstract | We develop a method for computing policies in Markov decision processes with risk-sensitive measures subject to temporal logic constraints. Specifically, we use a particular risk-sensitive measure from cumulative prospect theory, which has been previously adopted in psychology and economics. The nonlinear transformation of the probabilities and utility functions yields a nonlinear programming problem, which makes computation of optimal policies typically challenging. We show that this nonlinear weighting function can be accurately approximated by the difference of two convex functions. This observation enables efficient policy computation using convex-concave programming. We demonstrate the effectiveness of the approach on several scenarios. |
| Tasks | |
| Published | 2018-02-28 |
| URL | http://arxiv.org/abs/1803.00091v1 |
| http://arxiv.org/pdf/1803.00091v1.pdf | |
| PWC | https://paperswithcode.com/paper/verification-of-markov-decision-processes |
| Repo | |
| Framework | |
Evaluating GANs via Duality
| Title | Evaluating GANs via Duality |
| Authors | Paulina Grnarova, Kfir Y Levy, Aurelien Lucchi, Nathanael Perraudin, Thomas Hofmann, Andreas Krause |
| Abstract | Generative Adversarial Networks (GANs) have shown great results in accurately modeling complex distributions, but their training is known to be difficult due to instabilities caused by a challenging minimax optimization problem. This is especially troublesome given the lack of an evaluation metric that can reliably detect non-convergent behaviors. We leverage the notion of duality gap from game theory in order to propose a novel convergence metric for GANs that has low computational cost. We verify the validity of the proposed metric for various test scenarios commonly used in the literature. |
| Tasks | |
| Published | 2018-11-13 |
| URL | http://arxiv.org/abs/1811.05512v1 |
| http://arxiv.org/pdf/1811.05512v1.pdf | |
| PWC | https://paperswithcode.com/paper/evaluating-gans-via-duality |
| Repo | |
| Framework | |
Explainable artificial intelligence (XAI), the goodness criteria and the grasp-ability test
| Title | Explainable artificial intelligence (XAI), the goodness criteria and the grasp-ability test |
| Authors | Tae Wam Kim |
| Abstract | This paper introduces the “grasp-ability test” as a “goodness” criteria by which to compare which explanation is more or less meaningful than others for users to understand the automated algorithmic data processing. |
| Tasks | |
| Published | 2018-10-22 |
| URL | http://arxiv.org/abs/1810.09598v1 |
| http://arxiv.org/pdf/1810.09598v1.pdf | |
| PWC | https://paperswithcode.com/paper/explainable-artificial-intelligence-xai-the |
| Repo | |
| Framework | |
FeatureAnalytics: An approach to derive relevant attributes for analyzing Android Malware
| Title | FeatureAnalytics: An approach to derive relevant attributes for analyzing Android Malware |
| Authors | Deepa K, Radhamani G, Vinod P, Mohammad Shojafar, Neeraj Kumar, Mauro Conti |
| Abstract | Ever increasing number of Android malware, has always been a concern for cybersecurity professionals. Even though plenty of anti-malware solutions exist, a rational and pragmatic approach for the same is rare and has to be inspected further. In this paper, we propose a novel two-set feature selection approach based on Rough Set and Statistical Test named as RSST to extract relevant system calls. To address the problem of higher dimensional attribute set, we derived suboptimal system call space by applying the proposed feature selection method to maximize the separability between malware and benign samples. Comprehensive experiments conducted on a dataset consisting of 3500 samples with 30 RSST derived essential system calls resulted in an accuracy of 99.9%, Area Under Curve (AUC) of 1.0, with 1% False Positive Rate (FPR). However, other feature selectors (Information Gain, CFsSubsetEval, ChiSquare, FreqSel and Symmetric Uncertainty) used in the domain of malware analysis resulted in the accuracy of 95.5% with 8.5% FPR. Besides, empirical analysis of RSST derived system calls outperform other attributes such as permissions, opcodes, API, methods, call graphs, Droidbox attributes and network traces. |
| Tasks | Feature Selection |
| Published | 2018-09-17 |
| URL | https://arxiv.org/abs/1809.09035v1 |
| https://arxiv.org/pdf/1809.09035v1.pdf | |
| PWC | https://paperswithcode.com/paper/featureanalytics-an-approach-to-derive |
| Repo | |
| Framework | |
Combining Difficulty Ranking with Multi-Armed Bandits to Sequence Educational Content
| Title | Combining Difficulty Ranking with Multi-Armed Bandits to Sequence Educational Content |
| Authors | Avi Segal, Yossi Ben David, Joseph Jay Williams, Kobi Gal, Yaar Shalom |
| Abstract | As e-learning systems become more prevalent, there is a growing need for them to accommodate individual differences between students. This paper addresses the problem of how to personalize educational content to students in order to maximize their learning gains over time. We present a new computational approach to this problem called MAPLE (Multi-Armed Bandits based Personalization for Learning Environments) that combines difficulty ranking with multi-armed bandits. Given a set of target questions MAPLE estimates the expected learning gains for each question and uses an exploration-exploitation strategy to choose the next question to pose to the student. It maintains a personalized ranking over the difficulties of question in the target set which is used in two ways: First, to obtain initial estimates over the learning gains for the set of questions. Second, to update the estimates over time based on the students responses. We show in simulations that MAPLE was able to improve students’ learning gains compared to approaches that sequence questions in increasing level of difficulty, or rely on content experts. When implemented in a live e-learning system in the wild, MAPLE showed promising results. This work demonstrates the efficacy of using stochastic approaches to the sequencing problem when augmented with information about question difficulty. |
| Tasks | Multi-Armed Bandits |
| Published | 2018-04-14 |
| URL | http://arxiv.org/abs/1804.05212v1 |
| http://arxiv.org/pdf/1804.05212v1.pdf | |
| PWC | https://paperswithcode.com/paper/combining-difficulty-ranking-with-multi-armed |
| Repo | |
| Framework | |
A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters
| Title | A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters |
| Authors | Lei Yang, Jia Li, Defeng Sun, Kim-Chuan Toh |
| Abstract | In this paper, we consider the problem of computing a Wasserstein barycenter for a set of discrete probability distributions with finite supports, which finds many applications in areas such as statistics, machine learning and image processing. When the support points of the barycenter are pre-specified, this problem can be modeled as a linear program (LP) whose problem size can be extremely large. To handle this large-scale LP, we analyse the structure of its dual problem, which is conceivably more tractable and can be reformulated as a well-structured convex problem with 3 kinds of block variables and a coupling linear equality constraint. We then adapt a symmetric Gauss-Seidel based alternating direction method of multipliers (sGS-ADMM) to solve the resulting dual problem and establish its global convergence and global linear convergence rate. As a critical component for efficient computation, we also show how all the subproblems involved can be solved exactly and efficiently. This makes our method suitable for computing a Wasserstein barycenter on a large dataset, without introducing an entropy regularization term as is commonly practiced. In addition, our sGS-ADMM can be used as a subroutine in an alternating minimization method to compute a barycenter when its support points are not pre-specified. Numerical results on synthetic datasets and image datasets demonstrate that our method is highly competitive for solving large-scale problems, in comparison to two existing representative methods and the commercial software Gurobi. |
| Tasks | |
| Published | 2018-09-12 |
| URL | https://arxiv.org/abs/1809.04249v3 |
| https://arxiv.org/pdf/1809.04249v3.pdf | |
| PWC | https://paperswithcode.com/paper/a-fast-globally-linearly-convergent-algorithm |
| Repo | |
| Framework | |
No Blind Spots: Full-Surround Multi-Object Tracking for Autonomous Vehicles using Cameras & LiDARs
| Title | No Blind Spots: Full-Surround Multi-Object Tracking for Autonomous Vehicles using Cameras & LiDARs |
| Authors | Akshay Rangesh, Mohan M. Trivedi |
| Abstract | Online multi-object tracking (MOT) is extremely important for high-level spatial reasoning and path planning for autonomous and highly-automated vehicles. In this paper, we present a modular framework for tracking multiple objects (vehicles), capable of accepting object proposals from different sensor modalities (vision and range) and a variable number of sensors, to produce continuous object tracks. This work is a generalization of the MDP framework for MOT, with some key extensions - First, we track objects across multiple cameras and across different sensor modalities. This is done by fusing object proposals across sensors accurately and efficiently. Second, the objects of interest (targets) are tracked directly in the real world. This is a departure from traditional techniques where objects are simply tracked in the image plane. Doing so allows the tracks to be readily used by an autonomous agent for navigation and related tasks. To verify the effectiveness of our approach, we test it on real world highway data collected from a heavily sensorized testbed capable of capturing full-surround information. We demonstrate that our framework is well-suited to track objects through entire maneuvers around the ego-vehicle, some of which take more than a few minutes to complete. We also leverage the modularity of our approach by comparing the effects of including/excluding different sensors, changing the total number of sensors, and the quality of object proposals on the final tracking result. |
| Tasks | Autonomous Vehicles, Multi-Object Tracking, Object Tracking, Online Multi-Object Tracking |
| Published | 2018-02-23 |
| URL | http://arxiv.org/abs/1802.08755v4 |
| http://arxiv.org/pdf/1802.08755v4.pdf | |
| PWC | https://paperswithcode.com/paper/no-blind-spots-full-surround-multi-object |
| Repo | |
| Framework | |
Sentence-Level Sentiment Analysis of Financial News Using Distributed Text Representations and Multi-Instance Learning
| Title | Sentence-Level Sentiment Analysis of Financial News Using Distributed Text Representations and Multi-Instance Learning |
| Authors | Bernhard Lutz, Nicolas Pröllochs, Dirk Neumann |
| Abstract | Researchers and financial professionals require robust computerized tools that allow users to rapidly operationalize and assess the semantic textual content in financial news. However, existing methods commonly work at the document-level while deeper insights into the actual structure and the sentiment of individual sentences remain blurred. As a result, investors are required to apply the utmost attention and detailed, domain-specific knowledge in order to assess the information on a fine-grained basis. To facilitate this manual process, this paper proposes the use of distributed text representations and multi-instance learning to transfer information from the document-level to the sentence-level. Compared to alternative approaches, this method features superior predictive performance while preserving context and interpretability. Our analysis of a manually-labeled dataset yields a predictive accuracy of up to 69.90%, exceeding the performance of alternative approaches by at least 3.80 percentage points. Accordingly, this study not only benefits investors with regard to their financial decision-making, but also helps companies to communicate their messages as intended. |
| Tasks | Decision Making, Sentiment Analysis |
| Published | 2018-12-31 |
| URL | http://arxiv.org/abs/1901.00400v1 |
| http://arxiv.org/pdf/1901.00400v1.pdf | |
| PWC | https://paperswithcode.com/paper/sentence-level-sentiment-analysis-of |
| Repo | |
| Framework | |
