pwc-archive/papers-with-abstracts huggingface dataset:
Budget-aware Query Tuning: An AutoML Perspective
Authors: Wentao Wu, Chi Wang
Date: 2024-03-29 00:00:00
Tasks: AutoML

Modern database systems rely on cost-based query optimizers to come up with good execution plans for input queries. Such query optimizers rely on cost models to estimate the costs of candidate query execution plans. A cost model represents a function from a set of cost units to query execution cost, where each cost unit specifies the unit cost of executing a certain type of query processing operation (such as table scan or join). These cost units are traditionally viewed as constants, whose values only depend on the platform configuration where the database system runs on top of but are invariant for queries processed by the database system. In this paper, we challenge this classic view by thinking of these cost units as variables instead. We show that, by varying the cost-unit values one can obtain query plans that significantly outperform the default query plans returned by the query optimizer when viewing the cost units as constants. We term this cost-unit tuning process "query tuning" (QT) and show that it is similar to the well-known hyper-parameter optimization (HPO) problem in AutoML. As a result, any state-of-the-art HPO technologies can be applied to QT. We study the QT problem in the context of anytime tuning, which is desirable in practice by constraining the total time spent on QT within a given budget -- we call this problem budget-aware query tuning. We further extend our study from tuning a single query to tuning a workload with multiple queries, and we call this generalized problem budget-aware workload tuning (WT), which aims for minimizing the execution time of the entire workload. WT is more challenging as one needs to further prioritize individual query tuning within the given time budget. We propose solutions to both QT and WT and experimental evaluation using both benchmark and real workloads demonstrates the efficacy of our proposed solutions.
Computation and Communication Efficient Lightweighting Vertical Federated Learning for Smart Building IoT
Authors: Heqiang Wang, Xiang Liu, Yucheng Liu, Jia Zhou, Weihong Yang, Xiaoxiong Zhong
Date: 2024-03-30 00:00:00
Tasks: Computational Efficiency, Federated Learning, image-classification, Image Classification, Vertical Federated Learning

With the increasing number and enhanced capabilities of IoT devices in smart buildings, these devices are evolving beyond basic data collection and control to actively participate in deep learning tasks. Federated Learning (FL), as a decentralized learning paradigm, is well-suited for such scenarios. However, the limited computational and communication resources of IoT devices present significant challenges. While existing research has extensively explored efficiency improvements in Horizontal FL, these techniques cannot be directly applied to Vertical FL due to fundamental differences in data partitioning and model structure. To address this gap, we propose a Lightweight Vertical Federated Learning (LVFL) framework that jointly optimizes computational and communication efficiency. Our approach introduces two distinct lightweighting strategies: one for reducing the complexity of the feature model to improve local computation, and another for compressing feature embeddings to reduce communication overhead. Furthermore, we derive a convergence bound for the proposed LVFL algorithm that explicitly incorporates both computation and communication lightweighting ratios. Experimental results on an image classification task demonstrate that LVFL effectively mitigates resource demands while maintaining competitive learning performance.
Explaining deep learning models for ozone pollution prediction via embedded feature selection
Authors: Manuel Jesús Jiménez Navarro, María Martínez Ballesteros, Francisco Martínez Álvarez, Gualberto Asencio Cortés
Date: 2024-03-21 00:00:00
Proceeding: Applied Soft Computing 2024 3
Tasks: feature selection, Time Series, Time Series Forecasting, Time Series Prediction

