Philip Thompson
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Philip Thompson has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Roberto Imbuzeiro Oliveira
IMPA, Rio de Janeiro, Brazil
4 shared publications Alejandro Jofré
Universidad de Chile
1 shared publication- Alejandro Jofré
CMM, Universidad de Chile, Santiago, Chile
1 shared publication - Alfredo Noel Iusem
Fundação Getulio Vargas
1 shared publication - Arnak S. Dalalyan
ENSAE Paristech-CREST ENSAE Paristech-CREST
1 shared publication - Matteo Nannini
Microwaves and Radar Institute, SAR Technology Department, German Aerospace Center (DLR), 82234 Wessling, Germany
1 shared publication
Latest Publications
- Open Access
Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
We study high-dimensional least-squares regression within a subgaussian statistical learning framework with heterogeneous noise. It includes $s$-sparse and $r$-low-rank least-squares regression when a fraction $\epsilon$ of the labels are adversarially contaminated. We also present a novel theory of trace-regression with matrix decomposition based on a new application of the product process. For these problems, we show novel near-optimal "subgaussian" estimation rates of the form $r(n,d_{e})+\sqrt{\log(1/\delta)/n}+\epsilon\log(1/\epsilon)$, valid with probability at least $1-\delta$. Here, $r(n,d_{e})$ is the optimal uncontaminated rate as a function of the effective dimension $d_{e}$ but independent of the failure probability $\delta$. These rates are valid uniformly on $\delta$, i.e., the estimators' tuning do not depend on $\delta$. Lastly, we consider noisy robust matrix completion with non-uniform sampling. If only the low-rank matrix is of interest, we present a novel near-optimal rate that is independent of the corruption level $a$. Our estimators are tractable and based on a new "sorted" Huber-type loss. No information on $(s,r,\epsilon,a)$ are needed to tune these estimators. Our analysis makes use of novel $\delta$-optimal concentration inequalities for the multiplier and product processes which could be useful elsewhere. For instance, they imply novel sharp oracle inequalities for Lasso and Slope with optimal dependence on $\delta$. Numerical simulations confirm our theoretical predictions. In particular, "sorted" Huber regression can outperform classical Huber regression.Open AccessOutlier-robust sparse/low-rank least-squares regression and robust matrix completion
We study high-dimensional least-squares regression within a subgaussian statistical learning framework with heterogeneous noise. It includes $s$-sparse and $r$-low-rank least-squares regression when a fraction $\epsilon$ of the labels are adversarially contaminated. We also present a novel theory of trace-regression with matrix decomposition based on a new application of the product process. For these problems, we show novel near-optimal "subgaussian" estimation rates of the form $r(n,d_{e})+\sqrt{\log(1/\delta)/n}+\epsilon\log(1/\epsilon)$, valid with probability at least $1-\delta$. Here, $r(n,d_{e})$ is the optimal uncontaminated rate as a function of the effective dimension $d_{e}$ but independent of the failure probability $\delta$. These rates are valid uniformly on $\delta$, i.e., the estimators' tuning do not depend on $\delta$. Lastly, we consider noisy robust matrix completion with non-uniform sampling. If only the low-rank matrix is of interest, we present a novel near-optimal rate that is independent of the corruption level $a$. Our estimators are tractable and based on a new "sorted" Huber-type loss. No information on $(s,r,\epsilon,a)$ are needed to tune these estimators. Our analysis makes use of novel $\delta$-optimal concentration inequalities for the multiplier and product processes which could be useful elsewhere. For instance, they imply novel sharp oracle inequalities for Lasso and Slope with optimal dependence on $\delta$. Numerical simulations confirm our theoretical predictions. In particular, "sorted" Huber regression can outperform classical Huber regression. - Open Access
Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
``Localization'' has proven to be a valuable tool in the Statistical Learning literature as it allows sharp risk bounds in terms of the problem geometry. Localized bounds seem to be much less exploited in the Stochastic Optimization literature. In addition, there is an obvious interest in both communities in obtaining risk bounds that require weak moment assumptions or ``heavier-tails''. In this work we use a localization toolbox to derive risk bounds in two specific applications. The first is in portfolio risk minimization with conditional value-at-risk constraints. We consider a setting where, among all assets with high returns, there is a portion of dimension $g$, unknown to the investor, that has significant less risk than the other remaining portion. Our rates for the SAA problem show that ``risk inflation'', caused by a multiplicative factor, affects the statistical rate only via a term proportional to $g$. As the ``normalized risk'' increases, the contribution in the rate from the extrinsic dimension diminishes while the dependence on $g$ is kept fixed. Localization is a key tool to show this property. As a second application of our localization toolbox, we obtain sharp oracle inequalities for least-squares estimators with a Lasso-type constraint under weak moment assumptions. One main consequence of these inequalities is to obtain \emph{persistence}, as posed by Greenshtein and Ritov, with covariates having heavier tails. This gives improvements in prior work of Bartlett, Mendelson and Neeman.Open AccessSample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
``Localization'' has proven to be a valuable tool in the Statistical Learning literature as it allows sharp risk bounds in terms of the problem geometry. Localized bounds seem to be much less exploited in the Stochastic Optimization literature. In addition, there is an obvious interest in both communities in obtaining risk bounds that require weak moment assumptions or ``heavier-tails''. In this work we use a localization toolbox to derive risk bounds in two specific applications. The first is in portfolio risk minimization with conditional value-at-risk constraints. We consider a setting where, among all assets with high returns, there is a portion of dimension $g$, unknown to the investor, that has significant less risk than the other remaining portion. Our rates for the SAA problem show that ``risk inflation'', caused by a multiplicative factor, affects the statistical rate only via a term proportional to $g$. As the ``normalized risk'' increases, the contribution in the rate from the extrinsic dimension diminishes while the dependence on $g$ is kept fixed. Localization is a key tool to show this property. As a second application of our localization toolbox, we obtain sharp oracle inequalities for least-squares estimators with a Lasso-type constraint under weak moment assumptions. One main consequence of these inequalities is to obtain \emph{persistence}, as posed by Greenshtein and Ritov, with covariates having heavier tails. This gives improvements in prior work of Bartlett, Mendelson and Neeman. - 23 March 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 199 (1-2) , 49-86
Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
- 23 March 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 199 (1-2) , 49-86
Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
- 20 April 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 199 (1-2) , 1-48
Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints
- 20 April 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 199 (1-2) , 1-48
Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints
- Open Access
Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints
We derive new and improved non-asymptotic deviation inequalities for the sample average approximation (SAA) of an optimization problem. Our results give strong error probability bounds that are "sub-Gaussian"~even when the randomness of the problem is fairly heavy tailed. Additionally, we obtain good (often optimal) dependence on the sample size and geometrical parameters of the problem. Finally, we allow for random constraints on the SAA and unbounded feasible sets, which also do not seem to have been considered before in the non-asymptotic literature. Our proofs combine different ideas of potential independent interest: an adaptation of Talagrand's "generic chaining"~bound for sub-Gaussian processes; "localization"~ideas from the Statistical Learning literature; and the use of standard conditions in Optimization (metric regularity, Slater-type conditions) to control fluctuations of the feasible set.
Open AccessSample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints
We derive new and improved non-asymptotic deviation inequalities for the sample average approximation (SAA) of an optimization problem. Our results give strong error probability bounds that are "sub-Gaussian"~even when the randomness of the problem is fairly heavy tailed. Additionally, we obtain good (often optimal) dependence on the sample size and geometrical parameters of the problem. Finally, we allow for random constraints on the SAA and unbounded feasible sets, which also do not seem to have been considered before in the non-asymptotic literature. Our proofs combine different ideas of potential independent interest: an adaptation of Talagrand's "generic chaining"~bound for sub-Gaussian processes; "localization"~ideas from the Statistical Learning literature; and the use of standard conditions in Optimization (metric regularity, Slater-type conditions) to control fluctuations of the feasible set.
- Open Access
Outlier-robust estimation of a sparse linear model using $\ell_1$-penalized Huber's $M$-estimator
We study the problem of estimating a $p$-dimensional $s$-sparse vector in a linear model with Gaussian design and additive noise. In the case where the labels are contaminated by at most $o$ adversarial outliers, we prove that the $\ell_1$-penalized Huber's $M$-estimator based on $n$ samples attains the optimal rate of convergence $(s/n)^{1/2} + (o/n)$, up to a logarithmic factor. For more general design matrices, our results highlight the importance of two properties: the transfer principle and the incoherence property. These properties with suitable constants are shown to yield the optimal rates, up to log-factors, of robust estimation with adversarial contamination.Open AccessOutlier-robust estimation of a sparse linear model using $\ell_1$-penalized Huber's $M$-estimator
We study the problem of estimating a $p$-dimensional $s$-sparse vector in a linear model with Gaussian design and additive noise. In the case where the labels are contaminated by at most $o$ adversarial outliers, we prove that the $\ell_1$-penalized Huber's $M$-estimator based on $n$ samples attains the optimal rate of convergence $(s/n)^{1/2} + (o/n)$, up to a logarithmic factor. For more general design matrices, our results highlight the importance of two properties: the transfer principle and the incoherence property. These properties with suitable constants are shown to yield the optimal rates, up to log-factors, of robust estimation with adversarial contamination. - 18 September 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 44 (1) , 236-263
Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
We consider stochastic variational inequalities (VIs) with monotone operators where the feasible set is an intersection of a large number of convex sets. We propose a stochastic approximation method with incremental constraint projections, meaning that a projection method is taken after the random operator is sampled and a component of the feasible set is randomly chosen. Such a sequential scheme is well suited for large-scale online and distributed learning. First, we assume that the VI is weak sharp. We provide asymptotic convergence, infeasibility rate of O(1/k) in terms of the squared distance to the feasible set, and solvability rate of O(1/k) in terms of the distance to the solution set for a bounded or unbounded set. Then, we assume just a monotone operator and introduce an explicit iterative Tykhonov regularization to the method. We consider Cartesian VIs so as to encompass the distributed solution of multiagent problems under a limited coordination. We provide asymptotic convergence, infeasibilit...
- 18 September 2018
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 44 (1) , 236-263
Incremental Constraint Projection Methods for Monotone Stochastic Variational Inequalities
We consider stochastic variational inequalities (VIs) with monotone operators where the feasible set is an intersection of a large number of convex sets. We propose a stochastic approximation method with incremental constraint projections, meaning that a projection method is taken after the random operator is sampled and a component of the feasible set is randomly chosen. Such a sequential scheme is well suited for large-scale online and distributed learning. First, we assume that the VI is weak sharp. We provide asymptotic convergence, infeasibility rate of O(1/k) in terms of the squared distance to the feasible set, and solvability rate of O(1/k) in terms of the distance to the solution set for a bounded or unbounded set. Then, we assume just a monotone operator and introduce an explicit iterative Tykhonov regularization to the method. We consider Cartesian VIs so as to encompass the distributed solution of multiagent problems under a limited coordination. We provide asymptotic convergence, infeasibilit...
- 5 June 2018
- Published by Springer Nature in Mathematical Programming
- Vol. 174 (1-2) , 253-292
On variance reduction for stochastic smooth convex optimization with multiplicative noise
- 5 June 2018
- Published by Springer Nature in Mathematical Programming
- Vol. 174 (1-2) , 253-292
On variance reduction for stochastic smooth convex optimization with multiplicative noise
- 1 January 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21536996,p. 468-471
Target separation in SAR image with the MUSIC algorithm
The aim of this work is to exploit the MUSIC algorithm performance in order to enhance target separability in range and azimuth, i.e. achieve point targets separation inside a resolution cell. Simulations have been done in order to plan and check the feasibility of a super-resolution experiment that took place in September 2006 on the test site of Oberpfaffenhofen (Germany). The data set has been acquired with the E-SAR system of the DLR in X-band. The targets to be separated were seven small corner reflectors that have been placed in a way that their response falls in one or, at maximum, two resolution cells of the standard Fourier SAR image. A post-processing implementation of the MUSIC algorithm has been proposed allowing, in the already focused SAR image, to retrieve the targets geometry. Conditions and analysis of the results have been carried out.
- 1 January 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21536996,p. 468-471
Target separation in SAR image with the MUSIC algorithm
The aim of this work is to exploit the MUSIC algorithm performance in order to enhance target separability in range and azimuth, i.e. achieve point targets separation inside a resolution cell. Simulations have been done in order to plan and check the feasibility of a super-resolution experiment that took place in September 2006 on the test site of Oberpfaffenhofen (Germany). The data set has been acquired with the E-SAR system of the DLR in X-band. The targets to be separated were seven small corner reflectors that have been placed in a way that their response falls in one or, at maximum, two resolution cells of the standard Fourier SAR image. A post-processing implementation of the MUSIC algorithm has been proposed allowing, in the already focused SAR image, to retrieve the targets geometry. Conditions and analysis of the results have been carried out.