Matrix Completion with Heterogeneous Observation Cost Using Sparsity-Number of Column-Space

The matrix completion problem has been studied broadly under many underlying conditions. In many real-life scenarios, we could expect elements from distinct columns or distinct positions to have a different cost. In this paper, we explore this generalization under adaptive conditions. We approach the problem under two different cost models. The first one is that entries from different columns have different observation costs, but, within the same column, each entry has a uniform cost. The second one is any two entry has different observation cost, despite being the same or different columns. We provide complexity analysis of our algorithms and provide tightness guarantees.

• Ilqar Ramazanli

• Matrix completion
• adaptive learning
• heterogeneous cost
• Matroid optimization.

[1] Candes, Emmanuel J., and Yaniv Plan. Matrix completion with noise.
Proceedings of the IEEE 98.6 (2010): 925-936.
[2] Balcan, Maria-Florina F., and Hongyang Zhang. Noise-tolerant life-long
matrix completion via adaptive sampling. Advances in Neural Information
Processing Systems 29 (2016).
[3] B´ecigneul, Gary, and Octavian-Eugen Ganea. Riemannian adaptive
optimization methods. arXiv preprint arXiv:1810.00760 (2018).
[4] Bertsimas, Dimitris, and Michael Lingzhi Li. Fast exact matrix
completion: A unified optimization framework for matrix completion.
Journal of Machine Learning Research 21.231 (2020): 1-43.
[5] Bhargava, Aniruddha, Ravi Ganti, and Rob Nowak. Active positive
semidefinite matrix completion: Algorithms, theory and applications.
Artificial Intelligence and Statistics. PMLR, 2017.
[6] Cai, Jian-Feng, Emmanuel J. Cand`es, and Zuowei Shen. A singular
value thresholding algorithm for matrix completion. SIAM Journal on
optimization 20.4 (2010): 1956-1982.
[7] Cand`es, Emmanuel J., and Benjamin Recht. Exact matrix completion
via convex optimization. Foundations of Computational mathematics 9.6
(2009): 717-772. [8] Cand`es, Emmanuel J., and Terence Tao. The power of convex relaxation:
Near-optimal matrix completion. IEEE Transactions on Information
Theory 56.5 (2010): 2053-2080.
[9] Candes, Emmanuel J., and Benjamin Recht. Exact low-rank matrix
completion via convex optimization. 2008 46th Annual Allerton
Conference on Communication, Control, and Computing. IEEE, 2008.
[10] Chistov, Alexander L., and D. Yu Grigor’Ev. Complexity of quantifier
elimination in the theory of algebraically closed fields. International
Symposium on Mathematical Foundations of Computer Science. Springer,
Berlin, Heidelberg, 1984.
[11] Deshpande, Amit, et al. Matrix approximation and projective clustering
via volume sampling. Theory of Computing 2.1 (2006): 225-247.
[12] Frieze, Alan, Ravi Kannan, and Santosh Vempala. Fast Monte-Carlo
algorithms for finding low-rank approximations. Journal of the ACM
(JACM) 51.6 (2004): 1025-1041.
[13] Gross, David. Recovering low-rank matrices from few coefficients in any
basis. IEEE Transactions on Information Theory 57.3 (2011): 1548-1566.
[14] Helman, Paul, Bernard ME Moret, and Henry D. Shapiro. An
exact characterization of greedy structures. SIAM Journal on Discrete
Mathematics 6.2 (1993): 274-283.
[15] Huang, Yuge, et al. Curricularface: adaptive curriculum learning loss
for deep face recognition. proceedings of the IEEE/CVF conference on
computer vision and pattern recognition. 2020.
[16] Jain, Prateek, and Praneeth Netrapalli. Fast exact matrix completion with
finite samples. Conference on Learning Theory. PMLR, 2015.
[17] Keshavan, Raghunandan, Andrea Montanari, and Sewoong Oh. Matrix
completion from noisy entries. Advances in neural information processing
systems 22 (2009).
[18] Kong, Yajing, et al. Adaptive Curriculum Learning. Proceedings of the
IEEE/CVF International Conference on Computer Vision. 2021.
[19] Krishnamurthy, Akshay, and Aarti Singh. Low-rank matrix and tensor
completion via adaptive sampling. Advances in neural information
processing systems 26 (2013).
[20] Krishnamurthy, Akshay, and Aarti Singh. On the power of adaptivity
in matrix completion and approximation. arXiv preprint arXiv:1407.3619
(2014).
[21] Ma, Jerry, and Denis Yarats. On the adequacy of untuned warmup for
adaptive optimization. arXiv preprint arXiv:1910.04209 7 (2019).
[22] Mısır, Mustafa. Active matrix completion for algorithm selection.
International Conference on Machine Learning, Optimization, and Data
Science. Springer, Cham, 2019.
[23] Paramythis, Alexandros, and Susanne Loidl-Reisinger. Adaptive learning
environments and e-learning standards. Second european conference on
e-learning. Vol. 1. No. 2003. 2003.
[24] Ramazanli, Ilqar. Adaptive noisy matrix completion. arXiv preprint
arXiv:2203.08340 (2022).
[25] Ramazanli, Ilqar. Lifelong matrix completion with sparsity-number.
arXiv preprint arXiv:2203.07637 (2022).
[26] Ramazanli, Ilqar. Adaptive noisy matrix completion. arXiv preprint
arXiv:2203.08340 (2022).
[27] Ramazanli, Ilqar, and Barnabas Poczos. Optimal exact matrix completion
under new parametrization. arXiv preprint arXiv:2002.02431 (2020).
[28] Ramazanli, Ilqar, et al. Adaptive sampling distributed stochastic variance
reduced gradient for heterogeneous distributed datasets. arXiv preprint
arXiv:2002.08528 (2020).
[29] Recht, Benjamin. A simpler approach to matrix completion. Journal of
Machine Learning Research 12.12 (2011).
[30] Riedmiller, Martin, and Heinrich Braun. Rprop-a fast adaptive learning
algorithm. Proc. of ISCIS VII), Universitat. 1992.
[31] Rohde, Angelika, and Alexandre B. Tsybakov. Estimation of
high-dimensional low-rank matrices. The Annals of Statistics 39.2 (2011):
887-930.
[32] Ruchansky, Natali, Mark Crovella, and Evimaria Terzi. Matrix
completion with queries. Proceedings of the 21th ACM SIGKDD
international conference on knowledge discovery and data mining. 2015.
[33] Settles, Burr. Active learning literature survey. (2009).
[34] Xie, Kun, et al. Low cost and high accuracy data gathering in WSNs
with matrix completion. IEEE Transactions on Mobile Computing 17.7
(2017): 1595-1608.
[35] Zeiler, Matthew D. Adadelta: an adaptive learning rate method. arXiv
preprint arXiv:1212.5701 (2012).
[36] Zhao, R., et al. An Adaptive Curriculum Learning Framework
for Unbiased Glaucoma Diagnosis. Proceedings of the Computer
Vision—ECCV (2020).
[37] Zhang, Hui, et al. Strongly convex programming for exact matrix
completion and robust principal component analysis. arXiv preprint
arXiv:1112.3946 (2011).
[38] Arnold, Matthew, et al. A survey of adaptive optimization in virtual
machines. Proceedings of the IEEE 93.2 (2005): 449-466.