Department of Computer Science and Automation Department of Computer Science and Automation, IISc, Bangalore, India Indian Institute of Science
HOME | ABOUT US | PEOPLE | RESEARCH | ACADEMICS | FACILITIES | EVENTS / SEMINARS | NEWS | CONTACT US

UPCOMING SEMINARS

Series: M.Sc. (Engg) Thesis Defense
Title: On the gap between outcomes of voting rules

  • Speaker: Ms. Anurita Mathur
                   M.Sc. student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arnab Bhattacharyya
  • Date and Time: Friday, November 24, 2017, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Through the course of history, a variety of voting rules have been used to determine election outcomes. The traditional way in social choice theory to evaluate a voting rule is by checking whether it satisfies axioms deemed to be desirable for voting rules. Celebrated results in social choice theory say that even for a small set of seemingly necessary axioms, no voting rule exists satisfying them. In the face of such impossibility results, it becomes challenging to justify why certain voting rules work well in practice. Although in theory, these rules may yield drastically different outcomes, for real-world datasets, behavioural social choice analyses have found that the rules are often in perfect agreement with each other! This work attempts to give a mathematical explanation of this phenomenon.

In this work, we formulate a quantitative approach towards comparing voting rules by viewing them as two players engaged in a zero-sum game. If rule A selects candidate c_1 while rule B selects candidate c_2, the payoff for A is the number of voters who prefer c_1 to c_2 minus the number who prefer c_2 to c_1.The optimal voting rule according to this criterion (corresponding to the optimal randomized strategy for the game) is the "game-theoretic rule" (GT) while the best deterministic strategy is the well-known Minimax voting rule. We investigate rigorously how various common voting rules fare against each other in terms of the minimum payoff they receive for arbitrary voting profiles. We also study the case when the voting profiles are drawn from a mixture of multinomial logit distributions. This scenario corresponds to a population consisting of a small number of groups, each voting according to a latent preference ranking. We supplement the theoretical findings by empirically comparing the payoff of voting rules when they are applied to user preferences for movies as determined from the Netfix competition dataset. On this dataset, we find that the Minimax rule, the Schulze rule, and a deterministic variant of the GT rule perform the best in our framework.

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Stochastic Recursive Inclusions: Theory and Applications

  • Speaker: Mr. Arunselvan R
                   Ph.D student
                   Dept. of C.S.A
  • Faculty Advisor: Prof. Shalabh Bhatnagar
  • Date and Time: Friday, November 24, 2017, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Stochastic approximation algorithms encompass a class of iterative schemes that converge to a sought value through a series of successive approximations, even with erroneous observations. Such algorithms naturally arise in reinforcement learning, game theory, optimization, financial mathematics and cyber-physical systems. The first stochastic approximation algorithm was developed by Robbins and Monro in 1951 to solve the root-finding problem. In 1977 Ljung showed that the asymptotic behavior of a stochastic approximation algorithm can be studied by associating a deterministic ODE, called the associated ODE, and studying it's asymptotic behavior instead. In 1996 Benaim and Benaim and Hirsch used the dynamical systems approach to develop a framework to analyze generalized stochastic approximation algorithms. One bottleneck in deploying this framework was the requirement on stability (almost sure boundedness) of the iterates. In 1999 Borkar and Meyn developed a unified set of assumptions that guaranteed both stability and convergence of stochastic approximations. However, the aforementioned frameworks did not account for scenarios with set-valued mean fields. In 2005 Benaim, Hofbauer and Sorin showed that the dynamical systems approach to stochastic approximations can be extended to scenarios with set-valued mean-fields. Again, stability of the iterates was assumed.

The main focus of this talk will be on stochastic approximation methods with set-valued dynamical systems (stochastic recursive inclusions), with applications to reinforcement learning and optimization. In the first part of this talk we will discuss an extension of the Borkar-Meyn theorem to the scenario of stochastic recursive inclusions. As an application of this framework we will discuss a solution to the `approximate drift problem'. In the second part of this talk we will discuss the problem of gradient methods with errors. We will discuss a framework for the stability and convergence of gradient methods, even when the errors are `non-diminishing'. Our work extends the results of Bertsekas and Tsitsiklis, and Mangasarian and Solodov. Using our framework, we present a fast and hassle-free implementation of Simultaneous Perturbation Stochastic Approximation (SPSA), using constant sensitivity parameters. It is worth noting that our implementation `decouples' the sensitivity parameters and step-sizes.

We will also present experimental results in support of our theory. In the third part of this talk, we will discuss stochastic recursive inclusions with two-timescales. We use our framework to develop a two timescale algorithm to solve the constrained Lagrangian dual optimization problem. Due to the generality of our framework, the class of objective and constraint functions is enlarged, when compared to previous literature. In the final part of this talk, we will discuss a framework for stability and convergence of stochastic approximations with ‘controlled Markov processes’. Using this framework we present a relaxation of the assumptions for the analysis of temporal difference learning algorithms (an important policy evaluation scheme in reinforcement learning). It may be noted that our assumptions for stability (of temporal difference learning) are compatible with hitherto present frameworks. Further it may be noted that the conditions are weakened two-fold: (a) the Markov process is no longer required to evolve in a finite state space and (b) the state process is not required to be ergodic under a given stationary policy.

Video Archive Go Top

 