Ambient air pollution is a pervasive global issue that poses significant health risks. Among pollutants, ozone (O3) is responsible for an estimated 1 to 1.2 million premature deaths yearly. Furthermore, O3 adversely affects climate warming, crop productivity, and more. Its formation occurs when nitrogen oxides and volatile organic compounds react with short-wavelength solar radiation. Consequently, urban areas with high traffic volume and elevated temperatures are particularly prone to elevated O3 levels, which pose a significant health risk to their inhabitants. In response to this problem, many countries have developed web and mobile applications that provide real-time air pollution information using sensor data. However, while these applications offer valuable insight into current pollution levels, predicting future pollutant behavior is crucial for effective planning and mitigation strategies. Therefore, our main objectives are to develop accurate and efficient prediction models and identify the key factors that influence O3 levels. We adopt a time series forecasting approach to address these objectives, which allows us to analyze and predict future O3 behavior. Additionally, we tackle the feature selection problem to identify the most relevant features and periods that contribute to prediction accuracy by introducing a novel method called the Time Selection Layer in Deep Learning models, which significantly improves model performance, reduces complexity, and enhances interpretability. Our study focuses on data collected from five representative areas in Seville, Cordova, and Jaen provinces in Spain, using multiple sensors to capture comprehensive pollution data. We compare the performance of three models: Lasso, Decision Tree, and Deep Learning with and without incorporating the Time Selection Layer. Our results demonstrate that including the Time Selection Layer significantly enhances the effectiveness and interpretability of Deep Learning models, achieving an average effectiveness improvement of 9% across all monitored areas.
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis
Date: 2024-03-31 00:00:00
Tasks: PAC learning

We study the efficient learnability of low-degree polynomial threshold functions (PTFs) in the presence of a constant fraction of adversarial corruptions. Our main algorithmic result is a polynomial-time PAC learning algorithm for this concept class in the strong contamination model under the Gaussian distribution with error guarantee $O_{d, c}(\text{opt}^{1-c})$, for any desired constant $c>0$, where $\text{opt}$ is the fraction of corruptions. In the strong contamination model, an omniscient adversary can arbitrarily corrupt an $\text{opt}$-fraction of the data points and their labels. This model generalizes the malicious noise model and the adversarial label noise model. Prior to our work, known polynomial-time algorithms in this corruption model (or even in the weaker adversarial label noise model) achieved error $\tilde{O}_d(\text{opt}^{1/(d+1)})$, which deteriorates significantly as a function of the degree $d$. Our algorithm employs an iterative approach inspired by localization techniques previously used in the context of learning linear threshold functions. Specifically, we use a robust perceptron algorithm to compute a good partial classifier and then iterate on the unclassified points. In order to achieve this, we need to take a set defined by a number of polynomial inequalities and partition it into several well-behaved subsets. To this end, we develop new polynomial decomposition techniques that may be of independent interest.
Efficient 3D Implicit Head Avatar with Mesh-anchored Hash Table Blendshapes
Authors: Ziqian Bai, Feitong Tan, Sean Fanello, Rohit Pandey, Mingsong Dou, Shichen Liu, Ping Tan, yinda zhang
Date: 2024-04-02 00:00:00
Proceeding: CVPR 2024 1
Tasks: Neural Rendering

3D head avatars built with neural implicit volumetric representations have achieved unprecedented levels of photorealism. However, the computational cost of these methods remains a significant barrier to their widespread adoption, particularly in real-time applications such as virtual reality and teleconferencing. While attempts have been made to develop fast neural rendering approaches for static scenes, these methods cannot be simply employed to support realistic facial expressions, such as in the case of a dynamic facial performance. To address these challenges, we propose a novel fast 3D neural implicit head avatar model that achieves real-time rendering while maintaining fine-grained controllability and high rendering quality. Our key idea lies in the introduction of local hash table blendshapes, which are learned and attached to the vertices of an underlying face parametric model. These per-vertex hash-tables are linearly merged with weights predicted via a CNN, resulting in expression dependent embeddings. Our novel representation enables efficient density and color predictions using a lightweight MLP, which is further accelerated by a hierarchical nearest neighbor search method. Extensive experiments show that our approach runs in real-time while achieving comparable rendering quality to state-of-the-arts and decent results on challenging expressions.
3DGSR: Implicit Surface Reconstruction with 3D Gaussian Splatting
Authors: Xiaoyang Lyu, Yang-tian Sun, Yi-Hua Huang, Xiuzhe Wu, ZiYi Yang, Yilun Chen, Jiangmiao Pang, Xiaojuan Qi
Date: 2024-03-30 00:00:00
Tasks: 3DGS, 3D Reconstruction, Surface Reconstruction

