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

Lifting the Veil: Unlocking the Power of Depth in Q-learning

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Lin, Shao-Bo Li, Tao Tang, Shaojie Wang, Yao Zhou, Ding-Xuan The Center for Intelligent Decision-making and Machine Learning School of Management Xi'an Jiaotong University Xi'An China The Naveen Jindal School of Management The University of Texas at Dallas RichardsonTX United States School of Mathematics and Statistics University of Sydney Sydney Australia

With the help of massive data and rich computational resources, deep Q-learning has been widely used in operations research and management science and has contributed to great success in numerous applications, including recommender systems, supply chains, games, and robotic manipulation. However, the success of deep Q-learning lacks solid theoretical verification and interpretability. The aim of this paper is to theoretically verify the power of depth in deep Q-learning. Within the framework of statistical learning theory, we rigorously prove that deep Q-learning outperforms its traditional version by demonstrating its good generalization error bound. Our results reveal that the main reason for the success of deep Q-learning is the excellent performance of deep neural networks (deep nets) in capturing the special properties of rewards namely, spatial sparseness and piecewise constancy, rather than their large capacities. In this paper, we make fundamental contributions to the field of reinforcement learning by answering to the following three questions: Why does deep Q-learning perform so well? When does deep Q-learning perform better than traditional Q-learning? How many samples are required to achieve a specific prediction accuracy for deep Q-learning? Our theoretical assertions are verified by applying deep Q-learning in the well-known beer game in supply chain management and a simulated recommender system. © 2023, CC BY.

关键词： Recommender systems

Multi-consensus decentralized accelerated gradient descent

学校读者我要写书评

暂无评论

The Journal of Machine Learning Research

The Journal of machine learning Research 2023年第1期24卷 14474-14523页

作者： Haishan Ye Luo Luo Ziang Zhou Tong Zhang Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University Xi'an China School of Data Science Fudan University Shanghai China Department of Computing The Hong Kong Polytechnic University Hong Kong China Computer Science & Mathematics The Hong Kong University of Science and Technology Hong Kong China

This paper considers the decentralized convex optimization problem, which has a wide range of applications in large-scale machine learning, sensor networks, and control theory. We propose novel algorithms that achieve optimal computation complexity and near optimal communication complexity. Our theoretical results give affirmative answers to the open problem on whether there exists an algorithm that can achieve a communication complexity (nearly) matching the lower bound depending on the global condition number instead of the local one. Furthermore, the linear convergence of our algorithms only depends on the strong convexity of global objective and it does not require the local functions to be convex. The design of our methods relies on a novel integration of well-known techniques including Nesterov's acceleration, multi-consensus and gradient-tracking. Empirical studies show the outperformance of our methods for machine learning applications.

关键词： consensus optimization decentralized algorithm accelerated gradient descent gradient tracking composite optimization

Can Gaussian sketching converge faster on a preconditioned landscape? 24

学校读者我要写书评

暂无评论

Can Gaussian sketching converge faster on a preconditioned l...

Proceedings of the 41st International Conference on machine learning

作者： Yilong Wang Haishan Ye Guang Dai Ivor W. Tsang Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University China and SGIT AI Lab State Grid Corporation of China SGIT AI Lab State Grid Corporation of China CFAR and IHPC Agency for Science Technology and Research (A*STAR) Singapore and 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.

关键词：

Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Liu, Zhiyu Han, Zhi Tang, Yandong Zhao, Xi-Le 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 University of Electronic Science and Technology of China Chengdu610051 China Center for Intelligent Decision-making and Machine Learning School of Management Xi’an Jiaotong University Xi’an710049 China

This paper considers the problem of recovering a tensor with an underlying low-tubal-rank structure from a small number of corrupted linear measurements. Traditional approaches tackling such a problem require the computation of tensor Singular Value Decomposition (t-SVD), which is a computationally intensive process, rendering them impractical for dealing with large-scale tensors. Aiming to address this challenge, we propose an efficient and effective low-tubal-rank tensor recovery method based on a factorization procedure akin to the Burer-Monteiro (BM) method. Precisely, our fundamental approach involves decomposing a large tensor into two smaller factor tensors, followed by solving the problem through factorized gradient descent (FGD). This strategy eliminates the need for t-SVD computation, thereby reducing computational costs and storage requirements. We provide rigorous theoretical analysis to ensure the convergence of FGD under both noise-free and noisy situations. Additionally, it is worth noting that our method does not require the precise estimation of the tensor tubal-rank. Even in cases where the tubal-rank is slightly overestimated, our approach continues to demonstrate robust performance. A series of experiments have been carried out to demonstrate that, as compared to other popular ones, our approach exhibits superior performance in multiple scenarios, in terms of the faster computational speed and the smaller convergence error. Copyright © 2024, The Authors. All rights reserved.

关键词： Singular value decomposition