Series: Department Seminar
Title: Concentration Bounds for Stochastic Approximation with Applications to Reinforcement Learning

  • Speaker: Mr. Gugan Thoppe
  • Date and Time: Thursday, November 23, 2017, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Stochastic Approximation (SA) is useful when the aim is to find optimal points, or zeros of a function, given only its noisy estimates. In this talk, we will review our recent advances in techniques for SA analysis. This talk has four major parts. In the first part, we will see a motivating application of SA to network tomography. Also, we shall discuss the convergence of a novel stochastic Kaczmarz method. In the second part, we shall discuss a novel tool based on the Alekseev's formula to obtain the rate of convergence of a nonlinear SA to a specific solution, given that there are multiple locally stable solutions. In the third part, we shall extend the previous tool to the two timescale but linear SA setting. We shall also discuss how this tool applies to gradient Temporal Difference (TD) methods such as GTD(0), GTD2, and TDC used in reinforcement learning. For the analyses in the second and third parts to hold, the initial step size must be chosen sufficiently small, depending on unknown problem-dependent parameters. This is often impractical. In the fourth part, we shall discuss a trick to obviate this in context of the one timescale, linear TD(0) method. We strongly believe that this trick is generalizable. We also provide here a novel expectation bound. We shall end with some future directions.

Speaker Bio:
Gugan Thoppe did his Ph.D. in Systems Science under Prof. Vivek Borkar at TIFR, Mumbai, INDIA. His work won the TAA-Sasken best thesis award for 2017. He is also a two time recipient of the IBM Ph.D. fellowship award (2013–14) and (2014-15). He recently finished a two year postdoc position with Prof. Robert Adler at the Technion, Haifa, ISRAEL. From December, he will starting another postdoc with Prof. Sayan Mukherjee at Duke University, North Carolina, USA. His research interests include stochastic approximation and its applications to learning algorithms, and stochastic algebraic topology.

Host Faculty: Prof. Shalabh Bhatnagar

Video Archive Go Top

 

Series: Department Seminar
Title: Accountability for Social Values in Data-Driven Systems

  • Speaker: Prof. Anupam Datta
                   Carnegie Mellon University
                   USA
  • Date and Time: Wednesday, November 22, 2017, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Our vision is to enable data-driven systems to be accountable for social values, such as privacy and fairness. We use the term “accountable” to refer to computational mechanisms that can be used to “account for” behaviors of systems to support detection of privacy and fairness violations, as well as explain how they came about. We then leverage this understanding to repair systems and carefully account for the absence of violations.

As an illustration of this paradigm, I will introduce a notion of proxy non-discrimination and methods for making machine learning models accountable for this property. A key building block for these notions is Quantitative Input Influence -- a form of explanation for decisions of machine learning models. This work is motivated by recent discoveries of unfairness or bias in widely used data-driven systems, including our own work that discovered gender bias in the targeting of job-related ads in the Google advertising ecosystem.

The talk is based on results with colleagues at CMU published at the 2016 IEEE Symposium on Security and Privacy and the 2017 ACM Conference on Computer and Communications Security.

Speaker Bio:
Anupam Datta is an Associate Professor (with tenure) at Carnegie Mellon University where he holds a primary appointment in the Electrical and Computer Engineering Department and a courtesy appointment in the Computer Science Department. His research area is security and privacy, with an emphasis on bridging theory and practice. Datta's current focus is on information accountability: foundations and tools that can be used to provide oversight of complex information processing ecosystems (including big data systems) to examine whether they respect privacy, and other desirable values in the personal data protection area, such as fairness and transparency. His research group produced the first complete logical specification and audit of all disclosure-related clauses of the HIPAA Privacy Rule for healthcare privacy. His group's work with Microsoft Research produced the first automated privacy compliance analysis of the production code of an Internet-scale system -- the big data analytics pipeline for Bing, Microsoft's search engine. Datta has also made significant contributions to the research area of compositional security. Specifically, his work led to new principles for securely composing cryptographic protocols and their application to several protocol standards, most notably to the IEEE 802.11i standard for wireless authentication and to attestation protocols for trusted computing. Datta has authored a book and over 50 other publications on these topics. He serves as an Editor-in-Chief of Foundations and Trends in Privacy and Security, an Associate Editor of the Journal of Computer Security and the Journal of Computer and System Sciences, as well as the 2013-14 Program Co-Chair of the IEEE Computer Security Foundations Symposium. Datta obtained Ph.D. (2005) and M.S. (2002) degrees from Stanford University and a B.Tech. (2000) from IIT Kharagpur, all in Computer Science.

Host Faculty: Prof. Vinod Ganapathy

Video Archive Go Top

 

Series: M.Sc. (Engg) Colloquium
Title: Checking Observational Purity of Procedures

  • Speaker: Himanshu Arora
  • Faculty Advisor: K. V. Raghavan
  • Date and Time: Monday, November 20, 2017, 4:00 PM
  • Venue: CSA Conference Room (Room No. 225, First Floor)

