Trace norm regularization is a widely used approach for learning low rank
matrices. A standard optimization strategy is based on formulating the problem
as one of low rank matrix factorization which, however, leads to a non-convex
problem. In practice this approach works well, and it is often computationally
faster than standard convex solvers such as proximal gradient methods.
Nevertheless, it is not guaranteed to converge to a global optimum, and the
optimization can be trapped at poor stationary points. In this paper we show
that it is possible to characterize all critical points of the non-convex
problem. This allows us to provide an efficient criterion to determine whether
a critical point is also a global minimizer. Our analysis suggests an iterative
meta-algorithm that dynamically expands the parameter space and allows the
optimization to escape any non-global critical point, thereby converging to a
global minimizer. The algorithm can be applied to problems such as matrix
completion or multitask learning, and our analysis holds for any random
initialization of the factor matrices. Finally, we confirm the good performance
of the algorithm on synthetic and real datasets.

本文中提出了一种迭代元算法，通过动态扩展参数空间，避免优化陷入局部最优解，从而更好地解决低秩矩阵因式分解问题及其应用。

重新审视低秩矩阵分解的迹范数正则化

Reexamining Low Rank Matrix Factorization for Trace Norm Regularization

We study the problem of learning a tensor from a set of linear measurements.
A prominent methodology for this problem is based on a generalization of trace
norm regularization, which has been used extensively for learning low rank
matrices, to the tensor setting. In this paper, we highlight some limitations
of this approach and propose an alternative convex relaxation on the Euclidean
ball. We then describe a technique to solve the associated regularization
problem, which builds upon the alternating direction method of multipliers.
Experiments on one synthetic dataset and two real datasets indicate that the
proposed method improves significantly over tensor trace norm regularization in
terms of estimation error, while remaining computationally tractable.

该论文研究了如何通过欧几里得球的凸松弛和乘子法方法解决张量学习中由于痕迹规范化限制而存在的限制，并在合成和真实数据集上对该方法进行了验证，表明其估计误差显著降低，同时保持计算可行性。

张量补全的新凸松弛方法

A New Convex Relaxation for Tensor Completion

Trace norm regularization is a popular method of multitask learning. We give
excess risk bounds with explicit dependence on the number of tasks, the number
of examples per task and properties of the data distribution. The bounds are
independent of the dimension of the input space, which may be infinite as in
the case of reproducing kernel Hilbert spaces. A byproduct of the proof are
bounds on the expected norm of sums of random positive semidefinite matrices
with subexponential moments.

通过轨迹规范化正则化方法，可以在多任务学习中提高精度和性能，并给出过量风险界，并且独立于输入空间维度，同时考虑到数据分布的属性以及任务数和每个任务的示例数。

带痕范数正则化的多任务学习的超额风险界

Excess risk bounds for multitask learning with trace norm regularization

In this paper, we propose three approaches for the estimation of the Tucker
decomposition of multi-way arrays (tensors) from partial observations. All
approaches are formulated as convex minimization problems. Therefore, the
minimum is guaranteed to be unique. The proposed approaches can automatically
estimate the number of factors (rank) through the optimization. Thus, there is
no need to specify the rank beforehand. The key technique we employ is the
trace norm regularization, which is a popular approach for the estimation of
low-rank matrices. In addition, we propose a simple heuristic to improve the
interpretability of the obtained factorization. The advantages and
disadvantages of three proposed approaches are demonstrated through numerical
experiments on both synthetic and real world datasets. We show that the
proposed convex optimization based approaches are more accurate in predictive
performance, faster, and more reliable in recovering a known multilinear
structure than conventional approaches.

提出三种方法用于从部分观察中估计多维数组（张量）的 Tucker 分解，这些方法都可以自动估计因子数（秩），并采用凸优化进行求解，其中采用的主要技术是迹范数正则化，还提出了简单的启发式方法以提高因子分解的可解释性。通过合成和真实数据集上的数值实验，证明了该方法比传统方法预测性能更准确、更快，更可靠。