Abstract In 2013, Cuturi [9] introduced the SINKHORN algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a better convergence rate for a high accuracy solution, we work on understanding the SINKHORN algorithm under regularization scheduling, and thus modify it with a mechanism that adaptively doubles the regularization parameter η periodically. We prove that such modified version of SINKHORN has an exponential convergence rate as iteration complexity depending on log(l/ɛ) instead of ɛ-o(1) from previous analyses [1, 9] in the optimal transport problems with integral supply and demand. Furthermore, with cost and capacity scaling procedures, the general optimal transport problem can be solved with a logarithmic dependence on 1/ɛ as well.
Hardness of Graph-Structured Algebraic and Symbolic Problems
In this paper (A full version can be found at https://arxiv.org/abs/2109.12736v3.), we study the hardness of solving graph structured linear systems with coefficients over a finite field Z_p and over a polynomial ring F[x_1,...,x_t]. We reduce solving general linear systems in Z_p to solving unit-weight low-degree graph Laplacians over Z_p with a polylogarithmic overhead on the number of non-zeros. Under the by now common assumption of hardness of solving general linear systems in Z_p, this result shows that ideas for solving graph-structured linear systems over reals are unlikely to transfer to finite-field settings. We also reduce solving general linear systems over Z_p to solving linear systems whose coefficient matrices are walk matrices (matrices with all ones on the diagonal) and normalized Laplacians (Laplacians that are also walk matrices) over Z_p. Furthermore, motivated by applications that choose entries of such systems over finite fields randomly, we provide some generalizations of our reductions to symbolic settings.
2022
2021
2020
Fast Adaptively Weighted Matrix Factorization for Recommendation with Implicit Feedback
Chen, Jiawei, Wang, Can, Zhou, Sheng, Shi, Qihao, Chen, Jingbang, Feng, Yan, and Chen, Chun
In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020 2020
@inproceedings{DBLP:conf/aaai/Chen0ZSCF020,author={Chen, Jiawei and Wang, Can and Zhou, Sheng and Shi, Qihao and Chen, Jingbang and Feng, Yan and Chen, Chun},title={Fast Adaptively Weighted Matrix Factorization for Recommendation with
Implicit Feedback},booktitle={The Thirty-Fourth {AAAI} Conference on Artificial Intelligence, {AAAI}
2020, The Thirty-Second Innovative Applications of Artificial Intelligence
Conference, {IAAI} 2020, The Tenth {AAAI} Symposium on Educational
Advances in Artificial Intelligence, {EAAI} 2020, New York, NY, USA,
February 7-12, 2020},pages={3470--3477},publisher={{AAAI} Press},year={2020},url={https://ojs.aaai.org/index.php/AAAI/article/view/5751},timestamp={Tue, 26 Apr 2022 15:09:49 +0200},biburl={https://dblp.org/rec/conf/aaai/Chen0ZSCF020.bib},bibsource={dblp computer science bibliography, https://dblp.org}}
2019
Predicting Long-Term Scientific Impact Based on Multi-Field Feature Extraction
Wu, Ziming, Lin, Weiwei, Liu, Pan, Chen, Jingbang, and Mao, Li
@article{DBLP:journals/access/WuLLCM19,author={Wu, Ziming and Lin, Weiwei and Liu, Pan and Chen, Jingbang and Mao, Li},title={Predicting Long-Term Scientific Impact Based on Multi-Field Feature
Extraction},journal={{IEEE} Access},volume={7},pages={51759--51770},year={2019},url={https://doi.org/10.1109/ACCESS.2019.2910239},doi={10.1109/ACCESS.2019.2910239},timestamp={Fri, 31 May 2019 09:48:40 +0200},biburl={https://dblp.org/rec/journals/access/WuLLCM19.bib},bibsource={dblp computer science bibliography, https://dblp.org}}