Abstract
We provide two static analysis (using theorem proving) that check if a given (recursive) pro- cedure behaves as if it were stateless, even when it maintains state in global variables. In other words, we check if the given procedure behaves like a mathematical function. In order to eliminate the need for manual annotations, we define a syntactic invariant that represents the reachable global states in all runs of the program. This syntactic invariant makes use of function symbols, which aids in automated construction of the invariant. The two static analysis are an existential checker and an impurity witness checker. The impurity witness checker outputs a formula whose unsatisfiability implies that the procedure is observationally pure. Whereas, the existential checker outputs a formula that constrains the definition of the function that the given procedure may implement. Satisfiability of the formula generated by the existential checker implies that the given procedure is observationally pure. The impurity witness approach works better (empirically) with SMT solvers, whereas the existential approach is more precise on paper. We illustrate our work on examples such as matrix chain multiplication. Examples such as these are not addressable by related techniques in the literature. The closest work to our is by Barnett et al.; this work cannot handle procedures with self recursion. We prove both our approaches to be sound. We have implemented the two static analyses using the Boogie framework and the Z3 SMT solver, and have evaluated our implementation on a number of examples.

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Feature Selectio n under Multicollinearity & Causal Inference on Ti me Series

  • Speaker: Mr. Indranil Bhattacharya
                   M.Sc. student
                   Dept. of CSA
  • Faculty Advisor: Dr. Arnab Bhattacharyya
  • Date and Time: Monday, November 20, 2017, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In this work, we study and extend algorithms for Sparse Regression and Causal Inference problems. Both the problems are fundamental in the area of Data Science.

The goal of regression problem is to find out the “best” relationship between an output variable and input variables, given samples of the input and output values. We consider sparse regression under a highdimensional linear model with strongly correlated variables, situations which cannot be handled well using many existing model selection algorithms. We study the performance of the popular feature selection algorithms such as LASSO, Elastic Net, BoLasso, Clustered Lasso as well as Projected Gradient Descent algorithms under this setting in terms of their running time, stability and consistency in recovering the true support. We also propose a new feature selection algorithm, BoPGD, which cluster the features first based on their sample correlation and do subsequent sparse estimation using a bootstrapped variant of the projected gradient descent method with projection on the non-convex L 0 ball. We attempt to characterize the efficiency and consistency of our algorithm by performing a host of experiments on both synthetic and real world datasets.

Discovering causal relationships, beyond mere correlation, is widely recognized as a fundamental problem. The Causal Inference problems use observations to infer the underlying causal structure of the data generating process. The input to these problems is either a multivariate time series or i.i.d sequences and the output is a Feature Causal Graph where the nodes correspond to the variables and edges capture the direction of causality. For high dimensional datasets, determining the causal relationships becomes a challenging task because of the curse of dimensionality. Graphical modeling of temporal data based on the concept of “Granger Causality” has gained much attention in this context. The blend of Granger methods along with model selection techniques, such as LASSO, enables efficient discovery of a “sparse” subset of causal variables in high dimensional settings. However, these temporal causal methods use an input parameter, L, the maximum time lag. This parameter is the maximum gap in time between the occurrence of the output phenomenon and the causal input stimulus. However, in many situations of interest, the maximum time lag is not known, and indeed, finding the range of causal effects is an important problem. In this work, we propose and evaluate a data-driven and computationally efficient method for Granger causality inference in the Vector Auto Regressive (VAR) model without foreknowledge of the maximum time lag. We present two algorithms Lasso Granger++ and Group Lasso Granger++ which not only constructs the hypothesis feature causal graph, but also simultaneously estimates a value of maxlag ( Lˆ ) for each variable by balancing the trade-off between “goodness of fit” and “model complexity".

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Large Scale Graph Processing in a Distributed Environment

  • Speaker: Mr.Nitesh Chandra Upadhyay
                   M.Sc. (Engg) Student
                   Dept of CSA
                   IISc
  • Faculty Advisor: Prof. Y.N. Srikant
  • Date and Time: Monday, November 20, 2017, 12:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Graph algorithms are ubiquitously used across domains. They exhibit parallelism, which can be exploited on parallel architectures, such as, multi-core processors and accelerators. However, real world graphs are massive in size and cannot fit into the memory of a single machine. Such large graphs are partitioned and processed in a distributed cluster environment which consist of multiple GPUs and CPUs.

Existing frameworks that facilitate large scale graph processing in the distributed cluster have their own style of programming and require extensive involvement by the user in communication and synchronization aspects. Adaptation of these frameworks appears to be an overhead for a programmer. Furthermore, these frameworks have been developed to target only CPU clusters and lack the ability to harness the GPU architecture.

We provide a back-end framework to the graph Domain Specific Language, Falcon, for large scale graph processing on CPU and GPU clusters. The Motivation behind choosing this DSL as a front-end is its shared-memory based imperative programmability feature. Our framework generates Giraph code for CPU clusters. Giraph code runs on the Hadoop cluster and is known for scalable and fault-tolerant graph processing. For GPU cluster, Our framework applies a set of optimizations to reduce computation and communication latency, and generates efficient CUDA code coupled with MPI.

Experimental evaluations show the scalability and performance of our framework for both CPU and GPU clusters. The performance of the framework generated code is comparable to the manual implementations of various algorithms in distributed environments

Video Archive Go Top

 

PAST SEMINARS

Series: Department Seminar
Title: Actively Secure Garbled Circuits with Constant Communication Overhead in the Plain Model

  • Speaker: Dr. Carmit Hazay
                   Senior Lecturer
                   Computer Engineering Department
                   Bar-Ilan University
                   Israel
  • Date and Time: Wednesday, November 15, 2017, 11:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
