-
作者：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...
-
作者：Bolte, Jerome; Trong Phong Nguyen; Peypouquet, Juan; Suter, Bruce W.
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universidad Tecnica Federico Santa Maria; Universidad Tecnica Federico Santa Maria; United States Department of Defense; United States Air Force; US Air Force Research Laboratory; Yamaguchi University
摘要：This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-Aojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with Holderian growth). A counterexample shows that the...
-
作者：Chen, Xiaojun; Wets, Roger
-
作者：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).
