Random projection methods for stochastic convex minimization

stochastic convex minimization;random projection;stochastic convex feasibility problem

Tursun, Umit Deniz

关键词: stochastic convex minimization;    random projection;    stochastic convex feasibility problem;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/45381/Umit_Tursun.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

The first focus of this thesis is to solve a stochastic convex minimization problem over an arbitrary family of nonempty, closed and convex sets. The problem has random features. Gradient or subgradient of objective function carries stochastic errors. Number of constraint sets can be extensive or infinitely many. Constraint sets might not be known apriori yet revealed through random realizations or randomly chosen from a collection of constraint sets throughout the horizon as in online learning concept. The traditionalprojection algorithms for solving minimization problems require projecting overcomplete collection of constraints at once orover a subset of them based on a predefined selection rule. But in practical applicationseither all of the constraints might not be knownapriori or even if they are known projecting on the intersection set might be computationally prohibitive. We propose a two step gradient/subgradient iterativemethod with random projections. As the first step, arandom gradient /subgradient projection is performed before observing the random constraint set realization. After taking random gradient /subgradient projection step wereach an intermittent point, which we obtained without considering the feasibility violation.Once the set realization is revealed or chosen within collection of constraint sets, the feasibility violation ofintermittent point is corrected.We showed that projecting onto a random subcollection of them using our algorithm with diminishing stepsize is sufficient toconverge to the solution set almost surely. Also the convergence of the algorithm for constant andnondiminishing nonsummable stepsizes are provedwithin an error bound. As the first set of experiments we tested theperformance of thealgorithm over a dynamic control system.We study three versions of the problem withcorrelated unknown-but-bounded additive noise, uncorrelated unknown-but-bounded additive noise and uncorrelated bounded output and peak input additive noise under fully known system descriptioncases. It is essentially a robust least squares estimation problem where we recover state parametersfrom corrupted input and output data. We reformulated the linear least squares estimation problemas a stochastic convex minimization problem andthen usedthetwo step random projection algorithm to solve it. Although the problem has infinite number of constraints due to each realization of error term within bounded set, the algorithm goes through a finite subset of them and converges to the solution set.We also prove the existence of solution and provide equivalentminimization formulations or upper bound for these three types ofrobust least squares problems.We used standard subgradient algorithmto gauge the performance of our method.The implementation results are comparable to the ones found in literature. Our next focus is to solve a stochastic convex feasibility problem.We exploredan algorithmic approach to solve both consistent and inconsistent convex feasibility problems for closed convex uncertain sets. We concentrated ourattentionon uncertain nature of sets and finding a feasible point using a random subcollection of them.Thesets we consider might carry uncertainty due to inaccurate or imprecisespatial, spectral,stochastic information and confidence levels.For this objectivewe consider a stochastic optimization problem of minimizing an expected weightedproximity function over a collection of closed, convex sets. Weshow that the proposed algorithm converges to a point in the solution set when solution setis nonempty. In case of inconsistent feasibility problem i.e. the intersectionof closed convex constraintsets being empty the algorithm minimizes the proximityfunction. Theprojection onto a subcollection of sets approachcanbe viewed as somewhere between random implementation of alternating projection method and parallel projection method. But our method is not deterministic. Ituses random projections onto sets that carry additive bounded noise. Each realization within the bounded disturbances has equal chance of occurence.The conventional approach of set theoretic estimation problems provide solution that confirm with constraint sets known a priori or observed. But it fails to take into account that sets built on a priori or observed datamay carry disturbances or have erroneously predicted statistical information, which mayresult in inconsistent sets.The attributes of original signal such as amplitude bound, region of support, band-limitedness that are used to built sets inestimation problems may not be accurate. Additionallysets that are built using moments, spectral properties, distribution and bounds informationare based on predicted stochastic estimations. The overly conservative confidence bounds or statistical assumptions may cause inconsistencies.Also noise pertubations in measurements or random variations in the impulse response of a system can cause inconsistencies. Our algorithm projects onto a subcollection of sets some of which carry a random realization of noise on it. The implementation results show that thealgorithm converges to the solution asymptotically even if the algorithm projects onto a random subcollection of sets at each iteration.All in all this thesis work presents iterative methods to solve stochastic convex minimization problems and stochastic convex set intersection problems. The almost sure convergence of algorithms are proven. And the performance of them are shown on numerical experiments.