报告名称：L_p-sphere covering and approximating nuclear p-norm

主讲人：江 波 教授

邀请人：罗洪林 教授

时间：2023年10月27日 10 : 00

地点：best365体育官网登录入口X221学术报告厅

主办单位：best365体育官网登录入口

报告摘要

The spectral p-norm and nuclear p-norm of matrices and tensors appear in various applications albeit both are NP-hard to compute. The former sets a foundation of l_p-sphere constrained polynomial optimization problems and the latter has been found in many rank minimization problems in machine learning. We study approximation algorithms of the tensor nuclear p-norm with an aim to establish the approximation bound matching the best one of its dual norm, the tensor spectral p-norm. Driven by the application of sphere covering to approximate both tensor spectral and nuclear norms (p = 2), we propose several types of hitting sets that approximately represent `p-sphere with adjustable parameters for different levels of approximations and cardinalities, providing an independent toolbox for decision making on `p-spheres. Using the idea in robust optimization and second-order cone programming, we obtain the first polynomial-time algorithm with an O(1)-approximation bound for the computation of the matrix nuclear p-norm when p ∈ (2,∞) is a rational, paving a way for applications in optimization with the matrix nuclear p-norm. These two new results enable us to propose various polynomial-time approximation algorithms for the computation of the tensor nuclear p-norm using tensor partitions, convex optimization and duality theory, attaining the same approximation bound to the best one of the tensor spectral p-norm.

专家简介

江波，上海财经大学信息管理与工程学院常聘教授，副院长；国家级青年人才、上海市高校特聘教授(东方学者)、上海市青年拔尖人才。从事运筹优化、收益管理、机器学习等方向的研究。成果发表于运筹优化与机器学习的国际顶级期刊《Operations Research》、《Mathematics of Operations Research》、《Mathematical Programming》、《Journal of Machine Learning Research》。为顺丰、京东、太平金科、永辉等多个国内著名企业提供无人仓库内优化、智能定价、智能选址、智能排班等技术服务。获得了中国运筹学会青年科技奖、上海市自然科学奖二等奖等荣誉。