Integrating Response Time and Attention Duration in Bayesian Preference learning for Multiple Criteria decision Aiding

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Jiang, Jiaxuan Liu, Jiapeng Kadziński, Milosz Liao, Xiuwu Dong, Jingyu Center for Intelligent Decision-Making and Machine Learning School of Management Xi’an Jiaotong University Shaanxi Xi’an710049 China Institute of Computing Science Poznan University of Technology Piotrowo 2 Poznań60-965 Poland Collaborative Innovation Center of China Pilot Reform Exploration and Assessment - Hubei Sub-Center Hubei University of Economics Hubei Wuhan430205 China School of Management Xi’an Jiaotong University Shaanxi Xi’an710049 China

We introduce a multiple criteria Bayesian preference learning framework incorporating behavioral cues for decision aiding. The framework integrates pairwise comparisons, response time, and attention duration to deepen insights into decision-making processes. The approach employs an additive value function model and utilizes a Bayesian framework to derive the posterior distribution of potential ranking models by defining the likelihood of observed preference data and specifying a prior on the preference structure. This distribution highlights each model’s ability to reconstruct decision-Makers’ holistic pairwise comparisons. By leveraging both response time as a proxy for cognitive effort and alternative discriminability as well as attention duration as an indicator of criterion importance, the proposed model surpasses traditional methods by uncovering richer behavioral patterns. We report the results of a laboratory experiment on mobile phone contract selection involving 30 real subjects using a dedicated application with time-, eye-, and mouse-tracking components. We validate the novel method’s ability to reconstruct complete preferences. The detailed ablation studies reveal time- and attention-related behavioral patterns, confirming that integrating comprehensive data leads to developing models that better align with the DM’s actual preferences. Copyright © 2025, The Authors. All rights reserved.

关键词： Response time (computer systems)

Statistical estimation and inference via local SGD in federated learning

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Li, Xiang Liang, Jiadong Chang, Xiangyu Zhang, Zhihua School of Mathematical Sciences Peking University China Center for Intelligent Decision-Making and Machine Learning School of Management Xi'an Jiaotong University China

Federated learning (FL) makes a large amount of edge computing devices (e.g., mobile phones) jointly learn a global model without data sharing. In FL, data are generated in a decentralized manner with high heterogeneity. This paper studies how to perform statistical estimation and inference in the federated setting. We analyze the so-called Local SGD, a multi-round estimation procedure that uses intermittent communication to improve communication efficiency. We first establish a functional central limit theorem that shows the averaged iterates of Local SGD weakly converge to a rescaled Brownian motion. We next provide two iterative inference methods: the plug-in and the random scaling. Random scaling constructs an asymptotically pivotal statistic for inference by using the information along the whole Local SGD path. Both the methods are communication efficient and applicable to online data. Our theoretical and empirical results show that Local SGD simultaneously achieves both statistical efficiency and communication efficiency. Copyright © 2021, The Authors. All rights reserved.

关键词： Iterative methods

Adaptive stopping rule for kernel-based gradient descent algorithms

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Chang, Xiangyu Lin, Shao-Bo Center of Intelligence Decision-Making and Machine Learning School of Management Xi'an Jiaotong University Xi'an China

In this paper, we propose an adaptive stopping rule for kernel-based gradient descent (KGD) algorithms. We introduce the empirical effective dimension to quantify the increments of iterations in KGD and derive an implementable early stopping strategy. We analyze the performance of the adaptive stopping rule in the framework of learning theory. Using the recently developed integral operator approach, we rigorously prove the optimality of the adaptive stopping rule in terms of showing the optimal learning rates for KGD equipped with this rule. Furthermore, a sharp bound on the number of iterations in KGD equipped with the proposed early stopping rule is also given to demonstrate its computational advantage. Copyright © 2020, The Authors. All rights reserved.

关键词： Gradient methods

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

Deep Convolutional Neural Networks with Zero-Padding: Feature Extraction and learning

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Han, Zhi Liu, Baichen Lin, Shao-Bo Zhou, Ding-Xuan State Key Laboratory of Robotics Shenyang Institute of Automation Chinese Academy of Sciences Shenyang China Institutes for Robotics and Intelligent Manufacturing Chinese Academy of Sciences Shenyang China Center of Intelligent Decision-Making and Machine Learning School of Management Xi’an Jiaotong University Xi’an China School of Mathematics and Statistics University of Sydney SydneyNSW2006 Australia

This paper studies the performance of deep convolutional neural networks (DCNNs) with zero-padding in feature extraction and learning. After verifying the roles of zero-padding in enabling translation-equivalence, and pooling in its translation-invariance driven nature, we show that with similar number of free parameters, any deep fully connected networks (DFCNs) can be represented by DCNNs with zero-padding. This demonstrates that DCNNs with zero-padding is essentially better than DFCNs in feature extraction. Consequently, we derive universal consistency of DCNNs with zero-padding and show its translation-invariance in the learning process. All our theoretical results are verified by numerical experiments including both toy simulations and real-data running. © 2023, CC0.

关键词： Feature extraction