Showing 1–44 of 44 results for author: Shetty, A

Weighted Sum of Segmented Correlation: An Efficient Method for Spectra Matching in Hyperspectral Images

Authors: Sampriti Soor, Priyanka Kumari, B. S. Daya Sagar, Amba Shetty

Abstract: Matching a target spectrum with known spectra in a spectral library is a common method for material identification in hyperspectral imaging research. Hyperspectral spectra exhibit precise absorption features across different wavelength segments, and the unique shapes and positions of these absorptions create distinct spectral signatures for each material, aiding in their identification. Therefore,… ▽ More Matching a target spectrum with known spectra in a spectral library is a common method for material identification in hyperspectral imaging research. Hyperspectral spectra exhibit precise absorption features across different wavelength segments, and the unique shapes and positions of these absorptions create distinct spectral signatures for each material, aiding in their identification. Therefore, only the specific positions can be considered for material identification. This study introduces the Weighted Sum of Segmented Correlation method, which calculates correlation indices between various segments of a library and a test spectrum, and derives a matching index, favoring positive correlations and penalizing negative correlations using assigned weights. The effectiveness of this approach is evaluated for mineral identification in hyperspectral images from both Earth and Martian surfaces. △ Less

Submitted 18 June, 2024; originally announced June 2024.

Comments: Accepted in IEEE IGARSS 2024 conference

Tolerant Algorithms for Learning with Arbitrary Covariate Shift

Authors: Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos, Arsen Vasilyan

Abstract: We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially adversarially generated test distribution. We focus on two frameworks: PQ learning [Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS 2020], allowing abstention on adversarially generated parts of the test distribution, a… ▽ More We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially adversarially generated test distribution. We focus on two frameworks: PQ learning [Goldwasser, A. Kalai, Y. Kalai, Montasser NeurIPS 2020], allowing abstention on adversarially generated parts of the test distribution, and TDS learning [Klivans, Stavropoulos, Vasilyan COLT 2024], permitting abstention on the entire test distribution if distribution shift is detected. All prior known algorithms either rely on learning primitives that are computationally hard even for simple function classes, or end up abstaining entirely even in the presence of a tiny amount of distribution shift. We address both these challenges for natural function classes, including intersections of halfspaces and decision trees, and standard training distributions, including Gaussians. For PQ learning, we give efficient learning algorithms, while for TDS learning, our algorithms can tolerate moderate amounts of distribution shift. At the core of our approach is an improved analysis of spectral outlier-removal techniques from learning with nasty noise. Our analysis can (1) handle arbitrarily large fraction of outliers, which is crucial for handling arbitrary distribution shifts, and (2) obtain stronger bounds on polynomial moments of the distribution after outlier removal, yielding new insights into polynomial regression under distribution shifts. Lastly, our techniques lead to novel results for tolerant testable learning [Rubinfeld and Vasilyan STOC 2023], and learning with nasty noise. △ Less

Submitted 4 June, 2024; originally announced June 2024.

SVFT: Parameter-Efficient Fine-Tuning with Singular Vectors

Authors: Vijay Lingam, Atula Tejaswi, Aditya Vavre, Aneesh Shetty, Gautham Krishna Gudur, Joydeep Ghosh, Alex Dimakis, Eunsol Choi, Aleksandar Bojchevski, Sujay Sanghavi

Abstract: Popular parameter-efficient fine-tuning (PEFT) methods, such as LoRA and its variants, freeze pre-trained model weights \(W\) and inject learnable matrices \(ΔW\). These \(ΔW\) matrices are structured for efficient parameterization, often using techniques like low-rank approximations or scaling vectors. However, these methods typically show a performance gap compared to full fine-tuning. Although… ▽ More Popular parameter-efficient fine-tuning (PEFT) methods, such as LoRA and its variants, freeze pre-trained model weights \(W\) and inject learnable matrices \(ΔW\). These \(ΔW\) matrices are structured for efficient parameterization, often using techniques like low-rank approximations or scaling vectors. However, these methods typically show a performance gap compared to full fine-tuning. Although recent PEFT methods have narrowed this gap, they do so at the cost of additional learnable parameters. We propose SVFT, a simple approach that fundamentally differs from existing methods: the structure imposed on \(ΔW\) depends on the specific weight matrix \(W\). Specifically, SVFT updates \(W\) as a sparse combination of outer products of its singular vectors, training only the coefficients (scales) of these sparse combinations. This approach allows fine-grained control over expressivity through the number of coefficients. Extensive experiments on language and vision benchmarks show that SVFT recovers up to 96% of full fine-tuning performance while training only 0.006 to 0.25% of parameters, outperforming existing methods that only recover up to 85% performance using 0.03 to 0.8% of the trainable parameter budget. △ Less

Submitted 29 May, 2024; originally announced May 2024.

Comments: 17 pages, 5 figures, 14 tables

WARDEN: Multi-Directional Backdoor Watermarks for Embedding-as-a-Service Copyright Protection

Authors: Anudeex Shetty, Yue Teng, Ke He, Qiongkai Xu

Abstract: Embedding as a Service (EaaS) has become a widely adopted solution, which offers feature extraction capabilities for addressing various downstream tasks in Natural Language Processing (NLP). Prior studies have shown that EaaS can be prone to model extraction attacks; nevertheless, this concern could be mitigated by adding backdoor watermarks to the text embeddings and subsequently verifying the at… ▽ More Embedding as a Service (EaaS) has become a widely adopted solution, which offers feature extraction capabilities for addressing various downstream tasks in Natural Language Processing (NLP). Prior studies have shown that EaaS can be prone to model extraction attacks; nevertheless, this concern could be mitigated by adding backdoor watermarks to the text embeddings and subsequently verifying the attack models post-publication. Through the analysis of the recent watermarking strategy for EaaS, EmbMarker, we design a novel CSE (Clustering, Selection, Elimination) attack that removes the backdoor watermark while maintaining the high utility of embeddings, indicating that the previous watermarking approach can be breached. In response to this new threat, we propose a new protocol to make the removal of watermarks more challenging by incorporating multiple possible watermark directions. Our defense approach, WARDEN, notably increases the stealthiness of watermarks and has been empirically shown to be effective against CSE attack. △ Less

Submitted 9 June, 2024; v1 submitted 3 March, 2024; originally announced March 2024.

Comments: Accepted to ACL2024 (Main Proceedings)

On the Performance of Empirical Risk Minimization with Smoothed Data

Authors: Adam Block, Alexander Rakhlin, Abhishek Shetty

Abstract: In order to circumvent statistical and computational hardness results in sequential decision-making, recent work has considered smoothed online learning, where the distribution of data at each time is assumed to have bounded likeliehood ratio with respect to a base measure when conditioned on the history. While previous works have demonstrated the benefits of smoothness, they have either assumed t… ▽ More In order to circumvent statistical and computational hardness results in sequential decision-making, recent work has considered smoothed online learning, where the distribution of data at each time is assumed to have bounded likeliehood ratio with respect to a base measure when conditioned on the history. While previous works have demonstrated the benefits of smoothness, they have either assumed that the base measure is known to the learner or have presented computationally inefficient algorithms applying only in special cases. This work investigates the more general setting where the base measure is \emph{unknown} to the learner, focusing in particular on the performance of Empirical Risk Minimization (ERM) with square loss when the data are well-specified and smooth. We show that in this setting, ERM is able to achieve sublinear error whenever a class is learnable with iid data; in particular, ERM achieves error scaling as $\tilde O( \sqrt{\mathrm{comp}(\mathcal F)\cdot T} )$, where $\mathrm{comp}(\mathcal F)$ is the statistical complexity of learning $\mathcal F$ with iid data. In so doing, we prove a novel norm comparison bound for smoothed data that comprises the first sharp norm comparison for dependent data applying to arbitrary, nonlinear function classes. We complement these results with a lower bound indicating that our analysis of ERM is essentially tight, establishing a separation in the performance of ERM between smoothed and iid data. △ Less

Submitted 22 February, 2024; originally announced February 2024.

Oracle-Efficient Differentially Private Learning with Public Data

Authors: Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, Steven Wu

Abstract: Due to statistical lower bounds on the learnability of many function classes under privacy constraints, there has been recent interest in leveraging public data to improve the performance of private learning algorithms. In this model, algorithms must always guarantee differential privacy with respect to the private samples while also ensuring learning guarantees when the private data distribution… ▽ More Due to statistical lower bounds on the learnability of many function classes under privacy constraints, there has been recent interest in leveraging public data to improve the performance of private learning algorithms. In this model, algorithms must always guarantee differential privacy with respect to the private samples while also ensuring learning guarantees when the private data distribution is sufficiently close to that of the public data. Previous work has demonstrated that when sufficient public, unlabelled data is available, private learning can be made statistically tractable, but the resulting algorithms have all been computationally inefficient. In this work, we present the first computationally efficient, algorithms to provably leverage public data to learn privately whenever a function class is learnable non-privately, where our notion of computational efficiency is with respect to the number of calls to an optimization oracle for the function class. In addition to this general result, we provide specialized algorithms with improved sample complexities in the special cases when the function class is convex or when the task is binary classification. △ Less

