-
作者：Facchinei, Francisco; Lampariello, Lorenzo; Scutari, Gesualdo
作者单位：Sapienza University Rome; Roma Tre University; Purdue University System; Purdue University
摘要：We propose a general feasible method for nonsmooth, nonconvex constrained optimization problems. The algorithm is based on the (inexact) solution of a sequence of strongly convex optimization subproblems, followed by a step-size procedure. Key features of the scheme are: (i) it preserves feasibility of the iterates for nonconvex problems with nonconvex constraints, (ii) it can handle nonsmooth problems, and (iii) it naturally leads to parallel/distributed implementations. We illustrate the app...
-
作者：Schmidt, Mark; Le Roux, Nicolas; Bach, Francis
作者单位：University of British Columbia
摘要：We analyze the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from to O(1 / k) in general, and when the sum is strongly-convex the convergen...
-
作者：Jegelka, Stefanie; Bilmes, Jeff A.
作者单位：Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
摘要：We study an extension of the classical graph cut problem, wherein we replace the modular (sum of edge weights) cost function by a submodular set function defined over graph edges. Special cases of this problem have appeared in different applications in signal processing, machine learning, and computer vision. In this paper, we connect these applications via the generic formulation of cooperative graph cuts, for which we study complexity, algorithms, and connections to polymatroidal network flo...
-
作者：Bandeira, Afonso S.; Boumal, Nicolas; Singer, Amit
作者单位：New York University; Princeton University
摘要：Maximum likelihood estimation problems are, in general, intractable optimization problems. As a result, it is common to approximate the maximum likelihood estimator (MLE) using convex relaxations. In some cases, the relaxation is tight: it recovers the true MLE. Most tightness proofs only apply to situations where the MLE exactly recovers a planted solution (known to the analyst). It is then sufficient to establish that the optimality conditions hold at the planted signal. In this paper, we st...
-
作者：Drusvyatskiy, Dmitriy; Li, Guoyin; Wolkowicz, Henry
作者单位：University of Washington; University of Washington Seattle; University of New South Wales Sydney; University of Waterloo
摘要：We observe that Sturm's error bounds readily imply that for semidefinite feasibility problems, the method of alternating projections converges at a rate of , where d is the singularity degree of the problem-the minimal number of facial reduction iterations needed to induce Slater's condition. Consequently, for almost all such problems (in the sense of Lebesgue measure), alternating projections converge at a worst-case rate of O(1/root k).
