Search

It has been shown in (14) that the accelerated prox-level (APL) method and its variant, the uniform smoothing level (USL) method, have optimal iteration complexity for solving black-box and structured convex programming problems without requiring the input of any smoothness information. However, these algorithms require the assumption on the boundedness of the feasible set and their eciency relies on the solutions of two involved subproblems. These hindered the applicability of these algorithms in solving large-scale and unconstrained optimization problems. In this paper, we rst present a generic algorithmic framework to extend these uniformly optimal level methods for solving unconstrained problems. Moreover, we introduce two new variants of level methods, i.e., the fast APL (FAPL) method and the fast USL (FUSL) method, for solving large scale black-box and structured convex programming problems respectively. Both FAPL and FUSL enjoy the same optimal iteration complexity as APL and USL, while the number of subproblems in each iteration is reduced from two to one. Moreover, we present an exact method to solve the only subproblem for these algorithms. As a result, the proposed FAPL and FUSL methods have improved the performance of the APL and USL in practice signicantly in terms of both computational time and solution quality. Our numerical results on solving some large-scale least square problems and total variation based image reconstruction have shown great advantages of these new bundle-level type methods over APL, USL, and some other state-of-the-art rst-order methods.

In cluster-specific studies, ordinary logistic regression and conditional logistic regression for binary outcomes provide maximum likelihood estimator (MLE) and conditional maximum likelihood estimator (CMLE), respectively. In this paper, we show that CMLE is approaching to MLE asymptotically when each individual data point is replicated infinitely many times. Our theoretical derivation is based on the observation that a term appearing in the conditional average log-likelihood function is the coefficient of a polynomial, and hence can be transformed to a complex integral by Cauchy's differentiation formula. The asymptotic analysis of the complex integral can then be performed using the classical method of steepest descent. Our result implies that CMLE can be biased if individual weights are multiplied with a constant, and that we should be cautious when assigning weights to cluster-specific studies.

In this paper, we incorporate importance sampling strategy into accelerated framework of stochastic alternating direction method of multipliers for solving a class of stochastic composite problems with linear equality constraint. The rates of convergence for primal residual and feasibility violation are established. Moreover, the estimation of variance of stochastic gradient is improved due to the use of important sampling. The proposed algorithm is capable of dealing with the situation, where the feasible set is unbounded. The experimental results indicate the effectiveness of the proposed method.

This paper develops two accelerated Bregman Operator Splitting (BOS) algorithms with backtracking for solving regularized large-scale linear inverse problems, where the regularization term may not be smooth. The first algorithm improves the rate of convergence for BOSVS [ 5 ] in terms of the smooth component in the objective function by incorporating Nesterov's multi-step acceleration scheme under the assumption that the feasible set is bounded. The second algorithm is capable of dealing with the case where the feasible set is unbounded. Moreover, it allows more aggressive stepsize than that in the first scheme by properly selecting the penalty parameter and jointly updating the acceleration parameter and stepsize. Both algorithms exhibit better practical performance than BOSVS and AADMM [ 21 ], while preserve the same accelerated rate of convergence as that for AADMM. The numerical results on total-variation based image reconstruction problems indicate the effectiveness of the proposed algorithms.

We present in this paper some worst-case datasets of deterministic first-order methods for solving large-scale binary logistic regression problems. Under the assumption that the number of algorithm iterations is much smaller than the problem dimension, with our worst-case datasets it requires at least \begin{document}$ {{{\mathcal O}}}(1/\sqrt{\varepsilon}) $\end{document} first-order oracle inquiries to compute an \begin{document}$ \varepsilon $\end{document} -approximate solution. From traditional iteration complexity analysis point of view, the binary logistic regression loss functions with our worst-case datasets are new worst-case function instances among the class of smooth convex optimization problems.

On solving a convex-concave bilinear saddle-point problem (SPP), there have been many works studying the complexity results of first-order methods. These results are all about upper complexity bounds, which can determine at most how many efforts would guarantee a solution of desired accuracy. In this paper, we pursue the opposite direction by deriving lower complexity bounds of first-order methods on large-scale SPPs. Our results apply to the methods whose iterates are in the linear span of past first-order information, as well as more general methods that produce their iterates in an arbitrary manner based on first-order information. We first work on the affinely constrained smooth convex optimization that is a special case of SPP. Different from gradient method on unconstrained problems, we show that first-order methods on affinely constrained problems generally cannot be accelerated from the known convergence rate $O(1/t)$ to $O(1/t^2)$, and in addition, $O(1/t)$ is optimal for convex problems. Moreover, we prove that for strongly convex problems, $O(1/t^2)$ is the best possible convergence rate, while it is known that gradient methods can have linear convergence on unconstrained problems. Then we extend these results to general SPPs. It turns out that our lower complexity bounds match with several established upper complexity bounds in the literature, and thus they are tight and indicate the optimality of several existing first-order methods., Comment: submitted for publication

We introduce a variational model and a numerical method for simultaneous ODF smoothing and reconstruction. The model uses the sparsity of MR images in finite difference domain and wavelet domain as the spatial regularization means in ODF's reconstruction. The model also incorporates angular regularization using Laplace-Beltrami operator on the unit sphere. A primal-dual scheme is applied to solve the model efficiently. The experimental results indicate that with spatial and angular regularization in the process of reconstruction, we can get better directional structures of reconstructed ODFs.

