Author name cluster

Hong Qian

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers

2 author rows

IJCAI Conference 2025 Conference Paper

A Fast-Adaptive Cognitive Diagnosis Framework for Computerized Adaptive Testing Systems

Yuanhao Liu
Yiya You
Shuo Liu
Hong Qian
Ying Qian
Aimin Zhou

Computerized Adaptive Testing (CAT) measures student ability by iteratively selecting informative questions, with core components being the Cognitive Diagnosis Model (CDM) and selection strategy. Current research focuses on optimizing the selection strategy, assuming relatively accurate CDM results. However, existing static CDMs struggle with rapid and accurate diagnosis in the early stage of CAT. To this end, this paper proposes a Fast Adaptive Cognitive Diagnosis (FACD) framework, which incorporates dynamic collaborative and personalized diagnosis modules. Specifically, the collaborative module in FACD uses a dynamic response graph to quickly build student cognitive profiles, while the personalized module leverages each student's response sequence for robust and individualized diagnosis. Extensive experiments on real-world datasets show that, compared with existing static CDMs, FACD not only achieves superior prediction performance across various selection strategies with an improvement between roughly 5%-10% in the early stage of CAT, but also maintains a commendable inference speed.

PDF Details DOI

ECAI Conference 2025 Conference Paper

A Style-Aware Polytomous Diagnostic Model for Individual Traits

Yixuan Wang
Jiale Feng
Yue Huang
Xuruo Pan
Zhongjing Huang
Zhi Liu
Hong Qian

Diagnostic models aim to precisely infer individuals’ cognitive or non-cognitive competencies from their response logs, such as mathematical or social-emotional skills. While deep learning shows success in cognitive diagnosis, it remains underexplored in the equally important area of non-cognitive trait diagnosis. Accurate non-cognitive trait estimation is critical for individuals’ development. Unlike cognitive assessments using right or wrong responses, non-cognitive trait assessments typically use subjective Likert-scale items with ordinal polytomous options to reflect latent trait levels. Furthermore, individual response styles, such as tendencies toward higher or lower options, introduce bias in trait inference, causing estimations that deviate from true trait levels. Thus, maintaining options ordinal semantic structure and mitigating the response style bias in trait estimation are two major challenges for accurate trait diagnosis. To address these issues, this paper proposes a Style-Aware Polytomous Diagnosis (SAPD) model. Specifically, to capture the ordinal semantics of response options, SAPD constructs an Ordinal Option Graph (OOG) that explicitly encodes the ordinal relationship among polytomous options, where higher options reflect higher latent trait levels. To mitigate the bias caused by individual response styles, we first design a Style-Aware Relational Graph (SARG), a heterogeneous graph that integrates multiple interactions among participants, items, options and traits, implicitly embedding response style information within node representations. We then propose a Response Style Corrector (RSC) that explicitly captures individual response tendencies and disentangles response style bias during trait diagnosis, allowing for dynamic and adaptive correction of trait levels. Extensive experiments on five real-world datasets show that SAPD improves accuracy by an average of 4% over competitive methods. Visualizations confirm SAPD effectively disentangles response style effects, leading to more accurate and interpretable trait diagnosis.

Details

AAAI Conference 2025 Conference Paper

Constrained Offline Black-Box Optimization via Risk Evaluation and Management

Yiyi Zhu
Huakang Lu
Yupeng Wu
Shuo Liu
Jing-Wen Yang
Hong Qian

Offline black-box optimization aims to identify the optimal solution of a black-box objective function under the guidance of a surrogate model constructed solely from a pre-collected dataset. It is commonly used in industrial scenarios, which often involve constraints, i.e., constrained offline optimization (COO). Offline optimization has progressed in addressing the out-of-distribution (OOD) issue caused by its inherent inability to interact with the objective function. However, there is not enough research in addressing more difficult scenarios, which must simultaneously address OOD issues and constrained issues to find stable, high-quality (i.e., high-scoring and feasible) solutions. To bridge this gap, this paper proposes a method called constrained offline optimization via risk evaluation and management (COOREM), which is capable of consistently surpassing the offline dataset under the condition of satisfying constraints. Specifically, COOREM employs a dual-energy model to separately evaluate OOD risk and constrained risk. This separation strategy aims to distinguish and address two difficult cases: the infeasible but not OOD solutions and the feasible but OOD solutions. Moreover, COOREM effectively manages OOD risk and constrained risk, ensuring the identification of high-quality solutions. Extensive experiments on real-world tasks, e.g., space missions, process synthesis, and design problems, showcase COOREM's effectiveness in managing both OOD risk and constrained risk. Furthermore, our findings indicate that COOREM could outperform online methods that need to access the objective function in certain space missions.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Expensive Multi-Objective Bayesian Optimization Based on Diffusion Models