Submitted 13 February, 2024; originally announced February 2024.

Omnipredictors for Regression and the Approximate Rank of Convex Functions

Authors: Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Shetty, Mihir Singhal

Abstract: Consider the supervised learning setting where the goal is to learn to predict labels $\mathbf y$ given points $\mathbf x$ from a distribution. An \textit{omnipredictor} for a class $\mathcal L$ of loss functions and a class $\mathcal C$ of hypotheses is a predictor whose predictions incur less expected loss than the best hypothesis in $\mathcal C$ for every loss in $\mathcal L$. Since the work of… ▽ More Consider the supervised learning setting where the goal is to learn to predict labels $\mathbf y$ given points $\mathbf x$ from a distribution. An \textit{omnipredictor} for a class $\mathcal L$ of loss functions and a class $\mathcal C$ of hypotheses is a predictor whose predictions incur less expected loss than the best hypothesis in $\mathcal C$ for every loss in $\mathcal L$. Since the work of [GKR+21] that introduced the notion, there has been a large body of work in the setting of binary labels where $\mathbf y \in \{0, 1\}$, but much less is known about the regression setting where $\mathbf y \in [0,1]$ can be continuous. Our main conceptual contribution is the notion of \textit{sufficient statistics} for loss minimization over a family of loss functions: these are a set of statistics about a distribution such that knowing them allows one to take actions that minimize the expected loss for any loss in the family. The notion of sufficient statistics relates directly to the approximate rank of the family of loss functions. Our key technical contribution is a bound of $O(1/\varepsilon^{2/3})$ on the $ε$-approximate rank of convex, Lipschitz functions on the interval $[0,1]$, which we show is tight up to a factor of $\mathrm{polylog} (1/ε)$. This yields improved runtimes for learning omnipredictors for the class of all convex, Lipschitz loss functions under weak learnability assumptions about the class $\mathcal C$. We also give efficient omnipredictors when the loss families have low-degree polynomial approximations, or arise from generalized linear models (GLMs). This translation from sufficient statistics to faster omnipredictors is made possible by lifting the technique of loss outcome indistinguishability introduced by [GKH+23] for Boolean labels to the regression setting. △ Less

Submitted 25 January, 2024; originally announced January 2024.

Holoported Characters: Real-time Free-viewpoint Rendering of Humans from Sparse RGB Cameras

Authors: Ashwath Shetty, Marc Habermann, Guoxing Sun, Diogo Luvizon, Vladislav Golyanik, Christian Theobalt

Abstract: We present the first approach to render highly realistic free-viewpoint videos of a human actor in general apparel, from sparse multi-view recording to display, in real-time at an unprecedented 4K resolution. At inference, our method only requires four camera views of the moving actor and the respective 3D skeletal pose. It handles actors in wide clothing, and reproduces even fine-scale dynamic de… ▽ More We present the first approach to render highly realistic free-viewpoint videos of a human actor in general apparel, from sparse multi-view recording to display, in real-time at an unprecedented 4K resolution. At inference, our method only requires four camera views of the moving actor and the respective 3D skeletal pose. It handles actors in wide clothing, and reproduces even fine-scale dynamic detail, e.g. clothing wrinkles, face expressions, and hand gestures. At training time, our learning-based approach expects dense multi-view video and a rigged static surface scan of the actor. Our method comprises three main stages. Stage 1 is a skeleton-driven neural approach for high-quality capture of the detailed dynamic mesh geometry. Stage 2 is a novel solution to create a view-dependent texture using four test-time camera views as input. Finally, stage 3 comprises a new image-based refinement network rendering the final 4K image given the output from the previous stages. Our approach establishes a new benchmark for real-time rendering resolution and quality using sparse input camera views, unlocking possibilities for immersive telepresence. △ Less

Submitted 12 December, 2023; originally announced December 2023.

Comments: Project page: https://vcai.mpi-inf.mpg.de/projects/holochar/

Malware Classification using Deep Neural Networks: Performance Evaluation and Applications in Edge Devices

Authors: Akhil M R, Adithya Krishna V Sharma, Harivardhan Swamy, Pavan A, Ashray Shetty, Anirudh B Sathyanarayana

Abstract: With the increasing extent of malware attacks in the present day along with the difficulty in detecting modern malware, it is necessary to evaluate the effectiveness and performance of Deep Neural Networks (DNNs) for malware classification. Multiple DNN architectures can be designed and trained to detect and classify malware binaries. Results demonstrate the potential of DNNs in accurately classif… ▽ More With the increasing extent of malware attacks in the present day along with the difficulty in detecting modern malware, it is necessary to evaluate the effectiveness and performance of Deep Neural Networks (DNNs) for malware classification. Multiple DNN architectures can be designed and trained to detect and classify malware binaries. Results demonstrate the potential of DNNs in accurately classifying malware with high accuracy rates observed across different malware types. Additionally, the feasibility of deploying these DNN models on edge devices to enable real-time classification, particularly in resource-constrained scenarios proves to be integral to large IoT systems. By optimizing model architectures and leveraging edge computing capabilities, the proposed methodologies achieve efficient performance even with limited resources. This study contributes to advancing malware detection techniques and emphasizes the significance of integrating cybersecurity measures for the early detection of malware and further preventing the adverse effects caused by such attacks. Optimal considerations regarding the distribution of security tasks to edge devices are addressed to ensure that the integrity and availability of large scale IoT systems are not compromised due to malware attacks, advocating for a more resilient and secure digital ecosystem. △ Less

Submitted 21 August, 2023; originally announced October 2023.

Smooth Nash Equilibria: Algorithms and Complexity

Authors: Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, Abhishek Shetty

Abstract: A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis, we introduce a relaxed variant of Nash equilibrium called $σ$-smooth Nash equilibrium, for a smoothness parameter $σ$. In a $σ$-smooth Nash equilibrium, players only need to achi… ▽ More A fundamental shortcoming of the concept of Nash equilibrium is its computational intractability: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed analysis, we introduce a relaxed variant of Nash equilibrium called $σ$-smooth Nash equilibrium, for a smoothness parameter $σ$. In a $σ$-smooth Nash equilibrium, players only need to achieve utility at least as high as their best deviation to a $σ$-smooth strategy, which is a distribution that does not put too much mass (as parametrized by $σ$) on any fixed action. We distinguish two variants of $σ$-smooth Nash equilibria: strong $σ$-smooth Nash equilibria, in which players are required to play $σ$-smooth strategies under equilibrium play, and weak $σ$-smooth Nash equilibria, where there is no such requirement. We show that both weak and strong $σ$-smooth Nash equilibria have superior computational properties to Nash equilibria: when $σ$ as well as an approximation parameter $ε$ and the number of players are all constants, there is a constant-time randomized algorithm to find a weak $ε$-approximate $σ$-smooth Nash equilibrium in normal-form games. In the same parameter regime, there is a polynomial-time deterministic algorithm to find a strong $ε$-approximate $σ$-smooth Nash equilibrium in a normal-form game. These results stand in contrast to the optimal algorithm for computing $ε$-approximate Nash equilibria, which cannot run in faster than quasipolynomial-time. We complement our upper bounds by showing that when either $σ$ or $ε$ is an inverse polynomial, finding a weak $ε$-approximate $σ$-smooth Nash equilibria becomes computationally intractable. △ Less

Submitted 21 September, 2023; originally announced September 2023.

Eventually-Consistent Federated Scheduling for Data Center Workloads

Authors: Meghana Thiyyakat, Subramaniam Kalambur, Rishit Chaudhary, Saurav G Nayak, Adarsh Shetty, Dinkar Sitaram

Abstract: Data center schedulers operate at unprecedented scales today to accommodate the growing demand for computing and storage power. The challenge that schedulers face is meeting the requirements of scheduling speeds despite the scale. To do so, most scheduler architectures use parallelism. However, these architectures consist of multiple parallel scheduling entities that can only utilize partial knowl… ▽ More Data center schedulers operate at unprecedented scales today to accommodate the growing demand for computing and storage power. The challenge that schedulers face is meeting the requirements of scheduling speeds despite the scale. To do so, most scheduler architectures use parallelism. However, these architectures consist of multiple parallel scheduling entities that can only utilize partial knowledge of the data center's state, as maintaining consistent global knowledge or state would involve considerable communication overhead. The disadvantage of scheduling without global knowledge is sub-optimal placements-tasks may be made to wait in queues even though there are resources available in zones outside the scope of the scheduling entity's state. This leads to unnecessary queuing overheads and lower resource utilization of the data center. In this paper, extend our previous work on Megha, a federated decentralized data center scheduling architecture that uses eventual consistency. The architecture utilizes both parallelism and an eventually-consistent global state in each of its scheduling entities to make fast decisions in a scalable manner. In our work, we compare Megha with 3 scheduling architectures: Sparrow, Eagle, and Pigeon, using simulation. We also evaluate Megha's prototype on a 123-node cluster and compare its performance with Pigeon's prototype using cluster traces. The results of our experiments show that Megha consistently reduces delays in job completion time when compared to other architectures. △ Less

