• ### Tightness of a new and enhanced semidefinite relaxation for MIMO detection(1710.02048)

Dec. 24, 2018 cs.IT, math.IT, math.OC
In this paper, we consider a fundamental problem in modern digital communications known as multi-input multi-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefinite relaxation (SDR) based algorithms have been proposed to solve the problem in the literature. In this paper, we first show that the conventional SDR is generally not tight for the problem. Then, we propose a new and enhanced SDR and show its tightness under an easily checkable condition, which essentially requires the level of the noise to be below a certain threshold. The above results have answered an open question posed by So in [35]. Numerical simulation results show that our proposed SDR significantly outperforms the conventional SDR in terms of the relaxation gap.
• ### Low-M-Rank Tensor Completion and Robust Tensor PCA(1501.03689)

Oct. 10, 2018 math.OC
In this paper, we propose a new approach to solve low-rank tensor completion and robust tensor PCA. Our approach is based on some novel notion of (even-order) tensor ranks, to be called the M-rank, the symmetric M-rank, and the strongly symmetric M-rank. We discuss the connections between these new tensor ranks and the CP-rank and the symmetric CP-rank of an even-order tensor. We show that the M-rank provides a reliable and easy-computable approximation to the CP-rank. As a result, we propose to replace the CP-rank by the M-rank in the low-CP-rank tensor completion and robust tensor PCA. Numerical results suggest that our new approach based on the M-rank outperforms existing methods that are based on low-n-rank, t-SVD and KBR approaches for solving low-rank tensor completion and robust tensor PCA when the underlying tensor has low CP-rank.
• ### On Adaptive Cubic Regularized Newton's Methods for Convex Optimization via Random Sampling(1802.05426)

Feb. 15, 2018 math.OC
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 uniformly or non-uniformly sub-sampling the components of the objective. Based upon sub-sampling, we develop both standard and accelerated adaptive cubic regularization approaches and provide theoretical guarantees on global iteration complexity. We show that the standard and accelerated sub-sampled cubic regularization methods achieve iteration complexity in the order of $O(\epsilon^{-1/2})$ and $O(\epsilon^{-1/3})$ respectively, which match those of the original standard and accelerated cubic regularization methods \cite{Cartis-2012-Evaluation, Jiang-2017-Unified} using the full Hessian information. The performances of the proposed methods on regularized logistic regression problems show a clear effect of acceleration in terms of epochs on several real data sets.
• ### Highly accurate model for prediction of lung nodule malignancy with CT scans(1802.01756)

Feb. 6, 2018 cs.CV, q-bio.QM, stat.ML
Computed tomography (CT) examinations are commonly used to predict lung nodule malignancy in patients, which are shown to improve noninvasive early diagnosis of lung cancer. It remains challenging for computational approaches to achieve performance comparable to experienced radiologists. Here we present NoduleX, a systematic approach to predict lung nodule malignancy from CT data, based on deep learning convolutional neural networks (CNN). For training and validation, we analyze >1000 lung nodules in images from the LIDC/IDRI cohort. All nodules were identified and classified by four experienced thoracic radiologists who participated in the LIDC project. NoduleX achieves high accuracy for nodule malignancy classification, with an AUC of ~0.99. This is commensurate with the analysis of the dataset by experienced radiologists. Our approach, NoduleX, provides an effective framework for highly accurate nodule malignancy prediction with the model trained on a large patient population. Our results are replicable with software available at http://bioinformatics.astate.edu/NoduleX.
• ### Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis(1605.02408)