Our main goal in this paper is to show that one can skip gradient computations for gradient descent type methods applied to certain structured convex programming (CP) problems. To this end, we first present an accelerated gradient sliding (AGS) method for minimizing the summation of two smooth convex functions with different Lipschitz constants. We show that the AGS method can skip the gradient computation for one of these smooth components without slowing down the overall optimal rate of convergence. This result is much sharper than the classic black-box CP complexity results especially when the difference between the two Lipschitz constants associated with these components is large. We then consider an important class of bilinear saddle point problem whose objective function is given by the summation of a smooth component and a nonsmooth one with a bilinear saddle point structure. Using the aforementioned AGS method for smooth composite optimization and Nesterov's smoothing technique, we show that one only needs ${\cal O}(1/\sqrt{\epsilon})$ gradient computations for the smooth component while still preserving the optimal ${\cal O}(1/\epsilon)$ overall iteration complexity for solving these saddle point problems. We demonstrate that even more significant savings on gradient computations can be obtained for strongly convex smooth and bilinear saddle point problems., Comment: 26 pages, 1 figure

This study provides a link between a de novo gene and novel phenotype in wheat-rye hybrids that can be used as a model for induced de novo genetic variation. Wide hybridization can produce de novo DNA variation that may cause novel phenotypes. However, there is still a lack of specific links between changed genes and novel phenotypes in wide hybrids. The well-studied high-molecular-weight glutenin subunit (HMW-GS) genes in tribe Triticeae provide a useful model for addressing this issue. In this study, we investigated the feasibility of a wheat-rye hybridization method for inducing de novo phenotypes using the Glu-1Dx2.2 subunit as an example. We developed three hexaploid wheat lines with normal fertility and a Glu-1Dx2.2 variant, named Glu-1Dx2.2 (v) , derived from three F-1 hybrids. The wild-type Glu-1Dx2.2 has two direct repeats of 295 bp length separated by an intervening 101 bp in its central repetitive region. In the mutant Glu-1Dx2.2 (v) , one copy of the repeats and the intervening sequence were deleted, probably through homology-dependent illegitimate recombination (IR). This study provides a direct link between a de novo allele and novel phenotype. Our results indicate that the wheat-rye method may be a useful tool to induce de novo genetic variations that broaden the genetic diversity for wheat improvement.

We propose a novel stochastic method, namely the stochastic accelerated mirror-prox (SAMP) method, for solving a class of monotone stochastic variational inequalities (SVI). The main idea of the proposed algorithm is to incorporate a multi-step acceleration scheme into the stochastic mirror-prox method. The developed SAMP method computes weak solutions with the optimal iteration complexity for SVIs. In particular, if the operator in SVI consists of the stochastic gradient of a smooth function, the iteration complexity of the SAMP method can be accelerated in terms of their dependence on the Lipschitz constant of the smooth function. For SVIs with bounded feasible sets, the bound of the iteration complexity of the SAMP method depends on the diameter of the feasible set. For unbounded SVIs, we adopt the modified gap function introduced by Monteiro and Svaiter for solving monotone inclusion, and show that the iteration complexity of the SAMP method depends on the distance from the initial point to the set of strong solutions. It is worth noting that our study also significantly improves a few existing complexity results for solving deterministic variational inequality problems. We demonstrate the advantages of the SAMP method over some existing algorithms through our preliminary numerical experiments.

We propose a model for simultaneous Orientation Distribution Function (ODF) reconstruction and regularisation. The ODFs are represented by real spherical harmonic functions, and we propose to solve the spherical harmonic coefficients of the ODFs, with spatial regularisation by minimising the Vectorial Total Variation (VTV) of the coefficients. The proposed model also incorporates angular regularisation of the ODFs using Laplace-Beltrami operator on the unit sphere. A modified primal-dual hybrid gradient algorithm is applied to solve the model efficiently. The experimental results indicate better directional structures of reconstructed ODFs.

We present a novel framework, namely, accelerated alternating direction method of multipliers (AADMM), for acceleration of linearized ADMM. The basic idea of AADMM is to incorporate a multistep acceleration scheme into linearized ADMM. We demonstrate that for solving a class of convex composite optimization with linear constraints, the rate of convergence of AADMM is better than that of linearized ADMM, in terms of their dependence on the Lipschitz constant of the smooth component. Moreover, AADMM is capable of dealing with the situation when the feasible region is unbounded, as long as the corresponding saddle point problem has a solution. A backtracking algorithm is also proposed for practical performance.

We develop a variational model and a faster and robust numerical algorithm for simultaneous sensitivity map estimation and image reconstruction in partially parallel MR imaging with significantly under-sampled data. The proposed model uses a maximum likelihood approach to minimizing the residue of data fitting in the presence of independent Gaussian noise. The usage of maximum likelihood estimation dramatically reduces the sensitivity to the selection of model parameter, and increases the accuracy and robustness of the algorithm. Moreover, variable splitting based on the specific structure of the objective function, and alternating direction method of multipliers (ADMM) are used to accelerate the computation. The preliminary results indicate that the proposed method resulted in fast and robust reconstruction.

We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPP). The basic idea of this algorithm is to incorporate a multi-step acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence as Nesterov's smoothing technique. Our stochastic APD method exhibits an optimal rate of convergence for stochastic SPP not only in terms of its dependence on the number of the iteration, but also on a variety of problem parameters. To the best of our knowledge, this is the first time that such an optimal algorithm has been developed for stochastic SPP in the literature. Furthermore, for both deterministic and stochastic SPP, the developed APD algorithms can deal with the situation when the feasible region is unbounded, as long as a saddle point exists. In the unbounded case, we incorporate the modified termination criterion introduced by Monteiro and Svaiter in solving SPP problem posed as monotone inclusion, and demonstrate that the rate of convergence of the APD method depends on the distance from the initial point to the set of optimal solutions.