Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTransversality and alternating projections for nonconvex sets
174
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the method of alternating projections for finding a point in the intersection of two closed sets, possibly nonconvex. Assuming only the standard transversality condition (or a weaker version thereof), we prove local linear convergence. When the two sets are semi-algebraic and bounded, but not necessarily transversal, we nonetheless prove subsequence convergence.
rate research
Read More
For some typical and widely used non-convex half-quadratic regularization models and the Ambrosio-Tortorelli approximate Mumford-Shah model, based on the Kurdyka-L ojasiewicz analysis and the recent nonconvex proximal algorithms, we developed an efficient preconditioned framework aiming at the linear subproblems that appeared in the nonlinear alternating minimization procedure. Solving large-scale linear subproblems is always important and challenging for lots of alternating minimization algorithms. By cooperating the efficient and classical preconditioned iterations into the nonlinear and nonconvex optimization, we prove that only one or any finite times preconditioned iterations are needed for the linear subproblems without controlling the error as the usual inexact solvers. The proposed preconditioned framework can provide great flexibility and efficiency for dealing with linear subproblems and guarantee the global convergence of the nonlinear alternating minimization method simultaneously.
Two new optimization techniques based on projections onto convex space (POCS) framework for solving convex and some non-convex optimization problems are presented. The dimension of the minimization problem is lifted by one and sets corresponding to the cost function are defined. If the cost function is a convex function in R^N the corresponding set is a convex set in R^(N+1). The iterative optimization approach starts with an arbitrary initial estimate in R^(N+1) and an orthogonal projection is performed onto one of the sets in a sequential manner at each step of the optimization problem. The method provides globally optimal solutions in total-variation, filtered variation, l1, and entropic cost functions. It is also experimentally observed that cost functions based on lp, p<1 can be handled by using the supporting hyperplane concept.
By juxtaposing ideas from fractal geometry and dynamical systems, Furstenberg proposed a series of conjectures in the late 1960s that explore the relationship between digit expansions with respect to multiplicatively independent bases. In this work, we introduce and study - in the discrete context of the integers - analogues of some of the notions and results surrounding Furstenbergs work. In particular, we define a new class of fractal sets of integers that parallels the notion of $times r$-invariant sets on the 1-torus and investigate the additive and geometric independence between two such fractal sets when they are structured with respect to multiplicatively independent bases. Our main results in this direction parallel the works of Furstenberg, Hochman-Shmerkin, Shmerkin, Wu, and Lindenstrauss-Meiri-Peres and include: -a classification of all subsets of the positive integers that are simultaneously $times r$- and $times s$-invariant; -integer analogues of two of Furstenbergs transversality conjectures pertaining to the dimensions of the intersection $Acap B$ and the sumset $A+B$ of $times r$- and $times s$-invariant sets $A$ and $B$ when $r$ and $s$ are multiplicatively independent; and -a description of the dimension of iterated sumsets $A+A+cdots+A$ for any $times r$-invariant set $A$. We achieve these results by combining ideas from fractal geometry and ergodic theory to build a bridge between the continuous and discrete regimes. For the transversality results, we rely heavily on quantitative bounds on the $L^q$-dimensions of projections of restricted digit Cantor measures obtained recently by Shmerkin. We end by outlining a number of open questions and directions regarding fractal subsets of the integers.
We consider minimization of indefinite quadratics with either trust-region (norm) constraints or cubic regularization. Despite the nonconvexity of these problems we prove that, under mild assumptions, gradient descent converges to their global solutions, and give a non-asymptotic rate of convergence for the cubic variant. We also consider Krylov subspace solutions and establish sharp convergence guarantees to the solutions of both trust-region and cubic-regularized problems. Our rates mirror the behavior of these methods on convex quadratics and eigenvector problems, highlighting their scalability. When we use Krylov subspace solutions to approximate the cubic-regularized Newton step, our results recover the strongest known convergence guarantees to approximate second-order stationary points of general smooth nonconvex functions.
The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothness condition, which is satisfied by any finite-order polynomial objective function. Further, this work develops new Bregman-divergence based algorithms that are guaranteed to converge to a second-order stationary point for any relatively smooth problem. In addition, the proposed optimization methods cover both the proximal alternating minimization and the proximal alternating linearized minimization when we specialize the Bregman divergence to the Euclidian distance. Therefore, this work not only develops guaranteed optimization methods for non-Lipschitz smooth problems but also solves an open problem of showing the second-order convergence guarantees for these alternating minimization methods.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
