论文检索

随机数据下迭代非凸优化的精确全局收敛保证AI 解读

We consider a general class of regression models with normally distributed covariates, and the associated nonconvex problem of fitting these models from data. We develop a general recipe for analyzing the convergence of iterative algorithms for this task from a random initialization. In particular, provided each iteration can be written as the solution to a convex optimization problem satisfying some natural conditions, we leverage Gaussian comparison theorems to derive a…

未知排列下的保序回归：统计、计算与自适应AI 解读

Motivated by models for multiway comparison data, we consider the problem of estimating a coordinatewise isotonic function on the domain [0,1]d from noisy observations collected on a uniform lattice, but where the design points have been permuted along each dimension. While the univariate and bivariate versions of this problem have received significant attention, our focus is on the multivariate case d≥3. We study both the minimax risk of estimation (in empirical L2 loss)…

未知排列下双变量保序矩阵的最优估计探索AI 解读

Many applications, including rank aggregation, crowd-labeling and graphon estimation, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and/or columns. We consider the problem of estimating an unknown matrix in this class, based on noisy observations of (possibly, a subset of) its entries. We design and analyze polynomial-time algorithms that improve upon the state of the art in two distinct metrics, showing, in particular,…

部分成对比较估计的最坏情形与平均情形设计AI 解读

Pairwise comparison data arises in many domains, including tournament rankings, web search and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items, we study the problem of estimating the underlying comparison probabilities under the assumption of strong stochastic transitivity (SST). We also consider the noisy sorting subclass of the SST model. We show that when the assignment of items to the topology is arbitrary, these permutation-based…