In this paper, we present an implicit surface reconstruction method with 3D Gaussian Splatting (3DGS), namely 3DGSR, that allows for accurate 3D reconstruction with intricate details while inheriting the high efficiency and rendering quality of 3DGS. The key insight is incorporating an implicit signed distance field (SDF) within 3D Gaussians to enable them to be aligned and jointly optimized. First, we introduce a differentiable SDF-to-opacity transformation function that converts SDF values into corresponding Gaussians' opacities. This function connects the SDF and 3D Gaussians, allowing for unified optimization and enforcing surface constraints on the 3D Gaussians. During learning, optimizing the 3D Gaussians provides supervisory signals for SDF learning, enabling the reconstruction of intricate details. However, this only provides sparse supervisory signals to the SDF at locations occupied by Gaussians, which is insufficient for learning a continuous SDF. Then, to address this limitation, we incorporate volumetric rendering and align the rendered geometric attributes (depth, normal) with those derived from 3D Gaussians. This consistency regularization introduces supervisory signals to locations not covered by discrete 3D Gaussians, effectively eliminating redundant surfaces outside the Gaussian sampling range. Our extensive experimental results demonstrate that our 3DGSR method enables high-quality 3D surface reconstruction while preserving the efficiency and rendering quality of 3DGS. Besides, our method competes favorably with leading surface reconstruction techniques while offering a more efficient learning process and much better rendering qualities. The code will be available at https://github.com/CVMI-Lab/3DGSR.
P-Hologen: An End-to-End Generative Framework for Phase-Only Holograms
Authors: Joohyun Park, Yujin Jeon, HuiYong Kim, SeungHwan Baek, Hyeongyeop Kang
Date: 2024-03-29 00:00:00
Tasks: Computational Efficiency

Holography stands at the forefront of visual technology, offering immersive, three-dimensional visualizations through the manipulation of light wave amplitude and phase. Although generative models have been extensively explored in the image domain, their application to holograms remains relatively underexplored due to the inherent complexity of phase learning. Exploiting generative models for holograms offers exciting opportunities for advancing innovation and creativity, such as semantic-aware hologram generation and editing. Currently, the most viable approach for utilizing generative models in the hologram domain involves integrating an image-based generative model with an image-to-hologram conversion model, which comes at the cost of increased computational complexity and inefficiency. To tackle this problem, we introduce P-Hologen, the first end-to-end generative framework designed for phase-only holograms (POHs). P-Hologen employs vector quantized variational autoencoders to capture the complex distributions of POHs. It also integrates the angular spectrum method into the training process, constructing latent spaces for complex phase data using strategies from the image processing domain. Extensive experiments demonstrate that P-Hologen achieves superior quality and computational efficiency compared to the existing methods. Furthermore, our model generates high-quality unseen, diverse holographic content from its learned latent space without requiring pre-existing images. Our work paves the way for new applications and methodologies in holographic content creation, opening a new era in the exploration of generative holographic content. The code for our paper is publicly available on https://github.com/james0223/P-Hologen.
Priority-Neutral Matching Lattices Are Not Distributive
Authors: Clayton Thomas
Date: 2024-04-02 00:00:00

