Abstract
This thesis explores two areas in modern statistics: ranking problems and change-point detection. Both topics are investigated within the framework of high-dimensional statistics, where the number of unknown parameters can be greater than the number of samples. To manage this complexity, we introduce specific assumptions, or shape constraints, into the models.The first part of the thesis looks at ranking problems, which involve rearranging items based on noisy and partial observations. We mainly examine two models that aim to recover a permutation of the rows of a matrix that has specific shape constraints. Specifically, we consider the isotonic model where the reordered matrix has nondecreasing columns, and the bi-isotonic model where it has nondecreasing columns and rows.In both models, we develop polynomial-time algorithms to estimate the unknown permutation, and we prove that they achieve nearly optimal guarantees.The second part delves into detecting multiple change-points in high-dimensional time series. While we consider a general change-point setting, the main focus is on the case where we aim to detect changes in the mean of the data. We establish minimax optimal rates that are adaptive to the unknown sparsity of these changes, and to the distance between the change-points.