BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Shuzhong Zhang

Shuzhong Zhang contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.OCMachine Learningmath.NANumerical Analysisq-fin.MFq-fin.PMInformation Retrievalq-fin.RM

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
24works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

24 published item(s)

preprint2022arXiv

A Gradient Complexity Analysis for Minimizing the Sum of Strongly Convex Functions with Varying Condition Numbers

A popular approach to minimize a finite-sum of convex functions is stochastic gradient descent (SGD) and its variants. Fundamental research questions associated with SGD include: (i) To find a lower bound on the number of times that the gradient oracle of each individual function must be assessed in order to find an $ε$-minimizer of the overall objective; (ii) To design algorithms which guarantee to find an $ε$-minimizer of the overall objective in expectation at no more than a certain number of times (in terms of $1/ε$) that the gradient oracle of each functions needs to be assessed (i.e., upper bound). If these two bounds are at the same order of magnitude, then the algorithms may be called optimal. Most existing results along this line of research typically assume that the functions in the objective share the same condition number. In this paper, the first model we study is the problem of minimizing the sum of finitely many strongly convex functions whose condition numbers are all different. We propose an SGD method for this model and show that it is optimal in gradient computations, up to a logarithmic factor. We then consider a constrained separate block optimization model, and present lower and upper bounds for its gradient computation complexity. Next, we propose to solve the Fenchel dual of the constrained block optimization model via the SGD we introduced earlier, and show that it yields a lower iteration complexity than solving the original model by the ADMM-type approach. Finally, we extend the analysis to the general composite convex optimization model, and obtain gradient-computation complexity results under certain conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Accelerating Adaptive Cubic Regularization of Newton's Method via Random Sampling

In this paper, we consider an unconstrained optimization model where the objective is a sum of a large number of possibly nonconvex functions, though overall the objective is assumed to be smooth and convex. Our bid to solving such model uses the framework of cubic regularization of Newton's method. As well known, the crux in cubic regularization is its utilization of the Hessian information, which may be computationally expensive for large-scale problems. To tackle this, we resort to approximating the Hessian matrix via sub-sampling. In particular, we propose to compute an approximated Hessian matrix by either \textit{uniformly}\/ or \textit{non-uniformly}\/ sub-sampling the components of the objective. Based upon such sampling strategy, we develop accelerated adaptive cubic regularization approaches and provide theoretical guarantees on global iteration complexity of $O(ε^{-1/3})$ with high probability, which matches that of the original accelerated cubic regularization methods \cite{Jiang-2017-Unified} using the \textit{full}\/ Hessian information. Interestingly, we show that in the worst case scenario our algorithm still achieves an $O\left(\log(ε^{-1})ε^{-5/6}\right)$ iteration complexity bound. The performances of the proposed methods on the regularized logistic regression problems show a clear effect of acceleration in terms of the epoch counts on several real data sets.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Cubic-Regularized Newton for Spectral Constrained Matrix Optimization and its Application to Fairness

Matrix functions are utilized to rewrite smooth spectral constrained matrix optimization problems as smooth unconstrained problems over the set of symmetric matrices which are then solved via the cubic-regularized Newton method. A second-order chain rule identity for matrix functions is proven to compute the higher-order derivatives to implement cubic-regularized Newton, and a new convergence analysis is provided for cubic-regularized Newton for matrix vector spaces. We demonstrate the applicability of our approach by conducting numerical experiments on both synthetic and real datasets. In our experiments, we formulate a new model for estimating fair and robust covariance matrices in the spirit of the Tyler's M-estimator (TME) model and demonstrate its advantage.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Projectively and weakly simultaneously diagonalizable matrices and their applications