Bingdong Li
Zixiang Di
Yongfan Lu
Hong Qian
Feng Wang
Peng Yang
Ke Tang
Aimin Zhou

Multi-objective Bayesian optimization (MOBO) has shown promising performance on various expensive multi-objective optimization problems (EMOPs). However, effectively modeling complex distributions of the Pareto optimal solutions is difficult with limited function evaluations. Existing Pareto set learning algorithms may exhibit considerable instability in such expensive scenarios, leading to significant deviations between the obtained solution set and the Pareto set (PS). In this paper, we propose a novel Composite Diffusion Model based Pareto Set Learning algorithm (CDM-PSL) for expensive MOBO. CDM-PSL includes both unconditional and conditional diffusion model for generating high-quality samples efficiently. Besides, we introduce a weighting method based on information entropy to balance different objectives. This method is integrated with a guiding strategy to appropriately balancing different objectives during the optimization process. Experimental results on both synthetic and real-world problems demonstrates that CDM-PSL attains superior performance compared with state-of-the-art MOBO algorithms.

PDF Details DOI

AAMAS Conference 2025 Conference Paper

InCLET: Large Language Model In-context Learning can Improve Embodied Instruction-following

Peng-Yuan Wang
Jing-Cheng Pang
Chen-Yang Wang
Xuhui Liu
Tian-Shuo Liu
Si-Hang Yang
Hong Qian
Yang Yu

Natural language-conditioned reinforcement learning (NLC-RL) empowers embodied agent to complete various tasks following human instruction. However, the unbounded natural language examples still introduce much complexity for the agent that solves concrete RL tasks, which can distract policy learning from completing the task. Consequently, extracting effective task representation from human instruction emerges as the critical component of NLC-RL. While previous methods have attempted to address this issue by learning task-related representation using large language models (LLMs), they highly rely on pre-collected task data and require extra training procedure. In this study, we uncover the inherent capability of LLMs to generate task representations and present a novel method, in-context learning embedding as task representation (InCLET). InCLET is grounded on a foundational finding that LLM in-context learning using trajectories can greatly help represent tasks. We thus firstly employ LLM to imagine task trajectories following the natural language instruction, then use in-context learning of LLM to generate task representations, and ∗Equal Contribution †Corresponding Author. This work is licensed under a Creative Commons Attribution International 4. 0 License. Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025), Y. Vorobeychik, S. Das, A. Nowé (eds.), May 19 – 23, 2025, Detroit, Michigan, USA. © 2025 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). finally aggregate and project into a compact low-dimensional task representation. This representation is then used to train a human instruction-following agent. We conduct experiments on various embodied control environments and results show that InCLET creates effective task representations. Furthermore, this representation can significantly improve the RL training efficiency, compared to the baseline methods.

PDF

ICLR Conference 2025 Conference Paper

LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch

Caigao Jiang
Xiang Shu
Hong Qian
Xingyu Lu
Jun Zhou
Aimin Zhou
Yang Yu

Optimization problems are prevalent across various scenarios. Formulating and then solving optimization problems described by natural language often requires highly specialized human expertise, which could block the widespread application of optimization-based decision making. To automate problem formulation and solving, leveraging large language models (LLMs) has emerged as a potential way. However, this kind of approach suffers from the issue of optimization generalization. Namely, the accuracy of most current LLM-based methods and the generality of optimization problem types that they can model are still limited. In this paper, we propose a unified learning-based framework called LLMOPT to boost optimization generalization. Starting from the natural language descriptions of optimization problems and a pre-trained LLM, LLMOPT constructs the introduced five-element formulation as a universal model for learning to define diverse optimization problem types. Then, LLMOPT employs the multi-instruction tuning to enhance both problem formalization and solver code generation accuracy and generality. After that, to prevent hallucinations in LLMs, such as sacrificing solving accuracy to avoid execution errors, the model alignment and self-correction mechanism are adopted in LLMOPT. We evaluate the optimization generalization ability of LLMOPT and compared methods across six real-world datasets covering roughly 20 fields such as health, environment, energy and manufacturing, etc. Extensive experiment results show that LLMOPT is able to model various optimization problem types such as linear/nonlinear programming, mixed integer programming, and combinatorial optimization, and achieves a notable 11.08% average solving accuracy improvement compared with the state-of-the-art methods. The code is available at https://github.com/caigaojiang/LLMOPT.

