Search

We consider the problem of minimizing composite functions of the form f (g (x)) + h (x) , where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an ϵ -stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When g is a finite average of N components, we obtain sample complexity O (N + N 4 / 5 ϵ - 1) for both mapping and Jacobian evaluations. When g is a general expectation, we obtain sample complexities of O (ϵ - 5 / 2) and O (ϵ - 3 / 2) for component mappings and their Jacobians respectively. If in addition f is smooth, then improved sample complexities of O (N + N 1 / 2 ϵ - 1) and O (ϵ - 3 / 2) are derived for g being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations. [ABSTRACT FROM AUTHOR]

In this paper, we study the lower iteration complexity bounds for finding the saddle point of a strongly convex and strongly concave saddle point problem: min x max y F (x , y) . We restrict the classes of algorithms in our investigation to be either pure first-order methods or methods using proximal mappings. For problems with gradient Lipschitz constants ( L x , L y and L xy ) and strong convexity/concavity constants ( μ x and μ y ), the class of pure first-order algorithms with the linear span assumption is shown to have a lower iteration complexity bound of Ω L x μ x + L xy 2 μ x μ y + L y μ y · ln 1 ϵ , where the term L xy 2 μ x μ y explains how the coupling influences the iteration complexity. Under several special parameter regimes, this lower bound has been achieved by corresponding optimal algorithms. However, whether or not the bound under the general parameter regime is optimal remains open. Additionally, for the special case of bilinear coupling problems, given the availability of certain proximal operators, a lower bound of Ω L xy 2 μ x μ y · ln (1 ϵ) is established under the linear span assumption, and optimal algorithms have already been developed in the literature. By exploiting the orthogonal invariance technique, we extend both lower bounds to the general pure first-order algorithm class and the proximal algorithm class without the linear span assumption. As an application, we apply proper scaling to the worst-case instances, and we derive the lower bounds for the general convex concave problems with μ x = μ y = 0 . Several existing results in this case can be deduced from our results as special cases. [ABSTRACT FROM AUTHOR]

In this paper we study nonconvex and nonsmooth multi-block optimization over Euclidean embedded (smooth) Riemannian submanifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. By utilizing the embedding structure, we develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings, where the duality is with respect to the embedded Euclidean spaces. First, we introduce the optimality conditions for the afore-mentioned optimization models. Then, the notion of ϵ -stationary solutions is introduced as a result. The main part of the paper is to show that the proposed algorithms possess an iteration complexity of O (1 / ϵ 2) to reach an ϵ -stationary solution. For prohibitively large-size tensor or machine learning models, we present a sampling-based stochastic algorithm with the same iteration complexity bound in expectation. In case the subproblems are not analytically solvable, a feasible curvilinear line-search variant of the algorithm based on retraction operators is proposed. Finally, we show specifically how the algorithms can be implemented to solve a variety of practical problems such as the NP-hard maximum bisection problem, the ℓ q regularized sparse tensor principal component analysis and the community detection problem. Our preliminary numerical results show great potentials of the proposed methods. [ABSTRACT FROM AUTHOR]