Characterizing simultaneously diagonalizable (SD) matrices has been receiving considerable attention in the recent decades due to its wide applications and its role in matrix analysis. However, the notion of SD matrices is arguably still restrictive for wider applications. In this paper, we consider two error measures related to the simultaneous diagonalization of matrices, and propose several new variants of SD thereof; in particular, TWSD, TWSD-B, T_{m,n}-SD (SDO), DWSD and D_{m,n}-SD (SDO). Those are all weaker forms of SD. We derive various sufficient and/or necessary conditions of them under different assumptions, and show the relationships between these new notions. Finally, we discuss the applications of these new notions in, e.g., quadratically constrained quadratic programming (QCQP) and independent component analysis (ICA).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based On the Augmented Lagrangian

Nonlinearly constrained nonconvex and nonsmooth optimization models play an increasingly important role in machine learning, statistics and data analytics. In this paper, based on the augmented Lagrangian function we introduce a flexible first-order primal-dual method, to be called nonconvex auxiliary problem principle of augmented Lagrangian (NAPP-AL), for solving a class of nonlinearly constrained nonconvex and nonsmooth optimization problems. We demonstrate that NAPP-AL converges to a stationary solution at the rate of o(1/\sqrt{k}), where k is the number of iterations. Moreover, under an additional error bound condition (to be called VP-EB in the paper), we further show that the convergence rate is in fact linear. Finally, we show that the famous Kurdyka- Lojasiewicz property and the metric subregularity imply the afore-mentioned VP-EB condition.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization

In this paper, we propose a unified two-phase scheme to accelerate any high-order regularized tensor approximation approach on the smooth part of a composite convex optimization model. The proposed scheme has the advantage of not needing to assume any prior knowledge of the Lipschitz constants for the gradient, the Hessian and/or high-order derivatives. This is achieved by tuning the parameters used in the algorithm \textit{adaptively} in its process of progression, which has been successfully incorporated in high-order nonconvex optimization (CartisGouldToint2018, Birgin-Gardenghi-Martinez-Santos-Toint-2017). In general, we show that the adaptive high-order method has an iteration bound of $O\left( 1 / ε^{1/(p+1)} \right)$ if the first $p$-th order derivative information is used in the approximation, which has the same iteration complexity as in that of the nonadaptive version in (Baes-2009, Nesterov-2018) where the Lipschitz constants are assumed to be known and the subproblems are assumed to be solved exactly. Thus, our results partially address the problem of incorporating adaptive strategies into the high-order {\it accelerated} methods raised by Nesterov in (Nesterov-2018), although our strategies cannot assure the convexity of the auxiliary problem and such adaptive strategies are already popular in high-order nonconvex optimization (CartisGouldToint2018, Birgin-Gardenghi-Martinez-Santos-Toint-2017). Our numerical experiment results show a clear effect of real acceleration displayed in the adaptive Newton's method with cubic regularization on a set of regularized logistic regression instances.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An ADMM-Based Interior-Point Method for Large-Scale Linear Programming

We propose a new framework to implement interior point method (IPM) to solve very large linear programs (LP). Traditional IPMs typically use Newton's method to approximately solve a subproblem that aims to minimize a log-barrier penalty function at each iteration. Due its connection to Newton's method, IPM is often classified as second-order method -- a genre that is attached with stability and accuracy at the expense of scalability. Indeed, computing a Newton step amounts to solving a large linear system, which can be efficiently implemented if the input data are reasonably-sized and/or sparse and/or well-structured. However, in case the above premises fail, then the challenge still stands on the way for a traditional IPM. To deal with this challenge, one approach is to apply the iterative procedure, such as preconditioned conjugate gradient method, to solve the linear system. Since the linear system is different each iteration, it is difficult to find good pre-conditioner to achieve the overall solution efficiency. In this paper, an alternative approach is proposed. Instead of applying Newton's method, we resort to the alternating direction method of multipliers (ADMM) to approximately minimize the log-barrier penalty function at each iteration, under the framework of primal-dual path-following for a homogeneous self-dual embedded LP model. The resulting algorithm is an ADMM-Based Interior Point Method, abbreviated as ABIP in this paper. The new method inherits stability from IPM, and scalability from ADMM. Because of its self-dual embedding structure, ABIP is set to solve any LP without requiring prior knowledge about its feasibility. We conduct extensive numerical experiments testing ABIP with large-scale LPs from NETLIB and machine learning applications. The results demonstrate that ABIP compares favorably with existing LP solvers including SDPT3, MOSEK, DSDP-CG and SCS.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Optimal High-Order Tensor Method for Convex Optimization

