Multilevel Proximal Algorithm for Large-Scale Composite Convex Optimization
Explore the Multilevel Proximal Algorithm for optimizing large-scale composite convex functions. This paper discusses convergence rates, numerical experiments, and the extension of the multigrid framework for non-smooth cases. Learn about fine models, proximal update steps, and the MISTA algorithm for reducing problem dimensions and increasing smoothness. Dive into the details of composite convex optimization and the construction of coarse and smooth models. Discover the optimization structures, convergence rates, and gradient mappings involved in this innovative approach.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A Multilevel Proximal Algorithm for Large Scale Composite Convex Optimization Jianpei Wen 1301214553 Xin Pan 1401111635 2025/3/21 1
Content Introduction Composite Convex Optimization MISTA Convergence rate analysis Numerical experiments Conclusions 2025/3/21 2
Introduction Large scale optimization structures Composition Fidelity control For non-smooth convex function convergence rate Subgradient ? Proximal projection ?2 Extension of the multigrid framework for convex but possibly non-smooth cases 1 1 2025/3/21 3
Composite Convex Optimization Fine model of CCO min ? {? ? ? ? + ? (? )} : Closed convex set. ?: Smooth function with Lipschitz constant ? . ?: Non-smooth extended value convex function. : Fine model subscript. ? is coarse subscript. Quadratic approximation ? 2 ? (? ,? 1 ?? ,?) 2+?(?) ? ,?+1= arg min ? ? 2025/3/21 4
Composite Convex Optimization In this paper Proximal update step ? ,?+1= ? ,? ? ,?? ,? Gradient mapping ? ,? ? ,?= [? ,? ???? (? ,? 1 ?? ,?)] ?? 2025/3/21 5
MISTA Multilevel Iterative Shrinkage Thresholding Algorithm Favorable computational characteristics Reducing the dimensions of the problem Increasing the smoothness Three components of algorithm Specification of the restriction/prolongation operators Construction of an appropriate hierarchy of models Specification of smoother in the coarse model 2025/3/21 6
MISTA Information transformation ?? ,?,? ? ? Restriction ??,0= ? Prolongation ?? Coarse model construction Locally the optimality conditions of the two models match A linear term in unconstrained term in objective function A linear term to match the gradient of the Lagrangian ? 2025/3/21 7
MISTA Coarse model construction ???? ???? + ???? +< ??,??> The smooth coarse model ??= ??? Lemma 1. With the above coarse model construction and ??, then ??,0= ? Non-smooth coarse model with dual norm projection ??? = (? And ??=?? ? Lemma 2. ?? ,? ???,0+ ??,0 ?? ,? ?? )?= ? (2?) ??? ,? ???,0 ? 2025/3/21 8
MISTA Non-smooth coarse model with constraint projection ???? = ?? ?? ?? ? ?? ?????? And ????? (? ,? 1 ??= ????,0 (???,0+ ??? ?? ,?)) ? And ?? = ? ?? ?????? Lemma 3. 2025/3/21 9
MISTA 2025/3/21 10
Convergence rate analysis (Assumption 1) restriction/prolongation operators ? (Lemma 4) First order coherence property: ? , ? ??,0= ? = 0 (Lemma 5) Convex with a L-lipschitz continuous gradient: ??= ? ???? ? 1 ?? ??,? ? 3 ?? ?1? , ?? ?? ?2?? = 0 ?? ,? ??,? ?? ? 2 4?? ??
Convergence rate analysis First order algorithms: ? is convex and has a Lipschitz continuous gradient ? ? ,?? ? ?? ? 1 2 ??? ? ?? ? (Lemma 6): Replace the gradients in with the coarse correction term obtained from the coarse model. (Lemma 4), (Lemma 5) ? ,? ? , ,? ,? ? , 1+2? ? ,?= ?? 2 2 ? ,? ? , 4??2 ? 1??,???,? ??,?= ?? ?=0
Convergence rate analysis The coarse correction term satisfies a condition similar to the Lipschitz continuity of the gradient. ? ? 1 (Lemma 7) Convergent algorithm with non- expansive steps is applied at the coarse level: (Assumption 1), (Lemma 5) ? ,? ? , non-expansive: ??,?+1 ??,? ??,? ??,? 1 ??? ? ?? ? 2 16 2 2?2 2??,0 2 9?2?1 ? ,? ? ,
Convergence rate analysis (Theorem 3) Contraction for coarse correction update A coarse correction update is performed using m iterations of the coarse contraction algorithm. (Lemma 6) (Lemma 7) (Assumption 1) ? ,?+1 ? , 2 ? ?,? 2 ? ,? ? , ?1 1 and ?2 1, or ? is sufficiently large ? ?,? < 1 (Theorem 1) ? ? is convex and has Lipschitz- continuous gradients. Converges R-linearly (Theorem 2) ? ? is strongly convex and has Lipschitz- continuous gradients. Converges Q-linearly
Numerical Experiments Fine model 2+? ?(? ) 1 min ? ? ? ? 2 Coarse model with smoothing approach 2+< ??,??> +?? 2+ ?2 ? min ?? ? ???? ?? 2 ? ?? ? ? ? 2025/3/21 15
Numerical Experiments Image restoration 2025/3/21 16
Numerical Experiments Performance Comparison Convergence 2025/3/21 17
Numerical Experiments Performance Comparison CPU Time 0.5% noise 1% noise 2025/3/21 18
Numerical Experiments Experiments repetition mista( Maggie.jpeg , fista ) 2025/3/21 19
Numerical Experiments Experiments repetition 2025/3/21 20
Conclusions Develop a multilevel algorithm for composite optimization Replace quadratic approximation with coarse approximation Develop MISTA based on ISTA and establish its linear rate Future work Improve the results by advanced operators Develop multilevel algorithm on FISTA 2025/3/21 21
THANKS! Q&A 2025/3/21 22