We consider the problem of constant-round secure two-party computation in the presence of active (malicious) adversaries. We present the first protocol that has only a constant multiplicative communication overhead compared to Yao's protocol for passive adversaries and can be implemented in the plain model by only making a black-box use of (parallel) oblivious transfer and a pseudo- random generator. This improves over the polylogarithmic overhead of the previous best protocol. A similar result could previously be obtained only in an amortized setting, using preprocessing, or by assuming bit-oblivious-transfer as an ideal primitive that has a constant cost. We present two variants of this result, one which is aimed at minimizing the number of oblivious transfers and another which is aimed at optimizing concrete efficiency. Our protocols are based on a novel combination of previous techniques together with a new efficient protocol to certify that pairs of strings transmitted via oblivious transfer satisfy a global relation. The communication complexity of the second variant of our protocol can beat the best previous protocols even for realistic values of the circuit size and the security parameter. This variant is particularly attractive in the offline-online setting, where the online cost is dominated by a single evaluation of an authenticated garbled circuit, and can also be made non-interactive using the Fiat-Shamir heuristic. This is a joint work with Yuval Ishai and Muthuramakrishnan Venkitasubramaniam.

Speaker Bio:
Carmit Hazay is a Senior Lecturer in the Computer Engineering Department, Bar-Ilan University, Israel. In 2009 she completed her Ph.D. studies at Bar-Ilan University and started her post-doctoral training at Weizmann Institute of Science and IDC (2009-2010) and at Aarhus University, Denmark (2010-2012). She joined the Faculty of Engineering at Bar-Ilan University in October 2012.

Host Faculty: Dr. Arpita Patra

Video Archive Go Top

 

Series: Ph.D. Colloquium
Title: Developing Software Tools using Dynamic Program Analysis

  • Speaker: Ms.Monika Dhok
                   Ph.D student
                   Dept. of CSA
                   IISc
  • Faculty Advisor: Prof. K Gopinath
  • Date and Time: Tuesday, November 14, 2017, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Software development process consists of many stages like design, implementation, and testing. Programmers' intuition and expertise play a vital role in the success of these stages. Therefore, various tools have been developed that assist programmers by automating their tasks. Program analysis, the process of analyzing program behavior by examining its source code or execution, forms the basis of such software tools. We identify and address following three research gaps in the area of program analysis. Type-awareness in concolic testing Software testing is a widely used dynamic program analysis technique. Various automated test generation techniques have been proposed as manually writing effective test suite is challenging. Concolic testing is one such technique that outputs a test suite for the given program with the intent of maximizing code coverage. This technique is very effective for statically typed languages. We show that applying concolic testing to dynamically typed JS programs causes generation of a large number of test cases that explore paths and types of the variables repeatedly. We propose an effective approach that scales concolic testing by incorporating type-awareness. Our experimental results show that adapting type-aware concolic testing is as effective as conventional concolic testing in detecting bugs and achieving coverage, even with a small percentage of test cases.

Test synthesis to detect redundant traversal bugs Test generation techniques like concolic testing focus on verifying the functional correctness of the program. Performance testing, on the other hand, verifies the software efficiency. Our second work focuses on automated performance testing in the context of redundant traversal bugs. Such bugs occur when program fragment performs repetitive computations across loop iterations. Various static and dynamic analysis techniques have been proposed to detect such bugs automatically. However, while the effectiveness of dynamic analyses is dependent on input test cases, static analyses are less useful in validating the presence of this problem. We propose an approach to generate tests for exposing redundant traversal of loops automatically. Our experiments reveal the effectiveness of our approach in generating 224 tests that reveal 46 bugs across seven Java libraries, including 34 previously unknown bugs.

Performance hints for stable multithreaded systems Assuring correctness and efficiency of sequential programs is easier as compared to multithreaded programs. This is mainly because the execution of multithreaded programs depends not only on the input but also on thread interleavings. Stable multithreaded systems restrict the set of possible schedules such that schedule remains unaffected for the given input. This eases the process of bug reproduction and thereby guaranteeing correctness. However, the determinism imposed in these systems can serialize the schedule resulting into performance degradation. Our third work focuses on automatically deriving performance hints so that such serialization can be avoided. Our experimental results demonstrate that we are able to reduce the overall execution time of programs by up to 34% when compared to the execution time where performance hints are inserted manually.

Video Archive Go Top

 

Series: Department Seminar
Title: Approximation Algorithms for Stochastic k-TSP

  • Speaker: Dr. Rishi Saket
                   Researcher
                   IMB Research
                   Bangalore
  • Date and Time: Friday, October 27, 2017, 5:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
This paper studies the Stochastic k-TSP problem: the stochastic variant of the classical k-TSP problem where rewards at the vertices are independent random variables which are instantiated upon the tour's visit. The objective is to minimize the expected length of a tour that collects reward at least k. The solution is a policy describing the tour which may (adaptive) or may not (non-adaptive) depend on the observed rewards. Our work presents an adaptive O(log k)-approximation algorithm for Stochastic k-TSP, along with a non-adaptive O(log^2 k)-approximation algorithm which also upper bounds the adaptivity gap by O(log^2 k). We also show that the adaptivity gap of Stochastic k-TSP is at least e, even in the special case of stochastic knapsack cover. The talk shall give an overview of the main results and focus mostly on describing the adaptive algorithm.

Joint work with Alina Ene (Boston University) and Viswanath Nagarajan (University of Michigan)

Host Faculty: Dr. Anand Louis

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: Generalizations of Hitting, Covering and Packing Problems on Intervals

  • Speaker: Mr. Datta Krupa R
                   M.Sc. Student
                   Dept. of CSA
  • Faculty Advisor: Prof. Sathish Govindarajan
  • Date and Time: Friday, October 27, 2017, 10:00 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Interval graphs are well-studied structures. Intervals can represent resources like jobs to be scheduled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of non-conflicting jobs on the computer. Most optimization problems on interval graphs like the independent set, vertex cover, dominating set, maximum clique, etc can be solved efficiently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been extensively studied in the last few decades and have applications in diverse areas. While they are NP-hard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generalizations of hitting, covering and packing problems for intervals. For the general setting, we model the problems as min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms.