This paper is concerned with finding an optimal algorithm for minimizing a composite convex objective function. The basic setting is that the objective is the sum of two convex functions: the first function is smooth with up to the d-th order derivative information available, and the second function is possibly non-smooth, but its proximal tensor mappings can be computed approximately in an efficient manner. The problem is to find -- in that setting -- the best possible (optimal) iteration complexity for convex optimization. Along that line, for the smooth case (without the second non-smooth part in the objective), Nesterov (1983) proposed an optimal algorithm for the first-order methods (d=1) with iteration complexity O( 1 / k^2 ). A high-order tensor algorithm with iteration complexity of O( 1 / k^{d+1} ) was proposed by Baes (2009) and Nesterov (2018). In this paper, we propose a new high-order tensor algorithm for the general composite case, with the iteration complexity of O( 1 / k^{(3d+1)/2} ), which matches the lower bound for the d-th order methods as established in Nesterov (2018), and Shamir et al. (2018), and hence is optimal. Our approach is based on the Accelerated Hybrid Proximal Extragradient (A-HPE) framework proposed in Monteiro and Svaiter (2013), where a bisection procedure is installed for each A-HPE iteration. At each bisection step a proximal tensor subproblem is approximately solved, and the total number of bisection steps per A-HPE iteration is bounded by a logarithmic factor in the precision required.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Binary Random Projections with Controllable Sparsity Patterns

Random projection is often used to project higher-dimensional vectors onto a lower-dimensional space, while approximately preserving their pairwise distances. It has emerged as a powerful tool in various data processing tasks and has attracted considerable research interest. Partly motivated by the recent discoveries in neuroscience, in this paper we study the problem of random projection using binary matrices with controllable sparsity patterns. Specifically, we proposed two sparse binary projection models that work on general data vectors. Compared with the conventional random projection models with dense projection matrices, our proposed models enjoy significant computational advantages due to their sparsity structure, as well as improved accuracies in empirical evaluations.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Cubic Regularized Newton Method for Saddle Point Models: a Global and Local Convergence Analysis

In this paper, we propose a cubic regularized Newton (CRN) method for solving convex-concave saddle point problems (SPP). At each iteration, a cubic regularized saddle point subproblem is constructed and solved, which provides a search direction for the iterate. With properly chosen stepsizes, the method is shown to converge to the saddle point with global linear and local superlinear convergence rates, if the saddle point function is gradient Lipschitz and strongly-convex-strongly-concave. In the case that the function is merely convex-concave, we propose a homotopy continuation (or path-following) method. Under a Lipschitz-type error bound condition, we present an iteration complexity bound of $\mathcal{O}\left(\ln \left(1/ε\right)\right)$ to reach an $ε$-solution through a homotopy continuation approach, and the iteration complexity bound becomes $\mathcal{O}\left(\left(1/ε\right)^{\frac{1-θ}{θ^2}}\right)$ under a Hölderian-type error bound condition involving a parameter $θ$ ($0<θ<1$).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributionally Robust Profit Opportunities

This paper expands the notion of robust profit opportunities in financial markets to incorporate distributional uncertainty using Wasserstein distance as the ambiguity measure. Financial markets with risky and risk-free assets are considered. The infinite dimensional primal problems are formulated, leading to their simpler finite dimensional dual problems. A principal motivating question is how does distributional uncertainty help or hurt the robustness of the profit opportunity. Towards answering this question, some theory is developed and computational experiments are conducted. Finally some open questions and suggestions for future research are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributionally Robust XVA via Wasserstein Distance: Wrong Way Counterparty Credit and Funding Risk