Details

ICLR Conference 2025 Conference Paper

Preference Diffusion for Recommendation

Shuo Liu 0017
An Zhang 0003
Guoqing Hu
Hong Qian
Tat-Seng Chua

Recommender systems aim to predict personalized item rankings by modeling user preference distributions derived from historical behavior data. While diffusion models (DMs) have recently gained attention for their ability to model complex distributions, current DM-based recommenders typically rely on traditional objectives such as mean squared error (MSE) or standard recommendation objectives. These approaches are either suboptimal for personalized ranking tasks or fail to exploit the full generative potential of DMs. To address these limitations, we propose \textbf{PreferDiff}, an optimization objective tailored for DM-based recommenders. PreferDiff reformulates the traditional Bayesian Personalized Ranking (BPR) objective into a log-likelihood generative framework, enabling it to effectively capture user preferences by integrating multiple negative samples. To handle the intractability, we employ variational inference, minimizing the variational upper bound. Furthermore, we replace MSE with cosine error to improve alignment with recommendation tasks, and we balance generative learning and preference modeling to enhance the training stability of DMs. PreferDiff devises three appealing properties. First, it is the first personalized ranking loss designed specifically for DM-based recommenders. Second, it improves ranking performance and accelerates convergence by effectively addressing hard negatives. Third, we establish its theoretical connection to Direct Preference Optimization (DPO), demonstrating its potential to align user preferences within a generative modeling framework. Extensive experiments across six benchmarks validate PreferDiff's superior recommendation performance. Our codes are available at \url{https://github.com/lswhim/PreferDiff}.

Details

IJCAI Conference 2025 Conference Paper

Relation-Augmented Dueling Bayesian Optimization via Preference Propagation

Xiang Xia
Xiang Shu
Shuo Liu
Yiyi Zhu
Yijie Zhou
Weiye Wang
Bingdong Li
Hong Qian

In black-box optimization, when directly evaluating the function values of solutions is very costly or infeasible, access to the objective function is often limited to comparing pairs of solutions, which yields dueling black-box optimization. Dueling optimization is solely based on pairwise preferences, and thus notably reduces cost compared with function value based methods. However, the optimization performance of dueling optimization is often limited due to that most existing dueling optimization methods do not make full use of the pairwise preferences collected. To better utilize these preferences, this paper proposes relation-augmented dueling Bayesian optimization (RADBO) via preference propagation. By considering solution similarity, RADBO aims to uncover the potential dueling relations between solutions within different preferences through the proposed preference propagation technique. Specifically, RADBO first clusters solutions using a Gaussian mixture model. After obtaining the solution set with the highest intra-cluster similarity, RADBO utilizes a directed hypergraph to model the potential dueling relations between solutions, thereby realizing relation augmentation. Extensive experiments are conducted on both synthetic functions and real-world tasks such as motion control, car cab design and spacecraft trajectory optimization. The experimental results disclose the satisfactory accuracy of augmented preferences in RADBO, and show the superiority of RADBO compared with existing dueling optimization methods. Notably, it is verified that, under the same evaluation cost budget, RADBO can be competitive with or even surpass the function value based Bayesian optimization methods with respect to optimization performance.

PDF Details DOI

ICLR Conference 2025 Conference Paper

SOO-Bench: Benchmarks for Evaluating the Stability of Offline Black-Box Optimization

Hong Qian
Yiyi Zhu
Xiang Shu
Shuo Liu
Yaolin Wen
Xin An
Huakang Lu
Aimin Zhou

