When available, the publication has been linked as PDF. To access, please click on the PDF symbol at the bottom right of each listed publication.
2020 |
|
| 1. | Diddigi, Raghuram Bharadwaj; Chandramouli Kamanchi, Shalabh Bhatnagar A Convergent Off-Policy Temporal Difference Algorithm (Conference) 24th European Conference on Artificial Intelligence – ECAI 2020, Forthcoming. (Abstract | BibTeX | Tags: Conference | Links: ) @conference{@Raghuram, title = {A Convergent Off-Policy Temporal Difference Algorithm}, author = {Raghuram Bharadwaj Diddigi and Chandramouli Kamanchi, Shalabh Bhatnagar}, url = {https://cni.iisc.ac.in/wp-content/uploads/2020/07/A-Convergent-Off-Policy-Temporal-Difference-Algorithm.pdf}, year = {2020}, date = {2020-08-29}, booktitle = {24th European Conference on Artificial Intelligence – ECAI 2020}, journal = {24th European Conference on Artificial Intelligence – ECAI 2020}, abstract = {Learning the value function of a given policy (target policy) from the data samples obtained from a different policy (behavior policy) is an important problem in Reinforcement Learning (RL). This problem is studied under the setting of off-policy prediction. Temporal Difference (TD) learning algorithms are a popular class of algorithms for solving the prediction problem. TD algorithms with linear function approximation are shown to be convergent when the samples are generated from the target policy (known as on-policy prediction). However, it has been well established in the literature that off-policy TD algorithms under linear function approximation diverge. In this work, we propose a convergent on-line off-policy TD algorithm under linear function approximation. The main idea is to penalize the updates of the algorithm in a way as to ensure convergence of the iterates. We provide a convergence analysis of our algorithm. Through numerical evaluations, we further demonstrate the effectiveness of our algorithm. }, keywords = {Conference}, pubstate = {forthcoming}, tppubtype = {conference} } Learning the value function of a given policy (target policy) from the data samples obtained from a different policy (behavior policy) is an important problem in Reinforcement Learning (RL). This problem is studied under the setting of off-policy prediction. Temporal Difference (TD) learning algorithms are a popular class of algorithms for solving the prediction problem. TD algorithms with linear function approximation are shown to be convergent when the samples are generated from the target policy (known as on-policy prediction). However, it has been well established in the literature that off-policy TD algorithms under linear function approximation diverge. In this work, we propose a convergent on-line off-policy TD algorithm under linear function approximation. The main idea is to penalize the updates of the algorithm in a way as to ensure convergence of the iterates. We provide a convergence analysis of our algorithm. Through numerical evaluations, we further demonstrate the effectiveness of our algorithm. |
| 2. | Hanna, Serge Kas; Rawad Bitar, Parimal Parag ; Dasari, Venkat; Rouayheb, Salim El Adaptive Distributed Stochastic Gradient Descent for Minimizing delay in the presence of Stragglers (Conference) ICASSP 2020 – 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020. (Abstract | BibTeX | Tags: Conference | Links: ) @conference{@Serge, title = {Adaptive Distributed Stochastic Gradient Descent for Minimizing delay in the presence of Stragglers}, author = {Serge Kas Hanna and Rawad Bitar, Parimal Parag and Venkat Dasari and Salim El Rouayheb}, url = {https://cni.iisc.ac.in/wp-content/uploads/2020/02/Adaptive-Distributed-Stochastic-Gradient-Descent-for-Minimizing-delay-in-the-presence-of-Stragglers.pdf}, doi = {10.1109/ICASSP40776.2020.9053961}, year = {2020}, date = {2020-05-14}, booktitle = { ICASSP 2020 – 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)}, journal = {45th International Conference on Acoustics, Speech, and Signal Processing}, abstract = {We consider the setting where a master wants to run a distributed stochastic gradient descent (SGD) algorithm on n workers each having a subset of the data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or unresponsive workers who cause delays. One solution studied in the literature is to wait at each iteration for the responses of the fastest k pubstate = {published}, tppubtype = {conference} } We consider the setting where a master wants to run a distributed stochastic gradient descent (SGD) algorithm on n workers each having a subset of the data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or unresponsive workers who cause delays. One solution studied in the literature is to wait at each iteration for the responses of the fastest k<n workers before updating the model, where k is a fixed parameter. The choice of the value of k presents a trade-off between the runtime (i.e., convergence rate) of SGD and the error of the model. Towards optimizing the error-runtime trade-off, we investigate distributed SGD with adaptive k. We first design an adaptive policy for varying k that optimizes this trade-off based on an upper bound on the error as a function of the wall-clock time which we derive. Then, we propose an algorithm for adaptive distributed SGD that is based on a statistical heuristic. We implement our algorithm and provide numerical simulations which confirm our intuition and theoretical analysis. |
| 3. | Rawad Bitar, Parimal Parag ; Rouayheb, Salim El Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes (Journal Article) IEEE Transactions on Communications, pp. 1, 2020. (Abstract | BibTeX | Tags: Journal | Links: ) @article{@rawad, title = {Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes}, author = {Rawad Bitar, Parimal Parag and Salim El Rouayheb }, url = {https://cni.iisc.ac.in/wp-content/uploads/2020/07/Minimizing-Latency-for-Secure-Coded-Computing……..pdf}, doi = {10.1109/TCOMM.2020.2988506}, year = {2020}, date = {2020-04-17}, journal = { IEEE Transactions on Communications}, pages = {1}, abstract = {We consider the setting of a Master server, M, who possesses confidential data (e.g., personal, genomic or medical data) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The Master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private and not revealed to the individual workers. Some of the workers may be stragglers, e.g., slow or busy, and will take a random time to finish the task assigned to them. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms such as principal component analysis, support vector machines and other gradient-descent based algorithms. A classical solution is to use a linear secret sharing scheme, such as Shamir’s scheme, to divide the data into secret shares on which the workers can perform linear computations. However, classical codes can provide straggler mitigation assuming a worst-case scenario of a fixed number of stragglers. We propose a solution based on new secure codes, called Staircase codes, introduced previously by two of the authors. Staircase codes allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. Under the shifted exponential model, we find upper and lower bounds on the Master’s mean waiting time. We derive the distribution of the Master’s waiting time, and its mean, for systems with up to two stragglers. For systems with any number of stragglers, we derive an expression that can give the exact distribution, and the mean, of the waiting time of the Master. We show that Staircase codes always outperform classical secret sharing codes.}, keywords = {Journal}, pubstate = {published}, tppubtype = {article} } We consider the setting of a Master server, M, who possesses confidential data (e.g., personal, genomic or medical data) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The Master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private and not revealed to the individual workers. Some of the workers may be stragglers, e.g., slow or busy, and will take a random time to finish the task assigned to them. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms such as principal component analysis, support vector machines and other gradient-descent based algorithms. A classical solution is to use a linear secret sharing scheme, such as Shamir’s scheme, to divide the data into secret shares on which the workers can perform linear computations. However, classical codes can provide straggler mitigation assuming a worst-case scenario of a fixed number of stragglers. We propose a solution based on new secure codes, called Staircase codes, introduced previously by two of the authors. Staircase codes allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. Under the shifted exponential model, we find upper and lower bounds on the Master’s mean waiting time. We derive the distribution of the Master’s waiting time, and its mean, for systems with up to two stragglers. For systems with any number of stragglers, we derive an expression that can give the exact distribution, and the mean, of the waiting time of the Master. We show that Staircase codes always outperform classical secret sharing codes. |
| 4. | Patil, Prasanna; Govind Sharma, Narasimha Murty M Negative Sampling for Hyperlink Prediction in Networks (Conference) Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2020. (Abstract | BibTeX | Tags: Conference | Links: ) @conference{@Prasanna, title = {Negative Sampling for Hyperlink Prediction in Networks}, author = {Prasanna Patil and Govind Sharma, M Narasimha Murty}, url = {https://cni.iisc.ac.in/wp-content/uploads/2020/07/Negative-Sampling-for-Hyperlink-Prediction-in-Networks.pdf}, year = {2020}, date = {2020-05-06}, booktitle = {Pacific-Asia Conference on Knowledge Discovery and Data Mining}, pages = {607-619}, abstract = {While graphs capture pairwise relations between entities, hypergraphs deal with higher-order ones, thereby ensuring losslessness. However, in hyperlink (i.e., higher-order link) prediction, where hyperlinks and non-hyperlinks are treated as “positive” and “negative” classes respectively, hypergraphs suffer from the problem of extreme class imbalance. Given this context, “negative sampling”—under-sampling the negative class of non-hyperlinks—becomes mandatory for performing hyperlink prediction. No prior work on hyperlink prediction deals with this problem. In this work, which is the first of its kind, we deal with this problem in the context of hyperlink prediction. More specifically, we leverage graph sampling techniques for sampling non-hyperlinks in hyperlink prediction. Our analysis clearly establishes the effect of random sampling, which is the norm in both link- as well as hyperlink-prediction. Further, we formalize the notion of “hardness” of non-hyperlinks via a measure of density, and analyze its distribution over various negative sampling techniques. We experiment with some real-world hypergraph datasets and provide both qualitative and quantitative results on the effects of negative sampling. We also establish its importance in evaluating hyperlink prediction algorithms.}, keywords = {Conference}, pubstate = {published}, tppubtype = {conference} } While graphs capture pairwise relations between entities, hypergraphs deal with higher-order ones, thereby ensuring losslessness. However, in hyperlink (i.e., higher-order link) prediction, where hyperlinks and non-hyperlinks are treated as “positive” and “negative” classes respectively, hypergraphs suffer from the problem of extreme class imbalance. Given this context, “negative sampling”—under-sampling the negative class of non-hyperlinks—becomes mandatory for performing hyperlink prediction. No prior work on hyperlink prediction deals with this problem. In this work, which is the first of its kind, we deal with this problem in the context of hyperlink prediction. More specifically, we leverage graph sampling techniques for sampling non-hyperlinks in hyperlink prediction. Our analysis clearly establishes the effect of random sampling, which is the norm in both link- as well as hyperlink-prediction. Further, we formalize the notion of “hardness” of non-hyperlinks via a measure of density, and analyze its distribution over various negative sampling techniques. We experiment with some real-world hypergraph datasets and provide both qualitative and quantitative results on the effects of negative sampling. We also establish its importance in evaluating hyperlink prediction algorithms. |
| 5. | Pratik Sharma; Devam Awasare ; Bishal Jaiswal ; Srivats Mohan ; N. Abinaya ; Ishan Darwhekar ; Anand Svr ; Bharadwaj Amrutur ; Aditya Gopalan ; Parimal Parag ; Himanshu, Tyagi On the Latency in Vehicular Control using Video Streaming over Wi-Fi (Conference) 2020 National Conference on Communications (NCC), 2020. (Abstract | BibTeX | Tags: Conference | Links: ) @conference{@Pratik, title = {On the Latency in Vehicular Control using Video Streaming over Wi-Fi}, author = {Pratik Sharma; Devam Awasare ; Bishal Jaiswal ; Srivats Mohan ; N. Abinaya ; Ishan Darwhekar ; Anand Svr ; Bharadwaj Amrutur ; Aditya Gopalan ; Parimal Parag ; Himanshu,Tyagi }, url = {https://cni.iisc.ac.in/wp-content/uploads/2020/07/On-the-Latency-in-Vehicular-Control-using-Video-Streaming-over-Wi-Fi.pdf}, doi = {10.1109/NCC48643.2020.9056067}, year = {2020}, date = {2020-04-06}, booktitle = {2020 National Conference on Communications (NCC)}, abstract = {We consider the use of Wi-Fi (IEEE 802.11n/r) network for remote control of a vehicle using video transmission on the uplink and control signals for the actuator on the downlink. We have setup a network with multiple access points (AP) providing indoor and outdoor coverage, which connects an unmanned ground vehicle (UGV) to a remote command center. Additionally, our setup includes a redundant IEEE 802.11p link for sending control messages over downlink with high reliability and low latency. We study the end-to-end communication delay and complete a latency profiling for each sub-component, including the video codec and the Wi-Fi links. Furthermore, we provide guidelines for practical design choices including the optimal configuration of the scanning process during handoffs and the codec parameters for delay optimization. Overall, our proposed configuration reduces the end-to-end delay significantly in comparison with the default configuration.}, keywords = {Conference}, pubstate = {published}, tppubtype = {conference} } We consider the use of Wi-Fi (IEEE 802.11n/r) network for remote control of a vehicle using video transmission on the uplink and control signals for the actuator on the downlink. We have setup a network with multiple access points (AP) providing indoor and outdoor coverage, which connects an unmanned ground vehicle (UGV) to a remote command center. Additionally, our setup includes a redundant IEEE 802.11p link for sending control messages over downlink with high reliability and low latency. We study the end-to-end communication delay and complete a latency profiling for each sub-component, including the video codec and the Wi-Fi links. Furthermore, we provide guidelines for practical design choices including the optimal configuration of the scanning process during handoffs and the codec parameters for delay optimization. Overall, our proposed configuration reduces the end-to-end delay significantly in comparison with the default configuration. |