This paper investigates calculations of robust XVA, in particular, credit valuation adjustment (CVA) and funding valuation adjustment (FVA) for over-the-counter derivatives under distributional uncertainty using Wasserstein distance as the ambiguity measure. Wrong way counterparty credit risk and funding risk can be characterized (and indeed quantified) via the robust XVA formulations. The simpler dual formulations are derived using recent infinite dimensional Lagrangian duality results. Next, some computational experiments are conducted to measure the additional XVA charges due to distributional uncertainty under a variety of portfolio and market configurations. Finally some suggestions for future work are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Generalization Bounds for Stochastic Saddle Point Problems

This paper studies the generalization bounds for the empirical saddle point (ESP) solution to stochastic saddle point (SSP) problems. For SSP with Lipschitz continuous and strongly convex-strongly concave objective functions, we establish an $\mathcal{O}(1/n)$ generalization bound by using a uniform stability argument. We also provide generalization bounds under a variety of assumptions, including the cases without strong convexity and without bounded domains. We illustrate our results in two examples: batch policy learning in Markov decision process, and mixed strategy Nash equilibrium estimation for stochastic games. In each of these examples, we show that a regularized ESP solution enjoys a near-optimal sample complexity. To the best of our knowledge, this is the first set of results on the generalization theory of ESP.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Polar decomposition based algorithms on the product of Stiefel manifolds with applications in tensor approximation

In this paper, we propose a general algorithmic framework to solve a class of optimization problems on the product of complex Stiefel manifolds based on the matrix polar decomposition. We establish the weak convergence, global convergence and linear convergence rate of this general algorithmic approach using the Łojasiewicz gradient inequality and the Morse-Bott property. This general algorithm and its convergence results are applied to the simultaneous approximate tensor diagonalization and simultaneous approximate tensor compression, which include as special cases the low rank orthogonal approximation, best rank-1 approximation and low multilinear rank approximation for higher order complex tensors. We also present a symmetric variant of this general algorithm to solve a symmetric variant of this class of optimization models, which essentially optimizes over a single Stiefel manifold. We establish its weak convergence, global convergence and linear convergence rate in a similar way. This symmetric variant and its convergence results are applied to the simultaneous approximate symmetric tensor diagonalization, which includes as special cases the low rank symmetric orthogonal approximation and best symmetric rank-1 approximation for higher order complex symmetric tensors. It turns out that well-known algorithms such as LROAT, S-LROAT, HOPM, S-HOPM are all special cases of this general algorithmic framework and its symmetric variant, and our convergence results subsume the results found in the literature designed for those special cases. All the algorithms and convergence results in this paper also apply to the real case.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Robust Arbitrage Conditions for Financial Markets

This paper investigates arbitrage properties of financial markets under distributional uncertainty using Wasserstein distance as the ambiguity measure. The weak and strong forms of the classical arbitrage conditions are considered. A relaxation is introduced for which we coin the term statistical arbitrage. The simpler dual formulations of the robust arbitrage conditions are derived. A number of interesting questions arise in this context. One question is: can we compute a critical Wasserstein radius beyond which an arbitrage opportunity exists? What is the shape of the curve mapping the degree of ambiguity to statistical arbitrage levels? Other questions arise regarding the structure of best (worst) case distributions and optimal portfolios. Towards answering these questions, some theory is developed and computational experiments are conducted for specific problem instances. Finally some open questions and suggestions for future research are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Characterizing Real-Valued Multivariate Complex Polynomials and Their Symmetric Tensor Representations

