-
LibProf: A Python Profiler for Improving Cold Start Performance in Serverless Applications
Authors:
Syed Salauddin Mohammad Tariq,
Ali Al Zein,
Soumya Sripad Vaidya,
Arati Khanolkar,
Probir Roy
Abstract:
Serverless computing abstracts away server management, enabling automatic scaling and efficient resource utilization. However, cold-start latency remains a significant challenge, affecting end-to-end performance. Our preliminary study reveals that inefficient library initialization and usage are major contributors to this latency in Python-based serverless applications. We introduce LibProf, a Pyt…
▽ More
Serverless computing abstracts away server management, enabling automatic scaling and efficient resource utilization. However, cold-start latency remains a significant challenge, affecting end-to-end performance. Our preliminary study reveals that inefficient library initialization and usage are major contributors to this latency in Python-based serverless applications. We introduce LibProf, a Python profiler that uses dynamic program analysis to identify inefficient library initializations. LibProf collects library usage data through statistical sampling and call-path profiling, then generates a report to guide developers in addressing four types of inefficiency patterns. Systematic evaluations on 15 serverless applications demonstrate that LibProf effectively identifies inefficiencies. LibProf guided optimization results up to 2.26x speedup in cold-start execution time and 1.51x reduction in memory usage.
△ Less
Submitted 17 June, 2024;
originally announced June 2024.
-
KAN: Kolmogorov-Arnold Networks
Authors:
Ziming Liu,
Yixuan Wang,
Sachin Vaidya,
Fabian Ruehle,
James Halverson,
Marin Soljačić,
Thomas Y. Hou,
Max Tegmark
Abstract:
Inspired by the Kolmogorov-Arnold representation theorem, we propose Kolmogorov-Arnold Networks (KANs) as promising alternatives to Multi-Layer Perceptrons (MLPs). While MLPs have fixed activation functions on nodes ("neurons"), KANs have learnable activation functions on edges ("weights"). KANs have no linear weights at all -- every weight parameter is replaced by a univariate function parametriz…
▽ More
Inspired by the Kolmogorov-Arnold representation theorem, we propose Kolmogorov-Arnold Networks (KANs) as promising alternatives to Multi-Layer Perceptrons (MLPs). While MLPs have fixed activation functions on nodes ("neurons"), KANs have learnable activation functions on edges ("weights"). KANs have no linear weights at all -- every weight parameter is replaced by a univariate function parametrized as a spline. We show that this seemingly simple change makes KANs outperform MLPs in terms of accuracy and interpretability. For accuracy, much smaller KANs can achieve comparable or better accuracy than much larger MLPs in data fitting and PDE solving. Theoretically and empirically, KANs possess faster neural scaling laws than MLPs. For interpretability, KANs can be intuitively visualized and can easily interact with human users. Through two examples in mathematics and physics, KANs are shown to be useful collaborators helping scientists (re)discover mathematical and physical laws. In summary, KANs are promising alternatives for MLPs, opening opportunities for further improving today's deep learning models which rely heavily on MLPs.
△ Less
Submitted 16 June, 2024; v1 submitted 30 April, 2024;
originally announced April 2024.
-
Quantum Algorithms for the Pathwise Lasso
Authors:
Joao F. Doriguello,
Debbie Lim,
Chi Seng Pun,
Patrick Rebentrost,
Tushar Vaidya
Abstract:
We present a novel quantum high-dimensional linear regression algorithm with an $\ell_1$-penalty based on the classical LARS (Least Angle Regression) pathwise algorithm. Similarly to available classical algorithms for Lasso, our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. A quadratic speedup o…
▽ More
We present a novel quantum high-dimensional linear regression algorithm with an $\ell_1$-penalty based on the classical LARS (Least Angle Regression) pathwise algorithm. Similarly to available classical algorithms for Lasso, our quantum algorithm provides the full regularisation path as the penalty term varies, but quadratically faster per iteration under specific conditions. A quadratic speedup on the number of features $d$ is possible by using the quantum minimum-finding routine from Dürr and Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then improve upon this simple quantum algorithm and obtain a quadratic speedup both in the number of features $d$ and the number of observations $n$ by using the approximate quantum minimum-finding routine from Chen and de Wolf (ICALP'23). As one of our main contributions, we construct a quantum unitary to approximately compute the joining times to be searched over by the approximate quantum minimum finding. Since the joining times are no longer exactly computed, it is no longer clear that the resulting approximate quantum algorithm obtains a good solution. As our second main contribution, we prove, via an approximate version of the KKT conditions and a duality gap, that the LARS algorithm (and thus our quantum algorithm) is robust to errors. This means that it still outputs a path that minimises the Lasso cost function up to a small error if the joining times are approximately computed. Moreover, we show that, when the observations are sampled from a Gaussian distribution, our quantum algorithm's complexity only depends polylogarithmically on $n$, exponentially better than the classical LARS algorithm, while keeping the quadratic improvement on $d$. Finally, we propose a dequantised algorithm that also retains the polylogarithmic dependence on $n$, albeit with the linear scaling on $d$ from the standard LARS algorithm.
△ Less
Submitted 17 June, 2024; v1 submitted 21 December, 2023;
originally announced December 2023.
-
Adapter Pruning using Tropical Characterization
Authors:
Rishabh Bhardwaj,
Tushar Vaidya,
Soujanya Poria
Abstract:
Adapters are widely popular parameter-efficient transfer learning approaches in natural language processing that insert trainable modules in between layers of a pre-trained language model. Apart from several heuristics, however, there has been a lack of studies analyzing the optimal number of adapter parameters needed for downstream applications. In this paper, we propose an adapter pruning approa…
▽ More
Adapters are widely popular parameter-efficient transfer learning approaches in natural language processing that insert trainable modules in between layers of a pre-trained language model. Apart from several heuristics, however, there has been a lack of studies analyzing the optimal number of adapter parameters needed for downstream applications. In this paper, we propose an adapter pruning approach by studying the tropical characteristics of trainable modules. We cast it as an optimization problem that aims to prune parameters from the adapter layers without changing the orientation of underlying tropical hypersurfaces. Our experiments on five NLP datasets show that tropical geometry tends to identify more relevant parameters to prune when compared with the magnitude-based baseline, while a combined approach works best across the tasks.
△ Less
Submitted 29 October, 2023;
originally announced October 2023.
-
Show Me the World in My Language: Establishing the First Baseline for Scene-Text to Scene-Text Translation
Authors:
Shreyas Vaidya,
Arvind Kumar Sharma,
Prajwal Gatti,
Anand Mishra
Abstract:
In this work, we study the task of visually translating scene text from a source language (e.g., Hindi) to a target language (e.g., English). Visual translation involves not just the recognition and translation of scene text but also the generation of the translated image that preserves visual features of the source scene text, such as font, size, and background. There are several challenges assoc…
▽ More
In this work, we study the task of visually translating scene text from a source language (e.g., Hindi) to a target language (e.g., English). Visual translation involves not just the recognition and translation of scene text but also the generation of the translated image that preserves visual features of the source scene text, such as font, size, and background. There are several challenges associated with this task, such as translation with limited context, deciding between translation and transliteration, accommodating varying text lengths within fixed spatial boundaries, and preserving the font and background styles of the source scene text in the target language. To address this problem, we make the following contributions: (i) We study visual translation as a standalone problem for the first time in the literature. (ii) We present a cascaded framework for visual translation that combines state-of-the-art modules for scene text recognition, machine translation, and scene text synthesis as a baseline for the task. (iii) We propose a set of task-specific design enhancements to design a variant of the baseline to obtain performance improvements. (iv) Currently, the existing related literature lacks any comprehensive performance evaluation for this novel task. To fill this gap, we introduce several automatic and user-assisted evaluation metrics designed explicitly for evaluating visual translation. Further, we evaluate presented baselines for translating scene text between Hindi and English. Our experiments demonstrate that although we can effectively perform visual translation over a large collection of scene text images, the presented baseline only partially addresses challenges posed by visual translation tasks. We firmly believe that this new task and the limitations of existing models, as reported in this paper, should encourage further research in visual translation.
△ Less
Submitted 17 July, 2024; v1 submitted 6 August, 2023;
originally announced August 2023.
-
Psychological Metrics for Dialog System Evaluation
Authors:
Salvatore Giorgi,
Shreya Havaldar,
Farhan Ahmed,
Zuhaib Akhtar,
Shalaka Vaidya,
Gary Pan,
Lyle H. Ungar,
H. Andrew Schwartz,
Joao Sedoc
Abstract:
We present metrics for evaluating dialog systems through a psychologically-grounded "human" lens in which conversational agents express a diversity of both states (e.g., emotion) and traits (e.g., personality), just as people do. We present five interpretable metrics from established psychology that are fundamental to human communication and relationships: emotional entropy, linguistic style and e…
▽ More
We present metrics for evaluating dialog systems through a psychologically-grounded "human" lens in which conversational agents express a diversity of both states (e.g., emotion) and traits (e.g., personality), just as people do. We present five interpretable metrics from established psychology that are fundamental to human communication and relationships: emotional entropy, linguistic style and emotion matching, agreeableness, and empathy. These metrics can be applied (1) across dialogs and (2) on turns within dialogs. The psychological metrics are compared against seven state-of-the-art traditional metrics (e.g., BARTScore and BLEURT) on seven standard dialog system data sets. We also introduce a novel data set, the Three Bot Dialog Evaluation Corpus, which consists of annotated conversations from ChatGPT, GPT-3, and BlenderBot. We demonstrate that our proposed metrics offer novel information; they are uncorrelated with traditional metrics, can be used to meaningfully compare dialog systems, and lead to increased accuracy (beyond existing traditional metrics) in predicting crowd-sourced dialog judgements. The interpretability and unique signal of our psychological metrics make them a valuable tool for evaluating and improving dialog systems.
△ Less
Submitted 15 September, 2023; v1 submitted 24 May, 2023;
originally announced May 2023.
-
Time-Aware Datasets are Adaptive Knowledgebases for the New Normal
Authors:
Abhijit Suprem,
Sanjyot Vaidya,
Joao Eduardo Ferreira,
Calton Pu
Abstract:
Recent advances in text classification and knowledge capture in language models have relied on availability of large-scale text datasets. However, language models are trained on static snapshots of knowledge and are limited when that knowledge evolves. This is especially critical for misinformation detection, where new types of misinformation continuously appear, replacing old campaigns. We propos…
▽ More
Recent advances in text classification and knowledge capture in language models have relied on availability of large-scale text datasets. However, language models are trained on static snapshots of knowledge and are limited when that knowledge evolves. This is especially critical for misinformation detection, where new types of misinformation continuously appear, replacing old campaigns. We propose time-aware misinformation datasets to capture time-critical phenomena. In this paper, we first present evidence of evolving misinformation and show that incorporating even simple time-awareness significantly improves classifier accuracy. Second, we present COVID-TAD, a large-scale COVID-19 misinformation da-taset spanning 25 months. It is the first large-scale misinformation dataset that contains multiple snapshots of a datastream and is orders of magnitude bigger than related misinformation datasets. We describe the collection and labeling pro-cess, as well as preliminary experiments.
△ Less
Submitted 22 November, 2022;
originally announced November 2022.
-
ATEAM: Knowledge Integration from Federated Datasets for Vehicle Feature Extraction using Annotation Team of Experts
Authors:
Abhijit Suprem,
Purva Singh,
Suma Cherkadi,
Sanjyot Vaidya,
Joao Eduardo Ferreira,
Calton Pu
Abstract:
The vehicle recognition area, including vehicle make-model recognition (VMMR), re-id, tracking, and parts-detection, has made significant progress in recent years, driven by several large-scale datasets for each task. These datasets are often non-overlapping, with different label schemas for each task: VMMR focuses on make and model, while re-id focuses on vehicle ID. It is promising to combine th…
▽ More
The vehicle recognition area, including vehicle make-model recognition (VMMR), re-id, tracking, and parts-detection, has made significant progress in recent years, driven by several large-scale datasets for each task. These datasets are often non-overlapping, with different label schemas for each task: VMMR focuses on make and model, while re-id focuses on vehicle ID. It is promising to combine these datasets to take advantage of knowledge across datasets as well as increased training data; however, dataset integration is challenging due to the domain gap problem. This paper proposes ATEAM, an annotation team-of-experts to perform cross-dataset labeling and integration of disjoint annotation schemas. ATEAM uses diverse experts, each trained on datasets that contain an annotation schema, to transfer knowledge to datasets without that annotation. Using ATEAM, we integrated several common vehicle recognition datasets into a Knowledge Integrated Dataset (KID). We evaluate ATEAM and KID for vehicle recognition problems and show that our integrated dataset can help off-the-shelf models achieve excellent accuracy on VMMR and vehicle re-id with no changes to model architectures. We achieve mAP of 0.83 on VeRi, and accuracy of 0.97 on CompCars. We have released both the dataset and the ATEAM framework for public use.
△ Less
Submitted 16 November, 2022;
originally announced November 2022.
-
EdnaML: A Declarative API and Framework for Reproducible Deep Learning
Authors:
Abhijit Suprem,
Sanjyot Vaidya,
Avinash Venugopal,
Joao Eduardo Ferreira,
Calton Pu
Abstract:
Machine Learning has become the bedrock of recent advances in text, image, video, and audio processing and generation. Most production systems deal with several models during deployment and training, each with a variety of tuned hyperparameters. Furthermore, data collection and processing aspects of ML pipelines are receiving increasing interest due to their importance in creating sustainable high…
▽ More
Machine Learning has become the bedrock of recent advances in text, image, video, and audio processing and generation. Most production systems deal with several models during deployment and training, each with a variety of tuned hyperparameters. Furthermore, data collection and processing aspects of ML pipelines are receiving increasing interest due to their importance in creating sustainable high-quality classifiers. We present EdnaML, a framework with a declarative API for reproducible deep learning. EdnaML provides low-level building blocks that can be composed manually, as well as a high-level pipeline orchestration API to automate data collection, data processing, classifier training, classifier deployment, and model monitoring. Our layered API allows users to manage ML pipelines at high-level component abstractions, while providing flexibility to modify any part of it through the building blocks. We present several examples of ML pipelines with EdnaML, including a large-scale fake news labeling and classification system with six sub-pipelines managed by EdnaML.
△ Less
Submitted 12 November, 2022;
originally announced November 2022.
-
Action Quality Assessment using Transformers
Authors:
Abhay Iyer,
Mohammad Alali,
Hemanth Bodala,
Sunit Vaidya
Abstract:
Action quality assessment (AQA) is an active research problem in video-based applications that is a challenging task due to the score variance per frame. Existing methods address this problem via convolutional-based approaches but suffer from its limitation of effectively capturing long-range dependencies. With the recent advancements in Transformers, we show that they are a suitable alternative t…
▽ More
Action quality assessment (AQA) is an active research problem in video-based applications that is a challenging task due to the score variance per frame. Existing methods address this problem via convolutional-based approaches but suffer from its limitation of effectively capturing long-range dependencies. With the recent advancements in Transformers, we show that they are a suitable alternative to the conventional convolutional-based architectures. Specifically, can transformer-based models solve the task of AQA by effectively capturing long-range dependencies, parallelizing computation, and providing a wider receptive field for diving videos? To demonstrate the effectiveness of our proposed architectures, we conducted comprehensive experiments and achieved a competitive Spearman correlation score of 0.9317. Additionally, we explore the hyperparameters effect on the model's performance and pave a new path for exploiting Transformers in AQA.
△ Less
Submitted 20 July, 2022;
originally announced July 2022.
-
Constructive Interpretability with CoLabel: Corroborative Integration, Complementary Features, and Collaborative Learning
Authors:
Abhijit Suprem,
Sanjyot Vaidya,
Suma Cherkadi,
Purva Singh,
Joao Eduardo Ferreira,
Calton Pu
Abstract:
Machine learning models with explainable predictions are increasingly sought after, especially for real-world, mission-critical applications that require bias detection and risk mitigation. Inherent interpretability, where a model is designed from the ground-up for interpretability, provides intuitive insights and transparent explanations on model prediction and performance. In this paper, we pres…
▽ More
Machine learning models with explainable predictions are increasingly sought after, especially for real-world, mission-critical applications that require bias detection and risk mitigation. Inherent interpretability, where a model is designed from the ground-up for interpretability, provides intuitive insights and transparent explanations on model prediction and performance. In this paper, we present CoLabel, an approach to build interpretable models with explanations rooted in the ground truth. We demonstrate CoLabel in a vehicle feature extraction application in the context of vehicle make-model recognition (VMMR). CoLabel performs VMMR with a composite of interpretable features such as vehicle color, type, and make, all based on interpretable annotations of the ground truth labels. First, CoLabel performs corroborative integration to join multiple datasets that each have a subset of desired annotations of color, type, and make. Then, CoLabel uses decomposable branches to extract complementary features corresponding to desired annotations. Finally, CoLabel fuses them together for final predictions. During feature fusion, CoLabel harmonizes complementary branches so that VMMR features are compatible with each other and can be projected to the same semantic space for classification. With inherent interpretability, CoLabel achieves superior performance to the state-of-the-art black-box models, with accuracy of 0.98, 0.95, and 0.94 on CompCars, Cars196, and BoxCars116K, respectively. CoLabel provides intuitive explanations due to constructive interpretability, and subsequently achieves high accuracy and usability in mission-critical situations.
△ Less
Submitted 20 May, 2022;
originally announced May 2022.
-
Radio labelling of two-branch trees
Authors:
Devsi Bantva,
Samir Vaidya,
Sanming Zhou
Abstract:
A radio labelling of a graph $G$ is a mapping $f : V(G) \rightarrow \{0, 1, 2,\ldots\}$ such that $|f(u)-f(v)| \geq diam(G) + 1 - d(u,v)$ for every pair of distinct vertices $u,v$ of $G$, where $diam(G)$ is the diameter of $G$ and $d(u,v)$ is the distance between $u$ and $v$ in $G$. The radio number $rn(G)$ of $G$ is the smallest integer $k$ such that $G$ admits a radio labelling $f$ with…
▽ More
A radio labelling of a graph $G$ is a mapping $f : V(G) \rightarrow \{0, 1, 2,\ldots\}$ such that $|f(u)-f(v)| \geq diam(G) + 1 - d(u,v)$ for every pair of distinct vertices $u,v$ of $G$, where $diam(G)$ is the diameter of $G$ and $d(u,v)$ is the distance between $u$ and $v$ in $G$. The radio number $rn(G)$ of $G$ is the smallest integer $k$ such that $G$ admits a radio labelling $f$ with $\max\{f(v):v \in V(G)\} = k$. The weight of a tree $T$ from a vertex $v \in V(T)$ is the sum of the distances in $T$ from $v$ to all other vertices, and a vertex of $T$ achieving the minimum weight is called a weight center of $T$. It is known that any tree has one or two weight centers. A tree is called a two-branch tree if the removal of all its weight centers results in a forest with exactly two components. In this paper we obtain a sharp lower bound for the radio number of two-branch trees which improves a known lower bound for general trees. We also give a necessary and sufficient condition for this improved lower bound to be achieved. Using these results, we determine the radio number of two families of level-wise regular two-branch trees.
△ Less
Submitted 10 April, 2023; v1 submitted 29 January, 2022;
originally announced January 2022.
-
KNOT: Knowledge Distillation using Optimal Transport for Solving NLP Tasks
Authors:
Rishabh Bhardwaj,
Tushar Vaidya,
Soujanya Poria
Abstract:
We propose a new approach, Knowledge Distillation using Optimal Transport (KNOT), to distill the natural language semantic knowledge from multiple teacher networks to a student network. KNOT aims to train a (global) student model by learning to minimize the optimal transport cost of its assigned probability distribution over the labels to the weighted sum of probabilities predicted by the (local)…
▽ More
We propose a new approach, Knowledge Distillation using Optimal Transport (KNOT), to distill the natural language semantic knowledge from multiple teacher networks to a student network. KNOT aims to train a (global) student model by learning to minimize the optimal transport cost of its assigned probability distribution over the labels to the weighted sum of probabilities predicted by the (local) teacher models, under the constraints, that the student model does not have access to teacher models' parameters or training data. To evaluate the quality of knowledge transfer, we introduce a new metric, Semantic Distance (SD), that measures semantic closeness between the predicted and ground truth label distributions. The proposed method shows improvements in the global model's SD performance over the baseline across three NLP tasks while performing on par with Entropy-based distillation on standard accuracy and F1 metrics. The implementation pertaining to this work is publicly available at: https://github.com/declare-lab/KNOT.
△ Less
Submitted 16 September, 2022; v1 submitted 5 October, 2021;
originally announced October 2021.
-
Hamiltonian chromatic number of trees
Authors:
Devsi Bantva,
Samir Vaidya
Abstract:
Let $G$ be a simple finite connected graph of order $n$. The detour distance between two distinct vertices $u$ and $v$ denoted by $D(u,v)$ is the length of a longest $uv$-path in $G$. A hamiltonian coloring $h$ of a graph $G$ of order $n$ is a mapping $h : V(G) \rightarrow \{0,1,2,...\}$ such that $D(u,v) + |h(u)-h(v)| \geq n-1$, for every two distinct vertices $u$ and $v$ of $G$. The span of $h$,…
▽ More
Let $G$ be a simple finite connected graph of order $n$. The detour distance between two distinct vertices $u$ and $v$ denoted by $D(u,v)$ is the length of a longest $uv$-path in $G$. A hamiltonian coloring $h$ of a graph $G$ of order $n$ is a mapping $h : V(G) \rightarrow \{0,1,2,...\}$ such that $D(u,v) + |h(u)-h(v)| \geq n-1$, for every two distinct vertices $u$ and $v$ of $G$. The span of $h$, denoted by $span(h)$, is $\max\{|h(u)-h(v)| : u, v \in V(G)\}$. The hamiltonian chromatic number of $G$ is defined as $hc(G) := \min\{span(h)\}$ with minimum taken over all hamiltonian coloring $h$ of $G$. In this paper, we give an improved lower bound for the hamiltonian chromatic number of trees and give a necessary and sufficient condition to achieve the improved lower bound. Using this result, we determine the hamiltonian chromatic number of two families of trees.
△ Less
Submitted 14 December, 2020;
originally announced December 2020.
-
Elastic execution of checkpointed MPI applications
Authors:
Sumeet Gajjar,
Saurabh Vaidya
Abstract:
MPI applications begin with a fixed number of rank and, by default, the rank remains constant throughout the application's lifetime. The developer can choose to increase the rank by dynamically spawning MPI processes. However doing this manually adds complexity to the MPI application. Making the MPI applications malleable \cite{b20} would allow HPC applications to have the same elasticity as that…
▽ More
MPI applications begin with a fixed number of rank and, by default, the rank remains constant throughout the application's lifetime. The developer can choose to increase the rank by dynamically spawning MPI processes. However doing this manually adds complexity to the MPI application. Making the MPI applications malleable \cite{b20} would allow HPC applications to have the same elasticity as that of cloud applications. We propose multiple approaches to change the rank of an MPI program agnostic to the modification of the user code. We use checkpointing as a tool to achieve mutability of rank by halting the execution and resuming the MPI program with a new state. In this paper, we focus on the scenario of increasing the rank of an MPI program using ExaMPI as the implementation for MPI.
△ Less
Submitted 15 May, 2020;
originally announced May 2020.
-
Broken Detailed Balance and Non-Equilibrium Dynamics in Noisy Social Learning Models
Authors:
Tushar Vaidya,
Thiparat Chotibut,
Georgios Piliouras
Abstract:
We propose new Degroot-type social learning models with feedback in a continuous time, to investigate the effect of a noisy information source on consensus formation in a social network. Unlike the standard Degroot framework, noisy information models destroy consensus formation. On the other hand, the noisy opinion dynamics converge to the equilibrium distribution that encapsulates correlations am…
▽ More
We propose new Degroot-type social learning models with feedback in a continuous time, to investigate the effect of a noisy information source on consensus formation in a social network. Unlike the standard Degroot framework, noisy information models destroy consensus formation. On the other hand, the noisy opinion dynamics converge to the equilibrium distribution that encapsulates correlations among agents' opinions. Interestingly, such an equilibrium distribution is also a non-equilibrium steady state (NESS) with a non-zero probabilistic current loop. Thus, noisy information source leads to a NESS at long times that encodes persistent correlated opinion dynamics of learning agents. Our model provides a simple realization of NESS in the context of social learning. Other phenomena such as synchronization of opinions when agents are subject to a common noise are also studied.
△ Less
Submitted 13 May, 2020; v1 submitted 27 June, 2019;
originally announced June 2019.
-
Brief Review of Computational Intelligence Algorithms
Authors:
Satyarth Vaidya,
Arshveer Kaur,
Lavika Goel
Abstract:
Computational Intelligence algorithms have gained a lot of attention of researchers in the recent years due to their ability to deliver near optimal solutions.
Computational Intelligence algorithms have gained a lot of attention of researchers in the recent years due to their ability to deliver near optimal solutions.
△ Less
Submitted 28 January, 2019; v1 submitted 4 January, 2019;
originally announced January 2019.
-
Learning Agents in Black-Scholes Financial Markets: Consensus Dynamics and Volatility Smiles
Authors:
Tushar Vaidya,
Carlos Murguia,
Georgios Piliouras
Abstract:
Black-Scholes (BS) is the standard mathematical model for option pricing in financial markets. Option prices are calculated using an analytical formula whose main inputs are strike (at which price to exercise) and volatility. The BS framework assumes that volatility remains constant across all strikes, however, in practice it varies. How do traders come to learn these parameters? We introduce natu…
▽ More
Black-Scholes (BS) is the standard mathematical model for option pricing in financial markets. Option prices are calculated using an analytical formula whose main inputs are strike (at which price to exercise) and volatility. The BS framework assumes that volatility remains constant across all strikes, however, in practice it varies. How do traders come to learn these parameters? We introduce natural models of learning agents, in which they update their beliefs about the true implied volatility based on the opinions of other traders. We prove convergence of these opinion dynamics using techniques from control theory and leader-follower models, thus providing a resolution between theory and market practices. We allow for two different models, one with feedback and one with an unknown leader.
△ Less
Submitted 10 July, 2020; v1 submitted 25 April, 2017;
originally announced April 2017.
-
A New Benchmark For Evaluation Of Graph-Theoretic Algorithms
Authors:
Andy B. Yoo,
Yang Liu,
Sheila Vaidya,
Stephen Poole
Abstract:
We propose a new graph-theoretic benchmark in this paper. The benchmark is developed to address shortcomings of an existing widely-used graph benchmark. We thoroughly studied a large number of traditional and contemporary graph algorithms reported in the literature to have clear understanding of their algorithmic and run-time characteristics. Based on this study, we designed a suite of kernels, e…
▽ More
We propose a new graph-theoretic benchmark in this paper. The benchmark is developed to address shortcomings of an existing widely-used graph benchmark. We thoroughly studied a large number of traditional and contemporary graph algorithms reported in the literature to have clear understanding of their algorithmic and run-time characteristics. Based on this study, we designed a suite of kernels, each of which represents a specific class of graph algorithms. The kernels are designed to capture the typical run-time behavior of target algorithms accurately, while limiting computational and spatial overhead to ensure its computation finishes in reasonable time. We expect that the developed benchmark will serve as a much needed tool for evaluating different architectures and programming models to run graph algorithms.
△ Less
Submitted 5 May, 2010;
originally announced May 2010.
-
A Generalized Recursive Algorithm for Binary Multiplication based on Vedic Mathematics
Authors:
Ajinkya Kale,
Shaunak Vaidya,
Ashish Joglekar
Abstract:
A generalized algorithm for multiplication is proposed through recursive application of the Nikhilam Sutra from Vedic Mathematics, operating in radix - 2 number system environment suitable for digital platforms. Statistical analysis has been carried out based on the number of recursions profile as a function of the smaller multiplicand. The proposed algorithm is efficient for smaller multiplican…
▽ More
A generalized algorithm for multiplication is proposed through recursive application of the Nikhilam Sutra from Vedic Mathematics, operating in radix - 2 number system environment suitable for digital platforms. Statistical analysis has been carried out based on the number of recursions profile as a function of the smaller multiplicand. The proposed algorithm is efficient for smaller multiplicands as well, unlike most of the asymptotically fast algorithms. Further, a basic block schematic of Hardware Implementation of our algorithm is suggested to exploit parallelism and speed up the implementation of the algorithm in a multiprocessor environment.
△ Less
Submitted 11 October, 2009;
originally announced October 2009.