Submitted 20 August, 2023; originally announced August 2023.

Comments: 26 pages. Submitted to Elsevier's Ad Hoc Networks Journal

Adversarial Resilience in Sequential Prediction via Abstention

Authors: Surbhi Goel, Steve Hanneke, Shay Moran, Abhishek Shetty

Abstract: We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Algorithms designed to handle purely stochastic data tend to fail in the presence of such adversarial examples, often leading to erroneous predictions. This is undesirable in many high-stakes applications such as medical reco… ▽ More We study the problem of sequential prediction in the stochastic setting with an adversary that is allowed to inject clean-label adversarial (or out-of-distribution) examples. Algorithms designed to handle purely stochastic data tend to fail in the presence of such adversarial examples, often leading to erroneous predictions. This is undesirable in many high-stakes applications such as medical recommendations, where abstaining from predictions on adversarial examples is preferable to misclassification. On the other hand, assuming fully adversarial data leads to very pessimistic bounds that are often vacuous in practice. To capture this motivation, we propose a new model of sequential prediction that sits between the purely stochastic and fully adversarial settings by allowing the learner to abstain from making a prediction at no cost on adversarial examples. Assuming access to the marginal distribution on the non-adversarial examples, we design a learner whose error scales with the VC dimension (mirroring the stochastic setting) of the hypothesis class, as opposed to the Littlestone dimension which characterizes the fully adversarial setting. Furthermore, we design a learner for VC dimension~1 classes, which works even in the absence of access to the marginal distribution. Our key technical contribution is a novel measure for quantifying uncertainty for learning VC classes, which may be of independent interest. △ Less

Submitted 24 January, 2024; v1 submitted 22 June, 2023; originally announced June 2023.

Optimal PAC Bounds Without Uniform Convergence

Authors: Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy

Abstract: In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hanneke established sharp upper bounds in this setting. However, the reliance of their argument on the uniform convergence principle limits its applicability to more general learning settings such as multiclass classificatio… ▽ More In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hanneke established sharp upper bounds in this setting. However, the reliance of their argument on the uniform convergence principle limits its applicability to more general learning settings such as multiclass classification. In this paper, we address this issue by providing optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments. Our framework converts the leave-one-out error of permutation invariant predictors into high probability risk bounds. As an application, by adapting the one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth, we propose an algorithm that achieves an optimal PAC bound for binary classification. Specifically, our result shows that certain aggregations of one-inclusion graph algorithms are optimal, addressing a variant of a classic question posed by Warmuth. We further instantiate our framework in three settings where uniform convergence is provably suboptimal. For multiclass classification, we prove an optimal risk bound that scales with the one-inclusion hypergraph density of the class, addressing the suboptimality of the analysis of Daniely and Shalev-Shwartz. For partial hypothesis classification, we determine the optimal sample complexity bound, resolving a question posed by Alon, Hanneke, Holzman, and Moran. For realizable bounded regression with absolute loss, we derive an optimal risk bound that relies on a modified version of the scale-sensitive dimension, refining the results of Bartlett and Long. Our rates surpass standard uniform convergence-based results due to the smaller complexity measure in our risk bound. △ Less

Submitted 18 April, 2023; originally announced April 2023.

Comments: 27 pages

Smoothed Analysis of Sequential Probability Assignment

Authors: Alankrita Bhatt, Nika Haghtalab, Abhishek Shetty

Abstract: We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a framework for algorithmic reduction involving the maximum likelihood estimator oracle. Our approach establishes a general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries t… ▽ More We initiate the study of smoothed analysis for the sequential probability assignment problem with contexts. We study information-theoretically optimal minmax rates as well as a framework for algorithmic reduction involving the maximum likelihood estimator oracle. Our approach establishes a general-purpose reduction from minimax rates for sequential probability assignment for smoothed adversaries to minimax rates for transductive learning. This leads to optimal (logarithmic) fast rates for parametric classes and classes with finite VC dimension. On the algorithmic front, we develop an algorithm that efficiently taps into the MLE oracle, for general classes of functions. We show that under general conditions this algorithmic approach yields sublinear regret. △ Less

Submitted 8 March, 2023; originally announced March 2023.

Progressive Ensemble Distillation: Building Ensembles for Efficient Inference

Authors: Don Kurian Dennis, Abhishek Shetty, Anish Sevekari, Kazuhito Koishida, Virginia Smith

Abstract: We study the problem of progressive ensemble distillation: Given a large, pretrained teacher model $g$, we seek to decompose the model into smaller, low-inference cost student models $f_i$, such that progressively evaluating additional models in this ensemble leads to improved predictions. The resulting ensemble allows for flexibly tuning accuracy vs. inference cost at runtime, which is useful for… ▽ More We study the problem of progressive ensemble distillation: Given a large, pretrained teacher model $g$, we seek to decompose the model into smaller, low-inference cost student models $f_i$, such that progressively evaluating additional models in this ensemble leads to improved predictions. The resulting ensemble allows for flexibly tuning accuracy vs. inference cost at runtime, which is useful for a number of applications in on-device inference. The method we propose, B-DISTIL , relies on an algorithmic procedure that uses function composition over intermediate activations to construct expressive ensembles with similar performance as $g$ , but with smaller student models. We demonstrate the effectiveness of B-DISTIL by decomposing pretrained models across standard image, speech, and sensor datasets. We also provide theoretical guarantees in terms of convergence and generalization. △ Less

Submitted 9 November, 2023; v1 submitted 20 February, 2023; originally announced February 2023.

The One-Inclusion Graph Algorithm is not Always Optimal

Authors: Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy

Abstract: The one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth achieves an optimal in-expectation risk bound in the standard PAC classification setup. In one of the first COLT open problems, Warmuth conjectured that this prediction strategy always implies an optimal high probability bound on the risk, and hence is also an optimal PAC algorithm. We refute this conjecture in the strongest s… ▽ More The one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth achieves an optimal in-expectation risk bound in the standard PAC classification setup. In one of the first COLT open problems, Warmuth conjectured that this prediction strategy always implies an optimal high probability bound on the risk, and hence is also an optimal PAC algorithm. We refute this conjecture in the strongest sense: for any practically interesting Vapnik-Chervonenkis class, we provide an in-expectation optimal one-inclusion graph algorithm whose high probability risk bound cannot go beyond that implied by Markov's inequality. Our construction of these poorly performing one-inclusion graph algorithms uses Varshamov-Tenengolts error correcting codes. Our negative result has several implications. First, it shows that the same poor high-probability performance is inherited by several recent prediction strategies based on generalizations of the one-inclusion graph algorithm. Second, our analysis shows yet another statistical problem that enjoys an estimator that is provably optimal in expectation via a leave-one-out argument, but fails in the high-probability regime. This discrepancy occurs despite the boundedness of the binary loss for which arguments based on concentration inequalities often provide sharp high probability risk bounds. △ Less

Submitted 19 December, 2022; originally announced December 2022.

Comments: 16 pages

Identification of medical devices using machine learning on distribution feeder data for informing power outage response

Authors: Paraskevi Kourtza, Maitreyee Marathe, Anuj Shetty, Diego Kiedanski

Abstract: Power outages caused by extreme weather events due to climate change have doubled in the United States in the last two decades. Outages pose severe health risks to over 4.4 million individuals dependent on in-home medical devices. Data on the number of such individuals residing in a given area is limited. This study proposes a load disaggregation model to predict the number of medical devices behi… ▽ More Power outages caused by extreme weather events due to climate change have doubled in the United States in the last two decades. Outages pose severe health risks to over 4.4 million individuals dependent on in-home medical devices. Data on the number of such individuals residing in a given area is limited. This study proposes a load disaggregation model to predict the number of medical devices behind an electric distribution feeder. This data can be used to inform planning and response. The proposed solution serves as a measure for climate change adaptation. △ Less

Submitted 15 November, 2022; originally announced November 2022.

Comments: To appear in the Tackling Climate Change with Machine Learning workshop at NeurIPS 2022 (Proposals Track) 6 pages, 3 figures

Facial De-occlusion Network for Virtual Telepresence Systems

Authors: Surabhi Gupta, Ashwath Shetty, Avinash Sharma