Stable matchings are a cornerstone of market design, with numerous practical deployments backed by a rich, theoretically-tractable structure. However, in school-choice problems, stable matchings are not Pareto optimal for the students. Priority-neutral matchings, introduced by Reny (AER, 2022), generalizes the set of stable matchings by allowing for certain priority violations, and there is always a Pareto optimal priority-neutral matching. Moreover, like stable matchings, the set of priority-neutral matchings forms a lattice. We study the structure of the priority-neutral lattice. Unfortunately, we show that much of the simplicity of the stable matching lattice does not hold for the priority-neutral lattice. In particular, we show that the priority-neutral lattice need not be distributive. Moreover, we show that the greatest lower bound of two matchings in the priority-neutral lattice need not be their student-by-student minimum, answering an open question. This show that many widely-used properties of stable matchings fail for priority-neutral matchings; in particular, the set of priority-neutral matchings cannot be represented by via a partial ordering on a set of rotations. However, by proving a novel structural property of the set of priority-neutral matchings, we also show that not every lattice arises as a priority-neutral lattice, which suggests that the exact nature of the family of priority-neutral lattices may be subtle.
Resolute and symmetric mechanisms for two-sided matching problems
Authors: Daniela Bubboloni, Michele Gori, Claudia Meo
Date: 2024-04-01 00:00:00
Tasks: Fairness

We focus on the one-to-one two-sided matching model with two disjoint sets of agents of equal size, where each agent in a set has preferences on the agents in the other set modeled by a linear order. A matching mechanism associates a set of matchings to each preference profile; resoluteness, that is the capability to select a unique matching, and stability are important properties for a matching mechanism. The two versions of the deferred acceptance algorithm are resolute and stable matching mechanisms but they are unfair since they strongly favor one side of the market. We introduce a property for matching mechanisms that relates to fairness; such property, called symmetry, captures different levels of fairness and generalizes existing notions. We provide several possibility and impossibility results mainly involving the most general notion of symmetry, known as gender fairness, resoluteness, stability, weak Pareto optimality and minimal optimality. In particular, we prove that: resolute, gender fair matching mechanisms exist if and only if each side of the market consists of an odd number of agents; there exists no resolute, gender fair, minimally optimal matching mechanism. Those results are obtained by employing algebraic methods based on group theory, an approach not yet explored in matching theory.
Learning and steering game dynamics towards desirable outcomes
Authors: Ilayda Canyakmaz, Iosif Sakos, Wayne Lin, Antonios Varvitsiotis, Georgios Piliouras
Date: 2024-04-01 00:00:00
Tasks: Model Predictive Control

Game dynamics, which describe how agents' strategies evolve over time based on past interactions, can exhibit a variety of undesirable behaviours including convergence to suboptimal equilibria, cycling, and chaos. While central planners can employ incentives to mitigate such behaviors and steer game dynamics towards desirable outcomes, the effectiveness of such interventions critically relies on accurately predicting agents' responses to these incentives -- a task made particularly challenging when the underlying dynamics are unknown and observations are limited. To address this challenge, this work introduces the Side Information Assisted Regression with Model Predictive Control (SIAR-MPC) framework. We extend the recently introduced SIAR method to incorporate the effect of control, enabling it to utilize side-information constraints inherent to game-theoretic applications to model agents' responses to incentives from scarce data. MPC then leverages this model to implement dynamic incentive adjustments. Our experiments demonstrate the effectiveness of SIAR-MPC in guiding systems towards socially optimal equilibria, stabilizing chaotic and cycling behaviors. Notably, it achieves these results in data-scarce settings of few learning samples, where well-known system identification methods paired with MPC show less effective results.
Shill-Proof Auctions
Authors: Andrew Komo, Scott Duke Kominers, Tim Roughgarden
Date: 2024-03-30 00:00:00

In an auction, a seller may masquerade as one or more bidders in order to manipulate the clearing price. We characterize single-item auction formats that are shill-proof in the sense that a profit-maximizing seller has no incentive to submit shill bids. We distinguish between strong shill-proofness, in which a seller with full knowledge of bidders' valuations can never profit from shilling, and weak shill-proofness, which requires only that the expected equilibrium profit from shilling is nonpositive. The Dutch auction (with a suitable reserve) is the unique (revenue-)optimal and strongly shill-proof auction. Moreover, the Dutch auction (with no reserve) is the unique prior-independent auction that is both efficient and weakly shill-proof. While there are multiple ex-post incentive compatible, weakly shill-proof, and optimal auctions; any optimal auction can satisfy only two properties in the set {static, ex-post incentive compatible, weakly shill-proof}.
Policy Optimization finds Nash Equilibrium in Regularized General-Sum LQ Games
Authors: Muhammad Aneeq uz Zaman, Shubham Aggarwal, Melih Bastopcu, Tamer Başar
Date: 2024-03-25 00:00:00
Tasks: Reinforcement Learning (RL)