Black-box optimization aims to find the optima through building a model close to the black-box objective function based on function value evaluation. However, in many real-world tasks, such as the design of molecular formulas and mechanical structures, it is perilous, costly, or even infeasible to evaluate the objective function value of an actively sampled solution. In this situation, optimization can only be conducted via utilizing offline historical data, which yields offline black-box optimization. Different from the traditional goal that is to pursue the optimal solution, this paper emphasizes that the goal of offline optimization is to stably surpass the offline dataset during optimization procedure. Although benchmarks called Design-Bench already exist in this emerging field, it can hardly evaluate the stability of offline optimization and mainly provides real-world offline tasks and the corresponding offline datasets. To this end, this paper proposes benchmarks named SOO-Bench (i.e., Stable Offline Optimization Benchmarks) for offline black-box optimization algorithms, so as to systematically evaluate the stability of surpassing the offline dataset under different data distributions. Along with SOO-Bench, we also propose a stability indicator to measure the degree of stability. Specifically, SOO-Bench includes various real-world offline optimization tasks and offline datasets under different data distributions, involving the fields of satellites, materials science, structural mechanics, and automobile manufacturing. Empirically, baseline and state-of-the-art algorithms are tested and analyzed on SOO-Bench. Hopefully, SOO-Bench is expected to serve as a catalyst for the rapid developments of more novel and stable offline optimization methods. The code is available at \url{https://github.com/zhuyiyi-123/SOO-Bench}.

Details

ICML Conference 2025 Conference Paper

Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models

Mingjia Li 0002
Hong Qian
Tian-Zuo Wang
Shujun Li
Min Zhang 0068
Aimin Zhou

Causal discovery aims to identify causal relationships from observational data. Recently, optimization-based causal discovery methods have attracted extensive attention in the literature due to their efficiency in handling high-dimensional problems. However, we observe that optimization-based methods often perform well on certain problems but struggle with others. This paper identifies a specific characteristic of causal structural equations that determines the difficulty of identification in causal discovery and, in turn, the performance of optimization-based methods. We conduct an in-depth study of the additive noise model (ANM) and propose to further divide identifiable problems into strongly and weakly identifiable types based on the difficulty of identification. We also provide a sufficient condition to distinguish the two categories. Inspired by these findings, this paper further proposes GENE, a generic method for addressing strongly and weakly identifiable problems in a unified way under the ANM assumption. GENE adopts an order-based search framework that incorporates conditional independence tests into order fitness evaluation, ensuring effectiveness on weakly identifiable problems. In addition, GENE restricts the dimensionality of the effect variables to ensure scale invariance, a property crucial for practical applications. Experiments demonstrate that GENE is uniquely effective in addressing weakly identifiable problems while also remaining competitive with state-of-the-art causal discovery algorithms for strongly identifiable problems.

Details

NeurIPS Conference 2024 Conference Paper

A Simple yet Scalable Granger Causal Structural Learning Approach for Topological Event Sequences

Mingjia Li
Shuo Liu
Hong Qian
Aimin Zhou

In modern telecommunication networks, faults manifest as alarms, generating thousands of events daily. Network operators need an efficient method to identify the root causes of these alarms to mitigate potential losses. This task is challenging due to the increasing scale of telecommunication networks and the interconnected nature of devices, where one fault can trigger a cascade of alarms across multiple devices within a topological network. Recent years have seen a growing focus on causal approaches to addressing this problem, emphasizing the importance of learning a Granger causal graph from topological event sequences. Such causal graphs delineate the relations among alarms and can significantly aid engineers in identifying and rectifying faults. However, existing methods either ignore the topological relationships among devices or suffer from relatively low scalability and efficiency, failing to deliver high-quality responses in a timely manner. To this end, this paper proposes $S^2GCSL$, a simple yet scalable Granger causal structural learning approach for topological event sequences. $S^2GCSL$ utilizes a linear kernel to model activation interactions among various event types within a topological network, and employs gradient descent to efficiently optimize the likelihood function. Notably, it can seamlessly incorporate expert knowledge as constraints within the optimization process, which enhances the interpretability of the outcomes. Extensive experimental results on both large-scale synthetic and real-world problems verify the scalability and efficacy of $S^2GCSL$.

PDF Details DOI

ECAI Conference 2024 Conference Paper

High-Dimensional Causal Bayesian Optimization

Yupeng Wu
Weiye Wang
Yangwenhui Zhang
Mingjia Li 0002
Yuanhao Liu
Hong Qian
Aimin Zhou

Causal global optimization (CGO) aims to complete optimization tasks through causal inference. In the high-dimensional CGO problems, traditional causal Bayesian optimization (CBO) methods struggle with the curse of dimensionality attributed to the number of variables in the causal graph, and scale inconsistency among Gaussian Process (GP) models. These issues limit the application of CBO in domains requiring optimization over large causal graphs. To address these limitations, this paper proposes a high-dimensional causal Bayesian optimization (HCBO) algorithm. To address the curse of dimensionality, HCBO introduces a submodularity indicator for variable subsets through the concept of causal intrinsic dimensionality (CID). It then uses the submodular optimization algorithm to find approximations of CID within polynomial sample complexity. Theoretically, we disclose a sufficient condition for CID’s existence. To address the issue of scale inconsistency among GP models, HCBO introduces a scale-normalized scoring function, ensuring stable identification of the optimal GP model corresponding to CID for intervention. Extensive experiments are conducted on high-dimensional synthetic and real-world tasks, i. e. , coral ecology and health. The existence of CID is verified across the datasets of all tasks. HCBO achieves state-of-the-art performance in CGO problems and can handle causal graphs at a scale 10 times larger than that manageable by previous CBO methods.

Details

AAAI Conference 2024 Conference Paper

Symbolic Cognitive Diagnosis via Hybrid Optimization for Intelligent Education Systems

Junhao Shen
Hong Qian
Wei Zhang
Aimin Zhou

Cognitive diagnosis assessment is a fundamental and crucial task for student learning. It models the student-exercise interaction, and discovers the students' proficiency levels on each knowledge attribute. In real-world intelligent education systems, generalization and interpretability of cognitive diagnosis methods are of equal importance. However, most existing methods can hardly make the best of both worlds due to the complicated student-exercise interaction. To this end, this paper proposes a symbolic cognitive diagnosis~(SCD) framework to simultaneously enhance generalization and interpretability. The SCD framework incorporates the symbolic tree to explicably represent the complicated student-exercise interaction function, and utilizes gradient-based optimization methods to effectively learn the student and exercise parameters. Meanwhile, the accompanying challenge is that we need to tunnel the discrete symbolic representation and continuous parameter optimization. To address this challenge, we propose to hybridly optimize the representation and parameters in an alternating manner. To fulfill SCD, it alternately learns the symbolic tree by derivative-free genetic programming and learns the student and exercise parameters via gradient-based Adam. The extensive experimental results on various real-world datasets show the superiority of SCD on both generalization and interpretability. The ablation study verifies the efficacy of each ingredient in SCD, and the case study explicitly showcases how the interpretable ability of SCD works.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Degradation-Resistant Offline Optimization via Accumulative Risk Control

Huakang Lu
Hong Qian
Yupeng Wu
Ziqi Liu
Ya-Lin Zhang 0001
Aimin Zhou
Yang Yu 0001

Offline optimization aims to elaborately construct a solution that optimizes a black-box function with only access to the offline dataset. A typical manner of constructing the solution is to train a surrogate model of the black-box function on the offline dataset and optimize the solution guided by the surrogate model. However, this manner often encounters a fundamental challenge that the surrogate model could erroneously estimate out-of-distribution (OOD) solutions. Therefore, the optimizer would be misled to produce inferior solutions for online applications, i. e. , degradation of performance. To this end, this paper formalizes the risk of degradation for OOD solutions and proposes an accumulative risk controlled offline optimization (ARCOO) method. Specifically, ARCOO learns a surrogate model in conjunction with an energy model. The energy model characterizes the risk of degradation by learning on high-risk solutions and low-risk ones contrastively. In the optimization procedure, the behavior of the optimizer in each step is controlled by a risk suppression factor calculated via the energy model, which leads to the controllable accumulative risk. Theoretically, we justify the efficacy of energy for accumulative risk control. Extensive experiments on offline optimization tasks show that ARCOO surpasses state-of-the-art methods in both degradation-resistance and optimality of the output solution.

Details

AAAI Conference 2023 Conference Paper

High-Dimensional Dueling Optimization with Preference Embedding

Yangwenhui Zhang
Hong Qian
Xiang Shu
Aimin Zhou

In many scenarios of black-box optimization, evaluating the objective function values of solutions is expensive, while comparing a pair of solutions is relatively cheap, which yields the dueling black-box optimization. The side effect of dueling optimization is that it doubles the dimension of solution space and exacerbates the dimensionality scalability issue of black-box optimization, e.g., Bayesian optimization. To address this issue, the existing dueling optimization methods fix one solution when dueling throughout the optimization process, but it may reduce their efficacy. Fortunately, it has been observed that, in recommendation systems, the dueling results are mainly determined by the latent human preferences. In this paper, we abstract this phenomenon as the preferential intrinsic dimension and inject it into the dueling Bayesian optimization, resulting in the preferential embedding dueling Bayesian optimization (PE-DBO). PE-DBO decouples optimization and pairwise comparison via the preferential embedding matrix. Optimization is performed in the preferential intrinsic subspace with much lower dimensionality, while pairwise comparison is completed in the original dueling solution space. Theoretically, we disclose that the preference function can be approximately preserved in the lower-dimensional preferential intrinsic subspace. Experiment results verify that, on molecule discovery and web page recommendation dueling optimization tasks, the preferential intrinsic dimension exists and PE-DBO is superior in scalability compared with that of the state-of-the-art (SOTA) methods.

PDF Details DOI

ECAI Conference 2023 Conference Paper

QCCDM: A Q-Augmented Causal Cognitive Diagnosis Model for Student Learning

Shuo Liu 0017
Hong Qian
Mingjia Li 0002
Aimin Zhou

Cognitive diagnosis is vital for intelligent education to determine students’ knowledge mastery levels from their response logs. The Q-matrix, representing the relationships between exercises and knowledge attributes, improves the interpretability of cognitive diagnosis models. However, completing the Q-matrix poses an expensive and challenging task due to the fine-grained division of knowledge attributes. Moreover, a manually sparse Q-matrix can also compromise the accuracy and interpretability of deducing students’ mastery levels, especially for infrequently observed or unseen knowledge attributes. To address this issue, this paper proposes a Q-augmented Causal Cognitive Diagnosis Model (QCCDM) for student learning. Specifically, QCCDM incorporates the structure causal model (SCM) to capture the causality between students’ mastery levels on different attributes, which enables to infer their proficiency on rarely observed knowledge attributes with better accuracy and interpretability. Notably, with SCM, one can guide students on how to realize their self-improvement through intervention. Furthermore, we propose to augment the Q-matrix in QCCDM, which uses the manual Q-matrix as a prior to deduce the relationships between exercises and explicit as well as latent knowledge attributes, resulting in a complete and comprehensive assessment of students’ abilities. We assess the efficacy of Q-augmentation across the widely-used Q-based cognitive diagnosis models and conduct the ablation study. The extensive experimental results on real-world datasets show that QCCDM outperforms the compared methods in terms of both accuracy and interpretability.

Details

ICML Conference 2022 Conference Paper

Black-Box Tuning for Language-Model-as-a-Service

Tianxiang Sun
Yunfan Shao
Hong Qian
Xuanjing Huang 0001
Xipeng Qiu

Extremely large pre-trained language models (PTMs) such as GPT-3 are usually released as a service. It allows users to design task-specific prompts to query the PTMs through some black-box APIs. In such a scenario, which we call Language-Model-as-a-Service (LMaaS), the gradients of PTMs are usually unavailable. Can we optimize the task prompts by only accessing the model inference APIs? This paper proposes the black-box tuning framework to optimize the continuous prompt prepended to the input text via derivative-free optimization. Instead of optimizing in the original high-dimensional prompt space, which is intractable for traditional derivative-free optimization, we perform optimization in a randomly generated subspace due to the low intrinsic dimensionality of large PTMs. The experimental results show that the black-box tuning with RoBERTa on a few labeled samples not only significantly outperforms manual prompt and GPT-3’s in-context learning, but also surpasses the gradient-based counterparts, i. e. , prompt tuning and full model tuning.

Details

ICML Conference 2022 Conference Paper

The Teaching Dimension of Regularized Kernel Learners

Hong Qian
Xu-Hui Liu
Chen-Xi Su
Aimin Zhou
Yang Yu 0001

Teaching dimension (TD) is a fundamental theoretical property for understanding machine teaching algorithms. It measures the sample complexity of teaching a target hypothesis to a learner. The TD of linear learners has been studied extensively, whereas the results of teaching non-linear learners are rare. A recent result investigates the TD of polynomial and Gaussian kernel learners. Unfortunately, the theoretical bounds therein show that the TD is high when teaching those non-linear learners. Inspired by the fact that regularization can reduce the learning complexity in machine learning, a natural question is whether the similar fact happens in machine teaching. To answer this essential question, this paper proposes a unified theoretical framework termed STARKE to analyze the TD of regularized kernel learners. On the basis of STARKE, we derive a generic result of any type of kernels. Furthermore, we disclose that the TD of regularized linear and regularized polynomial kernel learners can be strictly reduced. For regularized Gaussian kernel learners, we reveal that, although their TD is infinite, their epsilon-approximate TD can be exponentially reduced compared with that of the unregularized learners. The extensive experimental results of teaching the optimization-based learners verify the theoretical findings.

Details

AAAI Conference 2018 Conference Paper

Noisy Derivative-Free Optimization With Value Suppression

Hong Wang
Hong Qian
Yang Yu

Derivative-free optimization has shown advantage in solving sophisticated problems such as policy search, when the environment is noise-free. Many real-world environments are noisy, where solution evaluations are inaccurate due to the noise. Noisy evaluation can badly injure derivative-free optimization, as it may make a worse solution looks better. Sampling is a straightforward way to reduce noise, while previous studies have shown that delay the noise handling to the comparison time point (i. e. , threshold selection) can be helpful for derivative-free optimization. This work further delays the noise handling, and proposes a simple noise handling mechanism, i. e. , value suppression. By value suppression, we do nothing about noise until the best-so-far solution has not been improved for a period, and then suppress the value of the best-so-far solution and continue the optimization. On synthetic problems as well as reinforcement learning tasks, experiments verify that value suppression can be signiﬁcantly more effective than the previous methods.

PDF Details

AAAI Conference 2017 Conference Paper

Sequential Classification-Based Optimization for Direct Policy Search

Yi-Qi Hu
Hong Qian
Yang Yu

Direct policy search often results in high-quality policies in complex reinforcement learning problems, which employs some optimization algorithms to search the parameters of the policy for maximizing the its total reward. Classiﬁcationbased optimization is a recently developed framework for derivative-free optimization, which has shown to be effective and efﬁcient for non-convex optimization problems with many local optima, and may provide a power optimization tool for direct policy search. However, this framework requires to sample a batch of solutions for every update of the search model, while in reinforcement learning, the environment often offers only sequential policy evaluation. Thus the classiﬁcation-based optimization may not efﬁcient for direct policy search, where solutions have to be sampled sequentially. In this paper, we adapt the classiﬁcation-based optimization for sequential sampled solutions by forming the sample batch via reusing historical solutions. Experiments on a helicopter hovering task and controlling tasks in OpenAI Gym show that the new algorithm signiﬁcantly improve the performance from several state-of-the-art derivative-free optimization approaches.

PDF Details

AAAI Conference 2017 Conference Paper

Solving High-Dimensional Multi-Objective Optimization Problems with Low Effective Dimensions

Hong Qian
Yang Yu

Multi-objective (MO) optimization problems require simultaneously optimizing two or more objective functions. An MO algorithm needs to ﬁnd solutions that reach different optimal balances of the objective functions, i. e. , optimal Pareto front, therefore, high dimensionality of the solution space can hurt MO optimization much severer than single-objective optimization, which was little addressed in previous studies. This paper proposes a general, theoretically-grounded yet simple approach ReMO, which can scale current derivativefree MO algorithms to the high-dimensional non-convex MO functions with low effective dimensions, using random embedding. We prove the conditions under which an MO function has a low effective dimension, and for such functions, we prove that ReMO possesses the desirable properties of optimal Pareto front preservation, time complexity reduction, and rotation perturbation invariance. Experimental results indicate that ReMO is effective for optimizing the highdimensional MO functions with low effective dimensions, and is even effective for the high-dimensional MO functions where all dimensions are effective but most only have a small and bounded effect on the function value.

PDF Details

IJCAI Conference 2016 Conference Paper

Derivative-Free Optimization of High-Dimensional Non-Convex Functions by Sequential Random Embeddings

Hong Qian
Yi-Qi Hu
Yang Yu

Derivative-free optimization methods are suitable for sophisticated optimization problems, while are hard to scale to high dimensionality (e. g. , larger than 1, 000). Previously, the random embedding technique has been shown successful for solving high-dimensional problems with low effective dimensions. However, it is unrealistic to assume a low effective dimension in many applications. This paper turns to study high-dimensional problems with low optimal epsilon-effective dimensions, which allow all dimensions to be effective but many of them only have a small bounded effect. We characterize the properties of random embedding for this kind of problems, and propose the sequential random embeddings (SRE) to reduce the embedding gap while running optimization algorithms in the low-dimensional spaces. We apply SRE to several state-of-the-art derivative-free optimization methods, and conduct experiments on synthetic functions as well as non-convex classification tasks with up to 100, 000 variables. Experiment results verify the effectiveness of SRE.

PDF Details

AAAI Conference 2016 Conference Paper

Derivative-Free Optimization via Classification

Yang Yu
Hong Qian
Yi-Qi Hu

Many randomized heuristic derivative-free optimization methods share a framework that iteratively learns a model for promising search areas and samples solutions from the model. This paper studies a particular setting of such framework, where the model is implemented by a classiﬁcation model discriminating good solutions from bad ones. This setting allows a general theoretical characterization, where critical factors to the optimization are discovered. We also prove that optimization problems with Local Lipschitz continuity can be solved in polynomial time by proper conﬁgurations of this framework. Following the critical factors, we propose the randomized coordinate shrinking classiﬁcation algorithm to learn the model, forming the RACOS algorithm, for optimization in continuous and discrete domains. Experiments on the testing functions as well as on the machine learning tasks including spectral clustering and classiﬁcation with Ramp loss demonstrate the effectiveness of RACOS.

PDF Details

AAAI Conference 2016 Conference Paper

Scaling Simultaneous Optimistic Optimization for High-Dimensional Non-Convex Functions with Low Effective Dimensions

Hong Qian
Yang Yu

Simultaneous optimistic optimization (SOO) is a recently proposed global optimization method with a strong theoretical foundation. Previous studies have shown that SOO has a good performance in lowdimensional optimization problems, however, its performance is unsatisfactory when the dimensionality is high. This paper adapts random embedding to scaling SOO, resulting in the RESOO algorithm. We prove that the simple regret of RESOO depends only on the effective dimension of the problem, while that of SOO depends on the dimension of the solution space. Empirically, on some high-dimensional non-convex testing functions as well as hyper-parameter tuning tasks for multi-class support vector machines, RESOO shows signiﬁcantly improved performance from SOO.

PDF Details

TIME Conference 2008 Conference Paper

Topology-based Variable Ordering Strategy for Solving Disjunctive Temporal Problems

Yuechang Liu
Yunfei Jiang
Hong Qian

Many temporal problems arising in automated planning and scheduling can be expressed as disjunctive temporal problems (DTPs). Most of DTP solvers in the literature treat DTPs as constraint satisfaction problems (CSPs) or satisfiability problems (SATs), and solve them using standard CSP (SAT) techniques. Basically DTPs are represented through logically related topological relations between temporal variables, however, unfortunately little work has been done on exploiting the topological information to direct the search for DTP resolving. According to the "fail-first "(FF) principle for dynamic variable ordering (DVO) heuristics in CSP literature, this paper proposes a DVO which is based on the topological structure of DTP (which is defined to be Disjunctive Temporal Network). Experimental results reveal that the proposed DVO outperforms Minimal Remaining Values heuristics-a DVO that is widely used in existing DTP solvers, especially for the hard and large-scale problems. And, a CSP based procedure with the best of the heuristics wins TSAT++ on most of the test problems.

Details

TIME Conference 2007 Conference Paper

Graph-DTP: Graph-Based Algorithm for Solving Disjunctive Temporal Problems

Yuechang Liu
Hong Qian
Yunfei Jiang

We study an expressive quantitative temporal model: disjunctive temporal problem (DTP), which was first proposed only in 1998 (Stergiou and Koubarakis). As extension of temporal constraint satisfaction problem (TCSP) (Dechter et al. 1991), DTP differs from TCSP in that two disjuncts in a same disjunctive constraint do not necessarily refer to same temporal variables. Traditionally, most of the DTP algorithms in the literature solve DTPs by treating them as constraint satisfaction problems (CSPs), and searching for solutions using standard CSP techniques, e. g. backtracking, back-jumping, forward checking, semantic branching, removal of subsumed variables, nogood recording, etc. Those CSP techniques are powerful in solving DTPs. However, an evident drawback of viewing DTPs as general CSPs is that much semantic information encoded in DTPs is neglected. In fact we can mine rich semantic information that can be exploited to reduce search space for DTPs (more than semantic branching). Through some topological analysis on the graphical representation of the problems, some techniques are developed to help to search solutions for other temporal models (e. g. TCSP), or to identify "crucial subproblems" for CSP (Epstein and Wallace, 2006). However, little effort has been made to exploit the inherent topological information in solving DTPs. Our idea runs on a graphical representation of DTPs - disjunctive temporal network (DTN). We define DTN as an edge-labeled weighted digraph, on which some relevant concepts are identified. Then, we define the concept of equivalency between DTNs with respect to their consistency. For a given DTN, deciding its consistency is ascribed to check the consistency of a DTN which is equivalent to it and has less constraints (edges). We iteratively reduce a DTN to a simpler but equivalent one according to a set of designed reduction rules (which can be performed within polynomial time). It is hoped that when the DTN reaches a fixed point under such reduction operation, the resulted DTN has minimal edges (which is like backdoor in SAT, or "near clique"). At last the resulted DTN (DTP) is transferred to CSP search phase, where we derive a special variable ordering strategy again through the DTN structure. We shall describe the generation of DTN structure, the DTN reduction rules, the implementation of the complete graph-DTP algorithm, and some first results of this approach.

Details