Abstract: To see what is not in the image is one of the broader missions of computer vision. Technology to inpaint images has made significant progress with the coming of deep learning. This paper proposes a method to tackle occlusion specific to human faces. Virtual presence is a promising direction in communication and recreation for the future. However, Virtual Reality (VR) headsets occlude a significant… ▽ More To see what is not in the image is one of the broader missions of computer vision. Technology to inpaint images has made significant progress with the coming of deep learning. This paper proposes a method to tackle occlusion specific to human faces. Virtual presence is a promising direction in communication and recreation for the future. However, Virtual Reality (VR) headsets occlude a significant portion of the face, hindering the photo-realistic appearance of the face in the virtual world. State-of-the-art image inpainting methods for de-occluding the eye region does not give usable results. To this end, we propose a working solution that gives usable results to tackle this problem enabling the use of the real-time photo-realistic de-occluded face of the user in VR settings. △ Less

Submitted 23 October, 2022; originally announced October 2022.

Comments: This workshop paper is presented in CVPR Workshop on Computer Vision for Augmented and Virtual Reality, New Orleans, LA, 2022. Link: https://xr.cornell.edu/workshop/2022/papers

TangibleGrid: Tangible Web Layout Design for Blind Users

Authors: Jiasheng Li, Zeyu Yan, Ebrima Jarjue, Ashrith Shetty, Huaishu Peng

Abstract: We present TangibleGrid, a novel device that allows blind users to understand and design the layout of a web page with real-time tangible feedback. We conducted semi-structured interviews and a series of co-design sessions with blind users to elicit insights that guided the design of TangibleGrid. Our final prototype contains shape-changing brackets representing the web elements and a baseboard re… ▽ More We present TangibleGrid, a novel device that allows blind users to understand and design the layout of a web page with real-time tangible feedback. We conducted semi-structured interviews and a series of co-design sessions with blind users to elicit insights that guided the design of TangibleGrid. Our final prototype contains shape-changing brackets representing the web elements and a baseboard representing the web page canvas. Blind users can design a web page layout through creating and editing web elements by snapping or adjusting tangible brackets on top of the baseboard. The baseboard senses the brackets' type, size, and location, verbalizes the information, and renders the web page on the client browser. Through a formative user study, we found that blind users could understand a web page layout through TangibleGrid. They were also able to design a new web layout from scratch without the help of sighted people. △ Less

Submitted 27 August, 2022; v1 submitted 17 August, 2022; originally announced August 2022.

Journal ref: UIST '22, October 29-November 2, 2022, Bend, OR, USA

Knowledge Graph Construction and Its Application in Automatic Radiology Report Generation from Radiologist's Dictation

Authors: Kaveri Kale, Pushpak Bhattacharyya, Aditya Shetty, Milind Gune, Kush Shrivastava, Rustom Lawyer, Spriha Biswas

Abstract: Conventionally, the radiologist prepares the diagnosis notes and shares them with the transcriptionist. Then the transcriptionist prepares a preliminary formatted report referring to the notes, and finally, the radiologist reviews the report, corrects the errors, and signs off. This workflow causes significant delays and errors in the report. In current research work, we focus on applications of N… ▽ More Conventionally, the radiologist prepares the diagnosis notes and shares them with the transcriptionist. Then the transcriptionist prepares a preliminary formatted report referring to the notes, and finally, the radiologist reviews the report, corrects the errors, and signs off. This workflow causes significant delays and errors in the report. In current research work, we focus on applications of NLP techniques like Information Extraction (IE) and domain-specific Knowledge Graph (KG) to automatically generate radiology reports from radiologist's dictation. This paper focuses on KG construction for each organ by extracting information from an existing large corpus of free-text radiology reports. We develop an information extraction pipeline that combines rule-based, pattern-based, and dictionary-based techniques with lexical-semantic features to extract entities and relations. Missing information in short dictation can be accessed from the KGs to generate pathological descriptions and hence the radiology report. Generated pathological descriptions evaluated using semantic similarity metrics, which shows 97% similarity with gold standard pathological descriptions. Also, our analysis shows that our IE module is performing better than the OpenIE tool for the radiology domain. Furthermore, we include a manual qualitative analysis from radiologists, which shows that 80-85% of the generated reports are correctly written, and the remaining are partially correct. △ Less

Submitted 13 June, 2022; v1 submitted 13 June, 2022; originally announced June 2022.

Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries

Authors: Nika Haghtalab, Yanjun Han, Abhishek Shetty, Kunhe Yang

Abstract: In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning. We focus on two settings. First, the smoothed analysis setting of [RST11,HRS22] where an adversary is constrained to generating samples from distributions whose density is upper bounded by $1/σ$ times the uniform density. Second, the setting of $K$-hint transductive learning, where the learner is… ▽ More In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning. We focus on two settings. First, the smoothed analysis setting of [RST11,HRS22] where an adversary is constrained to generating samples from distributions whose density is upper bounded by $1/σ$ times the uniform density. Second, the setting of $K$-hint transductive learning, where the learner is given access to $K$ hints per time step that are guaranteed to include the true instance. We give the first known oracle-efficient algorithms for both settings that depend only on the pseudo (or VC) dimension of the class and parameters $σ$ and $K$ that capture the power of the adversary. In particular, we achieve oracle-efficient regret bounds of $ \widetilde{O} ( \sqrt{T dσ^{-1}} ) $ and $ \widetilde{O} ( \sqrt{T dK} ) $ for learning real-valued functions and $ O ( \sqrt{T dσ^{-\frac{1}{2}} } )$ for learning binary-valued functions. For the smoothed analysis setting, our results give the first oracle-efficient algorithm for online learning with smoothed adversaries [HRS22]. This contrasts the computational separation between online learning with worst-case adversaries and offline learning established by [HK16]. Our algorithms also achieve improved bounds for worst-case setting with small domains. In particular, we give an oracle-efficient algorithm with regret of $O ( \sqrt{T(d |\mathcal{X}|)^{1/2} })$, which is a refinement of the earlier $O ( \sqrt{T|\mathcal{X}|})$ bound by [DS16]. △ Less

Submitted 22 November, 2022; v1 submitted 17 February, 2022; originally announced February 2022.

Comments: An extended abstract of this work was published under the title "Oracle-efficient Online Learning for Smoothed Adversaries'' in the Proceedings of the 36th Conference on Neural Information Processing Systems

Attention based Occlusion Removal for Hybrid Telepresence Systems

Authors: Surabhi Gupta, Ashwath Shetty, Avinash Sharma

Abstract: Traditionally, video conferencing is a widely adopted solution for telecommunication, but a lack of immersiveness comes inherently due to the 2D nature of facial representation. The integration of Virtual Reality (VR) in a communication/telepresence system through Head Mounted Displays (HMDs) promises to provide users a much better immersive experience. However, HMDs cause hindrance by blocking th… ▽ More Traditionally, video conferencing is a widely adopted solution for telecommunication, but a lack of immersiveness comes inherently due to the 2D nature of facial representation. The integration of Virtual Reality (VR) in a communication/telepresence system through Head Mounted Displays (HMDs) promises to provide users a much better immersive experience. However, HMDs cause hindrance by blocking the facial appearance and expressions of the user. To overcome these issues, we propose a novel attention-enabled encoder-decoder architecture for HMD de-occlusion. We also propose to train our person-specific model using short videos (1-2 minutes) of the user, captured in varying appearances, and demonstrated generalization to unseen poses and appearances of the user. We report superior qualitative and quantitative results over state-of-the-art methods. We also present applications of this approach to hybrid video teleconferencing using existing animation and 3D face reconstruction pipelines. △ Less

Submitted 2 December, 2021; originally announced December 2021.

Distribution Compression in Near-linear Time

Authors: Abhishek Shetty, Raaz Dwivedi, Lester Mackey

Abstract: In distribution compression, one aims to accurately summarize a probability distribution $\mathbb{P}$ using a small number of representative points. Near-optimal thinning procedures achieve this goal by sampling $n$ points from a Markov chain and identifying $\sqrt{n}$ points with $\widetilde{\mathcal{O}}(1/\sqrt{n})$ discrepancy to $\mathbb{P}$. Unfortunately, these algorithms suffer from quadrat… ▽ More In distribution compression, one aims to accurately summarize a probability distribution $\mathbb{P}$ using a small number of representative points. Near-optimal thinning procedures achieve this goal by sampling $n$ points from a Markov chain and identifying $\sqrt{n}$ points with $\widetilde{\mathcal{O}}(1/\sqrt{n})$ discrepancy to $\mathbb{P}$. Unfortunately, these algorithms suffer from quadratic or super-quadratic runtime in the sample size $n$. To address this deficiency, we introduce Compress++, a simple meta-procedure for speeding up any thinning algorithm while suffering at most a factor of $4$ in error. When combined with the quadratic-time kernel halving and kernel thinning algorithms of Dwivedi and Mackey (2021), Compress++ delivers $\sqrt{n}$ points with $\mathcal{O}(\sqrt{\log n/n})$ integration error and better-than-Monte-Carlo maximum mean discrepancy in $\mathcal{O}(n \log^3 n)$ time and $\mathcal{O}( \sqrt{n} \log^2 n )$ space. Moreover, Compress++ enjoys the same near-linear runtime given any quadratic-time input and reduces the runtime of super-quadratic algorithms by a square-root factor. In our benchmarks with high-dimensional Monte Carlo samples and Markov chains targeting challenging differential equation posteriors, Compress++ matches or nearly matches the accuracy of its input algorithm in orders of magnitude less time. △ Less