Demand-hitting problem which is a generalization of hitting problem is defined as follows: Given n intervals, a positive integer demand for every interval, m points, a real weight for every point, select a subset of points H, such that every interval contains at least its demand many points from H and sum of the weight of points in H minimized. When demands of intervals are one we give dynamic programming based O(m+n) time algorithm assuming that intervals and points are sorted. When demands are same, (say k), we give O(m^2*n) time flow-based algorithm. For the general case, we make an assumption that no interval is contained in another interval. Under this assumption, we give O(m^2*n) time flow-based algorithm.

Demand-covering problem which is a generalization of covering problem is defined as follows: Given n intervals, a real weight for every interval, m points, a positive integer demand for every point, select a subset of intervals C, such that every point is contained in at least its demand many intervals from C and sum of the weight of intervals in C minimized. When demand of points are one, we give dynamic programming based O(m+n log n) time algorithm. When demands are same, (say k) we give O(m*n^2) time flow based algorithm. For the general case, we give O(m*n^2) time flow based algorithm.

k-pack points problem which is a generalization of packing problem is defined as follows: Given n intervals, an integer k, m points, a real weight for every point, select a subset of points Y, such that every interval contains at most k points from Y and sum of the weight of points in Y is maximized. For k-pack points problem, we give O(m^2 log m) time flow based algorithm to solve it assuming intervals and points are sorted.

Video Archive Go Top

 

Series: CSA Distinguished Lecture
Title: Beating Floating Point at its Own Game: Posit Arithmetic

  • Speaker: Prof. John L. Gustafson
                   National University of Singapore
  • Date and Time: Thursday, October 26, 2017, 4:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
A new data type called "posit" is designed as a direct drop-in replacement for IEEE Standard 754 floating-point numbers (floats). Unlike earlier forms of universal number (unum) arithmetic, posits do not require interval arithmetic or variable size operands; like floats, they round if an answer is inexact. However, they provide compelling advantages over floats, including larger dynamic range, higher accuracy, better closure, bitwise identical results across systems, simpler hardware, and simpler exception handling. Posits never overflow to infinity or underflow to zero, and Not-a-Number (NaN) indicates an action instead of a bit pattern. A posit processing unit takes less circuitry than an IEEE float FPU. With lower power use and smaller silicon footprint, the posit operations per second (POPS) supported by a chip can be significantly higher than the FLOPS using similar hardware resources. GPU accelerators and Deep Learning processors, in particular, can do more per watt and per dollar with posits, yet deliver superior answer quality.

A comprehensive series of benchmarks compares floats and posits for decimals of accuracy produced for a set precision. Low precision posits provide a better solution than approximate computing methods that try to tolerate decreased answer quality. High precision posits provide more correct decimals than floats of the same size; in some cases, a 32-bit posit may safely replace a 64-bit float. In other words, posits beat floats at their own game.

Speaker Bio:
Dr. John L. Gustafson is an applied physicist and mathematician who is a Visiting Scientist at A-STAR and Professor at NUS. He is a former Director at Intel Labs and former Chief Product Architect at AMD. A pioneer in high-performance computing, he introduced cluster computing in 1985 and first demonstrated scalable massively parallel performance on real applications in 1988. This became known as Gustafson's Law, for which he won the inaugural ACM Gordon Bell Prize. He is also a recipient of the IEEE Computer Society's Golden Core Award.

Host Faculty: Prof. R. Govindarajan

Video Archive Go Top

 

Series: Mathematical Foundations of Data Science
Title: Lectures on Mathematical Foundations of Data Science

  • Speaker: Prof. Ravi Kannan
  • Date and Time: Monday, October 23, 2017, 3:30 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
This is a series of 12 tutorial lectures spread over 4 weeks on Mathematical Foundations of Data Science. The lectures will primarily focus on 1) High Dimensional geometry 2) Best fit subspaces and SVD Who should attend: PhD students, 2nd year MTech students Lecture Days: Monday- Wednesday-Friday Time: 3:30-4:30 Venue: 254 CSA Dept Start Date: 23rd Oct. The material will be based on a textbook currently being co-authored by Ravi Kannan, Avrim Blum and John Hopfcroft, copies will be made available.

Speaker Bio:
Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science. https://en.wikipedia.org/wiki/Ravindran_Kannan

Host Faculty: Chiranjib Bhattacharyya

Video Archive Go Top

 

Series: Department Seminar
Title: Evidence of non-Gaussianity in the Cosmic Microwave Background & Visualizing Cosmic Structures

  • Speaker: Dr. Pratyush Pranav
                   Technion, Israel
  • Date and Time: Monday, October 09, 2017, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The standard cosmological paradigm asserts that the Universe underwent a phase of rapid inflation moments after it's birth. In the simplest form, inflationary theories predict the spectrum of the fluctuation of matter distribution to be Gaussian distributed. Consequently, deviations from Gaussianity, if found, will point to novel physics driving the early phase of the Universe. In this talk, I will present an evidence of non-Gaussianity in the CMB, through new topological methods.

In a related aspect, as the universe evolves, the initial small perturbations in the matter distribution in the Universe give rise to the structures like galaxies and groups of galaxies, woven into a three dimensional web like network. Understanding the properties of this Cosmic Web is crucial to understanding the nature of the matter distribution. Visualizing these cosmic structures plays a crucial role in this effort. In an ongoing collaboration with Prof. Natarajan's visualization lab, we have developed visualization software based on topological methods. I will briefly describe the methodology and some results, with a view to develop this further.

