检索结果-内蒙古大学图书馆

Preference Construction: A Bayesian Interactive Preference Elicitation Framework Based on Monte Carlo Tree Search

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Wang, Yan Liu, Jiapeng Kadziński, Milosz Liao, Xiuwu Center for Intelligent Decision-making and Machine Learning School of Management Xi’an Jiaotong University Shaanxi Xi’an710049 China Faculty of Computing and Telecommunications Poznan University of Technology Piotrowo 2 Poznań60-965 Poland

We present a novel preference learning framework to capture participant preferences efficiently within limited interaction rounds. It involves three main contributions. First, we develop a variational Bayesian approach to infer the participant’s preference model by estimating posterior distributions and managing uncertainty from limited information. Second, we propose an adaptive questioning policy that maximizes cumulative uncertainty reduction, formulating questioning as a finite Markov decision process and using Monte Carlo Tree Search to prioritize promising question trajectories. By considering long-term effects and leveraging the efficiency of the Bayesian approach, the policy avoids shortsightedness. Third, we apply the framework to Multiple Criteria decision Aiding, with pairwise comparison as the preference information and an additive value function as the preference model. We integrate the reparameterization trick to address high-variance issues, enhancing robustness and efficiency. Computational studies on real-world and synthetic datasets demonstrate the framework’s practical usability, outperforming baselines in capturing preferences and achieving superior uncertainty reduction within limited interactions. Copyright © 2025, The Authors. All rights reserved.

关键词： Markov processes

Feature Qualification by Deep Nets: A Constructive Approach

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cao, Feilong Lin, Shao-Bo School of Mathematics Zhejiang Normal University Jinhua321014 China Institute of Mathematics and Cross-disciplinary Science Zhejiang Normal University Hangzhou310012 China Center for Intelligent Decision-Making and Machine Learning School of Management Xi’an Jiaotong University Xi’an710049 China

The great success of deep learning has stimulated avid research activities in verifying the power of depth in theory, a common consensus of which is that deep net are versatile in approximating and learning numerous functions. Such a versatility certainly enhances the understanding of the power of depth, but makes it difficult to judge which data features are crucial in a specific learning task. This paper proposes a constructive approach to equip deep nets for the feature qualification purpose. Using the product-gate nature and localized approximation property of deep nets with sigmoid activation (deep sigmoid nets), we succeed in constructing a linear deep net operator that possesses optimal approximation performance in approximating smooth and radial functions. Furthermore, we provide theoretical evidences that the constructed deep net operator is capable of qualifying multiple features such as the smoothness and radialness of the target functions. © 2025, CC0.

关键词： Deep neural networks

Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Liu, Zhiyu Han, Zhi Tang, Yandong Zhang, Hai Tang, Shaojie Wang, Yao State Key Laboratory of Robotics Shenyang Institute of Automation Chinese Academy of Sciences Shenyang110016 China University of Chinese Academy of Sciences Beijing100049 China Department of Statistics Northwest University Xi’an710000 China Department of Management Science and Systems State University of New York Buffalo United States Center for Intelligent Decision-making and Machine Learning School of Management Xi’an Jiaotong University Xi’an710049 China

We consider the noisy matrix sensing problem in the over-parameterization setting, where the estimated rank r is larger than the true rank r★. Specifically, our main objective is to recover a matrix X★ ∈ Rn1×n2 with rank r★ from noisy measurements using an over-parameterized factorized form LRT, where L ∈ n1×r, R ∈ n2×r and min{n1, n2} ≥ r > r★, with the true rank r★ being unknown. Recently, preconditioning methods have been proposed to accelerate the convergence of matrix sensing problem compared to vanilla gradient descent, incorporating preconditioning terms (LTL + λI)−1 and (RTR + λI)−1 into the original gradient. However, these methods require careful tuning of the damping parameter λ and are sensitive to initial points and step size. To address these limitations, we propose the alternating preconditioned gradient descent (APGD) algorithm, which alternately updates the two factor matrices, eliminating the need for the damping parameter and enabling faster convergence with larger step sizes. We theoretically prove that APGD achieves near-optimal error convergence at a linear rate, starting from arbitrary random initializations. Through extensive experiments, we validate our theoretical results and demonstrate that APGD outperforms other methods, achieving the fastest convergence rate. Notably, both our theoretical analysis and experimental results illustrate that APGD does not rely on the initialization procedure, making it more practical and versatile. Copyright © 2025, The Authors. All rights reserved.