Submitted 17 October, 2022; v1 submitted 15 November, 2021; originally announced November 2021.

Comments: Accepted to ICLR 2022; An outdated proof of Theorem 2 was previously included in the appendix; this oversight is corrected in this version

Matrix Discrepancy from Quantum Communication

Authors: Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty

Abstract: We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spencer conjecture. In particular, we show that for every collection of symmetric $n \times n$ matrices $A_1,\ldots,A_n$ with $\|A_i\| \leq 1$ and $\|A_i\|_F \leq n^{1/4}$ there exist signs $x \in \{ \pm 1\}^n$ such that the m… ▽ More We develop a novel connection between discrepancy minimization and (quantum) communication complexity. As an application, we resolve a substantial special case of the Matrix Spencer conjecture. In particular, we show that for every collection of symmetric $n \times n$ matrices $A_1,\ldots,A_n$ with $\|A_i\| \leq 1$ and $\|A_i\|_F \leq n^{1/4}$ there exist signs $x \in \{ \pm 1\}^n$ such that the maximum eigenvalue of $\sum_{i \leq n} x_i A_i$ is at most $O(\sqrt n)$. We give a polynomial-time algorithm based on partial coloring and semidefinite programming to find such $x$. Our techniques open a new avenue to use tools from communication complexity and information theory to study discrepancy. The proof of our main result combines a simple compression scheme for transcripts of repeated (quantum) communication protocols with quantum state purification, the Holevo bound from quantum information, and tools from sketching and dimensionality reduction. Our approach also offers a promising avenue to resolve the Matrix Spencer conjecture completely -- we show it is implied by a natural conjecture in quantum communication complexity. △ Less

Submitted 19 October, 2021; originally announced October 2021.

Improving GNSS Positioning using Neural Network-based Corrections

Authors: Ashwin V. Kanhere, Shubh Gupta, Akshay Shetty, Grace Gao

Abstract: Deep Neural Networks (DNNs) are a promising tool for Global Navigation Satellite System (GNSS) positioning in the presence of multipath and non-line-of-sight errors, owing to their ability to model complex errors using data. However, developing a DNN for GNSS positioning presents various challenges, such as 1) poor numerical conditioning caused by large variations in measurements and position valu… ▽ More Deep Neural Networks (DNNs) are a promising tool for Global Navigation Satellite System (GNSS) positioning in the presence of multipath and non-line-of-sight errors, owing to their ability to model complex errors using data. However, developing a DNN for GNSS positioning presents various challenges, such as 1) poor numerical conditioning caused by large variations in measurements and position values across the globe, 2) varying number and order within the set of measurements due to changing satellite visibility, and 3) overfitting to available data. In this work, we address the aforementioned challenges and propose an approach for GNSS positioning by applying DNN-based corrections to an initial position guess. Our DNN learns to output the position correction using the set of pseudorange residuals and satellite line-of-sight vectors as inputs. The limited variation in these input and output values improves the numerical conditioning for our DNN. We design our DNN architecture to combine information from the available GNSS measurements, which vary both in number and order, by leveraging recent advancements in set-based deep learning methods. Furthermore, we present a data augmentation strategy for reducing overfitting in the DNN by randomizing the initial position guesses. We first perform simulations and show an improvement in the initial positioning error when our DNN-based corrections are applied. After this, we demonstrate that our approach outperforms a WLS baseline on real-world data. Our implementation is available at github.com/Stanford-NavLab/deep_gnss. △ Less

Submitted 21 June, 2022; v1 submitted 18 October, 2021; originally announced October 2021.

Comments: 15 pages, 8 figures, accepted in Navigation: Journal of the Institute of Navigation

Decentralized Connectivity Maintenance for Multi-robot Systems Under Motion and Sensing Uncertainties

Authors: Akshay Shetty, Timmy Hussain, Grace Gao

Abstract: Communication connectivity is desirable for safe and efficient operation of multi-robot systems. While decentralized algorithms for connectivity maintenance have been explored in recent literature, the majority of these works do not account for robot motion and sensing uncertainties. These uncertainties are inherent in practical robots and result in robots deviating from their desired positions wh… ▽ More Communication connectivity is desirable for safe and efficient operation of multi-robot systems. While decentralized algorithms for connectivity maintenance have been explored in recent literature, the majority of these works do not account for robot motion and sensing uncertainties. These uncertainties are inherent in practical robots and result in robots deviating from their desired positions which could potentially result in a loss of connectivity. In this paper we present a Decentralized Connectivity Maintenance algorithm accounting for robot motion and sensing Uncertainties (DCMU). We first propose a novel weighted graph definition for the multi-robot system that accounts for the aforementioned uncertainties along with realistic connectivity constraints such as line-of-sight connectivity and collision avoidance. Next we design a decentralized gradient-based controller for connectivity maintenance where we derive the gradients of our weighted graph edge weights required for computing the control. Finally, we perform multiple simulations to validate the connectivity maintenance performance of our DCMU algorithm under robot motion and sensing uncertainties and show an improvement compared to previous work. △ Less

Submitted 20 July, 2022; v1 submitted 12 October, 2021; originally announced October 2021.

Comments: Accepted in NAVIGATION: Journal of The Institute of Navigation

Scope-Bounded Reachability in Valence Systems

Authors: Aneesh K. Shetty, S. Krishna, Georg Zetzsche

Abstract: Multi-pushdown systems are a standard model for concurrent recursive programs, but they have an undecidable reachability problem. Therefore, there have been several proposals to underapproximate their sets of runs so that reachability in this underapproximation becomes decidable. One such underapproximation that covers a relatively high portion of runs is scope boundedness. In such a run, after ea… ▽ More Multi-pushdown systems are a standard model for concurrent recursive programs, but they have an undecidable reachability problem. Therefore, there have been several proposals to underapproximate their sets of runs so that reachability in this underapproximation becomes decidable. One such underapproximation that covers a relatively high portion of runs is scope boundedness. In such a run, after each push to stack $i$, the corresponding pop operation must come within a bounded number of visits to stack $i$. In this work, we generalize this approach to a large class of infinite-state systems. For this, we consider the model of valence systems, which consist of a finite-state control and an infinite-state storage mechanism that is specified by a finite undirected graph. This framework captures pushdowns, vector addition systems, integer vector addition systems, and combinations thereof. For this framework, we propose a notion of scope boundedness that coincides with the classical notion when the storage mechanism happens to be a multi-pushdown. We show that with this notion, reachability can be decided in PSPACE for every storage mechanism in the framework. Moreover, we describe the full complexity landscape of this problem across all storage mechanisms, both in the case of (i) the scope bound being given as input and (ii) for fixed scope bounds. Finally, we provide an almost complete description of the complexity landscape if even a description of the storage mechanism is part of the input. △ Less

Submitted 2 August, 2021; originally announced August 2021.

Comments: To appear in proceedings of CONCUR 2021

Smoothed Analysis with Adaptive Adversaries

Authors: Nika Haghtalab, Tim Roughgarden, Abhishek Shetty

Abstract: We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time an adversary chooses an input distribution with density function bounded above by $\tfrac{1}σ$ times that of the uniform distribution; nature then samples an input from this distribution. Crucially, our results hold for {\em adaptive} adversaries that can choose an input di… ▽ More We prove novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time an adversary chooses an input distribution with density function bounded above by $\tfrac{1}σ$ times that of the uniform distribution; nature then samples an input from this distribution. Crucially, our results hold for {\em adaptive} adversaries that can choose an input distribution based on the decisions of the algorithm and the realizations of the inputs in the previous time steps. This paper presents a general technique for proving smoothed algorithmic guarantees against adaptive adversaries, in effect reducing the setting of adaptive adversaries to the simpler case of oblivious adversaries. We apply this technique to prove strong smoothed guarantees for three problems: -Online learning: We consider the online prediction problem, where instances are generated from an adaptive sequence of $σ$-smooth distributions and the hypothesis class has VC dimension $d$. We bound the regret by $\tilde{O}\big(\sqrt{T d\ln(1/σ)} + d\sqrt{\ln(T/σ)}\big)$. This answers open questions of [RST11,Hag18]. -Online discrepancy minimization: We consider the online Komlós problem, where the input is generated from an adaptive sequence of $σ$-smooth and isotropic distributions on the $\ell_2$ unit ball. We bound the $\ell_\infty$ norm of the discrepancy vector by $\tilde{O}\big(\ln^2\!\big( \frac{nT}σ\big) \big)$. -Dispersion in online optimization: We consider online optimization of piecewise Lipschitz functions where functions with $\ell$ discontinuities are chosen by a smoothed adaptive adversary and show that the resulting sequence is $\big( σ/{\sqrt{T\ell}}, \tilde O\big(\sqrt{T\ell} \big)\big)$-dispersed. This matches the parameters of [BDV18] for oblivious adversaries, up to log factors. △ Less