Speaker Bio:
PP obtained his B.Sc. at St. Stephens college Delhi University, and the M.S. degree at IISc. There after he moved to the Kapteyn Astronomical Institute, Groningen , the Netherlands, to obtain a PhD. Currently he is in a transition, finishing his postdoctoral at Technion, Israel and starting the second one at Ecole Normale Superiure in Lyon, France.

Host Faculty: Prof. Vijay Natarajan

Video Archive Go Top

 

Series: Ph.D. Thesis Defense
Title: Optimization Algorithms for Deterministic, Stochastic and Reinforcement Learning Settings

  • Speaker: Mr. Ajin George Joseph
  • Faculty Advisor: Prof. Shalabh Bhatnagar
  • Date and Time: Thursday, October 05, 2017, 2:30 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Optimization is a very important field with diverse applications in physical, social and biological sciences and in various areas of engineering. It appears widely in machine learning, information retrieval, regression, estimation, operations research and a wide variety of computing domains. The subject is being deeply studied both theoretically and experimentally and several algorithms are available in the literature. These algorithms which can be executed (sequentially or concurrently) on a computing machine explore the space of input parameters to seek high quality solutions to the optimization problem with the search mostly guided by certain structural properties of the objective function. In certain situations, the setting might additionally demand for ``absolute optimum'' or solutions close to it, which makes the task even more challenging.

In this thesis, we propose an optimization algorithm which is ``gradient-free'', i.e., does not employ any knowledge of the gradient or higher order derivatives of the objective function, rather utilizes objective function values themselves to steer the search. The proposed algorithm is particularly effective in a black-box setting, where a closed-form expression of the objective function is unavailable and gradient or higher-order derivatives are hard to compute or estimate. Our algorithm is inspired by the well known cross entropy (CE) method. The CE method is a model based search method to solve continuous/discrete multi-extremal optimization problems, where the objective function has minimal structure. The proposed method seeks, in the statistical manifold of the parameters which identify the probability distribution/model defined over the input space to find the degenerate distribution concentrated on the global optima (assumed to be finite in quantity). In the early part of the thesis, we propose a novel stochastic approximation version of the CE method to the unconstrained optimization problem, where the objective function is real-valued and deterministic. The basis of the algorithm is a stochastic process of model parameters which is probabilistically dependent on the past history, where we reuse all the previous samples obtained in the process till the current instant based on discounted averaging. This approach can save the overall computational and storage cost. Our algorithm is incremental in nature and possesses attractive features such as stability, computational and storage efficiency and better accuracy. We further investigate, both theoretically and empirically, the asymptotic behaviour of the algorithm and find that the proposed algorithm exhibits global optimum convergence for a particular class of objective functions.

Further, we extend the algorithm to solve the simulation/stochastic optimization problem. In stochastic optimization, the objective function possesses a stochastic characteristic, where the underlying probability distribution in most cases is hard to comprehend and quantify. This begets a more challenging optimization problem, where the ostentatious nature is primarily due to the hardness in computing the objective function values for various input parameters with absolute certainty. In this case, one can only hope to obtain noise corrupted objective function values for various input parameters. Settings of this kind can be found in scenarios where the objective function is evaluated using a continuously evolving dynamical system or through a simulation. We propose a multi-timescale stochastic approximation algorithm, where we integrate an additional timescale to accommodate the noisy measurements and decimate the effects of the gratuitous noise asymptotically. We found that if the objective function and the noise involved in the measurements are well behaved and the timescales are compatible, then our algorithm can generate high quality solutions.

In the later part of the thesis, we propose algorithms for reinforcement learning/Markov decision processes using the optimization techniques we developed in the early stage. MDP can be considered as a generalized framework for modeling planning under uncertainty. We provide a novel algorithm for the problem of prediction in reinforcement learning, emph{i.e.}, estimating the value function of a given stationary policy of a model free MDP (with large state and action spaces) using the linear function approximation architecture. Here, the value function is defined as the long-run average of the discounted transition costs. The resource requirement of the proposed method in terms of computational and storage cost scales quadratically in the size of the feature set. The algorithm is an adaptation of the multi-timescale variant of the CE method proposed in the earlier part of the thesis for simulation optimization. We also provide both theoretical and empirical evidence to corroborate the credibility and effectiveness of the approach.

In the final part of the thesis, we consider a modified version of the control problem in a model free MDP with large state and action spaces. The control problem most commonly addressed in the literature is to find an optimal policy which maximizes the value function, i.e., the long-run average of the discounted transition payoffs. The contemporary methods also presume access to a generative model/simulator of the MDP with the hidden premise that observations of the system behaviour in the form of sample trajectories can be obtained with ease from the model. In this thesis, we consider a modified version, where the cost function to be optimized is a real-valued performance function (possibly non-convex) of the value function. Additionally, one has to seek the optimal policy without presuming access to the generative model. In this thesis, we propose a stochastic approximation algorithm for this peculiar control problem. The only information, we presuppose, available to the algorithm is the sample trajectory generated using a priori chosen behaviour policy. The algorithm is data (sample trajectory) efficient, stable, robust as well as computationally and storage efficient. We provide a proof of convergence of our algorithm to a high performing policy relative to the behaviour policy.

Video Archive Go Top

 