In this paper we study multivariate polynomial functions in complex variables and the corresponding associated symmetric tensor representations. The focus is on finding conditions under which such complex polynomials/tensors always take real values. We introduce the notion of symmetric conjugate forms and general conjugate forms, and present characteristic conditions for such complex polynomials to be real-valued. As applications of our results, we discuss the relation between nonnegative polynomials and sums of squares in the context of complex polynomials. Moreover, new notions of eigenvalues/eigenvectors for complex tensors are introduced, extending properties from the Hermitian matrices. Finally, we discuss an important property for symmetric tensors, which states that the largest absolute value of eigenvalue of a symmetric real tensor is equal to its largest singular value; the result is known as Banach&#39;s theorem. We show that a similar result holds in the complex case as well.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Extragradient-Based Alternating Direction Method for Convex Minimization

In this paper, we consider the problem of minimizing the sum of two convex functions subject to linear linking constraints. The classical alternating direction type methods usually assume that the two convex functions have relatively easy proximal mappings. However, many problems arising from statistics, image processing and other fields have the structure that while one of the two functions has easy proximal mapping, the other function is smoothly convex but does not have an easy proximal mapping. Therefore, the classical alternating direction methods cannot be applied. To deal with the difficulty, we propose in this paper an alternating direction method based on extragradients. Under the assumption that the smooth function has a Lipschitz continuous gradient, we prove that the proposed method returns an $ε$-optimal solution within $O(1/ε)$ iterations. We apply the proposed method to solve a new statistical model called fused logistic regression. Our numerical experiments show that the proposed method performs very well when solving the test problems. We also test the performance of the proposed method through solving the lasso problem arising from statistics and compare the result with several existing efficient solvers for this problem; the results are very encouraging indeed.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity

The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in [7] indicating that the multi-block ADMM for minimizing the sum of $N$ $(N\geq 3)$ convex functions with $N$ block variables linked by linear constraints may diverge. It is therefore of great interest to investigate further sufficient conditions on the input side which can guarantee convergence for the multi-block ADMM. The existing results typically require the strong convexity on parts of the objective. In this paper, we present convergence and convergence rate results for the multi-block ADMM applied to solve certain $N$-block $(N\geq 3)$ convex minimization problems without requiring strong convexity. Specifically, we prove the following two results: (1) the multi-block ADMM returns an $ε$-optimal solution within $O(1/ε^2)$ iterations by solving an associated perturbation to the original problem; (2) the multi-block ADMM returns an $ε$-optimal solution within $O(1/ε)$ iterations when it is applied to solve a certain sharing problem, under the condition that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz property, which essentially covers most convex optimization models except for some pathological cases.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Local Linear Convergence of ISTA and FISTA on the LASSO Problem

We establish local linear convergence bounds for the ISTA and FISTA iterations on the model LASSO problem. We show that FISTA can be viewed as an accelerated ISTA process. Using a spectral analysis, we show that, when close enough to the solution, both iterations converge linearly, but FISTA slows down compared to ISTA, making it advantageous to switch to ISTA toward the end of the iteration processs. We illustrate the results with some synthetic numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Global Linear Convergence of the ADMM with Multi-Block Variables

The alternating direction method of multipliers (ADMM) has been widely used for solving structured convex optimization problems. In particular, the ADMM can solve convex programs that minimize the sum of $N$ convex functions with $N$-block variables linked by some linear constraints. While the convergence of the ADMM for $N=2$ was well established in the literature, it remained an open problem for a long time whether or not the ADMM for $N \ge 3$ is still convergent. Recently, it was shown in [3] that without further conditions the ADMM for $N\ge 3$ may actually fail to converge. In this paper, we show that under some easily verifiable and reasonable conditions the global linear convergence of the ADMM when $N\geq 3$ can still be assured, which is important since the ADMM is a popular method for solving large scale multi-block optimization models and is known to perform very well in practice even when $N\ge 3$. Our study aims to offer an explanation for this phenomenon.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Sublinear Convergence Rate of Multi-Block ADMM

