Statistical inference via convex optimization

Cover......Page 1
Title......Page 4
Copyright......Page 5
Contents......Page 6
List of Figures......Page 12
Preface......Page 14
Acknowledgements......Page 18
Notational Conventions......Page 20
On Computational Tractability......Page 22
  1.1.1 Signal Recovery Problem......Page 26
  1.1.2 Signal Recovery: Parametric and nonparametric cases......Page 27
  1.1.3 Compressed Sensing via l1 minimization: Motivation......Page 31
  1.2.1 Validity of l1 minimization in the noiseless case......Page 33
  1.2.2 Imperfect l1 minimization......Page 36
  1.2.3 Regular l1 recovery......Page 38
  1.2.5 Discussion......Page 39
 1.3 Verifiability and tractability issues......Page 44
  1.3.2 Verifiable sufficient conditions for Qq(s, k)......Page 45
  1.3.3 Tractability of Q∞(s, k)......Page 47
 1.4 Exercises for Chapter 1......Page 51
  1.5.1 Proofs of Theorem 1.3, 1.4......Page 55
  1.5.2 Proof of Theorem 1.5......Page 57
  1.5.3 Proof of Proposition 1.7......Page 58
  1.5.4 Proof of Propositions 1.8 and 1.12......Page 61
  1.5.5 Proof of Proposition 1.10......Page 62
  1.5.6 Proof of Proposition 1.13......Page 64
  2.1.1 Hypothesis Testing Problem......Page 66
  2.1.3 Testing from repeated observations......Page 67
  2.1.4 Risk of a simple test......Page 70
  2.1.5 Two-point lower risk bound......Page 71
  2.2.1 Situation......Page 74
  2.2.2 Pairwise Hypothesis Testing via Euclidean Separation......Page 75
  2.2.3 Euclidean Separation, Repeated Observations, and Majority Tests......Page 80
  2.2.4 From Pairwise to Multiple Hypotheses Testing......Page 83
  2.3.2 Detector-based tests......Page 90
  2.4.1 Simple observation schemes—Motivation......Page 97
  2.4.2 Simple observation schemes—The definition......Page 98
  2.4.3 Simple observation schemes—Examples......Page 99
  2.4.4 Simple observation schemes—Main result......Page 104
  2.4.5 Simple observation schemes—Examples of optimal detectors......Page 108
 2.5 Testing multiple hypotheses......Page 112
  2.5.1 Testing unions......Page 113
  2.5.2 Testing multiple hypotheses “up to closeness”......Page 116
  2.5.3 Illustration: Selecting the best among a family of estimates......Page 122
  2.6.1 Motivation: Election polls......Page 130
  2.6.2 Sequential hypothesis testing......Page 133
  2.7.1 Motivation: Opinion polls revisited......Page 138
  2.7.2 Measurement Design: Setup......Page 140
  2.7.3 Formulating the MD problem......Page 141
 2.8 Affine detectors beyond simple observation schemes......Page 148
  2.8.1 Situation......Page 149
  2.8.2 Main result......Page 157
  2.9.1 Motivation......Page 164
  2.9.2 Quadratic lifting: Gaussian case......Page 165
  2.9.3 Quadratic lifting—Does it help?......Page 167
  2.9.4 Quadratic lifting: Sub-Gaussian case......Page 170
  2.9.5 Generic application: Quadratically constrained hypotheses......Page 172
  2.10.3 Hypothesis testing via l1-separation......Page 182
  2.10.4 Miscellaneous exercises......Page 188
  2.11.2 Proof of Proposition 2.6 in the case of quasi-stationary K-repeated observations......Page 193
  2.11.3 Proof of Theorem 2.23......Page 197
  2.11.4 Proof of Proposition 2.37......Page 200
  2.11.5 Proof of Proposition 2.43......Page 201
  2.11.6 Proof of Proposition 2.46......Page 205
 3.1 Estimating linear forms on unions of convex sets......Page 210
  3.1.1 The problem......Page 211
  3.1.2 The estimate......Page 212
  3.1.3 Main result......Page 214
  3.1.4 Near-optimality......Page 215
  3.1.5 Illustration......Page 216
 3.2 Estimating N-convex functions on unions of convex sets......Page 218
  3.2.1 Outline......Page 219
  3.2.2 Estimating N-convex functions: Problem setting......Page 222
  3.2.3 Bisection estimate: Construction......Page 224
  3.2.4 Building Bisection estimate......Page 226
  3.2.5 Bisection estimate: Main result......Page 227
  3.2.6 Illustration......Page 228
  3.2.7 Estimating N-convex functions: An alternative......Page 230
 3.3 Estimating linear forms beyond simple observation schemes......Page 236
  3.3.1 Situation and goal......Page 237
  3.3.2 Construction and main results......Page 238
  3.3.3 Estimation from repeated observations......Page 241
  3.3.4 Application: Estimating linear forms of sub-Gaussianity parameters......Page 243
  3.4.1 Estimating quadratic forms, Gaussian case......Page 247
  3.4.2 Estimating quadratic form, sub-Gaussian case......Page 253
 3.5 Exercises for Chapter 3......Page 263
  3.6.1 Proof of Proposition 3.3......Page 275
  3.6.2 Verifying 1-convexity of the conditional quantile......Page 278
  3.6.3 Proof of Proposition 3.4......Page 279
  3.6.4 Proof of Proposition 3.14......Page 283
 Overview......Page 285
  4.1.1 Cones......Page 287
  4.1.2 Conic problems and their duals......Page 288
  4.2.1 Situation and goal......Page 290
  4.2.2 Building a linear estimate......Page 292
  4.2.3 Byproduct on semidefinite relaxation......Page 299
  4.3.1 Spectratopes: Definition and examples......Page 300
  4.3.2 Semidefinite relaxation on spectratopes......Page 302
  4.3.3 Linear estimates beyond ellitopic signal sets and ‖ • ‖2-risk......Page 303
 4.4 Linear estimates of stochastic signals......Page 316
  4.4.1 Minimizing Euclidean risk......Page 318
  4.4.2 Minimizing ‖ • ‖-risk......Page 319
  4.5.1 Uncertain-but-bounded noise......Page 320
  4.5.2 Mixed noise......Page 324
 4.6 Calculus of ellitopes/spectratopes......Page 325
  4.7.1 Linear estimates vs. Maximum Likelihood......Page 327
  4.7.2 Measurement Design in Signal Recovery......Page 328
  4.7.3 Around semidefinite relaxation......Page 331
  4.7.4 Around Propositions 4.4 and 4.14......Page 342
  4.7.5 Signal recovery in Discrete and Poisson observation schemes......Page 360
  4.7.6 Numerical lower-bounding minimax risk......Page 372
  4.7.7 Around S-Lemma......Page 384
  4.7.8 Miscellaneous exercises......Page 385
  4.8.1 Preliminaries......Page 386
  4.8.2 Proof of Proposition 4.6......Page 389
  4.8.3 Proof of Proposition 4.8......Page 391
  4.8.4 Proof of Lemma 4.17......Page 393
  4.8.5 Proofs of Propositions 4.5, 4.16 and 4.19......Page 396
  4.8.6 Proofs of Propositions 4.18 and 4.19, and justification of Remark 4.20......Page 408
  5.1.1 Motivation......Page 411
  5.1.2 Generic polyhedral estimate......Page 413
  5.1.3 Specifying sets Hδ for basic observation schemes......Page 415
  5.1.4 Efficient upper-bounding of R[H] and contrast design, I......Page 417
  5.1.5 Efficient upper-bounding of R[H] and contrast design, II......Page 424
  5.1.6 Assembling estimates: Contrast aggregation......Page 436
  5.1.8 Calculus of compatibility......Page 438
  5.2.1 Problem setting......Page 440
  5.2.2 Assumptions......Page 442
  5.2.3 Estimating via Sample Average Approximation......Page 445
  5.2.4 Stochastic Approximation estimate......Page 448
  5.2.5 Numerical illustration......Page 450
  5.2.6 “Single-observation” case......Page 453
  5.3.1 Estimation by Stochastic Optimization......Page 456
  5.4.1 Proof of (5.8)......Page 465
  5.4.2 Proof of Lemma 5.6......Page 466
  5.4.3 Verification of (5.44)......Page 467
  5.4.4 Proof of Proposition 5.10......Page 468
 6.1 Solutions for Chapter 1......Page 472
  6.2.1 Two-point lower risk bound......Page 479
  6.2.2 Around Euclidean Separation......Page 480
  6.2.3 Hypothesis testing via l1 separation......Page 482
  6.2.4 Miscellaneous exercises......Page 490
 6.3 Solutions for Chapter 3......Page 502
  6.4.1 Linear Estimates vs. Maximum Likelihood......Page 520
  6.4.2 Measurement Design in Signal Recovery......Page 522
  6.4.3 Around semidefinite relaxation......Page 527
  6.4.4 Around Propositions 4.4 and 4.14......Page 543
  6.4.5 Numerical lower-bounding minimax risk......Page 597
  6.4.6 Around S-Lemma......Page 611
  6.4.7 Miscellaneous exercises......Page 614
  6.5.1 Estimation by Stochastic Optimization......Page 617
Appendix: Executive Summary on Efficient Solvability of Convex Optimization Problems......Page 634
Bibliography......Page 638
Index......Page 654