Series: Department Seminar
Title: Reachability for dynamic parametric processes

  • Speaker: Prof. Helmut Seidl,
                   Technical University of Munich
  • Date and Time: Wednesday, September 27, 2017, 3:30 PM
  • Venue: CSA Lecture Hall (Room No. 117, Ground Floor)

Abstract
In a dynamic parametric process every subprocess may spawn arbitrarily many, identical child processes, that may communicate either over global variables, or over local variables that are shared with their parent. We show that reachability for dynamic parametric processes is decidable under mild assumptions. These assumptions are met if individual processes are realized by pushdown systems, or even higher-order pushdown systems. We also provide algorithms for subclasses of pushdown dynamic parametric processes, with complexity ranging between NP and DEXPTIME.

These results are based on joint work with Anca Muscholl and Igor Walukiewicz.

Speaker Bio:
Helmut Seidl is a Professor at the Institute for Informatics, at the Technical University of Munich, Germany. His research interests include Program Analysis, Semi-Structured Data, and Tree Automata.

Host Faculty: Prof. Deepak D Souza

Video Archive Go Top

 

Series: Ph.D. Colloquium
Title: Deep Learning with Minimal Supervision

  • Speaker: Mr. Gaurav Pandey
                   Ph.D student
                   Dept. of CSA
  • Faculty Advisor: Prof. Ambedkar Dukkipati
  • Date and Time: Tuesday, September 26, 2017, 12:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In recent years, deep neural networks have achieved extraordinary performance on supervised learning tasks. Convolutional neural networks (CNN) have vastly improved the state of the art for most computer vision tasks including object recognition and segmentation. However, their success relies on the presence of a large amount of labeled data. In contrast, relatively fewer work has been done in deep learning to handle scenarios when access to ground truth is limited, partial or completely absent. In this thesis, we propose some deep neural network models to handle challenging problems with limited labeled information.

