First order algorithms for computing linear and polyhedral estimates
Bekri, Yannis1 ; Juditsky, Anatoli1 ; Nemirovski, Arkadi2
1LJK, Université Grenoble Alpes, Campus de Saint-Martin-d’Hères, 38401 France
2Arkadi Nemirovski, Georgia Institute of Technology, Atlanta, Georgia 30332, USA
Open Journal of Mathematical Optimization, Tome 5 (2024), article no. 7, 15 p.

It was recently shown [6, 8] that “properly built” linear and polyhedral estimates nearly attain minimax accuracy bounds in the problem of recovery of unknown signal from noisy observations of linear images of the signal when the signal set is an ellitope. However, design of nearly optimal estimates relies upon solving semidefinite optimization problems with matrix variables, what puts the synthesis of such estimates beyond the reach of the standard Interior Point algorithms of semidefinite optimization even for moderate size recovery problems. Our goal is to develop First Order Optimization algorithms for the computationally efficient design of linear and polyhedral estimates. In this paper we (a) explain how to eliminate matrix variables, thus reducing dramatically the design dimension when passing from Interior Point to First Order optimization algorithms and (b) develop and analyse a dedicated algorithm of the latter type — Composite Truncated Level method.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/ojmo.35

Bekri, Yannis  1   ; Juditsky, Anatoli  1   ; Nemirovski, Arkadi  2

1 LJK, Université Grenoble Alpes, Campus de Saint-Martin-d’Hères, 38401 France
2 Arkadi Nemirovski, Georgia Institute of Technology, Atlanta, Georgia 30332, USA
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits
@article{OJMO_2024__5__A8_0,
     author = {Bekri, Yannis and Juditsky, Anatoli and Nemirovski, Arkadi},
     title = {First order algorithms for computing linear and polyhedral estimates},
     journal = {Open Journal of Mathematical Optimization},
     eid = {7},
     pages = {1--15},
     year = {2024},
     publisher = {Universit\'e de Montpellier},
     volume = {5},
     doi = {10.5802/ojmo.35},
     mrnumber = {4822313},
     language = {en},
     url = {https://www.numdam.org/articles/10.5802/ojmo.35/}
}
TY  - JOUR
AU  - Bekri, Yannis
AU  - Juditsky, Anatoli
AU  - Nemirovski, Arkadi
TI  - First order algorithms for computing linear and polyhedral estimates
JO  - Open Journal of Mathematical Optimization
PY  - 2024
SP  - 1
EP  - 15
VL  - 5
PB  - Université de Montpellier
UR  - https://www.numdam.org/articles/10.5802/ojmo.35/
DO  - 10.5802/ojmo.35
LA  - en
ID  - OJMO_2024__5__A8_0
ER  - 
%0 Journal Article
%A Bekri, Yannis
%A Juditsky, Anatoli
%A Nemirovski, Arkadi
%T First order algorithms for computing linear and polyhedral estimates
%J Open Journal of Mathematical Optimization
%] 7
%D 2024
%P 1-15
%V 5
%I Université de Montpellier
%U https://www.numdam.org/articles/10.5802/ojmo.35/
%R 10.5802/ojmo.35
%G en
%F OJMO_2024__5__A8_0
Bekri, Yannis; Juditsky, Anatoli; Nemirovski, Arkadi. First order algorithms for computing linear and polyhedral estimates. Open Journal of Mathematical Optimization, Tome 5 (2024), article  no. 7, 15 p.. doi: 10.5802/ojmo.35

[1] Bekri, Yannis; Juditsky, Anatoli; Nemirovski, Arkadi On robust recovery of signals from indirect observations (2023) | arXiv

[2] Ben-Tal, Aharon; Nemirovski, Arkadi Lectures on modern convex optimization: analysis, algorithms, and engineering applications, MPS/SIAM Series on Optimization, 2, Society for Industrial and Applied Mathematics, 2001 | MR | Zbl | DOI

[3] Ben-Tal, Aharon; Nemirovski, Arkadi Non-euclidean restricted memory level method for large-scale convex optimization, Math. Program., Volume 102 (2005) no. 3, pp. 407-456 | MR | DOI | Zbl

[4] Grant, Michael; Boyd, Stephen The CVX Users’ Guide. Release 2.1, 2014 (https://web.cvxr.com/cvx/doc/CVX.pdf)

[5] Hsu, Daniel; Kakade, Sham M.; Zhang, Tong A tail inequality for quadratic forms of subgaussian random vectors, Electron. Commun. Probab., Volume 17 (2012), 52, 6 pages | MR | Zbl

[6] Juditsky, Anatoli; Nemirovski, Arkadi Near-optimality of linear recovery from indirect observations, Math. Stat. Learn., Volume 1 (2018) no. 2, pp. 171-225 | MR | DOI | Zbl

[7] Juditsky, Anatoli; Nemirovski, Arkadi Near-optimality of linear recovery in gaussian observation scheme under ∥·∥ 2 2 -loss, Ann. Stat., Volume 46 (2018) no. 2, pp. 1603-1629 | MR | Zbl

[8] Juditsky, Anatoli; Nemirovski, Arkadi On polyhedral estimation of signals via indirect observations, Electron. J. Stat., Volume 14 (2020) no. 1, p. 458--502 | MR | Zbl

[9] Juditsky, Anatoli; Nemirovski, Arkadi Statistical Inference via Convex Optimization, Princeton Series in Applied Mathematics, Princeton University Press, 2020, xxiv+631 pages | MR

[10] Kiwiel, Krzysztof C. Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities, Math. Program., Volume 69 (1995) no. 1, pp. 89-109 | MR | DOI | Zbl

[11] Nesterov, Yurii; Nemirovski, Arkadi On first-order algorithms for ℓ 1 /nuclear norm minimization, Acta Numer., Volume 22 (2013), pp. 509-575 | MR | Zbl | DOI

[12] Rudelson, Mark; Vershynin, Roman Hanson–Wright inequality and sub-Gaussian concentration, Electron. Commun. Probab., Volume 18 (2013), 82, 9 pages | MR | Zbl

[13] Spokoiny, Vladimir; Zhilova, Maya Sharp deviation bounds for quadratic forms, Math. Methods Stat., Volume 22 (2013) no. 2, pp. 100-113 | MR | DOI | Zbl

Cité par Sources :