In this paper, we investigate the impact of introducing relative entropy regularization on the Nash Equilibria (NE) of General-Sum $N$-agent games, revealing the fact that the NE of such games conform to linear Gaussian policies. Moreover, it delineates sufficient conditions, contingent upon the adequacy of entropy regularization, for the uniqueness of the NE within the game. As Policy Optimization serves as a foundational approach for Reinforcement Learning (RL) techniques aimed at finding the NE, in this work we prove the linear convergence of a policy optimization algorithm which (subject to the adequacy of entropy regularization) is capable of provably attaining the NE. Furthermore, in scenarios where the entropy regularization proves insufficient, we present a $\delta$-augmentation technique, which facilitates the achievement of an $\epsilon$-NE within the game.
Leveraging Digital Perceptual Technologies for Remote Perception and Analysis of Human Biomechanical Processes: A Contactless Approach for Workload and Joint Force Assessment
Authors: Jesudara Omidokun, Darlington Egeonu, Bochen Jia, Liang Yang
Date: 2024-04-02 00:00:00

This study presents an innovative computer vision framework designed to analyze human movements in industrial settings, aiming to enhance biomechanical analysis by integrating seamlessly with existing software. Through a combination of advanced imaging and modeling techniques, the framework allows for comprehensive scrutiny of human motion, providing valuable insights into kinematic patterns and kinetic data. Utilizing Convolutional Neural Networks (CNNs), Direct Linear Transform (DLT), and Long Short-Term Memory (LSTM) networks, the methodology accurately detects key body points, reconstructs 3D landmarks, and generates detailed 3D body meshes. Extensive evaluations across various movements validate the framework's effectiveness, demonstrating comparable results to traditional marker-based models with minor differences in joint angle estimations and precise estimations of weight and height. Statistical analyses consistently support the framework's reliability, with joint angle estimations showing less than a 5-degree difference for hip flexion, elbow flexion, and knee angle methods. Additionally, weight estimation exhibits an average error of less than 6 % for weight and less than 2 % for height when compared to ground-truth values from 10 subjects. The integration of the Biomech-57 landmark skeleton template further enhances the robustness and reinforces the framework's credibility. This framework shows significant promise for meticulous biomechanical analysis in industrial contexts, eliminating the need for cumbersome markers and extending its utility to diverse research domains, including the study of specific exoskeleton devices' impact on facilitating the prompt return of injured workers to their tasks.
Perceptogram: Reconstructing Visual Percepts from EEG
Authors: Teng Fei, Abhinav Uppal, Ian Jackson, Srinivas Ravishankar, David Wang, Virginia R. de Sa
Date: 2024-04-01 00:00:00
Tasks: Decoder, EEG, Image Reconstruction

Visual neural decoding from EEG has improved significantly due to diffusion models that can reconstruct high-quality images from decoded latents. While recent works have focused on relatively complex architectures to achieve good reconstruction performance from EEG, less attention has been paid to the source of this information. In this work, we attempt to discover EEG features that represent perceptual and semantic visual categories, using a simple pipeline. Notably, the high temporal resolution of EEG allows us to go beyond static semantic maps as obtained from fMRI. We show (a) Training a simple linear decoder from EEG to CLIP latent space, followed by a frozen pre-trained diffusion model, is sufficient to decode images with state-of-the-art reconstruction performance. (b) Mapping the decoded latents back to EEG using a linear encoder isolates CLIP-relevant EEG spatiotemporal features. (c) By using other latent spaces representing lower-level image features, we obtain similar time-courses of texture/hue-related information. We thus use our framework, Perceptogram, to probe EEG signals at various levels of the visual information hierarchy.