Submitted 18 August, 2021; v1 submitted 16 February, 2021; originally announced February 2021.

Comments: Accepted to FOCS 2021

Connectivity Maintenance for Multi-Robot Systems Under Motion and Sensing Uncertainties Using Distributed ADMM-based Trajectory Planning

Authors: Akshay Shetty, Derek Knowles, Grace Xingxin Gao

Abstract: Inter-robot communication enables multi-robot systems to coordinate and execute complex missions efficiently. Thus, maintaining connectivity of the communication network between robots is essential for many multi-robot systems. In this paper, we present a trajectory planner for connectivity maintenance of a multi-robot system. We first define a weighted undirected graph to represent the connectivi… ▽ More Inter-robot communication enables multi-robot systems to coordinate and execute complex missions efficiently. Thus, maintaining connectivity of the communication network between robots is essential for many multi-robot systems. In this paper, we present a trajectory planner for connectivity maintenance of a multi-robot system. We first define a weighted undirected graph to represent the connectivity of the system. Unlike previous connectivity maintenance works, we explicitly account for robot motion and sensing uncertainties while formulating the graph edge weights. These uncertainties result in uncertain robot positions which directly affect the connectivity of the system. Next, the algebraic connectivity of the weighted undirected graph is maintained above a specified lower limit using a trajectory planner based on a distributed alternating direction method of multipliers (ADMM) framework. Here we derive an approximation for the Hessian matrices required within the ADMM optimization step to reduce the computational load. Finally, simulation results are presented to statistically validate the connectivity maintenance of our trajectory planner. △ Less

Submitted 16 December, 2021; v1 submitted 17 December, 2020; originally announced December 2020.

Comments: Submitted to IEEE Transactions on Control of Network Systems

Trajectory Planning Under Stochastic and Bounded Sensing Uncertainties Using Reachability Analysis

Authors: Akshay Shetty, Grace Xingxin Gao

Abstract: Trajectory planning under uncertainty is an active research topic. Previous works predict state and state estimation uncertainties along trajectories to check for collision safety. They assume either stochastic or bounded sensing uncertainties. However, GNSS pseudoranges are typically modeled to contain stochastic uncertainties with additional biases in urban environments. Thus, given bounds for t… ▽ More Trajectory planning under uncertainty is an active research topic. Previous works predict state and state estimation uncertainties along trajectories to check for collision safety. They assume either stochastic or bounded sensing uncertainties. However, GNSS pseudoranges are typically modeled to contain stochastic uncertainties with additional biases in urban environments. Thus, given bounds for the bias, the planner needs to account for both stochastic and bounded sensing uncertainties. In our prior work we presented a reachability analysis to predict state and state estimation uncertainties under stochastic and bounded uncertainties. However, we ignored the correlation between these uncertainties, leading to an imperfect approximation of the state uncertainty. In this paper we improve our reachability analysis by predicting state uncertainty as a function of independent quantities. We design a metric for the predicted uncertainty to compare candidate trajectories during planning. Finally, we validate the planner for GNSS-based urban navigation of fixed-wing UAS. △ Less

Submitted 17 December, 2020; originally announced December 2020.

Comments: Submitted to Navigation: Journal of the Institute of Navigation

Fractional Pseudorandom Generators from Any Fourier Level

Authors: Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty

Abstract: We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the $k$-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with $k$. This in… ▽ More We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the $k$-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with $k$. This interpolates previous works, which either require Fourier bounds on all levels [CHHL19], or have polynomial dependence on the error parameter in the seed length [CHLT10], and thus answers an open question in [CHLT19]. As an example, we show that for polynomial error, Fourier bounds on the first $O(\log n)$ levels is sufficient to recover the seed length in [CHHL19], which requires bounds on the entire tail. We obtain our results by an alternate analysis of fractional PRGs using Taylor's theorem and bounding the degree-$k$ Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the \emph{level-k unsigned Fourier sum}, which is potentially a much smaller quantity than the $L_1$ notion in previous works. By generalizing a connection established in [CHH+20], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for $\mathbb{F}_2$ polynomials with seed length close to the state-of-the-art construction due to Viola [Vio09], which was not known to be possible using this framework. △ Less

Submitted 7 November, 2020; v1 submitted 4 August, 2020; originally announced August 2020.

Learning to Play Cup-and-Ball with Noisy Camera Observations

Authors: Monimoy Bujarbaruah, Tony Zheng, Akhil Shetty, Martin Sehr, Francesco Borrelli

Abstract: Playing the cup-and-ball game is an intriguing task for robotics research since it abstracts important problem characteristics including system nonlinearity, contact forces and precise positioning as terminal goal. In this paper, we present a learning model based control strategy for the cup-and-ball game, where a Universal Robots UR5e manipulator arm learns to catch a ball in one of the cups on a… ▽ More Playing the cup-and-ball game is an intriguing task for robotics research since it abstracts important problem characteristics including system nonlinearity, contact forces and precise positioning as terminal goal. In this paper, we present a learning model based control strategy for the cup-and-ball game, where a Universal Robots UR5e manipulator arm learns to catch a ball in one of the cups on a Kendama. Our control problem is divided into two sub-tasks, namely $(i)$ swinging the ball up in a constrained motion, and $(ii)$ catching the free-falling ball. The swing-up trajectory is computed offline, and applied in open-loop to the arm. Subsequently, a convex optimization problem is solved online during the ball's free-fall to control the manipulator and catch the ball. The controller utilizes noisy position feedback of the ball from an Intel RealSense D435 depth camera. We propose a novel iterative framework, where data is used to learn the support of the camera noise distribution iteratively in order to update the control policy. The probability of a catch with a fixed policy is computed empirically with a user specified number of roll-outs. Our design guarantees that probability of the catch increases in the limit, as the learned support nears the true support of the camera noise distribution. High-fidelity Mujoco simulations and preliminary experimental results support our theoretical analysis. △ Less

Submitted 18 July, 2020; originally announced July 2020.

Comments: Final paper for IEEE CASE, Hong Kong, August, 2020. First three authors contributed equally

Smoothed Analysis of Online and Differentially Private Learning

Authors: Nika Haghtalab, Tim Roughgarden, Abhishek Shetty

Abstract: Practical and pervasive needs for robustness and privacy in algorithms have inspired the design of online adversarial and differentially private learning algorithms. The primary quantity that characterizes learnability in these settings is the Littlestone dimension of the class of hypotheses [Ben-David et al., 2009, Alon et al., 2019]. This characterization is often interpreted as an impossibility… ▽ More Practical and pervasive needs for robustness and privacy in algorithms have inspired the design of online adversarial and differentially private learning algorithms. The primary quantity that characterizes learnability in these settings is the Littlestone dimension of the class of hypotheses [Ben-David et al., 2009, Alon et al., 2019]. This characterization is often interpreted as an impossibility result because classes such as linear thresholds and neural networks have infinite Littlestone dimension. In this paper, we apply the framework of smoothed analysis [Spielman and Teng, 2004], in which adversarially chosen inputs are perturbed slightly by nature. We show that fundamentally stronger regret and error guarantees are possible with smoothed adversaries than with worst-case adversaries. In particular, we obtain regret and privacy error bounds that depend only on the VC dimension and the bracketing number of a hypothesis class, and on the magnitudes of the perturbations. △ Less

Submitted 17 June, 2020; originally announced June 2020.

Safety Challenges for Autonomous Vehicles in the Absence of Connectivity

Authors: Akhil Shetty, Mengqiao Yu, Alex Kurzhanskiy, Offer Grembek, Hamidreza Tavafoghi, Pravin Varaiya