Jan. 17, 2018 math.OC, cs.LG, stat.ML
Nonconvex and nonsmooth optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology in the sense of scalability. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its convex counterpart. This paper aims to take one step in the direction of disciplined nonconvex and nonsmooth optimization. In particular, we consider in this paper some constrained nonconvex optimization models in block decision variables, with or without coupled affine constraints. In the case of without coupled constraints, we show a sublinear rate of convergence to an $\epsilon$-stationary solution in the form of variational inequality for a generalized conditional gradient method, where the convergence rate is shown to be dependent on the H\"olderian continuity of the gradient of the smooth part of the objective. For the model with coupled affine constraints, we introduce corresponding $\epsilon$-stationarity conditions, and apply two proximal-type variants of the ADMM to solve such a model, assuming the proximal ADMM updates can be implemented for all the block variables except for the last block, for which either a gradient step or a majorization-minimization step is implemented. We show an iteration complexity bound of $O(1/\epsilon^2)$ to reach an $\epsilon$-stationary solution for both algorithms. Moreover, we show that the same iteration complexity of a proximal BCD method follows immediately. Numerical results are provided to illustrate the efficacy of the proposed algorithms for tensor robust PCA.
• ### Global Convergence of Unmodified 3-Block ADMM for a Class of Convex Minimization Problems(1505.04252)

Jan. 17, 2018 math.OC, cs.LG, stat.ML
The alternating direction method of multipliers (ADMM) has been successfully applied to solve structured convex optimization problems due to its superior practical performance. The convergence properties of the 2-block ADMM have been studied extensively in the literature. Specifically, it has been proven that the 2-block ADMM globally converges for any penalty parameter $\gamma>0$. In this sense, the 2-block ADMM allows the parameter to be free, i.e., there is no need to restrict the value for the parameter when implementing this algorithm in order to ensure convergence. However, for the 3-block ADMM, Chen \etal \cite{Chen-admm-failure-2013} recently constructed a counter-example showing that it can diverge if no further condition is imposed. The existing results on studying further sufficient conditions on guaranteeing the convergence of the 3-block ADMM usually require $\gamma$ to be smaller than a certain bound, which is usually either difficult to compute or too small to make it a practical algorithm. In this paper, we show that the 3-block ADMM still globally converges with any penalty parameter $\gamma>0$ if the third function $f_3$ in the objective is smooth and strongly convex, and its condition number is in $[1,1.0798)$, besides some other mild conditions. This requirement covers an important class of problems to be called regularized least squares decomposition (RLSD) in this paper.
• ### A Unified Scheme to Accelerate Adaptive Cubic Regularization and Gradient Methods for Convex Optimization(1710.04788)

Dec. 27, 2017 math.OC
In this paper we propose a unified two-phase scheme for convex optimization to accelerate: (1) the adaptive cubic regularization methods with exact/inexact Hessian matrices, and (2) the adaptive gradient method, without any knowledge of the Lipschitz constants for the gradient or the Hessian. This is achieved by tuning the parameters used in the algorithm $\textit{adaptively}$ in its process of progression, which can be viewed as a relaxation over the existing algorithms in the literature. Under the assumption that the sub-problems can be solved approximately, we establish overall iteration complexity bounds for three newly proposed algorithms to obtain an $\epsilon$-approximate solution. Specifically, we show that the adaptive cubic regularization methods with the exact/inexact Hessian matrix both achieve an iteration complexity in the order of $O\left( 1 / \epsilon^{1/3} \right)$, which matches that of the original accelerated cubic regularization method presented in [Nesterov-2008-Accelerating] assuming the availability of the exact Hessian information and the Lipschitz constants, and that the sub-problems are solved to optimality. Under the same two-phase adaptive acceleration framework, the gradient method achieves an iteration complexity in the order $O\left( 1 / \epsilon^{1/2} \right)$, which is known to be best possible (cf. Nesterov-2013-Introductory). Our numerical experiment results show a clear effect of acceleration displayed in the adaptive Newton method with cubic regularization on a set of regularized logistic regression instances.
• ### Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis(1710.02236)

Oct. 5, 2017 math.OC, stat.ML
In this paper we study nonconvex and nonsmooth multi-block optimization over Riemannian manifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. We develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings. First, we introduce the optimality conditions for the afore-mentioned optimization models. Then, the notion of $\epsilon$-stationary solutions is introduced as a result. The main part of the paper is to show that the proposed algorithms enjoy an iteration complexity of $O(1/\epsilon^2)$ to reach an $\epsilon$-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 $\ell_q$ regularized sparse tensor principal component analysis and the community detection problem. Our preliminary numerical results show great potentials of the proposed methods.
• ### A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection(1708.01072)