Our first contribution is a neural architecture that allows for the extraction of infinitely many features from an object while allowing for tractable inference. This is achieved by using the `kernel trick', that is, we express the inner product in the infinite dimensional feature space as a kernel. The kernel can either be computed exactly for single layer feedforward networks, or approximated by an iterative algorithm for deep convolutional networks. The corresponding models are referred to as stretched deep networks (SDN). We show that when the amount of training data is limited, SDNs with random weights drastically outperform fully supervised CNNs with similar architectures.

While SDNs perform reasonably well for classification with limited labeled data, they can not utilize unlabeled data which is often much easier to obtain. A common approach to utilize unlabeled data is to couple the classifier with an autoencoder (or its variants) thereby minimizing reconstruction error in addition to the classification error. We discuss the limitations of decoder-based architectures and propose a model that allows for the utilization of unlabeled data without the need of a decoder. This is achieved by jointly modeling the distribution of data and latent features in a manner that explicitly assigns zero probability to unobserved data. The joint probability of the data and the latent features is maximized using a two step EM-like procedure. Depending on the task, we allow the latent features to be one-hot or real-valued vectors and define a suitable prior on the features. For instance, one-hot features correspond to class labels and are directly used for the unsupervised and semi-supervised classification task, whereas real-valued feature vectors are fed as input to simple classifiers for auxiliary supervised discrimination tasks. The proposed model, which we refer to as discriminative encoder (or DisCoder), is flexible in the type of latent features that it can capture. The proposed model achieves state-of-the-art performance on several challenging datasets.

Having addressed the problem of utilizing unlabeled data for classification, we move to a domain where obtaining labels is a lot more expensive, that is, semantic image segmentation. Explicitly labeling each pixel of an image with the object that the pixel belongs to, is an expensive operation, in terms of time as well as effort. Currently, only a few classes of images have been densely (pixel-level) labeled. Even among these classes, only a few images per class have pixel-level supervision. Models that rely on densely-labeled images, can not utilize a much larger set of weakly annotated images available on the web. Moreover, these models can not learn the segmentation masks for new classes, where there is no densely labeled data.

Hence, we propose a model for utilizing weakly-labeled data for semantic segmentation of images. This is achieved by generating fake labels for each image, while simultaneously forcing the output of the CNN to satisfy the mean-field constraints imposed by a conditional random field. We show that one can enforce the CRF constraints by forcing the distribution at each pixel to be close to the distribution of its neighbors. The proposed model is very fast to train and achieves state-of-the-art performance on the popular VOC-2012 dataset for the task of weakly supervised semantic image segmentation.

Video Archive Go Top

 

Series: Department Seminar
Title: SOPER : Discovering the Influence of Fashion and the Many Faces of User from Session Logs using Stick Breaking Process

  • Speaker: Ms. Lucky Dhakad
                   Flipkart
  • Date and Time: Monday, September 25, 2017, 2:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
Recommending lifestyle articles is of immediate interest to the e-commerce industry and is beginning to attract research attention. Often followed strategies, such as recommending popular items are inadequate for this vertical because of two reasons. Firstly, users have their own personal preference over items, referred to as personal styles, which lead to the long-tail phenomenon. Secondly, each user displays multiple personas, each persona has a preference over items which could be dictated by a particular occasion, e.g. dressing for a party would be different from dressing to go to office. Recommendation in this vertical is crucially dependent on discovering styles for each of the multiple personas. There is no literature which addresses this problem.

We posit a generative model which describes each user by a Simplex Over PERsona, SOPER, where a persona is described as the individuals preferences over prevailing styles modeled as topics over items. The choice of simplex and the long-tail nature necessitates the use of stick-breaking process. The main technical contribution is an efficient collapsed Gibbs sampling based algorithm for solving the attendant inference problem.

Trained on large-scale interaction logs spanning more than half-a-million sessions collected from an e-commerce portal, SOPER out-performs previous baselines by a large margin of 35% in identifying persona. Consequently it outperforms several competitive baselines comprehensively on the task of recommending from a catalogue of roughly 150 thousand lifestyle articles, by improving the recommendation quality as measured by AUC by a staggering 12.23%, in addition to aiding the interpretability of uncovered personal and fashionable styles thus advancing our precise understanding of the underlying phenomena.

Speaker Bio:
Lucky Dhakad completed her ME from CSA, IISc in 2016 and is presently working with Flipkart. *This is a practice talk for CIKM 2017*

Host Faculty: Prof. Chiranjib Bhattacharyya

Video Archive Go Top

 

Series: M.Sc. (Engg) Thesis Defense
Title: A Study of Thompson Sampling Approach for Sleeping Multi-Armed Bandit Problems

  • Speaker: Mr. Aritra Chatterjee
                   M.Sc. (Engg) Student
                   Dept of CSA
                   IISc
  • Faculty Advisor: Prof. Y. Narahari
  • Date and Time: Monday, September 25, 2017, 11:30 AM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
The Multi-armed bandit (MAB) problem provides a convenient abstraction for many online learning problems arising in modern applications including Internet advertising, crowdsourcing, online procurement, smart grids, etc. Several variants of the MAB problem have been proposed to extend the basic model to a variety of practical and general settings. The sleeping multi-armed (S-MAB) problem is one such variant where the subset of available arms varies with time. This study is focused on analyzing the efficacy of the Thompson Sampling algorithm for solving the S-MAB problem.

Any algorithm for the classical MAB problem is expected to choose one of K available arms (actions) in each of T consecutive rounds. Each choice of an arm generates a stochastic reward from an unknown but fixed distribution. The goal of the algorithm is to maximize the expected sum of rewards over the T rounds (or equivalently minimize the expected total regret), relative to the best-fixed action in hindsight. In many of these settings, however, not all arms may be available in any given round. For example, in Internet advertising, some advertisers might choose to stay away from the auction due to budget constraints; in crowdsourcing, some workers may not be available at a given time due to timezone difference, etc. This implies that the algorithm needs to work only with the set of available arms. Further, unlike in the classical setting, the performance of an algorithm can no longer be evaluated relative to the best-fixed arm in hindsight; the regret is now to be measured relative to the best "available" arm in hindsight. One possible way is to compute the overall regret as the worst-case regret over all possible sample paths of availabilities (that is, under adversarial selection of available arms).

In the literature, upper confidence bound (UCB)-based approaches have been proposed and investigated for the S-MAB problem. Our contribution is to investigate a Thompson sampling-based approach. Our key finding is to establish a logarithmic regret bound, which non-trivially generalizes a similar bound known for this approach in the classical MAB setting. Our bound also matches (up to constants) the best-known lower bound for the S-MAB problem. And, we show via detailed simulations, that the Thompson Sampling approach, in fact, outperforms the known algorithms for the S-MAB problem.

Video Archive Go Top

 

Series: Department Seminar
Title: Maliciously Secure Oblivious Linear Function Evaluation with Constant Overhead

  • Speaker: Mr. Satrajit Ghosh
                   PhD Student
                   Cryptography and Security Group
                   Aarhus University
                   Denmark
  • Date and Time: Thursday, September 21, 2017, 3:00 PM
  • Venue: CSA Seminar Hall (Room No. 254, First Floor)

Abstract
In this work we consider the problem of oblivious linear function evaluation (OLE). OLE is a special case of oblivious polynomial evaluation (OPE) and deals with the oblivious evaluation of a linear function $f(x)=ax+b$. This problem is non-trivial in the sense that the sender chooses $a,b$ and the receiver $x$, but the receiver may only learn $f(x)$. We present a highly efficient and UC-secure construction of OLE in the OT-hybrid model that requires only $O(1)$ OTs per OLE. The construction is based on noisy encodings introduced by Naor and Pinkas (STOC'99) and used for passive secure OLE's by Ishai, Prabhakaran and Sahai (TCC'09). A result asymptotically similar to ours is known by applying the IPS compiler to the mentioned passive secure OLE protocol, but our protocol provides better constants and would be considerably simpler to implement. Concretely we use only $16$ OTs to generate one active secure OLE, and our protocol achieves active security by adding fairly simple checks to the passive secure protocol. We therefore believe our protocol takes an important step towards basing practical active-secure arithmetic computations on OLEs. Our result requires novel techniques that might be of independent interest. As an application we present the currently most efficient OPE construction.

Speaker Bio:
Satrajit Ghosh is doing his PhD at Cryptography and Security Group, Aarhus University, Denmark under supervision of Jesper Buus Nielsen and Claudio Orlandi. He did his Masters from the Computer Science and Engineering Department, IIT Kharagpur under the guidance of Dr. Abhijit Das. Prior to that, he did his B.Tech in Computer Science and Engineering and B.Sc (Honors) in Physics from University of Calcutta. Before joining Aarhus University, he also worked as researcher at the R. C. Bose Centre of Cryptology and Security, Indian Statistical Institute, Kolkata and in Saarland University, Germany.

Host Faculty: Dr. Arpita Patra

Video Archive Go Top

 

 

 

 

 

 

 

 

 

 

Copyright: CSA, IISc 2017      Phone: +91-80-22932368          Fax: +91-80-23602911 Travel Blog    Feedback    Credits