Author name cluster

Yawei Zhao

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.

5 papers

1 author row

TIST Journal 2022 Journal Article

Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend

Wendi Wu
Zongren Li
Yawei Zhao
Chen Yu
Peilin Zhao
Ji Liu
Kunlun He

Decentralized online learning (online learning in decentralized networks) has been attracting more and more attention, since it is believed that decentralized online learning can help data providers cooperatively better solve their online problems without sharing their private data to a third party or other providers. Typically, the cooperation is achieved by letting the data providers exchange their models between neighbors, e.g., recommendation model. However, the best regret bound for a decentralized online learning algorithm is 𝒪( n √ T ), where n is the number of nodes (or users) and T is the number of iterations. This is clearly insignificant, since this bound can be achieved without any communication in the networks. This reminds us to ask a fundamental question: Can people really get benefit from the decentralized online learning by exchanging information? In this article, we studied when and why the communication can help the decentralized online learning to reduce the regret. Specifically, each loss function is characterized by two components: the adversarial component and the stochastic component. Under this characterization, we show that decentralized online gradient enjoys a regret bound \( {\mathcal {O}(\sqrt {n^2TG^2 + n T \sigma ^2})} \), where G measures the magnitude of the adversarial component in the private data (or equivalently the local loss function) and σ measures the randomness within the private data. This regret suggests that people can get benefits from the randomness in the private data by exchanging private information. Another important contribution of this article is to consider the dynamic regret—a more practical regret to track users’ interest dynamics. Empirical studies are also conducted to validate our analysis.

Details DOI

TIST Journal 2020 Journal Article

A Theoretical Revisit to Linear Convergence for Saddle Point Problems

Wendi Wu
Yawei Zhao
En Zhu
Xinwang Liu
Xingxing Zhang
Lailong Luo
Shixiong Wang
Jianping Yin

Recently, convex-concave bilinear Saddle Point Problems (SPP) is widely used in lasso problems, Support Vector Machines, game theory, and so on. Previous researches have proposed many methods to solve SPP, and present their convergence rate theoretically. To achieve linear convergence, analysis in those previouse studies requires strong convexity of φ( z ). But, we find the linear convergence can also be achieved even for a general convex but not strongly convex φ( z ). In the article, by exploiting the strong duality of SPP, we propose a new method to solve SPP, and achieve the linear convergence. We present a new general sufficient condition to achieve linear convergence, but do not require the strong convexity of φ( z ). Furthermore, a more efficient method is also proposed, and its convergence rate is analyzed in theoretical. Our analysis shows that the well conditioned φ( z ) is necessary to improve the efficiency of our method. Finally, we conduct extensive empirical studies to evaluate the convergence performance of our methods.

Details DOI

AAAI Conference 2020 Conference Paper

Multi-View Spectral Clustering with Optimal Neighborhood Laplacian Matrix

Sihang Zhou
Xinwang Liu
Jiyuan Liu
Xifeng Guo
Yawei Zhao
En Zhu
Yongping Zhai
Jianping Yin

Multi-view spectral clustering aims to group data into different categories by optimally exploring complementary information from multiple Laplacian matrices. However, existing methods usually linearly combine a group of pre-speciﬁed ﬁrst-order Laplacian matrices to construct an optimal Laplacian matrix, which may result in limited representation capability and insufﬁcient information exploitation. In this paper, we propose a novel optimal neighborhood multi-view spectral clustering (ONMSC) algorithm to address these issues. Speciﬁcally, the proposed algorithm generates an optimal Laplacian matrix by searching the neighborhood of both the linear combination of the ﬁrst-order and high-order base Laplacian matrices simultaneously. This design enhances the representative capacity of the optimal Laplacian and better utilizes the hidden high-order connection information, leading to improved clustering performance. An efﬁcient algorithm with proved convergence is designed to solve the resultant optimization problem. Extensive experimental results on 9 datasets demonstrate the superiority of our algorithm against state-of-the-art methods, which veriﬁes the effectiveness and advantages of the proposed ONMSC.

PDF Details

TIST Journal 2020 Journal Article

Understand Dynamic Regret with Switching Cost for Online Decision Making

Yawei Zhao
Qian Zhao
Xingxing Zhang
En Zhu
Xinwang Liu
Jianping Yin

As a metric to measure the performance of an online method, dynamic regret with switching cost has drawn much attention for online decision making problems. Although the sublinear regret has been provided in much previous research, we still have little knowledge about the relation between the dynamic regret and the switching cost. In the article, we investigate the relation for two classic online settings: Online Algorithms (OA) and Online Convex Optimization (OCO). We provide a new theoretical analysis framework that shows an interesting observation; that is, the relation between the switching cost and the dynamic regret is different for settings of OA and OCO. Specifically, the switching cost has significant impact on the dynamic regret in the setting of OA. But it does not have an impact on the dynamic regret in the setting of OCO. Furthermore, we provide a lower bound of regret for the setting of OCO, which is same with the lower bound in the case of no switching cost. It shows that the switching cost does not change the difficulty of online decision making problems in the setting of OCO.

Details DOI

AAAI Conference 2018 Short Paper

Variance Reduced K-Means Clustering

Yawei Zhao
Yuewei Ming
Xinwang Liu
En Zhu
Jianping Yin

It is challenging to perform k-means clustering on a large scale dataset efficiently. One of the reasons is that k-means needs to scan a batch of training data to update the cluster centers at every iteration, which is time-consuming. In the paper, we propose a variance reduced k-mean VRKM, which outperforms the state-of-the-art method, and obtain 4× speedup for large-scale clustering. The source code is available on https://github.com/YaweiZhao/VRKM_sofia-ml.

PDF Details