Abstract: Autonomous vehicles (AVs) are promoted as a technology that will create a future with effortless driving and virtually no traffic accidents. AV companies claim that, when fully developed, the technology will eliminate 94% of all accidents that are caused by human error. These AVs will likely avoid the large number of crashes caused by impaired, distracted or reckless drivers. But there remains a s… ▽ More Autonomous vehicles (AVs) are promoted as a technology that will create a future with effortless driving and virtually no traffic accidents. AV companies claim that, when fully developed, the technology will eliminate 94% of all accidents that are caused by human error. These AVs will likely avoid the large number of crashes caused by impaired, distracted or reckless drivers. But there remains a significant proportion of crashes for which no driver is directly responsible. In particular, the absence of connectivity of an AV with its neighboring vehicles (V2V) and the infrastructure (I2V) leads to a lack of information that can induce such crashes. Since AV designs today do not require such connectivity, these crashes would persist in the future. Using prototypical examples motivated by the NHTSA pre-crash scenario typology, we show that fully autonomous vehicles cannot guarantee safety in the absence of connectivity. Combining theoretical models and empirical data, we also argue that such hazardous scenarios will occur with a significantly high probability. This suggests that incorporating connectivity is an essential step on the path towards safe AV technology. △ Less

Submitted 14 April, 2021; v1 submitted 6 June, 2020; originally announced June 2020.

Effect of Activation Functions on the Training of Overparametrized Neural Nets

Authors: Abhishek Panigrahi, Abhishek Shetty, Navin Goyal

Abstract: It is well-known that overparametrized neural networks trained using gradient-based methods quickly achieve small training error with appropriate hyperparameter settings. Recent papers have proved this statement theoretically for highly overparametrized networks under reasonable assumptions. These results either assume that the activation function is ReLU or they crucially depend on the minimum ei… ▽ More It is well-known that overparametrized neural networks trained using gradient-based methods quickly achieve small training error with appropriate hyperparameter settings. Recent papers have proved this statement theoretically for highly overparametrized networks under reasonable assumptions. These results either assume that the activation function is ReLU or they crucially depend on the minimum eigenvalue of a certain Gram matrix depending on the data, random initialization and the activation function. In the later case, existing works only prove that this minimum eigenvalue is non-zero and do not provide quantitative bounds. On the empirical side, a contemporary line of investigations has proposed a number of alternative activation functions which tend to perform better than ReLU at least in some settings but no clear understanding has emerged. This state of affairs underscores the importance of theoretically understanding the impact of activation functions on training. In the present paper, we provide theoretical results about the effect of activation function on the training of highly overparametrized 2-layer neural networks. A crucial property that governs the performance of an activation is whether or not it is smooth. For non-smooth activations such as ReLU, SELU and ELU, all eigenvalues of the associated Gram matrix are large under minimal assumptions on the data. For smooth activations such as tanh, swish and polynomials, the situation is more complex. If the subspace spanned by the data has small dimension then the minimum eigenvalue of the Gram matrix can be small leading to slow training. But if the dimension is large and the data satisfies another mild condition, then the eigenvalues are large. If we allow deep networks, then the small data dimension is not a limitation provided that the depth is sufficient. We discuss a number of extensions and applications of these results. △ Less

Submitted 10 April, 2020; v1 submitted 16 August, 2019; originally announced August 2019.

Comments: Major update: Several new results, some reorganization and rewriting of previous results, new references

Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature

Authors: Navin Goyal, Abhishek Shetty

Abstract: The Euclidean space notion of convex sets (and functions) generalizes to Riemannian manifolds in a natural sense and is called geodesic convexity. Extensively studied computational problems such as convex optimization and sampling in convex sets also have meaningful counterparts in the manifold setting. Geodesically convex optimization is a well-studied problem with ongoing research and considerab… ▽ More The Euclidean space notion of convex sets (and functions) generalizes to Riemannian manifolds in a natural sense and is called geodesic convexity. Extensively studied computational problems such as convex optimization and sampling in convex sets also have meaningful counterparts in the manifold setting. Geodesically convex optimization is a well-studied problem with ongoing research and considerable recent interest in machine learning and theoretical computer science. In this paper, we study sampling and convex optimization problems over manifolds of non-negative curvature proving polynomial running time in the dimension and other relevant parameters. Our algorithms assume a warm start. We first present a random walk based sampling algorithm and then combine it with simulated annealing for solving convex optimization problems. To our knowledge, these are the first algorithms in the general setting of positively curved manifolds with provable polynomial guarantees under reasonable assumptions, and the first study of the connection between sampling and optimization in this setting. △ Less

Submitted 24 July, 2019; originally announced July 2019.

Comments: Appeared at COLT 2019

Report number: PMLR 99:1519-1561, 2019

$n$-VDD: Location Privacy Protection Based on Voronoi-Delaunay Duality

Authors: Wei Zeng, Abdur B. Shahid, Keyan Zolfaghari, Aditya Shetty, Niki Pissinou, Sitharama S. Iyengar

Abstract: To date, location privacy protection is a critical issue in Location-Based Services (LBS). In this work, we propose a novel geometric framework based on the classical discrete geometric structure, the Voronoi-Delaunay duality (VDD). We utilize the fact that the user location cannot be recovered if only given an irregular $n$-sided Voronoi cell around it, and the anonymity zone is the intersection… ▽ More To date, location privacy protection is a critical issue in Location-Based Services (LBS). In this work, we propose a novel geometric framework based on the classical discrete geometric structure, the Voronoi-Delaunay duality (VDD). We utilize the fact that the user location cannot be recovered if only given an irregular $n$-sided Voronoi cell around it, and the anonymity zone is the intersection of all the parallel strips perpendicular to and bounded by $n$ Voronoi edges. The irregular Voronoi cell and its variations can be used as the concealing space to hide the user location or the region of interest and submitted to the LBS server. Within this framework, we propose multiple typical anonymizing models by introducing irregularity to the convex regular VDD structure by shifting the interior Voronoi cell, exterior Delaunay polygon, sector rays, or their combinations. The proposed methods are efficient by taking advantage of the VDD principle where main computations are linear line-line intersections. Experiments with various parameters demonstrate the efficiency and efficacy of the proposed $n$-VDD framework. △ Less

Submitted 21 June, 2019; originally announced June 2019.

Comments: 12 pages, 19 figures

An Open-Source Benchmark Suite for Cloud and IoT Microservices

Authors: Yu Gan, Yanqi Zhang, Dailun Cheng, Ankitha Shetty, Priyal Rathi, Nayan Katarki, Ariana Bruno, Justin Hu, Brian Ritchken, Brendon Jackson, Kelvin Hu, Meghna Pancholi, Yuan He, Brett Clancy, Chris Colen, Fukang Wen, Catherine Leung, Siyuan Wang, Leon Zaruvinsky, Mateo Espinosa, Rick Lin, Zhongling Liu, Jake Padilla, Christina Delimitrou

Abstract: Cloud services have recently started undergoing a major shift from monolithic applications, to graphs of hundreds of loosely-coupled microservices. Microservices fundamentally change a lot of assumptions current cloud systems are designed with, and present both opportunities and challenges when optimizing for quality of service (QoS) and utilization. In this paper we explore the implications micro… ▽ More Cloud services have recently started undergoing a major shift from monolithic applications, to graphs of hundreds of loosely-coupled microservices. Microservices fundamentally change a lot of assumptions current cloud systems are designed with, and present both opportunities and challenges when optimizing for quality of service (QoS) and utilization. In this paper we explore the implications microservices have across the cloud system stack. We first present DeathStarBench, a novel, open-source benchmark suite built with microservices that is representative of large end-to-end services, modular and extensible. DeathStarBench includes a social network, a media service, an e-commerce site, a banking system, and IoT applications for coordination control of UAV swarms. We then use DeathStarBench to study the architectural characteristics of microservices, their implications in networking and operating systems, their challenges with respect to cluster management, and their trade-offs in terms of application design and programming frameworks. Finally, we explore the tail at scale effects of microservices in real deployments with hundreds of users, and highlight the increased pressure they put on performance predictability. △ Less

Submitted 27 May, 2019; originally announced May 2019.

UAV Pose Estimation using Cross-view Geolocalization with Satellite Imagery

Authors: Akshay Shetty, Grace Xingxin Gao

Abstract: We propose an image-based cross-view geolocalization method that estimates the global pose of a UAV with the aid of georeferenced satellite imagery. Our method consists of two Siamese neural networks that extract relevant features despite large differences in viewpoints. The input to our method is an aerial UAV image and nearby satellite images, and the output is the weighted global pose estimate… ▽ More We propose an image-based cross-view geolocalization method that estimates the global pose of a UAV with the aid of georeferenced satellite imagery. Our method consists of two Siamese neural networks that extract relevant features despite large differences in viewpoints. The input to our method is an aerial UAV image and nearby satellite images, and the output is the weighted global pose estimate of the UAV camera. We also present a framework to integrate our cross-view geolocalization output with visual odometry through a Kalman filter. We build a dataset of simulated UAV images and satellite imagery to train and test our networks. We show that our method performs better than previous camera pose estimation methods, and we demonstrate our networks ability to generalize well to test datasets with unseen images. Finally, we show that integrating our method with visual odometry significantly reduces trajectory estimation errors. △ Less