The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems. Despite of its success in practice, the convergence properties of the standard ADMM for minimizing the sum of $N$ $(N\geq 3)$ convex functions with $N$ block variables linked by linear constraints, have remained unclear for a very long time. In this paper, we present convergence and convergence rate results for the standard ADMM applied to solve $N$-block $(N\geq 3)$ convex minimization problem, under the condition that one of these functions is convex (not necessarily strongly convex) and the other $N-1$ functions are strongly convex. Specifically, in that case the ADMM is proven to converge with rate $O(1/t)$ in a certain ergodic sense, and $o(1/t)$ in non-ergodic sense, where $t$ denotes the number of iterations. As a by-product, we also provide a simple proof for the $O(1/t)$ convergence rate of two-block ADMM in terms of both objective error and constraint violation, without assuming any condition on the penalty parameter and strong convexity on the functions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Smoothing SQP Framework for a Class of Composite $L_q$ Minimization over Polyhedron

The composite $L_q~(0<q<1)$ minimization problem over a general polyhedron has received various applications in machine learning, wireless communications, image restoration, signal reconstruction, etc. This paper aims to provide a theoretical study on this problem. Firstly, we show that for any fixed $0<q<1$, finding the global minimizer of the problem, even its unconstrained counterpart, is strongly NP-hard. Secondly, we derive Karush-Kuhn-Tucker (KKT) optimality conditions for local minimizers of the problem. Thirdly, we propose a smoothing sequential quadratic programming framework for solving this problem. The framework requires a (approximate) solution of a convex quadratic program at each iteration. Finally, we analyze the worst-case iteration complexity of the framework for returning an $ε$-KKT point; i.e., a feasible point that satisfies a perturbed version of the derived KKT optimality conditions. To the best of our knowledge, the proposed framework is the first one with a worst-case iteration complexity guarantee for solving composite $L_q$ minimization over a general polyhedron.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Iteration Bounds for Finding the $ε$-Stationary Points for Structured Nonconvex Optimization

In this paper we study proximal conditional-gradient (CG) and proximal gradient-projection type algorithms for a block-structured constrained nonconvex optimization model, which arises naturally from tensor data analysis. First, we introduce a new notion of $ε$-stationarity, which is suitable for the structured problem under consideration. %, compared with other similar solution concepts. We then propose two types of first-order algorithms for the model based on the proximal conditional-gradient (CG) method and the proximal gradient-projection method respectively. If the nonconvex objective function is in the form of mathematical expectation, we then discuss how to incorporate randomized sampling to avoid computing the expectations exactly. For the general block optimization model, the proximal subroutines are performed for each block according to either the block-coordinate-descent (BCD) or the maximum-block-improvement (MBI) updating rule. If the gradient of the nonconvex part of the objective $f$ satisfies $\| \nabla f(x) - \nabla f(y)\|_q \le M \|x-y\|_p^δ$ where $δ=p/q$ with $1/p+1/q=1$, then we prove that the new algorithms have an overall iteration complexity bound of $O(1/ε^q)$ in finding an $ε$-stationary solution. If $f$ is concave then the iteration complexity reduces to $O(1/ε)$. Our numerical experiments for tensor approximation problems show promising performances of the new solution algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Tensor Principal Component Analysis via Convex Optimization

This paper is concerned with the computation of the principal components for a general tensor, known as the tensor principal component analysis (PCA) problem. We show that the general tensor PCA problem is reducible to its special case where the tensor in question is super-symmetric with an even degree. In that case, the tensor can be embedded into a symmetric matrix. We prove that if the tensor is rank-one, then the embedded matrix must be rank-one too, and vice versa. The tensor PCA problem can thus be solved by means of matrix optimization under a rank-one constraint, for which we propose two solution methods: (1) imposing a nuclear norm penalty in the objective to enforce a low-rank solution; (2) relaxing the rank-one constraint by Semidefinite Programming. Interestingly, our experiments show that both methods yield a rank-one solution with high probability, thereby solving the original tensor PCA problem to optimality with high probability. To further cope with the size of the resulting convex optimization models, we propose to use the alternating direction method of multipliers, which reduces significantly the computational efforts. Various extensions of the model are considered as well.

0 citations0 reviewsNo code linkedOpen access