Aug. 3, 2017 cs.SI, math.OC
In this paper, we consider the community detection problem under either the stochastic block model (SBM) assumption or the degree-correlated stochastic block model (DCSBM) assumption. The modularity maximization formulation for the community detection problem is NP-hard in general. In this paper, we propose a sparse and low-rank completely positive relaxation for the modularity maximization problem, we then develop an efficient row-by-row (RBR) type block coordinate descent (BCD) algorithm to solve the relaxation and prove an $\mathcal{O}(1/\sqrt{N})$ convergence rate to a stationary point where $N$ is the number of iterations. A fast rounding scheme is constructed to retrieve the community structure from the solution. Non-asymptotic high probability bounds on the misclassification rate are established to justify our approach. We further develop an asynchronous parallel RBR algorithm to speed up the convergence. Extensive numerical experiments on both synthetic and real world networks show that the proposed approach enjoys advantages in both clustering accuracy and numerical efficiency. Our numerical results indicate that the newly proposed method is a quite competitive alternative for community detection on sparse networks with over 50 million nodes.
• ### Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation(1705.09059)

May 25, 2017 math.OC
In this paper, we propose a vector transport-free stochastic variance reduced gradient (SVRG) method with general retraction for empirical risk minimization over Riemannian manifold. Existing SVRG methods on manifold usually consider a specific retraction operation, and involve additional computational costs such as parallel transport or vector transport. The vector transport-free SVRG with general retraction we propose in this paper handles general retraction operations, and do not need additional computational costs mentioned above. As a result, we name our algorithm S-SVRG, where the first "S" means simple. We analyze the iteration complexity of S-SVRG for obtaining an $\epsilon$-stationary point and its local linear convergence by assuming the \L ojasiewicz inequality, which naturally holds for PCA and holds with high probability for matrix completion problem. We also incorporate the Barzilai-Borwein step size and design a very practical S-SVRG-BB method. Numerical results on PCA and matrix completion problems are reported to demonstrate the efficiency of our methods.
• ### Accelerated Primal-Dual Proximal Block Coordinate Updating Methods for Constrained Convex Optimization(1702.05423)

Feb. 17, 2017 cs.NA, math.OC, stat.ML
Block Coordinate Update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primal-dual BCU method for solving linearly constrained convex program in multi-block variables. The method is an accelerated version of a primal-dual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an $O(1/t)$ convergence rate under weak convexity assumption. We show that the rate can be accelerated to $O(1/t^2)$ if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can be modified to achieve a linear rate of convergence. The numerical experiments show that the accelerated method performs stably with a single set of parameters while the original method needs to tune the parameters for different datasets in order to achieve a comparable level of performance.
• ### Randomized Primal-Dual Proximal Block Coordinate Updates(1605.05969)

Jan. 24, 2017 math.NA, math.OC, stat.ML
In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility measure. The framework includes several existing algorithms as special cases such as a primal-dual method for bilinear saddle-point problems (PD-S), the proximal Jacobian ADMM (Prox-JADMM) and a randomized variant of the ADMM method for multi-block convex optimization. Our analysis recovers and/or strengthens the convergence properties of several existing algorithms. For example, for PD-S our result leads to the same order of convergence rate without the previously assumed boundedness condition on the constraint sets, and for Prox-JADMM the new result provides convergence rate in terms of the objective value and the feasibility violation. It is well known that the original ADMM may fail to converge when the number of blocks exceeds two. Our result shows that if an appropriate randomization procedure is invoked to select the updating blocks, then a sublinear rate of convergence in expectation can be guaranteed for multi-block ADMM, without assuming any strong convexity. The new approach is also extended to solve problems where only a stochastic approximation of the (sub-)gradient of the objective is available, and we establish an $O(1/\sqrt{t})$ convergence rate of the extended approach for solving stochastic programming.
• ### Tensor and Its Tucker Core: the Invariance Relationships(1601.01469)