关键词： Damping

Robust Tensor Completion With Side Information

学校读者我要写书评

暂无评论

IEEE Transactions on Knowledge and Data Engineering 2025年

作者： Wang, Yao Yi, Qianxin Yang, Yiyang Gao, Shanxing Tang, Shaojie Wang, Di Xi'an Jiaotong University Center for Intelligent Decision-making and Machine Learning School of Management Xi'an China Xi'an Jiaotong University Department of Marketing School of Management Xi'an China University at Buffalo Department of Management Science and Systems BuffaloNY United States

Although robust tensor completion has been extensively studied, the effect of incorporating side information has not been explored. In this article, we fill this gap by developing a novel high-order robust tensor completion model that incorporates both latent and explicit side information. We base our model on the transformed t-product because the corresponding tensor tubal rank can characterize the inherent low-rank structure of a tensor. We study the effect of side information on sample complexity and prove that our model needs fewer observations than other tensor recovery methods when side information is perfect. This theoretically shows that informative side information is beneficial for learning. Extensive experimental results on synthetic and real data further demonstrate the superiority of the proposed method over several popular alternatives. In particular, we evaluate the performance of our solution based on two important applications, namely, link prediction in signed networks and rating prediction in recommender systems. We show that the proposed model, which manages to exploit side information in learning, outperforms other methods in the learning of such low-rank tensor data. Furthermore, when dealing with varying dimensions, we also design an online robust tensor completion with side information algorithm and validate its effectiveness using a real-world traffic dataset in the supplementary material. © 1989-2012 IEEE.

关键词： Recommender systems

A Fast and Accurate Frequent Directions Algorithm for Low Rank Approximation via Block Krylov Iteration

学校读者我要写书评

暂无评论

A Fast and Accurate Frequent Directions Algorithm for Low Ra...

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Qianxin Yi Chenhao Wang Xiuwu Liao Yao Wang Center for Intelligent Decision-making and Machine Learning Xi’an Jiaotong University China

ISBN: (数字)9781509066315

ISBN: (纸本)9781509066322

It is known that frequent directions (FD) is a popular deterministic matrix sketching technique for low rank approximation. However, FD and its randomized variants usually meet high computational cost or computational instability in dealing with large-scale datasets, which limits their use in practice. To remedy such issues, this paper aims at improving the efficiency and effectiveness of FD. Specifically, by utilizing the power of Block Krylov Iteration and count sketch techniques, we propose a fast and accurate FD algorithm dubbed as BKICS-FD. We derive the error bound of the proposed BKICS-FD and then carry out extensive numerical experiments to illustrate its superiority over several popular FD algorithms, both in terms of computational speed and accuracy.

关键词：

Can Gaussian Sketching Converge Faster on a Preconditioned Landscape? 41

学校读者我要写书评

暂无评论

Can Gaussian Sketching Converge Faster on a Preconditioned L...

41st International Conference on machine learning, ICML 2024

作者： Wang, Yilong Ye, Haishan Dai, Guang Tsang, Ivor W. Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University China SGIT AI Lab State Grid Corporation of China China Singapore College of Computing and Data Science NTU Singapore

This paper focuses on the large-scale optimization which is very popular in the big data era. The gradient sketching is an important technique in the large-scale optimization. Specifically, the random coordinate descent algorithm is a kind of gradient sketching method with the random sampling matrix as the sketching matrix. In this paper, we propose a novel gradient sketching called GSGD (Gaussian Sketched Gradient Descent). Compared with the classical gradient sketching methods such as the random coordinate descent and SEGA (Hanzely et al., 2018), our GSGD does not require the importance sampling but can achieve a fast convergence rate matching the ones of these methods with importance sampling. Furthermore, if the objective function has a non-smooth regularization term, our GSGD can also exploit the implicit structure information of the regularization term to achieve a fast convergence rate. Finally, our experimental results substantiate the effectiveness and efficiency of our algorithm. Copyright 2024 by the author(s)