Submitted 16 September, 2018; originally announced September 2018.

Comments: Submitted as contributed paper to ICRA 2019

Non-Gaussian Component Analysis using Entropy Methods

Authors: Navin Goyal, Abhishek Shetty

Abstract: Non-Gaussian component analysis (NGCA) is a problem in multidimensional data analysis which, since its formulation in 2006, has attracted considerable attention in statistics and machine learning. In this problem, we have a random variable $X$ in $n$-dimensional Euclidean space. There is an unknown subspace $Γ$ of the $n$-dimensional Euclidean space such that the orthogonal projection of $X$ onto… ▽ More Non-Gaussian component analysis (NGCA) is a problem in multidimensional data analysis which, since its formulation in 2006, has attracted considerable attention in statistics and machine learning. In this problem, we have a random variable $X$ in $n$-dimensional Euclidean space. There is an unknown subspace $Γ$ of the $n$-dimensional Euclidean space such that the orthogonal projection of $X$ onto $Γ$ is standard multidimensional Gaussian and the orthogonal projection of $X$ onto $Γ^{\perp}$, the orthogonal complement of $Γ$, is non-Gaussian, in the sense that all its one-dimensional marginals are different from the Gaussian in a certain metric defined in terms of moments. The NGCA problem is to approximate the non-Gaussian subspace $Γ^{\perp}$ given samples of $X$. Vectors in $Γ^{\perp}$ correspond to `interesting' directions, whereas vectors in $Γ$ correspond to the directions where data is very noisy. The most interesting applications of the NGCA model is for the case when the magnitude of the noise is comparable to that of the true signal, a setting in which traditional noise reduction techniques such as PCA don't apply directly. NGCA is also related to dimension reduction and to other data analysis problems such as ICA. NGCA-like problems have been studied in statistics for a long time using techniques such as projection pursuit. We give an algorithm that takes polynomial time in the dimension $n$ and has an inverse polynomial dependence on the error parameter measuring the angle distance between the non-Gaussian subspace and the subspace output by the algorithm. Our algorithm is based on relative entropy as the contrast function and fits under the projection pursuit framework. The techniques we develop for analyzing our algorithm maybe of use for other related problems. △ Less

Submitted 4 November, 2018; v1 submitted 13 July, 2018; originally announced July 2018.

Exponential Weights on the Hypercube in Polynomial Time

Authors: Sudeep Raja Putta, Abhishek Shetty

Abstract: We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of $n$ objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the total cost incurred over all iterations and the cost of the best fixed subset in h… ▽ More We study a general online linear optimization problem(OLO). At each round, a subset of objects from a fixed universe of $n$ objects is chosen, and a linear cost associated with the chosen subset is incurred. To measure the performance of our algorithms, we use the notion of regret which is the difference between the total cost incurred over all iterations and the cost of the best fixed subset in hindsight. We consider Full Information and Bandit feedback for this problem. This problem is equivalent to OLO on the $\{0,1\}^n$ hypercube. The Exp2 algorithm and its bandit variant are commonly used strategies for this problem. It was previously unknown if it is possible to run Exp2 on the hypercube in polynomial time. In this paper, we present a polynomial time algorithm called PolyExp for OLO on the hypercube. We show that our algorithm is equivalent Exp2 on $\{0,1\}^n$, Online Mirror Descent(OMD), Follow The Regularized Leader(FTRL) and Follow The Perturbed Leader(FTPL) algorithms. We show PolyExp achieves expected regret bound that is a factor of $\sqrt{n}$ better than Exp2 in the full information setting under $L_\infty$ adversarial losses. Because of the equivalence of these algorithms, this implies an improvement on Exp2's regret bound in full information. We also show matching regret lower bounds. Finally, we show how to use PolyExp on the $\{-1,+1\}^n$ hypercube, solving an open problem in Bubeck et al (COLT 2012). △ Less

Submitted 22 August, 2019; v1 submitted 12 June, 2018; originally announced June 2018.

Show and Recall: Learning What Makes Videos Memorable

Authors: Sumit Shekhar, Dhruv Singal, Harvineet Singh, Manav Kedia, Akhil Shetty

Abstract: With the explosion of video content on the Internet, there is a need for research on methods for video analysis which take human cognition into account. One such cognitive measure is memorability, or the ability to recall visual content after watching it. Prior research has looked into image memorability and shown that it is intrinsic to visual content, but the problem of modeling video memorabili… ▽ More With the explosion of video content on the Internet, there is a need for research on methods for video analysis which take human cognition into account. One such cognitive measure is memorability, or the ability to recall visual content after watching it. Prior research has looked into image memorability and shown that it is intrinsic to visual content, but the problem of modeling video memorability has not been addressed sufficiently. In this work, we develop a prediction model for video memorability, including complexities of video content in it. Detailed feature analysis reveals that the proposed method correlates well with existing findings on memorability. We also describe a novel experiment of predicting video sub-shot memorability and show that our approach improves over current memorability methods in this task. Experiments on standard datasets demonstrate that the proposed metric can achieve results on par or better than the state-of-the art methods for video summarization. △ Less

Submitted 28 August, 2017; v1 submitted 17 July, 2017; originally announced July 2017.

Comments: 10 pages, updated abstract, added few references, project page link and acknowledgements. Accepted at ICCV 2017 Workshop on Mutual Benefits of Cognitive and Computer Vision (MBCC)

Analysis of Maximum Likelihood and Mahalanobis Distance for Identifying Cheating Anchor Nodes

Authors: Jeril Kuriakose, Amruth V., Sandesh A. G., Jampu Venkata Naveenbabu, Mohammed Shahid, Ashish Shetty

Abstract: Malicious anchor nodes will constantly hinder genuine and appropriate localization. Discovering the malicious or vulnerable anchor node is an essential problem in wireless sensor networks (WSNs). In wireless sensor networks, anchor nodes are the nodes that know its current location. Neighboring nodes or non-anchor nodes calculate its location (or its location reference) with the help of anchor nod… ▽ More Malicious anchor nodes will constantly hinder genuine and appropriate localization. Discovering the malicious or vulnerable anchor node is an essential problem in wireless sensor networks (WSNs). In wireless sensor networks, anchor nodes are the nodes that know its current location. Neighboring nodes or non-anchor nodes calculate its location (or its location reference) with the help of anchor nodes. Ingenuous localization is not possible in the presence of a cheating anchor node or a cheating node. Nowadays, its a challenging task to identify the cheating anchor node or cheating node in a network. Even after finding out the location of the cheating anchor node, there is no assurance, that the identified node is legitimate or not. This paper aims to localize the cheating anchor nodes using trilateration algorithm and later associate it with maximum likelihood expectation technique (MLE), and Mahalanobis distance to obtain maximum accuracy in identifying malicious or cheating anchor nodes during localization. We were able to attain a considerable reduction in the error achieved during localization. For implementation purpose we simulated our scheme using ns-3 network simulator. △ Less

Submitted 9 December, 2014; originally announced December 2014.

Comments: 10 pages, 13 pages, conference

Stereo Acoustic Perception based on Real Time Video Acquisition for Navigational Assistance

Authors: Supreeth K. Rao, Arpitha Prasad B., Anushree R. Shetty, Chinmai, R. Bhakthavathsalam, Rajeshwari Hegde

Abstract: A smart navigation system (an Electronic Travel Aid) based on an object detection mechanism has been designed to detect the presence of obstacles that immediately impede the path, by means of real time video processing. The algorithm can be used for any general purpose navigational aid. This paper is discussed, keeping in mind the navigation of the visually impaired, and is not limited to the same… ▽ More A smart navigation system (an Electronic Travel Aid) based on an object detection mechanism has been designed to detect the presence of obstacles that immediately impede the path, by means of real time video processing. The algorithm can be used for any general purpose navigational aid. This paper is discussed, keeping in mind the navigation of the visually impaired, and is not limited to the same. A video camera feeds images of the surroundings to a Da- Vinci Digital Media Processor, DM642, which works on the video, frame by frame. The processor carries out image processing techniques whose result contains information about the object in terms of image pixels. The algorithm aims to select the object which, among all others, poses maximum threat to the navigation. A database containing a total of three sounds is constructed. Hence, each image translates to a beep, where every beep informs the navigator of the obstacles directly in front of him. This paper implements an algorithm that is more efficient as compared to its predecessors. △ Less

Submitted 9 August, 2012; originally announced August 2012.

Comments: 12 pages, 8 figures, 1 table, SIPM-2012, pp. 97-108, 2012; http://airccj.org/CSCP/vol2/csit2311.pdf