High-Dimensional Optimization and Probability: With a View Towards Data Science

Preface
Contents
Projection of a Point onto a Convex Set via Charged Balls Method
1 Introduction
2 Charged Balls Method and its Modification
3 Case of the Set with Nonsmooth Boundary
4 Numerical Experiments
5 Conclusion
References
Towards Optimal Sampling for Learning Sparse Approximations in High Dimensions
1 Introduction
1.1 Main Problem
1.2 Overview
1.3 Additional Contributions
1.4 Related Literature
1.5 Outline
2 Preliminaries
2.1 Notation
2.2 Problem and Key Questions
2.3 Examples
2.4 Multi-Index Sets
3 Sparse Approximation via (Weighted) Least Squares
3.1 Computation of the Least-Squares Approximation
3.2 Accuracy, Stability and Sample Complexity
3.3 Monte Carlo Sampling
3.4 Optimal Sampling
3.5 Practical Optimal Sampling via Discrete Measures
3.6 Numerical Examples
3.7 Proofs of Theorems 2 and 3
4 Sparse Approximation via 1-Minimization
4.1 Formulation
4.2 Accuracy, Stability and Sample Complexity
4.3 Monte Carlo Sampling
4.4 `Optimal' Sampling
4.5 `Optimal' Sampling and Discrete Measures
4.6 Further Discussion and Numerical Examples
4.7 Proof of Theorems 5 and 6
5 A Novel Approach for Sparse Polynomial Approximation on Irregular Domains
5.1 Method
5.2 Orderings
5.3 Numerical Examples
6 Structured Sparse Approximation
6.1 Weighted Sparsity and Weighted 1-Minimization
6.2 Sparsity in Lower Sets
6.3 Sampling and Numerical Experiments
7 Conclusions and Challenges
References
Recent Theoretical Advances in Non-Convex Optimization
1 Introduction
2 Preliminaries
2.1 Global Optimization Is NP-Hard
2.2 Lower Complexity Bound for Global Optimization
2.3 Examples of Non-Convex Problems
2.3.1 Problems with Hidden Convexity or Analytic Solutions
2.3.2 Problems with Convergence Results
2.3.3 Geometry of Non-Convex Optimization Problems
3 Deterministic First-Order Methods
3.1 Unconstrained Minimization
3.2 Incorporating Simple Constraints
3.3 Incorporating Momentum for Acceleration
4 Stochastic First-Order Methods
4.1 General View on Optimal Deterministic and Stochastic First-Order Methods for Non-Convex Optimization
4.1.1 Deterministic Case
4.1.2 Stochastic Case: Uniformly Bounded Variance
4.1.3 Stochastic Case: Finite-Sum Minimization
4.2 SGD and Its Variants
4.2.1 Assumptions on the Stochastic Gradient
4.2.2 The Choice of the Stepsize
4.2.3 Over-Parameterized Models
4.2.4 Proximal Variants
4.2.5 Momentum-SGD
4.2.6 Random Reshuffling
4.3 Variance-Reduced Methods
4.3.1 Convex and Weakly Convex Sums of Non-Convex Functions
4.4 Adaptive Methods
4.4.1 AdaGrad and Adam
4.4.2 Adaptive SGD
5 First-Order Methods Under Additional Assumptions
5.1 Polyak–Łojasiewicz Condition
5.1.1 Stochastic First-Order Methods Under Polyak–Łojasiewicz Condition
5.2 Star-Convexity and α-Weak-Quasi-Convexity
5.2.1 Stochastic Methods and α-Weak-Quasi-Convexity
5.2.2 Further Generalizations
6 Higher-Order Methods
6.1 Second-Order Methods
6.2 Stochastic Second-Order Methods
6.3 Tensor Methods
7 Zeroth-Order Methods
7.1 Random Directions Gradient Estimations
7.2 Variance-Reduced Zeroth-Order Methods
8 Globalization Techniques
8.1 Multistart Technique
8.2 Multidimensional Bisection
8.3 Langevin Dynamics
References
Higher Order Embeddings for the Composition of the Harmonic Projection and Homotopy Operators
1 Introduction
2 Preliminary Results
3 Main Results
4 Applications
References
Codifferentials and Quasidifferentials of the Expectation of Nonsmooth Random Integrands and Two-Stage StochasticProgramming
1 Introduction
2 Preliminaries
3 Codifferentials of the Expectation of Nonsmooth Random Integrands
4 Nonsmooth Two-Stage Stochastic Programming
4.1 Exact Penalty Functions
4.2 Optimality Conditions
5 Conclusions
References
On the Expected Extinction Time for the Adjoint Circuit Chains Associated with a Random Walk with Jumps in RandomEnvironments
1 Introduction
2 Circuit and Weight Representations of the Adjoint Circuit Chains Associated with a Random Walk with Jumps in Fixed, Random Environments
2.1 Fixed Environments
2.2 Random Environments
3 The Expected Extinction Time for the Adjoint Circuit Chains Associated with a Random Walk with Jumps in Random Environments
3.1 For the Circuit Chain (Xn)n N
3.1.1 k Z+
3.1.2 k Z*-
3.2 For the Circuit Chain (X'n)n N
3.2.1 k Z+
3.2.2 k Z-
References
A Statistical Learning Theory Approach for the Analysis of the Trade-off Between Sample Size and Precision in Truncated Ordinary Least Squares
1 Introduction
2 Model
3 Optimal Trade-off Between Sample Size and Precision of Supervision via Statistical Learning Theory
4 Discussion
References
Recent Theoretical Advances in Decentralized Distributed Convex Optimization
1 Introduction
2 Decentralized Optimization of Smooth Convex Functions
2.1 Consensus Algorithms
2.1.1 Quadratic Optimization Point of View
2.1.2 Chebyshev Acceleration
2.1.3 Summary
2.2 Main Assumptions on Objective Functions
2.3 Distributed Gradient Descent
2.4 EXTRA
2.5 Accelerated Decentralized Algorithms
2.6 Time-Varying Networks
2.7 Inexact Oracle Point of View
2.7.1 Inexact Oracle Construction
2.7.2 Convergence Result for Algorithm 18
2.7.3 Stochastic Decentralized Optimization
2.8 Decentralized Saddle-Point Problems
3 Convex Problems with Affine Constraints
3.1 Primal Approach
3.2 Dual Approach
3.2.1 Convex Dual Function
3.2.2 Strongly Convex Dual Functions and Restarts Technique
3.2.3 Direct Acceleration for Strongly Convex Dual Function
3.3 Applications to Decentralized Distributed Optimization
3.4 Discussion
3.5 Application for Population Wasserstein Barycenter Calculation
3.5.1 Definitions and Properties
3.5.2 SA Approach
3.5.3 SAA Approach
3.5.4 SA vs SAA Comparison
4 Derivative-Free Distributed Optimization
4.1 Theoretical Part
4.1.1 Convex Case
4.1.2 Strongly Convex Case
4.1.3 From Composite Optimization to Decentralized Distributed Optimization
References
On Training Set Selection in Spatial Deep Learning
1 Introduction
2 Selection Criteria Illustration
2.1 Training as Parameter Estimation
2.2 Training Set Selection and Parameter Estimation
2.3 Auto-Correlation due to Overlap
3 Model
3.1 Model Formulation
3.2 Model Illustration
4 Conclusions
References
Surrogate-Based Reduced-Dimension Global Optimization in Process Systems Engineering
1 Introduction
2 Model Types in Process Systems Engineering
2.1 White-Box Model
2.2 Black-Box Model
2.3 Gray-Box Model
3 Surrogate Modeling for Solving Reduced-Dimension Subproblems
3.1 Sampling Plan/Design of Experiments
3.2 Surrogate Model Validation
3.3 Sample-Point Refinement/Adaptive Sampling
3.4 Selection of Surrogate Type
4 Surrogate Modeling Applications in Process Systems Optimization
5 Summary and Future Work
References
A Viscosity Iterative Method with Alternated Inertial Terms for Solving the Split Feasibility Problem
1 Introduction
2 Preliminaries
3 Main Results
4 Numerical Results
References
Efficient Location-Based Tracking for IoT Devices Using Compressive Sensing and Machine Learning Techniques
1 Introduction
2 Signal Representation
2.1 Principles
2.2 Model
3 Compressive Sensing
3.1 Basics
3.2 Sparsity
3.3 Discrete Cosine Transform
3.4 Measurement Matrix
3.5 Block-Wise Reconstruction
4 Lasso
4.1 Algorithm
4.2 Parameter Optimization
4.3 Adaptive Sampling
5 Neural Networks
5.1 Introduction
5.2 Network Design and Optimization
5.3 Adaptive Sampling
6 Numerical Results
6.1 Simulation Results
6.2 Real Data Experiment
7 Future Work
8 Conclusion
References
Nonsmooth Mathematical Programs with Vanishing Constraints in Banach Spaces
1 Introduction
2 Preliminaries
3 Necessary Optimality Conditions
4 Sufficient Conditions for the Nonsmooth Abadie Constraint Qualification
5 Conclusions
References