In this work we propose to combine the advantages of learning-based and combinatorial formalisms for 3D shape matching. While learning-based methods lead to state-of-the-art matching performance, they do not ensure geometric consistency, so that obtained matchings are locally non-smooth. On the contrary, axiomatic, optimisation-based methods allow to take geometric consistency into account by explicitly constraining the space of valid matchings. However, existing axiomatic formalisms do not scale to practically relevant problem sizes, and require user input for the initialisation of non-convex optimisation problems. We work towards closing this gap by proposing a novel combinatorial solver that combines a unique set of favourable properties: our approach (i) is initialisation free, (ii) is massively parallelisable and powered by a quasi-Newton method, (iii) provides optimality gaps, and (iv) delivers improved matching quality with decreased runtime and globally optimal results for many instances.
论文检索
输入标题、作者或关键词，从 1,217 篇学术成果中精准定位
Research of adversarial attacks is important for AI security because it shows the vulnerability of deep learning models and helps to build more robust models. Adversarial attacks on images are most widely studied, which include noise-based attacks, image editing-based attacks, and latent space-based attacks. However, the adversarial examples crafted by these methods often lack sufficient semantic information, making it challenging for humans to understand the failure modes of deep learning models under natural conditions. To address this limitation, we propose a natural language induced adversarial image attack method. The core idea is to leverage a text-to-image model to generate adversarial images given input prompts, which are maliciously constructed to lead to misclassification for a target model. To adopt commercial text-to-image models for synthesizing more natural adversarial images, we propose an adaptive genetic algorithm (GA) for optimizing discrete adversarial prompts without requiring gradients and an adaptive word space reduction method for improving query efficiency. We further used CLIP to maintain the semantic consistency of the generated images. In our experiments, we found that some high-frequency semantic information such as ''foggy'', ''humid'', ''stretching'', etc. can easily cause classifier errors. This adversarial semantic information exists not only in generated images but also in photos captured in the real world. We also found that some adversarial semantic information can be transferred to unknown classification tasks. Furthermore, our attack method can transfer to different text-to-image models (e.g., Midjourney, DALL·E 3, etc.) and image classifiers. Our code is available at:https://github.com/zxp555/Natural-Language-Induced-Adversarial-Images.
Recent advances in continuous super-resolution (SR) has made a substantial progress towards universal SR models, which are characterized by using a single deep neural network (DNN) to fulfill arbitrary scale SR tasks. When deployed on resource stringent platforms, however, a trained DNN model usually requires experience-demanding and laborious manual efforts to compress the models following a predetermined compute budget. This paper proposes an inference-time adaptive network width optimization method for arbitrary scale SR modules, dubbed as Scalable Super-Resolution Neural Operator (SSRNO), which is capable of efficient performance-preserving deployment on various mobile or edge devices with only a user input parameter indicating the desired compression rate. SSRNO realizes the continuous parameterization of SRNO (CVPR2023) by virtue of two novel contributions. First, we propose the Integral Neural Network (INN) formulation for the Galerkin type attention, which is an indispensable component for spatial discretization invariant SR neural networks. Second, we further propose an adaptive layer-wise compression rate estimation mechanism, which allows for flexible adaptation to variant capacity through the neural network layers. Extensive experiments validate the outperforming overall performances over existing continuous SR models in terms of reconstruction accuracy, model scalability as well as throughput. For instance, compared with the baseline SRNO, a typical configuration of SSRNO can achieve a model size compression up to 62% and an over 2x speedup in situations where resources are limited, while it can also expand itself to keep the PSNR degradation within 0.1 dB when the limitations are alleviated. The code is available at https://github.com/ZXS-Labs/SSRNO.
Self-supervised category-level 6D pose estimation stands as a fundamental task in computer vision. However, current self-supervised methods face two major challenges. Firstly, existing networks struggle to reconstruct precise object models due to significant part-level shape variations among specific categories. Secondly, they are impacted by the many-to-one ambiguity in the correspondences between pixels and point clouds. To address these challenges, we propose a novel approach that includes a Part-level Shape Reconstruction (PSR) module and a Coarse-to-Fine Correspondence Optimization (CFCO) module. In the (PSR) module, we introduce a part-level discrete shape memory to capture more fine-grained shape variations of different objects and use it to perform precise reconstruction. In the (CFCO) module, we utilize Hungarian matching to generate one-to-one pseudo labels at both region and pixel levels, which provides explicit supervision for the corresponding similarity matrices. We evaluate our method on the REAL275 and WILD6D datasets. Our extensive experiments show that our self-supervised approach outperforms existing methods and achieves new state-of-the-art results within the self-supervised framework.
Conversational Speech Synthesis (CSS) aims to express a target utterance with the proper speaking style in a user-agent conversation setting. Existing CSS methods employ effective multi-modal context modeling techniques to achieve empathy understanding and expression. However, they often need to design complex network architectures and meticulously optimize the modules within them. In addition, due to the limitations of small-scale datasets containing scripted recording styles, they often fail to simulate real natural conversational styles. To address the above issues, we propose a novel generative expressive CSS system, termed GPT-Talker.We transform the multimodal information of the multi-turn dialogue history into discrete token sequences and seamlessly integrate them to form a comprehensive user-agent dialogue context. Leveraging the power of GPT, we predict the token sequence, that includes both semantic and style knowledge, of response for the agent. After that, the expressive conversational speech is synthesized by the conversation-enriched VITS to deliver feedback to the user.Furthermore, we propose a large-scale Natural CSS Dataset called NCSSD, that includes both naturally recorded conversational speech in improvised styles and dialogues extracted from TV shows. It encompasses both Chinese and English languages, with a total duration of 236 hours. We conducted comprehensive experiments on the reliability of the NCSSD and the effectiveness of our GPT-Talker. Both subjective and objective evaluations demonstrate that our model outperforms other state-of-the-art CSS systems significantly in terms of naturalness and expressiveness. The Code, Dataset, and Pre-trained Model are available at: https://github.com/AI-S2-Lab/GPT-Talker.
The energy industry is undergoing significant transformations as it strives to achieve net-zero emissions and future-proof its infrastructure, where every participant in the power grid has the potential to both consume and produce energy resources. Federated learning -- which enables multiple participants to collaboratively train a model without aggregating the training data -- becomes a viable technology. However, the global model parameters that have to be shared for optimization are still susceptible to training data leakage. In this work, we propose confined gradient descent (CGD) that enhances the privacy of federated learning by eliminating the sharing of global model parameters. CGD exploits the fact that a gradient descent optimization can start with a set of discrete points and converges to another set in the neighborhood of the global minimum of the objective function. As such, each participant can independently initiate its own private global model~(referred to as the confined model ), and collaboratively learn it towards the optimum. The updates to their own models are worked out in a secure collaborative way during the training process.In such a manner, CGD retains the ability of learning from distributed data but greatly diminishes information sharing. Such a strategy also allows the proprietary confined models to adapt to the heterogeneity in federated learning, providing inherent benefits of fairness. We theoretically and empirically demonstrate that decentralized CGD øne provides a stronger differential privacy (DP) protection; \two is robust against the state-of-the-art poisoning privacy attacks; þree results in bounded fairness guarantee among participants; and \four provides high test accuracy (comparable with centralized learning) with a bounded convergence rate over four real-world datasets.
In causal inference, estimating heterogeneous treatment effects (HTE) is critical for identifying how different subgroups respond to interventions, with broad applications in fields such as precision medicine and personalized advertising. Although HTE estimation methods aim to improve accuracy, how to provide explicit subgroup descriptions remains unclear, hindering data interpretation and strategic intervention management. In this paper, we propose CURLS, a novel rule learning method leveraging HTE, which can effectively describe subgroups with significant treatment effects. Specifically, we frame causal rule learning as a discrete optimization problem, finely balancing treatment effect with variance and considering the rule interpretability. We design an iterative procedure based on the minorize-maximization algorithm and solve a submodular lower bound as an approximation for the original. Quantitative experiments and qualitative case studies verify that compared with state-of-the-art methods, CURLS can find subgroups where the estimated and true effects are 16.1% and 13.8% higher and the variance is 12.0% smaller, while maintaining similar or better estimation accuracy and rule interpretability. Code is available at https://osf.io/zwp2k/.
This paper addresses the problem of partial multi-label learning (PML), a challenging weakly supervised learning framework, where each sample is associated with a candidate label set comprising both ground-true labels and noisy labels. We theoretically reveal that an increased number of noisy labels in the candidate label set leads to an enlarged generalization error bound, consequently degrading the classification performance. Accordingly, the key to solving PML lies in accurately removing the noisy labels within the candidate label set. To achieve this objective, we leverage prior knowledge about the noisy labels in PML, which suggests that they only exist within the candidate label set and possess binary values. Specifically, we propose a constrained regression model to learn a PML classifier and select the noisy labels. The constraints of the model strictly enforce the location and value of the noisy labels. Simultaneously, the supervision information provided by the candidate label set is unreliable due to the presence of noisy labels. In contrast, the non-candidate labels of a sample precisely indicate the classes to which the sample does not belong. To aid in the selection of noisy labels, we construct a competitive classifier based on the non-candidate labels. The PML classifier and the competitive classifier form a competitive relationship, encouraging mutual learning. We formulate the proposed model as a discrete optimization problem to effectively remove the noisy labels, and we solve it using an alternative algorithm. Extensive experiments conducted on 6 real-world partial multi-label data sets and 7 synthetic data sets, employing various evaluation metrics, demonstrate that our method significantly outperforms state-of-the-art PML methods. The code implementation is publicly available at https://github.com/Yangfc-ML/NLR.
Traditional Neural Processes (NPs) and their variants aim to learn relationships between context sample points but do not consider multi-level information, resulting in a limited ability to learn complex distributions.This paper draws inspiration from features such as the hierarchical nature and interpretability of tree-like structures. This paper proposes a Hierarchical Linear Symbolized Tree-structured Neural Processes (HLNPs) architecture. This framework utilizes variables to build a top-down hierarchical linear symbolized tree-structured network architecture, enhancing positional representation information in a hierarchical manner along the deterministic path. In the latent distribution, the hierarchical linear symbolized tree-structured network approximates functions discretely through a layered approach. By decomposing the latent complex distribution into several simpler sub-problems using sum and product symbols, the upper bound of optimization is thereby increased. The tree structure discretizes variables to capture model uncertainty in the form of entropy. This approach also imparts a causal effect to the HLNPs model. Finally, we demonstrate the effectiveness of the HLNPs models for 1D data, Bayesian optimization, and 2D data.
Despite the recent progress of molecular representation learning, its effectiveness is assumed on the close-world assumptions that training and testing graphs are from identical distribution. The open-world test dataset is often mixed with out-of-distribution (OOD) samples, where the deployed models will struggle to make accurate predictions. The misleading estimations of molecules' properties in drug screening or design can result in the tremendous waste of wet-lab resources and delay the discovery of novel therapies. Traditional detection methods need to trade off OOD detection and in-distribution (ID) classification performance since they share the same representation learning model. In this work, we propose to detect OOD molecules by adopting an auxiliary diffusion model-based framework, which compares similarities between input molecules and reconstructed graphs. Due to the generative bias towards reconstructing ID training samples, the similarity scores of OOD molecules will be much lower to facilitate detection. Although it is conceptually simple, extending this vanilla framework to practical detection applications is still limited by two significant challenges. First, the popular similarity metrics based on Euclidian distance fail to consider the complex graph structure. Second, the generative model involving iterative denoising steps is notoriously time-consuming especially when it runs on the enormous pool of drugs. To address these challenges, our research pioneers an approach of Prototypical Graph Reconstruction for Molecular OOd Detection, dubbed as PGR-MOOD. Specifically, PGR-MOOD hinges on three innovations: i) An effective metric to comprehensively quantify the matching degree of input and reconstructed molecules according to their discrete edges and continuous node features; ii) A creative graph generator to construct a list of prototypical graphs that are in line with ID distribution but away from OOD one; iii) An efficient and scalable OOD detector to compare the similarity between test samples and pre-constructed prototypical graphs and omit the generative process on every new molecule. Extensive experiments on ten benchmark datasets and six baselines are conducted to demonstrate our superiority: PGR-MOOD achieves more than 8% of average improvement in terms of detection AUC and AUPR accompanied by the reduced cost of testing time and memory consumption. The anonymous code is in: https://github.com/se7esx/PGR-MOOD.
Given a multidimensional array, how can we optimize the computation process for a part of Fourier coefficients? Discrete Fourier transform plays an overarching role in various data mining tasks. Recent interest has focused on efficiently calculating a small part of Fourier coefficients, exploiting the energy compaction property of real-world data. Current methods for partial Fourier transform frequently encounter efficiency issues, yet the adoption of pre-computation techniques within the PFT algorithm has shown promising performance. However, PFT still faces limitations in handling multidimensional data efficiently and requires manual hyperparameter tuning, leading to additional costs. In this paper, we propose Auto-MPFT (Automatic Multidimensional Partial Fourier Transform), which efficiently computes a subset of Fourier coefficients in multidimensional data without the need for manual hyperparameter search. Auto-MPFT leverages multivariate polynomial approximation for trigonometric functions, generalizing its domain to multidimensional Euclidean space. Moreover, we present a convex optimization-based algorithm for automatically selecting the optimal hyperparameter of Auto-MPFT. We provide a rigorous proof for the explicit reformulation of the original optimization problem of Auto-MPFT, demonstrating the process that converts it into a well-established unconstrained convex optimization problem. Extensive experiments show that Auto-MPFT surpasses existing partial Fourier transform methods and optimized FFT libraries, achieving up to 7.6x increase in speed without sacrificing accuracy. In addition, our optimization algorithm accurately finds the optimal hyperparameter for Auto-MPFT, significantly reducing the cost associated with hyperparameter search.
Multi-task learning (MTL), which aims to make full use of knowledge contained in multiple tasks to enhance overall performance and efficiency, has been broadly applied in recommendations. The main challenge for MTL models is negative transfer. Existing MTL models, mainly built on the Mixture-of-Experts (MoE) structure, seek enhancements in performance through feature selection and specific expert sharing mode design. However, one expert sharing mode may not be universally applicable due to the complex correlations and diverse demands among various tasks. Additionally, homogeneous expert architectures in such models further limit their performance. To address these issues, in this paper, we propose an innovative automatic MTL framework, AutoMTL, leveraging neural architecture search (NAS) to design optimal expert architectures and sharing modes. The Dual-level Expert Sharing mode and Architecture Navigator (DESAN) search space of AutoMTL can not only efficiently explore expert sharing modes and feature selection schemes but also focus on the architectures of expert subnetworks. Along with this, we introduce an efficient Progressively Discretizing Differentiable Architecture Search (PD-DARTS) algorithm for search space exploration. Extensive experiments demonstrate that AutoMTL can consistently outperform state-of-the-art, human-crafted MTL models. Moreover, the insights obtained from the discovered architectures provide valuable guidance for building new multi-task recommendation models.
FreQuant: A Reinforcement-Learning based Adaptive Portfolio Optimization with Multi-frequency Decomposition
PDF ↗How can we leverage inherent frequency features of stock signals for effective portfolio optimization? Portfolio optimization in the domain of finance revolves around strategically allocating assets to maximize returns. Recent advancements highlight the efficacy of deep learning and reinforcement learning (RL) in capturing temporal asset patterns for portfolio optimization. However, previous methodologies focusing on time-domain often fail to detect sudden market shifts and abrupt events because their models are overly tailored to prevalent patterns, resulting in significant losses. In this paper, we propose FreQuant (Adaptive Portfolio Optimization via Multi-Frequency Quantitative Analysis), an effective deep RL framework for portfolio optimization that fully operates in the frequency domain, tackling the limitations of time domain-focused models. By bringing the analysis into the frequency domain with the Discrete Fourier Transform, our framework captures both prominent and subtle market frequencies, enhancing its adaptability and stability in response to market shifts. This approach allows FreQuant to adeptly identify primary asset patterns while also effectively responding to less common and abrupt market events, providing a more accurate and comprehensive asset representation. Empirical validation on diverse real-world trading datasets underscores the remarkable performance of FreQuant, showing its superiority in terms of profitability. Notably, FreQuant achieves up to 2.1x higher Annualized Rate of Return and 2.9x higher Portfolio Value than the best-performing competitors.
We investigate the existence and computation of fair and efficient allocations of indivisible chores to agents with additive preferences. We consider the popular envy-based fairness notions of envy-freeness up to one chore (EF1) and the efficiency notion of Pareto-optimality (PO). The existence of an allocation of chores that is simultaneously EF1 and PO is regarded a major open problem in discrete fair division. We show that an EF1 and PO allocation can be computed in polynomial time for certain structured instances. These results comprise the first non-trivial positive results for the problem and reveal insights towards settling the problem in its full generality.
Self-Repellent Random Walks on General Graphs - Achieving Minimal Sampling Variance via Nonlinear Markov Chains (Extended Abstract)
PDF ↗We consider random walks on discrete state spaces, such as general undirected graphs, where the random walkers are designed to approximate a target quantity over the network topology via sampling and neighborhood exploration in the form of Markov chain Monte Carlo (MCMC) procedures. Given any Markov chain corresponding to a target probability distribution, we design a self-repellent random walk (SRRW) which is less likely to transition to nodes that were highly visited in the past, and more likely to transition to seldom visited nodes. For a class of SRRWs parameterized by a positive real α, we prove that the empirical distribution of the process converges almost surely to the target (stationary) distribution of the underlying Markov chain kernel. We then provide a central limit theorem and derive the exact form of the arising asymptotic co-variance matrix, which allows us to show that the SRRW with stronger repellence (larger α) always achieves a smaller asymptotic covariance, in the sense of Loewner ordering of co-variance matrices. Especially for SRRW-driven MCMC algorithms, we show that the decrease in the asymptotic sampling variance is of the order O(1/α), eventually going down to zero. After generalizing these results for a class of weighted empirical measures, we use them as a stepping stone to show that a similar performance ordering can also be obtained for distributed stochastic optimization tasks using token algorithms. More explicitly, by replacing a Markovian token by a SRRW version with the same target distribution, we show that the asymptotic co-variance of the optimization iterates decreases at rate O(1/α^2) - the performance benefit of using SRRW thereby amplified in the stochastic optimization context. Empirical results support our theoretical findings.
The fabrication of visual misinformation on the web and social media has increased exponentially with the advent of foundational text-to-image diffusion models. Namely, Stable Diffusion inpainters allow the synthesis of maliciously inpainted images of personal and private figures, and copyrighted contents, also known as deepfakes. To combat such generations, a disruption framework, namely Photoguard, has been proposed, where it adds adversarial noise to the context image to disrupt their inpainting synthesis. While their framework suggested a diffusion-friendly approach, the disruption is not sufficiently strong and it requires a significant amount of GPU and time to immunize the context image. In our work, we re-examine both the minimal and favorable conditions for a successful inpainting disruption, proposing DDD, a “Digression guided Diffusion Disruption” framework. First, we identify the most adversarially vulnerable diffusion timestep range with respect to the hidden space. Within this scope of noised manifold, we pose the problem as a semantic digression optimization. We maximize the distance between the inpainting instance's hidden states and a semantic-aware hidden state centroid, calibrated both by Monte Carlo sampling of hidden states and a discretely projected optimization in the token space. Effectively, our approach achieves stronger disruption and a higher success rate than Photoguard while lowering the GPU memory requirement, and speeding the optimization up to three times faster.
Constrained text generation remains a challenging task, particularly when dealing with hard constraints. Traditional Natural Language Processing (NLP) approaches prioritize generating meaningful and coherent output. Also, the current state-of-the-art methods often lack the expressiveness and constraint satisfaction capabilities to handle such tasks effectively. This paper presents the Constraints First Framework to remedy this issue. This framework considers a constrained text generation problem as a discrete combinatorial optimization problem. It is solved by a constraint programming method that combines linguistic properties (e.g., n-grams or language level) with other more classical constraints (e.g., the number of characters, syllables, or words). Eventually, a curation phase allows for selecting the best-generated sentences according to perplexity using a large language model. The effectiveness of this approach is demonstrated by tackling a new more tediously constrained text generation problem: the iconic RADNER sentences problem. This problem aims to generate sentences respecting a set of quite strict rules defined by their use in vision and clinical research. Thanks to our CP-based approach, many new strongly constrained sentences have been successfully generated in an automatic manner. This highlights the potential of our approach to handle unreasonably constrained text generation scenarios.
Optimization models used to make discrete decisions often contain uncertain parameters that are context-dependent and estimated through prediction. To account for the quality of the decision made based on the prediction, decision-focused learning (end-to-end predict-then-optimize) aims at training the predictive model to minimize regret, i.e., the loss incurred by making a suboptimal decision. Despite the challenge of the gradient of this loss w.r.t. the predictive model parameters being zero almost everywhere for optimization problems with a linear objective, effective gradient-based learning approaches have been proposed to minimize the expected loss, using the empirical loss as a surrogate. However, empirical regret can be an ineffective surrogate because empirical optimal decisions can vary substantially from expected optimal decisions. To understand the impact of this deficiency, we evaluate the effect of aleatoric and epistemic uncertainty on the accuracy of empirical regret as a surrogate. Next, we propose three novel loss functions that approximate expected regret more robustly. Experimental results show that training two state-of-the-art decision-focused learning approaches using robust regret losses improves test-sample empirical regret in general while keeping computational time equivalent relative to the number of training epochs.
Learning Low-Rank Tensor Cores with Probabilistic ℓ0-Regularized Rank Selection for Model Compression
PDF ↗Compressing deep neural networks is of great importance for real-world applications on resource-constrained devices. Tensor decomposition is one promising answer that retains the functionality and most of the expressive power of the original deep models by replacing the weights with their decomposed cores. Decomposition with optimal ranks can achieve a good compression-accuracy trade-off, but it is expensive to optimize due to its discrete and combinatorial nature. A common practice is to set all ranks equal and tune one hyperparameter, but it may significantly harm the flexibility and generalization. In this paper, we propose a novel automatic rank selection method for deep model compression that allows learning model weights and decomposition ranks simultaneously. We propose to penalize the ℓ0 (quasi-)norm of the slices of decomposed tensor cores during model training. To avoid combinatorial optimization, we develop a probabilistic formulation and apply an approximate Bernoulli gate to each of the slices of tensor cores, which can be implemented in an end-to-end and scalable framework via gradient descent. It enables the automatic rank selection to be incorporated with arbitrary tensor decompositions and neural network layers such as linear layers, convolutional layers, and embedding layers. Comprehensive experiments on various tasks, including image classification, text sentiment classification, and neural machine translation, demonstrate the superior effectiveness of the proposed method over baselines.
This work studies Stackelberg network interdiction games --- an important class of games in which a defender first allocates (randomized) defense resources to a set of critical nodes on a graph while an adversary chooses its path to attack these nodes accordingly. We consider a boundedly rational adversary in which the adversary's response model is based on a dynamic form of classic logit-based (quantal response) discrete choice models. The resulting optimization is non-convex and additionally, involves complex terms that sum over exponentially many paths. We tackle these computational challenges by presenting new efficient algorithms with solution guarantees. First, we present a near optimal solution method based on path sampling, piece-wise linear approximation and mixed-integer linear programming (MILP) reformulation. Second, we explore a dynamic programming based method, addressing the exponentially-many-path challenge. We then show that the gradient of the non-convex objective can also be computed in polynomial time, which allows us to use a gradient-based method to solve the problem efficiently. Experiments based on instances of different sizes demonstrate the efficiency of our approach in achieving near-optimal solutions.