关键词： Big data

Double Stochasticity Gazes Faster: Snap-Shot Decentralized Stochastic Gradient Tracking Methods 41

学校读者我要写书评

暂无评论

Double Stochasticity Gazes Faster: Snap-Shot Decentralized S...

41st International Conference on machine learning, ICML 2024

作者： Di, Hao Ye, Haishan Chang, Xiangyu Dai, Guang Tsang, Ivor W. Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University China SGIT AI Lab State Grid Corporation of China China College of Computing and Data Science NTU Singapore Singapore

In decentralized optimization, m agents form a network and only communicate with their neighbors, which gives advantages in data ownership, privacy, and scalability. At the same time, decentralized stochastic gradient descent (SGD) methods, as popular decentralized algorithms for training large-scale machine learning models, have shown their superiority over centralized counterparts. Distributed stochastic gradient tracking (DSGT) (Pu & Nedić, 2021) has been recognized as the popular and state-of-the-art decentralized SGD method due to its proper theoretical guarantees. However, the theoretical analysis of DSGT (Koloskova et al., 2021) shows that its iteration complexity is (equation presented) where the doubly stochastic matrix W represents the network topology and CW is a parameter that depends on W. Thus, it indicates that the convergence property of DSGT is heavily affected by the topology of the communication network. To overcome the weakness of DSGT, we resort to the snapshot gradient tracking skill and propose two novel algorithms, snap-shot DSGT (SS DSGT) and accelerated snap-shot DSGT (ASS DSGT). We further justify that SS DSGT exhibits a lower iteration complexity compared to DSGT in the general communication network topology. Additionally, ASS DSGT matches DSGT's iteration complexity (equation presented) under the same conditions as DSGT. Numerical experiments validate SS DSGT's superior performance in the general communication network topology and exhibit better practical performance of ASS DSGT on the specified W compared to DSGT. Copyright 2024 by the author(s)

关键词： Network topology

Snap-Shot Decentralized Stochastic Gradient Tracking Methods

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ye, Haishan Chang, Xiangyu Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University China

In decentralized optimization, m agents form a network and only communicate with their neighbors, which gives advantages in data ownership, privacy, and scalability. At the same time, decentralized stochastic gradient descent (SGD) methods, as popular decentralized algorithms for training large-scale machine learning models, have shown their superiority over centralized counterparts. Distributed stochastic gradient tracking (DSGT) [Pu and Nedić, 2021] has been recognized as the popular and state-of-the-art decentralized SGD method due to its proper theoretical guarantees. However, the theoretical analysis of DSGT [Koloskova et al., 2021] shows that its iteration complexity is (Equation presented), where W is a double stochastic mixing matrix that presents the network topology and CW is a parameter that depends on W. Thus, it indicates that the convergence property of DSGT is heavily affected by the topology of the communication network. To overcome the weakness of DSGT, we resort to the snap-shot gradient tracking skill and propose two novel algorithms. We further justify that the proposed two algorithms are more robust to the topology of communication networks under similar algorithmic structures and the same communication strategy to DSGT. Compared with DSGT, their iteration complexity are (Equation presented) and (Equation presented) which reduce the impact on network topology (no CW ). © 2022, CC BY-NC-ND.

关键词： Network topology

Distributed learning with dependent samples

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Sun, Zirui Lin, Shao-Bo The Center of Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University China

This paper focuses on learning rate ansalysis of distributed kernel ridge regression (DKRR) for strong mixing sequences. Using a recently developed integral operator approach and a classical covariance inequality for Banach-valued strong mixing sequences, we succeed in deriving optimal learning rates of DKRR. As a byproduct, we deduce a sufficient condition for the mixing property to guarantee the optimal learning rates for kernel ridge regression, which fills the gap of learning rates between i.i.d. samples and strong mixing sequences. A series of numerical experiments are conducted to verify our theoretical assertions via showing excellent learning performance of DKRR in learning both toy and real world time series data. All these results extend the applicable range of distributed learning from i.i.d. samples to non-i.i.d. sequences. Copyright © 2020, The Authors. All rights reserved.

关键词： learning algorithms