GenAI4ELab/papercli-papers huggingface dataset:
On the Surprising Effectiveness of Attention Transfer for Vision Transformers
Authors: Alexander Cong Li; Yuandong Tian; Beidi Chen; Deepak Pathak; Xinlei Chen
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Conventional wisdom suggests that pre-training Vision Transformers (ViT) improves downstream performance by learning useful representations. Is this actually true? We investigate this question and find that the features and representations learned during pre-training are not essential.  Surprisingly, using only the attention patterns from pre-training (i.e., guiding how information flows between tokens) is sufficient for models to learn high quality features from scratch and achieve comparable downstream performance. We show this by introducing a simple method called attention transfer, where only the attention patterns from a pre-trained teacher ViT are transferred to a student, either by copying or distilling the attention maps. Since attention transfer lets the student learn its own features, ensembling it with a fine-tuned teacher also further improves accuracy on ImageNet. We systematically study various aspects of our findings on the sufficiency of attention maps, including distribution shift settings where they underperform fine-tuning. We hope our exploration provides a better understanding of what pre-training accomplishes and leads to a useful alternative to the standard practice of fine-tuning.
A Canonicalization Perspective on Invariant and Equivariant Learning
Authors: George Ma; Yifei Wang; Derek Lim; Stefanie Jegelka; Yisen Wang
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: In many applications, we desire neural networks to exhibit invariance or equivariance to certain groups due to symmetries inherent in the data. Recently, frame-averaging methods emerged to be a unified framework for attaining symmetries efficiently by averaging over input-dependent subsets of the group, i.e., frames. What we currently lack is a principled understanding of the design of frames. In this work, we introduce a canonicalization perspective that provides an essential and complete view of the design of frames. Canonicalization is a classic approach for attaining invariance by mapping inputs to their canonical forms. We show that there exists an inherent connection between frames and canonical forms. Leveraging this connection, we can efficiently compare the complexity of frames as well as determine the optimality of certain frames. Guided by this principle, we design novel frames for eigenvectors that are strictly superior to existing methods --- some are even optimal --- both theoretically and empirically. The reduction to the canonicalization perspective further uncovers equivalences between previous methods. These observations suggest that canonicalization provides a fundamental understanding of existing frame-averaging methods and unifies existing equivariant and invariant learning methods. Code is available at https://github.com/PKU-ML/canonicalization.
SkiLD: Unsupervised Skill Discovery Guided by Factor Interactions
Authors: Zizhao Wang; Jiaheng Hu; Caleb Chuck; Stephen Chen; Roberto Martín-Martín; Amy Zhang; Scott Niekum; Peter Stone
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Unsupervised skill discovery carries the promise that an intelligent agent can learn reusable skills through autonomous, reward-free interactions with environments. Existing unsupervised skill discovery methods learn skills by encouraging distinguishable behaviors that cover diverse states. However, in complex environments with many state factors (e.g., household environments with many objects), learning skills that cover all possible states is impossible, and naively encouraging state diversity often leads to simple skills that are not ideal for solving downstream tasks. This work introduces Skill Discovery from Local Dependencies (SkiLD), which leverages state factorization as a natural inductive bias to guide the skill learning process. The key intuition guiding SkiLD is that skills that induce \textbf{diverse interactions} between state factors are often more valuable for solving downstream tasks. To this end, SkiLD develops a novel skill learning objective that explicitly encourages the mastering of skills that effectively induce different interactions within an environment. We evaluate SkiLD in several domains with challenging, long-horizon sparse reward tasks including a realistic simulated household robot domain, where SkiLD successfully learns skills with clear semantic meaning and shows superior performance compared to existing unsupervised reinforcement learning methods that only maximize state coverage.
SpaFL: Communication-Efficient Federated Learning With Sparse Models And Low Computational Overhead
Authors: Minsu Kim; Walid Saad; Merouane Abdelkader DEBBAH; Choong Seon Hong
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: The large communication and computation overhead of federated learning (FL) is one of the main challenges facing its practical deployment over resource-constrained clients and systems. In this work, SpaFL: a communication-efficient FL framework is proposed to optimize sparse model structures  with low computational overhead. In SpaFL, a trainable threshold is defined for each filter/neuron to prune its all connected 
parameters, thereby leading to structured sparsity. To optimize the pruning process itself,  only thresholds are communicated between a server and clients instead of parameters, thereby learning how to prune. Further, global thresholds are used to update model parameters by extracting aggregated parameter importance. The generalization bound of SpaFL is also derived, thereby proving key insights on the relation between sparsity and performance. Experimental results show that SpaFL improves accuracy while requiring much less communication and computing resources compared to sparse baselines. The code is available at https://github.com/news-vt/SpaFL_NeruIPS_2024
UniAR: A Unified model for predicting human Attention and Responses on visual content
Authors: Peizhao Li; Junfeng He; Gang Li; Rachit Bhargava; Shaolei Shen; NACHIAPPAN VALLIAPPAN; Youwei Liang; Hongxiang Gu; Venky Ramachandran; Golnaz farhadi; Yang Li; Kai J Kohlhoff; Vidhya Navalpakkam
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Progress in human behavior modeling involves understanding both implicit, early-stage perceptual behavior, such as human attention, and explicit, later-stage behavior, such as subjective preferences or likes. Yet most prior research has focused on modeling implicit and explicit human behavior in isolation; and often limited to a specific type of visual content. We propose UniAR -- a unified model of human attention and preference behavior across diverse visual content. UniAR leverages a multimodal transformer to predict subjective feedback, such as satisfaction or aesthetic quality, along with the underlying human attention or interaction heatmaps and viewing order. We train UniAR on diverse public datasets spanning natural images, webpages, and graphic designs, and achieve SOTA performance on multiple benchmarks across various image domains and behavior modeling tasks. Potential applications include providing instant feedback on the effectiveness of UIs/visual content, and enabling designers and content-creation models to optimize their creation for human-centric improvements.
Hypothesis Testing the Circuit Hypothesis in LLMs
Authors: Claudia Shi; Nicolas Beltran-Velez; Achille Nazaret; Carolina Zheng; Adrià Garriga-Alonso; Andrew Jesson; Maggie Makar; David Blei
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Large language models (LLMs) demonstrate surprising capabilities, but we do not understand how they are implemented. 
One hypothesis suggests that these capabilities are primarily executed by small subnetworks within the LLM, known as circuits. But how can we evaluate this hypothesis?
In this paper, we formalize a set of criteria that a circuit is hypothesized to meet and develop a suite of hypothesis tests to evaluate how well circuits satisfy them. 
The criteria focus on the extent to which the LLM's behavior is preserved, the degree of localization of this behavior, and whether the circuit is minimal.
We apply these tests to six circuits described in the research literature. 
We find that synthetic circuits -- circuits that are hard-coded in the model -- align with the idealized properties. 
Circuits discovered in Transformer models satisfy the criteria to varying degrees.
To facilitate future empirical studies of circuits, we created the \textit{circuitry} package, a wrapper around the \textit{TransformerLens} library, which abstracts away lower-level manipulations of hooks and activations. The software is available at \url{https://github.com/blei-lab/circuitry}.
Reconstruction Attacks on Machine Unlearning: Simple Models are Vulnerable
Authors: Martin Andres Bertran; Shuai Tang; Michael Kearns; Jamie Heather Morgenstern; Aaron Roth; Steven Wu
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Machine unlearning is motivated by principles of data autonomy. The premise is that a person can request to have their data's influence removed from deployed models, and those models should be updated as if they were retrained without the person's data. We show that these updates expose individuals to high-accuracy reconstruction attacks which allow the attacker to recover their data in its entirety, even when the original models are so simple that privacy risk might not otherwise have been a concern. We show how to mount a near-perfect attack on the deleted data point from linear regression models. We then generalize our attack to other loss functions and architectures,  and empirically demonstrate the effectiveness of our attacks across a wide range of datasets (capturing both tabular and image data). Our work highlights that privacy risk is significant even for extremely simple model classes when individuals can request deletion of their data from the model.
Explaining Datasets in Words: Statistical Models with Natural Language Parameters
Authors: Ruiqi Zhong; Heng Wang; Dan Klein; Jacob Steinhardt
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: To make sense of massive data, we often first fit simplified models and then interpret the parameters; for example, we cluster the text embeddings and then interpret the mean parameters of each cluster.
However, these parameters are often high-dimensional and hard to interpret.
To make model parameters directly interpretable, we introduce a family of statistical models---including clustering, time series, and classification models---parameterized by *natural language predicates*. 
For example, a cluster of text about COVID could be parameterized by the predicate ``*discusses COVID*''.
To learn these statistical models effectively, we develop a model-agnostic algorithm that optimizes continuous relaxations of predicate parameters with gradient descent and discretizes them by prompting language models (LMs).
Finally, we apply our framework to a wide range of problems: taxonomizing user chat dialogues, characterizing how they evolve across time, finding categories where one language model is better than the other, clustering math problems based on subareas, and explaining visual features in memorable images.
Our framework is highly versatile, applicable to both textual and visual domains, can be easily steered to focus on specific properties (e.g. subareas), and explains sophisticated concepts that classical methods (e.g. n-gram analysis) struggle to produce.
Faster Algorithms for User-Level Private Stochastic Convex Optimization
Authors: Andrew Lowy; Daogao Liu; Hilal Asi
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: We study private stochastic convex optimization (SCO) under user-level differential privacy (DP) constraints. In this setting, there are $n$ users (e.g., cell phones), each possessing $m$ data items (e.g., text messages), and we need to protect the privacy of each user's entire collection of data items. Existing algorithms for user-level DP SCO are impractical in many large-scale machine learning scenarios because: (i) they make restrictive assumptions on the smoothness parameter of the loss function and require the number of users to grow polynomially with the dimension of the parameter space; or (ii) they are prohibitively slow, requiring at least $(mn)^{3/2}$ gradient computations for smooth losses and $(mn)^3$ computations for non-smooth losses. To address these limitations, we provide novel user-level DP algorithms with state-of-the-art excess risk and runtime guarantees, without stringent assumptions. First, we develop a linear-time algorithm with state-of-the-art excess risk (for a non-trivial linear-time algorithm) under a mild smoothness assumption. Our second algorithm applies to arbitrary smooth losses and achieves optimal excess risk in $\approx (mn)^{9/8}$ gradient computations. Third, for non-smooth loss functions, we obtain optimal excess risk in $n^{11/8} m^{5/4}$ gradient computations. Moreover, our algorithms do not require the number of users to grow polynomially with the dimension.
Task Confusion and Catastrophic Forgetting in Class-Incremental Learning: A Mathematical Framework for Discriminative and Generative Modelings
Authors: Milad Khademi Nori; IL MIN KIM
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: In class-incremental learning (class-IL), models must classify all previously seen classes at test time without task-IDs, leading to task confusion. Despite being a key challenge, task confusion lacks a theoretical understanding. We present a novel mathematical framework for class-IL and prove the Infeasibility Theorem, showing optimal class-IL is impossible with discriminative modeling due to task confusion. However, we establish the Feasibility Theorem, demonstrating that generative modeling can achieve optimal class-IL by overcoming task confusion. We then assess popular class-IL strategies, including regularization, bias-correction, replay, and generative classifier, using our framework. Our analysis suggests that adopting generative modeling, either for generative replay or direct classification (generative classifier), is essential for optimal class-IL.
Boundary Decomposition for Nadir Objective Vector Estimation
Authors: Ruihao Zheng; Zhenkun Wang
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: The nadir objective vector plays a key role in solving multi-objective optimization problems (MOPs), where it is often used to normalize the objective space and guide the search. The current methods for estimating the nadir objective vector perform effectively only on specific MOPs. This paper reveals the limitations of these methods: exact methods can only work on discrete MOPs, while heuristic methods cannot deal with the MOP with a complicated feasible objective region. To fill this gap, we propose a general and rigorous method, namely boundary decomposition for nadir objective vector estimation (BDNE). BDNE scalarizes the MOP into a set of boundary subproblems. By utilizing bilevel optimization, boundary subproblems are optimized and adjusted alternately, thereby refining their optimal solutions to align with the nadir objective vector. We prove that the bilevel optimization identifies the nadir objective vector under mild conditions. We compare BDNE with existing methods on various black-box MOPs. The results conform to the theoretical analysis and show the significant potential of BDNE for real-world application.
OSLO: One-Shot Label-Only Membership Inference Attacks
Authors: Yuefeng Peng; Jaechul Roh; Subhransu Maji; Amir Houmansadr
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: We introduce One-Shot Label-Only (OSLO) membership inference attacks (MIAs), which accurately infer a given sample's membership in a target model's training set with high precision using just a single query, where the target model only returns the predicted hard label. 
  This is in contrast to state-of-the-art label-only attacks which require $\sim6000$ queries, yet get attack precisions lower than OSLO's.
  OSLO leverages transfer-based black-box adversarial attacks. The core idea is that a member sample exhibits more resistance to adversarial perturbations than  a non-member. We compare OSLO against state-of-the-art label-only attacks and demonstrate that, despite requiring only one query, our method significantly outperforms previous attacks in terms of precision and true positive rate (TPR) under the same false positive rates (FPR). For example, compared to previous label-only MIAs, OSLO achieves a TPR that is at least 7$\times$ higher under a 1\% FPR and at least 22$\times$ higher under a 0.1\% FPR on CIFAR100 for a ResNet18 model. We evaluated multiple defense mechanisms against OSLO.
End-To-End Causal Effect Estimation from Unstructured Natural Language Data
Authors: Nikita Dhawan; Leonardo Cotta; Karen Ullrich; Rahul Krishnan; Chris J. Maddison
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Knowing the effect of an intervention is critical for human decision-making, but current approaches for causal effect estimation rely on manual data collection and structuring, regardless of the causal assumptions. This increases both the cost and time-to-completion for studies. We show how large, diverse observational text data can be mined with large language models (LLMs) to produce inexpensive causal effect estimates under appropriate causal assumptions. We introduce _NATURAL_, a novel family of causal effect estimators built with LLMs that operate over datasets of unstructured text. Our estimators use LLM conditional distributions (over variables of interest, given the text data) to assist in the computation of classical estimators of causal effect. We overcome a number of technical challenges to realize this idea, such as automating data curation and using LLMs to impute missing information. We prepare six (two synthetic and four real) observational datasets, paired with corresponding ground truth in the form of randomized trials, which we used to systematically evaluate each step of our pipeline. NATURAL estimators demonstrate remarkable performance, yielding causal effect estimates that fall within 3 percentage points of their ground truth counterparts, including on real-world Phase 3/4 clinical trials. Our results suggest that unstructured text data is a rich source of causal effect information, and NATURAL is a first step towards an automated pipeline to tap this resource.
Semidefinite Relaxations of the Gromov-Wasserstein Distance
Authors: Junyu Chen; Binh Nguyen; Shang Hui Koh; Yong Sheng Soh
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: The Gromov-Wasserstein (GW) distance is an extension of the optimal transport problem that allows one to match objects between incomparable spaces.  At its core, the GW distance is specified as the solution of a non-convex quadratic program and is not known to be tractable to solve.  In particular, existing solvers for the GW distance are only able to find locally optimal solutions.  In this work, we propose a semi-definite programming (SDP) relaxation of the GW distance. The relaxation can be viewed as the Lagrangian dual of the GW distance augmented with constraints that relate to the linear and quadratic terms of transportation plans. In particular, our relaxation provides a tractable (polynomial-time) algorithm to compute globally optimal transportation plans (in some instances) together with an accompanying proof of global optimality.  Our numerical experiments suggest that the proposed relaxation is strong in that it frequently computes the globally optimal solution.  Our Python implementation is available at https://github.com/tbng/gwsdp.
Are Graph Neural Networks Optimal Approximation Algorithms?
Authors: Morris Yau; Nikolaos Karalias; Eric Hanqing Lu; Jessica Xu; Stefanie Jegelka
Venue: NeurIPS 2024 (NeurIPS 2024 spotlight)

Abstract: In this work we design graph neural network architectures that capture optimal
approximation algorithms for a large class of combinatorial optimization problems,
using powerful algorithmic tools from semidefinite programming (SDP). Concretely, we prove that polynomial-sized message-passing algorithms can represent
the most powerful polynomial time algorithms for Max Constraint Satisfaction
Problems assuming the Unique Games Conjecture. We leverage this result to
construct efficient graph neural network architectures, OptGNN, that obtain high quality approximate solutions on landmark combinatorial optimization problems
such as Max-Cut, Min-Vertex-Cover, and Max-3-SAT. Our approach achieves
strong empirical results across a wide range of real-world and synthetic datasets
against solvers and neural baselines. Finally, we take advantage of OptGNN’s
ability to capture convex relaxations to design an algorithm for producing bounds
on the optimal solution from the learned embeddings of OptGNN.
TableRAG: Million-Token Table Understanding with Language Models
Authors: Si-An Chen; Lesly Miculicich; Julian Martin Eisenschlos; Zifeng Wang; Zilong Wang; Yanfei Chen; Yasuhisa Fujii; Hsuan-Tien Lin; Chen-Yu Lee; Tomas Pfister
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Recent advancements in language models (LMs) have notably enhanced their ability to reason with tabular data, primarily through program-aided mechanisms that manipulate and analyze tables.
However, these methods often require the entire table as input, leading to scalability challenges due to the positional bias or context length constraints.
In response to these challenges, we introduce TableRAG, a Retrieval-Augmented Generation (RAG) framework specifically designed for LM-based table understanding.
TableRAG leverages query expansion combined with schema and cell retrieval to pinpoint crucial information  before providing it to the LMs.
This enables more efficient data encoding and precise retrieval, significantly reducing prompt lengths and mitigating information loss.
We have developed two new million-token benchmarks from the Arcade and BIRD-SQL datasets to thoroughly evaluate TableRAG's effectiveness at scale.
Our results demonstrate that TableRAG's retrieval design achieves the highest retrieval quality, leading to the new state-of-the-art performance on large-scale table understanding.
One-Shot Safety Alignment for Large Language Models via Optimal Dualization
Authors: Xinmeng Huang; Shuo Li; Edgar Dobriban; Osbert Bastani; Hamed Hassani; Dongsheng Ding
Venue: NeurIPS 2024 (NeurIPS 2024 spotlight)

Abstract: The growing safety concerns surrounding large language models raise an urgent need to align them with diverse human preferences to simultaneously enhance their helpfulness and safety. A promising approach is to enforce safety constraints through Reinforcement Learning from Human Feedback (RLHF). For such constrained RLHF, typical Lagrangian-based primal-dual policy optimization methods are computationally expensive and often unstable. This paper presents a perspective of dualization that  reduces constrained alignment to an equivalent unconstrained alignment problem. We do so by pre-optimizing a smooth and convex dual function that has a closed form. This shortcut eliminates the need for cumbersome primal-dual policy iterations, greatly reducing the computational burden and improving training stability. Our strategy leads to two practical algorithms in model-based and preference-based settings (MoCAN and PeCAN, respectively). A broad range of experiments demonstrate the effectiveness and merits of our algorithms.