Nov. 6, 2016 cs.NA, math.OC
In [13], Hillar and Lim famously demonstrated that "multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard". Despite many recent advancements, the state-of-the-art methods for computing such `tensor analogues' still suffer severely from the curse of dimensionality. In this paper we show that the Tucker core of a tensor however, retains many properties of the original tensor, including the CP rank, the border rank, the tensor Schatten quasi norms, and the Z-eigenvalues. When the core tensor is smaller than the original tensor, this property leads to considerable computational advantages as confirmed by our numerical experiments. In our analysis, we in fact work with a generalized Tucker-like decomposition that can accommodate any full column-rank factor matrices.
• ### Characterizing Real-Valued Multivariate Complex Polynomials and Their Symmetric Tensor Representations(1501.01058)

Feb. 21, 2016 math.OC
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's theorem. We show that a similar result holds in the complex case as well.
• ### On the Sublinear Convergence Rate of Multi-Block ADMM(1408.4265)

July 9, 2015 math.OC
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.
• ### An Extragradient-Based Alternating Direction Method for Convex Minimization(1301.6308)

July 9, 2015 math.OC, stat.ML
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 $\epsilon$-optimal solution within $O(1/\epsilon)$ 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.
• ### On the Global Linear Convergence of the ADMM with Multi-Block Variables(1408.4266)

May 24, 2015 math.OC
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.
• ### Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity(1504.03087)

May 19, 2015 math.OC
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 $\epsilon$-optimal solution within $O(1/\epsilon^2)$ iterations by solving an associated perturbation to the original problem; (2) the multi-block ADMM returns an $\epsilon$-optimal solution within $O(1/\epsilon)$ 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.
• ### Local Linear Convergence of ISTA and FISTA on the LASSO Problem(1501.02888)

Jan. 13, 2015 math.OC
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.
• ### Iteration Bounds for Finding the $\epsilon$-Stationary Points for Structured Nonconvex Optimization(1410.4066)

Oct. 15, 2014 math.OC
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 $\epsilon$-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^\delta$ where $\delta=p/q$ with $1/p+1/q=1$, then we prove that the new algorithms have an overall iteration complexity bound of $O(1/\epsilon^q)$ in finding an $\epsilon$-stationary solution. If $f$ is concave then the iteration complexity reduces to $O(1/\epsilon)$. Our numerical experiments for tensor approximation problems show promising performances of the new solution algorithms.
• ### A Smoothing SQP Framework for a Class of Composite $L_q$ Minimization over Polyhedron(1407.7205)

July 27, 2014 math.OC
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 $\epsilon$-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.
• ### Tensor Principal Component Analysis via Convex Optimization(1212.2702)

Nov. 16, 2013 math.OC
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.
• ### Semidefnite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization(math/0701070)

Jan. 2, 2007 math.NA, math.OC
In this paper we study the relationship between the optimal value of a homogeneous quadratic optimization problem and that of its Semidefinite Programming (SDP) relaxation. We consider two quadratic optimization models: (1) $\min \{x^* C x \mid x^* A_k x \ge 1, x\in\mathbb{F}^n, k=0,1,...,m\}$; and (2) $\max \{x^* C x \mid x^* A_k x \le 1, x\in\mathbb{F}^n, k=0,1,...,m\}$. If \emph{one} of $A_k$'s is indefinite while others and $C$ are positive semidefinite, we prove that the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by $O(m^2)$ when $\mathbb{F}$ is the real line $\mathbb{R}$, and by $O(m)$ when $\mathbb{F}$ is the complex plane $\mathbb{C}$. This result is an extension of the recent work of Luo {\em et al.} \cite{LSTZ}. For (2), we show that the same ratio is bounded from below by $O(1/\log m)$ for both the real and complex case, whenever all but one of $A_k$'s are positive semidefinite while $C$ can be indefinite. This result improves the so-called approximate S-Lemma of Ben-Tal {\em et al.} \cite{BNR02}. We also consider (2) with multiple indefinite quadratic constraints and derive a general bound in terms of the problem data and the SDP solution. Throughout the paper, we present examples showing that all of our results are essentially tight.