pwc-archive/papers-with-abstracts huggingface dataset:
Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems
Authors: Chhavi Sharma, Vishnu Narayanan, P. Balamurugan
Date: 2023-09-02 00:00:00

We consider a class of non-smooth strongly convex-strongly concave saddle point problems in a decentralized setting without a central server. To solve a consensus formulation of problems in this class, we develop an inexact primal dual hybrid gradient (inexact PDHG) procedure that allows generic gradient computation oracles to update the primal and dual variables. We first investigate the performance of inexact PDHG with stochastic variance reduction gradient (SVRG) oracle. Our numerical study uncovers a significant phenomenon of initial conservative progress of iterates of IPDHG with SVRG oracle. To tackle this, we develop a simple and effective switching idea, where a generalized stochastic gradient (GSG) computation oracle is employed to hasten the iterates' progress to a saddle point solution during the initial phase of updates, followed by a switch to the SVRG oracle at an appropriate juncture. The proposed algorithm is named Decentralized Proximal Switching Stochastic Gradient method with Compression (C-DPSSG), and is proven to converge to an $\epsilon$-accurate saddle point solution with linear rate. Apart from delivering highly accurate solutions, our study reveals that utilizing the best convergence phases of GSG and SVRG oracles makes C-DPSSG well suited for obtaining solutions of low/medium accuracy faster, useful for certain applications. Numerical experiments on two benchmark machine learning applications show C-DPSSG's competitive performance which validate our theoretical findings. The codes used in the experiments can be found \href{https://github.com/chhavisharma123/C-DPSSG-CDC2023}{here}.
Randomized Polar Codes for Anytime Distributed Machine Learning
Authors: Burak Bartan, Mert Pilanci
Date: 2023-09-01 00:00:00
Tasks: Cloud Computing, Distributed Computing

We present a novel distributed computing framework that is robust to slow compute nodes, and is capable of both approximate and exact computation of linear operations. The proposed mechanism integrates the concepts of randomized sketching and polar codes in the context of coded computation. We propose a sequential decoding algorithm designed to handle real valued data while maintaining low computational complexity for recovery. Additionally, we provide an anytime estimator that can generate provably accurate estimates even when the set of available node outputs is not decodable. We demonstrate the potential applications of this framework in various contexts, such as large-scale matrix multiplication and black-box optimization. We present the implementation of these methods on a serverless cloud computing system and provide numerical results to demonstrate their scalability in practice, including ImageNet scale computations.
Establishing Markov Equivalence in Cyclic Directed Graphs
Authors: Tom Claassen, Joris M. Mooij
Date: 2023-09-01 00:00:00

We present a new, efficient procedure to establish Markov equivalence between directed graphs that may or may not contain cycles under the \textit{d}-separation criterion. It is based on the Cyclic Equivalence Theorem (CET) in the seminal works on cyclic models by Thomas Richardson in the mid '90s, but now rephrased from an ancestral perspective. The resulting characterization leads to a procedure for establishing Markov equivalence between graphs that no longer requires tests for d-separation, leading to a significantly reduced algorithmic complexity. The conceptually simplified characterization may help to reinvigorate theoretical research towards sound and complete cyclic discovery in the presence of latent confounders. This version includes a correction to rule (iv) in Theorem 1, and the subsequent adjustment in part 2 of Algorithm 2.
Ensemble Fusion for Small Object Detection
Authors: Hao-Yu Hou, Mu-Yi Shen, Chia-Chi Hsu, En-Ming Huang, Yu-Chen Huang, Yu-Cheng Xia, Chien-Yao Wang, Chun-Yi Lee
Date: 2023-08-22 00:00:00
Proceeding: 18th International Conference on Machine Vision and Applications (MVA) 2023 8
Tasks: Object, object-detection, Object Detection, Small Object Detection

Detecting small objects is often impeded by blurriness and low resolution, which poses substantial challenges for accurately detecting and localizing such objects. In addition, conventional feature extraction methods usually face difficulties in capturing effective representations for these entities, as down-sampling and convolutional operations contribute to the blurring of small object details. To tackle these challenges, this study introduces an approach for detecting tiny objects through ensemble fusion, which leverages the advantages of multiple diverse model variants and combines their predictions. Experimental results reveal that the proposed method effectively harnesses the strengths of each model via ensemble fusion, leading to enhanced accuracy and robustness in small object detection. Our model achieves the highest score of 0.776 in terms of average precision (AP) at an IoU threshold of 0.5 in the MVA Challenge on Small Object Detection for Birds.
Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
Authors: Lukas Drexler, Annika Hennes, Abhiruk Lahiri, Melanie Schmidt, Julian Wargalla
Date: 2023-09-02 00:00:00
Tasks: Attribute, Fairness

The $k$-center problem is a classical clustering problem in which one is asked to find a partitioning of a point set $P$ into $k$ clusters such that the maximum radius of any cluster is minimized. It is well-studied. But what if we add up the radii of the clusters instead of only considering the cluster with maximum radius? This natural variant is called the $k$-min-sum-radii problem. It has become the subject of more and more interest in recent years, inspiring the development of approximation algorithms for the $k$-min-sum-radii problem in its plain version as well as in constrained settings. We study the problem for Euclidean spaces $\mathbb{R}^d$ of arbitrary dimension but assume the number $k$ of clusters to be constant. In this case, a PTAS for the problem is known (see Bandyapadhyay, Lochet and Saurabh, SoCG, 2023). Our aim is to extend the knowledge base for $k$-min-sum-radii to the domain of fair clustering. We study several group fairness constraints, such as the one introduced by Chierichetti et al. (NeurIPS, 2017). In this model, input points have an additional attribute (e.g., colors such as red and blue), and clusters have to preserve the ratio between different attribute values (e.g., have the same fraction of red and blue points as the ground set). Different variants of this general idea have been studied in the literature. To the best of our knowledge, no approximative results for the fair $k$-min-sum-radii problem are known, despite the immense amount of work on the related fair $k$-center problem. We propose a PTAS for the fair $k$-min-sum-radii problem in Euclidean spaces of arbitrary dimension for the case of constant $k$. To the best of our knowledge, this is the first PTAS for the problem. It works for different notions of group fairness.
A balanced Memristor-CMOS ternary logic family and its application
Authors: Xiao-Yuan Wang, Jia-Wei Zhou, Chuan-Tao Dong, Xin-Hui Chen, Sanjoy Kumar Nandi, Robert G. Elliman, Sung-Mo Kang, Herbert Ho-Ching Iu
Date: 2023-09-04 00:00:00

The design of balanced ternary digital logic circuits based on memristors and conventional CMOS devices is proposed. First, balanced ternary minimum gate TMIN, maximum gate TMAX and ternary inverters are systematically designed and verified by simulation, and then logic circuits such as ternary encoders, decoders and multiplexers are designed on this basis. Two different schemes are then used to realize the design of functional combinational logic circuits such as a balanced ternary half adder, multiplier, and numerical comparator. Finally, we report a series of comparisons and analyses of the two design schemes, which provide a reference for subsequent research and development of three-valued logic circuits.
MAGMA: Music Aligned Generative Motion Autodecoder
Authors: Sohan Anisetty, Amit Raj, James Hays
Date: 2023-09-03 00:00:00
Tasks: Audio Compression, Decoder, Motion Generation

Mapping music to dance is a challenging problem that requires spatial and temporal coherence along with a continual synchronization with the music's progression. Taking inspiration from large language models, we introduce a 2-step approach for generating dance using a Vector Quantized-Variational Autoencoder (VQ-VAE) to distill motion into primitives and train a Transformer decoder to learn the correct sequencing of these primitives. We also evaluate the importance of music representations by comparing naive music feature extraction using Librosa to deep audio representations generated by state-of-the-art audio compression algorithms. Additionally, we train variations of the motion generator using relative and absolute positional encodings to determine the effect on generated motion quality when generating arbitrarily long sequence lengths. Our proposed approach achieve state-of-the-art results in music-to-motion generation benchmarks and enables the real-time generation of considerably longer motion sequences, the ability to chain multiple motion sequences seamlessly, and easy customization of motion sequences to meet style requirements.
Quantifying MEV On Layer 2 Networks
Authors: Arthur Bagourd, Luca Georges Francois
Date: 2023-08-07 00:00:00
Tasks: Decision Making

This paper addresses the lack of research on quantifying Maximal Extractable Value (MEV) on Ethereum Layer 2 networks (L2s). Our findings reveal a substantial amount of MEV to be extracted on L2s, particularly on Polygon, with a lower bound of $213 million surpassing previous estimates. We observe that the majority of detected MEV on L2s consists of arbitrage opportunities, as liquidations are rare. These results emphasize the need for continuous monitoring and analysis of MEV on L2s, promoting informed decision-making for network selection and highlighting the associated risks.
Multimodal Contrastive Learning with Hard Negative Sampling for Human Activity Recognition
Authors: Hyeongju Choi, Apoorva Beedu, Irfan Essa
Date: 2023-09-03 00:00:00
Tasks: Activity Recognition, Contrastive Learning, Human Activity Recognition

Human Activity Recognition (HAR) systems have been extensively studied by the vision and ubiquitous computing communities due to their practical applications in daily life, such as smart homes, surveillance, and health monitoring. Typically, this process is supervised in nature and the development of such systems requires access to large quantities of annotated data. However, the higher costs and challenges associated with obtaining good quality annotations have rendered the application of self-supervised methods an attractive option and contrastive learning comprises one such method. However, a major component of successful contrastive learning is the selection of good positive and negative samples. Although positive samples are directly obtainable, sampling good negative samples remain a challenge. As human activities can be recorded by several modalities like camera and IMU sensors, we propose a hard negative sampling method for multimodal HAR with a hard negative sampling loss for skeleton and IMU data pairs. We exploit hard negatives that have different labels from the anchor but are projected nearby in the latent space using an adjustable concentration parameter. Through extensive experiments on two benchmark datasets: UTD-MHAD and MMAct, we demonstrate the robustness of our approach forlearning strong feature representation for HAR tasks, and on the limited data setting. We further show that our model outperforms all other state-of-the-art methods for UTD-MHAD dataset, and self-supervised methods for MMAct: Cross session, even when uni-modal data are used during downstream activity recognition.
Sherlock Holmes Doesn't Play Dice: The mathematics of uncertain reasoning when something may happen, that one is not even able to figure out
Authors: Guido Fioretti
Date: 2023-09-01 00:00:00

While Evidence Theory (also known as Dempster-Shafer Theory, or Belief Functions Theory) is being increasingly used in data fusion, its potentialities in the Social and Life Sciences are often obscured by lack of awareness of its distinctive features. In particular, with this paper I stress that an extended version of Evidence Theory can express the uncertainty deriving from the fear that events may materialize, that one is not even able to figure out. By contrast, Probability Theory must limit itself to the possibilities that a decision-maker is currently envisaging. I compare this extended version of Evidence Theory to sophisticated extensions of Probability Theory, such as imprecise and sub-additive probabilities, as well as unconventional versions of Information Theory that are employed in data fusion and transmission of cultural information. A further extension to multi-agent interaction is outlined.
Improving the State of the Art for Training Human-AI Teams: Technical Report #3 -- Analysis of Testbed Alternatives
Authors: Lillian Asiala, James E. McCarthy, Lixiao Huang
Date: 2023-08-29 00:00:00

Sonalysts is working on an initiative to expand our current expertise in teaming to Human-Artificial Intelligence (AI) teams by developing original research in this area. To provide a foundation for that research, Sonalysts is investigating the development of a Synthetic Task Environment (STE). In a previous report, we documented the findings of a recent outreach effort in which we asked military Subject Matter Experts (SMEs) and other researchers in the Human-AI teaming domain to identify the qualities that they most valued in a testbed. A surprising finding from that outreach was that several respondents recommended that our team look into existing human-AI teaming testbeds, rather than creating something new. Based on that recommendation, we conducted a systematic investigation of the associated landscape. In this report, we describe the results of that investigation. Building on the survey results, we developed testbed evaluation criteria, identified potential testbeds, and conducted qualitative and quantitative evaluations of candidate testbeds. The evaluation process led to five candidate testbeds for the research team to consider. In the coming months, we will assess the viability of the various alternatives and begin to execute our program of research.
Improving the State of the Art for Training Human-AI Teams: Technical Report #2 -- Results of Researcher Knowledge Elicitation Survey
Authors: James E. McCarthy, Lillian Asiala, LeeAnn Maryeski, Dawn Sillars
Date: 2023-08-29 00:00:00
Tasks: Survey

A consensus report produced for the Air Force Research Laboratory (AFRL) by the National Academies of Sciences, Engineering, and Mathematics documented a prevalent and increasing desire to support human-Artificial Intelligence (AI) teaming across military service branches. Sonalysts has begun an internal initiative to explore the training of Human-AI teams. The first step in this effort is to develop a Synthetic Task Environment (STE) that is capable of facilitating research on Human-AI teams. Our goal is to create a STE that offers a task environment that could support the breadth of research that stakeholders plan to perform within this domain. As a result, we wanted to sample the priorities of the relevant research community broadly, and the effort documented in this report is our initial attempt to do so. We created a survey that featured two types of questions. The first asked respondents to report their agreement with STE features that we anticipated might be important. The second represented open-ended questions that asked respondents to specify their priorities within several dimensions of the anticipated STE. The research team invited nineteen researchers from academic and Government labs to participate, and 11 were able to complete the survey. The team analyzed their responses to identify themes that emerged and topics that would benefit from further analysis. The most significant finding of the survey was that a number of researchers felt that various open-source STEs that would meet our needs already exist. Researchers also emphasized the need for automated transcription and coding tools to ease the burden of assessing inter-team communications; the importance of robust data capture and export capabilities; and the desirability of extensive flexibility across many aspects of the tool.
Improving the State of the Art for Training Human-AI Teams: Technical Report #1 -- Results of Subject-Matter Expert Knowledge Elicitation Survey
Authors: James E. McCarthy, Lillian Asiala, LeeAnn Maryeski, Nyla Warren
Date: 2023-08-29 00:00:00

A consensus report produced for the Air Force Research Laboratory by the National Academies of Sciences, Engineering, and Mathematics documented a prevalent and increasing desire to support human-Artificial Intelligence (AI) teaming across military service branches. Sonalysts has begun an internal initiative to explore the training of human-AI teams. The first step in this effort is to develop a Synthetic Task Environment (STE) that is capable of facilitating research on human-AI teams. We decided to use Joint All-Domain Command and Control (JADC2) as a focus point for developing the STE because the volume of sensor inputs and decision options within the JADC2 concept likely requires the use of AI systems to enable timely decisions. Given this focus, we engaged a number of Subject-Matter Experts (SMEs) with Command and Control experience to gain insight into developing a STE that embodied the teaming challenges associated with JADC2. This report documents our initial engagement with those stakeholders. The research team identified thirteen Sonalysts employees with military backgrounds and Command and Control experience, and invited them to participate. Twelve respondents completed the survey. The team then analyzed the responses to identify themes that emerged and topics that would benefit from further analysis. The results indicated that our SMEs were amenable to research using tasks that were analogous to those encountered in military environments, as long as they required teams to process a great deal of incoming data to arrive at complex decisions. The SMEs felt that the testbed should support 'teams of teams" that represented a matrixed organization, and that it should support a robust array to spoken, text-based, and face-to-face communications.
A Human-Machine Joint Learning Framework to Boost Endogenous BCI Training
Authors: Hanwen Wang, Yu Qi, Lin Yao, Yueming Wang, Dario Farina, Gang Pan
Date: 2023-08-25 00:00:00
Tasks: Decoder, EEG, Electroencephalogram (EEG), Motor Imagery

Brain-computer interfaces (BCIs) provide a direct pathway from the brain to external devices and have demonstrated great potential for assistive and rehabilitation technologies. Endogenous BCIs based on electroencephalogram (EEG) signals, such as motor imagery (MI) BCIs, can provide some level of control. However, mastering spontaneous BCI control requires the users to generate discriminative and stable brain signal patterns by imagery, which is challenging and is usually achieved over a very long training time (weeks/months). Here, we propose a human-machine joint learning framework to boost the learning process in endogenous BCIs, by guiding the user to generate brain signals towards an optimal distribution estimated by the decoder, given the historical brain signals of the user. To this end, we firstly model the human-machine joint learning process in a uniform formulation. Then a human-machine joint learning framework is proposed: 1) for the human side, we model the learning process in a sequential trial-and-error scenario and propose a novel ``copy/new'' feedback paradigm to help shape the signal generation of the subject toward the optimal distribution; 2) for the machine side, we propose a novel adaptive learning algorithm to learn an optimal signal distribution along with the subject's learning process. Specifically, the decoder reweighs the brain signals generated by the subject to focus more on ``good'' samples to cope with the learning process of the subject. Online and psuedo-online BCI experiments with 18 healthy subjects demonstrated the advantages of the proposed joint learning process over co-adaptive approaches in both learning efficiency and effectiveness.
Unreflected Acceptance -- Investigating the Negative Consequences of ChatGPT-Assisted Problem Solving in Physics Education
Authors: Lars Krupp, Steffen Steinert, Maximilian Kiefer-Emmanouilidis, Karina E. Avila, Paul Lukowicz, Jochen Kuhn, Stefan Küchemann, Jakob Karolus
Date: 2023-08-21 00:00:00

