Tensor Completion via Integer Optimization
<|reference_start|>Tensor Completion via Integer Optimization: The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution, or have polynomial-time algorithms that require an exponentially-larger number of samples for low estimation error. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate. Our approach formulates tensor completion as a convex optimization problem constrained using a gauge-based tensor norm, which is defined in a way that allows the use of integer linear optimization to solve linear separation problems over the unit-ball in this new norm. Adaptations based on this insight are incorporated into a Frank-Wolfe variant to build our algorithm. We show our algorithm scales-well using numerical experiments on tensors with up to ten million entries.<|reference_end|>
@article{chen2024tensor,
    title={Tensor Completion via Integer Optimization},
    author={Xin Chen, Sukanya Kudva, Yongzheng Dai, Anil Aswani, Chen Chen},
    journal={arXiv preprint arXiv:2402.05141},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.05141},
    primaryClass={math.OC cs.LG}
}