Synapse

Monthly Newsletter from CNI

Issue - September 2024

Join us at the upcoming talk on "Locality Sensitive Hashing in Fourier Frequency Domain For Soft Set Containment Search" by Prof. Abir De, IIT Bombay on 17/09/2024.

Join us at the upcoming talk on “Flipped Huber: A new additive noise mechanism  for differential privacy” by  Prof. Sheetal Kalyani, from IIT Bombay on 24/09/2024.

Welcome to the 2024 batch of CNI Scholars!!

We’re thrilled to welcome the 2024 batch of CNI Scholars to our community! This year's group brings an incredible mix of talent, enthusiasm, and fresh ideas, and we can’t wait to see the impact you'll make.  Here’s to new beginnings, collaborations, and all the exciting discoveries ahead!

Introducing the CNI Podcast: Stay Tuned!

We’re excited to announce that we’re preparing to launch a new podcast series featuring conversations with eminent researchers. This series will offer in-depth discussions on cutting-edge research, emerging trends, and innovative breakthroughs in networked systems and intelligence. Stay tuned as we finalize the details and look forward to sharing these engaging and insightful episodes with you soon!

Random Separating Hyperplane Theorem and Learning Polytopes

In this talk, Prof. Amit Kumar discussed a strengthened version of the classical separating hyperplane theorem, which states that for any point not in a closed convex set, there exists a hyperplane that separates the point and the convex set. The strengthened result applies specifically to polytopes and is used to identify the vertices of a polytope defined by an optimization oracle. This approach provides a general framework for learning polytopes in various hidden variable problems in machine learning, where optimization oracles are available.

Codes for (Un)Expected Loads

In this talk, Prof. Emina Soljanin discussed how distributed computing systems can efficiently handle data access requests using erasure coding. Erasure coding helps manage fluctuating data access patterns, especially in dynamic settings like edge computing, by providing robust and efficient storage. The talk introduced the concept of the access service rate region, a key metric for designing stable and efficient distributed systems under varying loads. The problems related to this metric extend existing ideas in coding theory and are tackled using combinatorial optimization and other mathematical tools.

Markov Chain Variance Estimation: A Stochastic Approximation Approach

In this talk, Dr. Shubhada Agrawal discussed a new approach to estimating the asymptotic variance of a function on a Markov chain, crucial for statistical inference of the stationary mean. The proposed recursive estimator requires minimal computation at each step, doesn’t need historical samples or run-length knowledge, and achieves an optimal convergence rate for mean-squared error. It improves on existing methods by addressing key limitations and extends to estimating covariance matrices and variances in larger state spaces. Applications include reinforcement learning, where the estimator helps model risk in safety-critical scenarios, and a new algorithm is introduced for policy evaluation. This work also opens the door to developing variance-constrained actor-critic algorithms in reinforcement learning.

Sample Efficient Constrained Reinforcement Learning with General Parametrized Policies

In this talk, Prof. Washim Uddin Mondal discussed recent work on developing a sample-efficient algorithm for Constrained Markov Decision Processes (CMDPs) with general parameterized policies. The framework allows for infinite state spaces and policies represented by neural networks, including tabular and linear CMDPs as special cases. The proposed Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) algorithm ensures both near-optimal rewards and constraints with a sample complexity that scales efficiently as constraints tighten. This approach significantly improves upon previous methods, narrowing the gap between theoretical lower and upper bounds.