Large language models (LLMs) have recently gained popularity. However, the impact of their general availability through ChatGPT on sensitive areas of everyday life, such as education, remains unclear. Nevertheless, the societal impact on established educational methods is already being experienced by both students and educators. Our work focuses on higher physics education and examines problem solving strategies. In a study, students with a background in physics were assigned to solve physics exercises, with one group having access to an internet search engine (N=12) and the other group being allowed to use ChatGPT (N=27). We evaluated their performance, strategies, and interaction with the provided tools. Our results showed that nearly half of the solutions provided with the support of ChatGPT were mistakenly assumed to be correct by the students, indicating that they overly trusted ChatGPT even in their field of expertise. Likewise, in 42% of cases, students used copy & paste to query ChatGPT -- an approach only used in 4% of search engine queries -- highlighting the stark differences in interaction behavior between the groups and indicating limited reflection when using ChatGPT. In our work, we demonstrated a need to (1) guide students on how to interact with LLMs and (2) create awareness of potential shortcomings for users.
Data efficiency, dimensionality reduction, and the generalized symmetric information bottleneck
Authors: K. Michael Martini, Ilya Nemenman
Date: 2023-09-11 00:00:00
Tasks: Dimensionality Reduction

The Symmetric Information Bottleneck (SIB), an extension of the more familiar Information Bottleneck, is a dimensionality reduction technique that simultaneously compresses two random variables to preserve information between their compressed versions. We introduce the Generalized Symmetric Information Bottleneck (GSIB), which explores different functional forms of the cost of such simultaneous reduction. We then explore the dataset size requirements of such simultaneous compression. We do this by deriving bounds and root-mean-squared estimates of statistical fluctuations of the involved loss functions. We show that, in typical situations, the simultaneous GSIB compression requires qualitatively less data to achieve the same errors compared to compressing variables one at a time. We suggest that this is an example of a more general principle that simultaneous compression is more data efficient than independent compression of each of the input variables.