Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity

Many recent applications in machine learning and data fitting call for the algorithmic solution of structured smooth convex optimization problems. Although the gradient descent method is a natural choice for this task, it requires exact gradient computations and hence can be inefficient when the problem size is large or the gradient is difficult to evaluate. Therefore, there has been much interest in inexact gradient methods (IGMs), in which an efficiently computable approximate gradient is used to perform the update in each iteration. Currently, non-asymptotic linear convergence results for IGMs are typically established under the assumption that the objective function is strongly convex, which is not satisfied in many applications of interest; while linear convergence results that do not require the strong convexity assumption are usually asymptotic in nature. In this paper, we combine the best of these two types of results by developing a framework for analysing the non-asymptotic convergence rates of IGMs when they are applied to a class of structured convex optimization problems that includes least squares regression and logistic regression. We then demonstrate the power of our framework by proving, in a unified manner, new linear convergence results for three recently proposed algorithms—the incremental gradient method with increasing sample size [R.H. Byrd, G.M. Chin, J. Nocedal, and Y. Wu, Sample size selection in optimization methods for machine learning, Math. Program. Ser. B 134 (2012), pp. 127–155; M.P. Friedlander and M. Schmidt, Hybrid deterministic–stochastic methods for data fitting, SIAM J. Sci. Comput. 34 (2012), pp. A1380–A1405], the stochastic variance-reduced gradient (SVRG) method [R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, Advances in Neural Information Processing Systems 26: Proceedings of the 2013 Conference, 2013, pp. 315–323], and the incremental aggregated gradient (IAG) method [D. Blatt, A.O. Hero, and H. Gauchman, A convergent incremental gradient method with a constant step size, SIAM J. Optim. 18 (2007), pp. 29–51]. We believe that our techniques will find further applications in the non-asymptotic convergence analysis of other first-order methods.     

Fast multilevel augmentation method for nonlinear integral equations

In this study, we extend the multilevel augmentation method for Hammerstein equations established in Chen et al. [Fast multilevel augmentation methods for solving Hammerstein equations, SIAM J. Numer. Anal. 47 (2009), pp. 2321–2346] to solve nonlinear Urysohn integral equations. Under certain differentiability assumptions on the kernel function, we show that the method enjoys the optimal convergence order and linear computational complexity. Finally, numerical experiments are presented to confirm the theoretical results and illustrate the efficiency of the method.     

A wavelet Petrov–Galerkin method for solving integro-differential equations

In this paper, we solve integro-differential equation by using the Alpert multiwavelets as basis functions. We also use the orthogonality of the basis of the trial and test spaces in the Petrov–Galerkin method. The computations are reduced because of orthogonality. Thus the final system that we get from discretizing the integro-differential equation has a very small dimension and enough accuracy. We compare the results with [M. Lakestani, M. Razzaghi, and M. Dehghan, Semiorthogonal spline wavelets approximation for Fredholm integro-differential equations, Math. Probl. Eng. 2006 (2006), pp. 1–12, Article ID 96184] and [A. Ayad, Spline approximation for first-order Fredholm integro-differential equation, Stud. Univ. Babes-Bolyai. Math., 41(3), (1996), pp. 1–8] which used a much larger dimension system and got less accurate results. In [Z. Chen and Y. Xu, The Petrov–Galerkin and iterated Petrov–Galerkin methods for second kind integral equations, SIAM J. Numer. Anal. 35(1) (1998), pp. 406–434], convergence of Petrov–Galerkin method has been discussed with some restrictions on degrees of chosen polynomial basis, but in this paper convergence is obtained for every degree.     

Convergence analysis of the two-stage¶multisplitting method

An example is given which shows that the asymptotic convergence rate of the two-stage multisplitting method (see D.B. Szyld and M.T. Jones, SIAM J. Matrix Anal. Appl. 13, 671–679 (1992)) with one inner iteration is, generally, either faster or slower than that with many inner iterations. When the coefficient matrix is an H-matrix and a monotone matrix, respectively, we formulate the convergence as well as the monotone convergence theories for this two-stage multisplitting method under suitable constraints on the two-stage multisplitting. Furthermore, the corresponding comparison theorem in the sense of monotonicity for this method is established and several concrete applications are discussed. Received: April 1996 / Accepted: April 1998     

Maximal solution to algebraic Riccati equations linked to infinite Markov jump linear systems

In this paper, we deal with a perturbed algebraic Riccati equation in an infinite dimensional Banach space. Besides the interest in its own right, this class of equations appears, for instance, in the optimal control problem for infinite Markov jump linear systems (from now on iMJLS). Here, infinite or finite has to do with the state space of the Markov chain being infinite countable or finite (see Fragoso and Baczynski in SIAM J Control Optim 40(1):270–297, 2001). By using a certain concept of stochastic stability (a sort of L ₂-stability), we prove the existence (and uniqueness) of maximal solution for this class of equation and provide a tool to compute this solution recursively, based on an initial stabilizing controller. When we recast the problem in the finite setting (finite state space of the Markov chain), we recover the result of de Souza and Fragoso (Syst Control Lett 14:233–239, 1999) set to the Markovian jump scenario, now free from an inconvenient technical hypothesis used there, originally introduced in Wonham in (SIAM J Control 6(4):681–697). Research supported by grants CNPq 520367-97-9, 300662/2003-3 and 474653/2003-0, FAPERJ 171384/2002, PRONEX and IM-AGIMB.     

An Efficient NRxx?Method for Boltzmann-BGK Equation

In Cai and Li (SIAM J. Sci. Comput. 32(5):2875–2907, 2010), we proposed a numerical regularized moment method of arbitrary order (abbreviated as NRxx method) for Boltzmann-BGK equation, which makes numerical simulation using very large number of moments possible. In this paper, we are further exploring the efficiency of the NRxx method with techniques including the 2nd order HLL flux with linear reconstruction to improve spatial accuracy, the RKC schemes to relieve the time step length constraint by the regularization terms, and the revised Strang splitting to calculate convective and diffusive terms only once without loss of accuracy. It is validated by the numerical results that the overall efficiency is significantly improved and the convergence order is kept well.     

A Full Curvature Based Algorithm for Image Registration

Image registration, i.e., finding an optimal displacement field u which minimizes a distance functional D(u) is known to be an ill-posed problem. In this paper a novel variational image registration method is presented, which matches two images acquired from the same or from different medical imaging modalities. The approach proposed here is also independent of the image dimension. The proposed variational penalty against oscillations in the solutions is the standard H²(Ω) Sobolev semi-inner product for each component of the displacement. We investigate the associated Euler-Lagrange equation of the energy functional. Furthermore, we approach the solution of the underlying system of biharmonic differential equations with higher order boundary conditions as the steady-state solution of a parabolic partial differential equation (PDE). One of the important aspects of this approach is that the kernel of the Euler-Lagrange equation is spanned by all rigid motions. Hence, the presented approach includes a rigid alignment. Experimental results on both synthetic and real images are presented to illustrate the capabilities of the proposed approach. Stefan Henn obtained his diploma (1997) and his Ph.D. in mathematics (2001), both from the Heinrich-Heine University (HHU) of Düsseldorf (Germany). From 1997–1999 he had a researcher position at the Institute for Brain Research at the HHU Düsseldorf. Since 1999 he is a research assistant at the Institute of Mathematics at the HHU Düsseldorf. He received the SIAM outstanding paper prize in 2003 for the paper (Iterative Multigrid Regularization Techniques for Image Matching, SIAM Journal on Scientific Computing, 23(4), pp. 1077-1093). His research interests include Multiscale methods in Scientific Computing and Image Processing, nonlinear large-scale optimization, and numerical analysis of partial differential equations.     

A Comparison of Iterated Optimal Stopping and Local Policy Iteration for American Options Under Regime Switching

A theoretical analysis tool, iterated optimal stopping, has been used as the basis of a numerical algorithm for American options under regime switching (Le and Wang in SIAM J Control Optim 48(8):5193–5213, 2010). Similar methods have also been proposed for American options under jump diffusion (Bayraktar and Xing in Math Methods Oper Res 70:505–525, 2009) and Asian options under jump diffusion (Bayraktar and Xing in Math Fin 21(1):117–143, 2011). An alternative method, local policy iteration, has been suggested in Huang et al. (SIAM J Sci Comput 33(5):2144–2168, 2011), and Salmi and Toivanen (Appl Numer Math 61:821–831, 2011). Worst case upper bounds on the convergence rates of these two methods suggest that local policy iteration should be preferred over iterated optimal stopping (Huang et al. in SIAM J Sci Comput 33(5):2144–2168, 2011). In this article, numerical tests are presented which indicate that the observed performance of these two methods is consistent with the worst case upper bounds. In addition, while these two methods seem quite different, we show that either one can be converted into the other by a simple rearrangement of two loops.     

Permutation Betting Markets: Singleton Betting with Extra Information

We study permutation betting markets, introduced by Chen et al. (Proceedings of the ACM Conference on Electronic Commerce, 2007). For these markets, we consider subset bettings in which each trader can bet on a subset of candidates ending up in a subset of positions. We consider the revenue maximization problem for the auctioneer in two main frameworks: the risk-free revenue maximization (studied in Chen et al., Proceedings of the ACM Conference on Electronic Commerce, 2007), and the probabilistic revenue maximization. We also explore the use of some certain knowledge or extra information about the possible outcomes of the market. We first show that finding the optimal revenue in the risk-free model for the subset betting problem is inapproximable. This resolves an open question posed by Chen et al. (Proceedings of the ACM Conference on Electronic Commerce, 2007). In order to identify solvable variants of the problem, we propose the singleton betting language which allows traders to bet an arbitrary value on one candidate for one position. For singleton bettings, we first provide a linear-time implementable necessary and sufficient condition for existence of a solution with positive revenue for any possible outcome. Furthermore, we develop an LP-based polynomial-time algorithm to find the optimum solution of this problem. In addition, we show how to extend this LP-based method to handle some extra information about the possible outcomes. Finally, we consider the revenue maximization problem in a probabilistic setting. For this variant, we observe that the problem of maximizing the expected revenue is polynomial-time solvable, but we show that maximizing the probability of achieving a pre-specified revenue is #P-Complete.     

Two-parameter generalized Hermitian and skew-Hermitian splitting iteration method

It is known that the Hermitian and skew-Hermitian splitting (HSS) iteration method is an efficient solver for non-Hermitian positive-definite linear system of equations. Benzi [A generalization of the Hermitian and skew-Hermitian splitting iteration, SIAM J. Matrix Anal. Appl. 31 (2009), pp. 360–374] proposed a generalized HSS (GHSS) iteration method. In this paper, we present a two-parameter version of the GHSS (TGHSS) method and investigate its convergence properties. To show the effectiveness of the proposed method the TGHSS iteration method is applied to image restoration and convection–diffusion problems and the results are compared with those of the HSS and GHSS methods.     

Adjoint Recovery of Superconvergent Linear Functionals from Galerkin Approximations. The One-dimensional Case

In this paper, we extend the adjoint error correction of Pierce and Giles (SIAM Rev. 42, 247–264 (2000)) for obtaining superconvergent approximations of functionals to Galerkin methods. We illustrate the technique in the framework of discontinuous Galerkin methods for ordinary differential and convection–diffusion equations in one space dimension. It is well known that approximations to linear functionals obtained by discontinuous Galerkin methods with polynomials of degree k can be proven to converge with order 2k + 1 and 2k for ordinary differential and convection–diffusion equations, respectively. In contrast, the order of convergence of the adjoint error correction method can be proven to be 4k + 1 and 4k, respectively. Since both approaches have a computational complexity of the same order, the adjoint error correction method is clearly a competitive alternative. Numerical results which confirm the theoretical predictions are presented.     

Descent three-term conjugate gradient methods based on secant conditions for unconstrained optimization

The conjugate gradient method is an effective method for large-scale unconstrained optimization problems. Recent research has proposed conjugate gradient methods based on secant conditions to establish fast convergence of the methods. However, these methods do not always generate a descent search direction. In contrast, Y. Narushima, H. Yabe, and J.A. Ford [A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM J. Optim. 21 (2011), pp. 212–230] proposed a three-term conjugate gradient method which always satisfies the sufficient descent condition. This paper makes use of both ideas to propose descent three-term conjugate gradient methods based on particular secant conditions, and then shows their global convergence properties. Finally, numerical results are given.     

Solving inverse eigenvalue problems by a projected Newton method

The inverse eigenvalue problem for symmetric matrices (IEP) can be formulated as a system of two matrix equations. For solving the system a variation of Newton's method is used which has been proposed by Fusco and Zecca [Calcolo XXIII (1986), pp. 285–303] for the simultaneous computation of eigenvalues and eigenvectors of a given symmetric matrix. An iteration step of this method consists of a Newton step followed by an orthonormalization with the consequence that each iterate satisfies one of the given equations. The method is proved to convergence locally quadratically to regular solutions. The algorithm and some numerical examples are presented. In addition, it is shown that the so-called Method III proposed by Friedland, Nocedal, and Overton [SIAM J. Numer. Anal., 24 (1987), pp. 634–667] for solving IEP may be constructed similarly to the method presented here.     

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes unique. The Isolation Lemma as described in Mulmuley et al. (Combinatorica 7(1):105–131, 1987) achieves the same for general graphs using randomness, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the perfect matching problem in bipartite planar graphs to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a highly parallel SPL\mathsf{SPL} algorithm for both decision and construction versions of the bipartite perfect matching problem. This improves the earlier known bounds of non-uniform SPL\mathsf{SPL} by Allender et al. (J. Comput. Syst. Sci. 59(2):164–181, 1999) and NC\mathsf{NC} ² by Miller and Naor (SIAM J. Comput. 24:1002–1017, 1995), and by Mahajan and Varadarajan (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), pp. 351–357, 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Further we try to find the lower bound on the number of bits needed for deterministically isolating a perfect matching. We show that our particular method for isolation will require Ω(log n) bits. Our techniques are elementary.     

Tree Rerooting in Distributed Garbage Collection: Implementation and Performance Evaluation

We have recently defined a new algorithm for distributed garbage collection based on reference-counting (Luc Moreau, in Proceedings of the Third International Conference of Functional Programming (ICFP'98), Sept. 1998, pp. 204–215; Luc Moreau and J. Duprat, Technical Report RR1999-18, Ecole Normale Supérieure, Lyon, March 1999). At the heart of the algorithm, we find tree rerooting, a mechanism able to reduce third-party dependencies by reorganising diffusion trees. In reality, the algorithm describes a spectrum of algorithms according to the policy used to manage messages. In this paper, we present the implementation of the algorithm and evaluate its performance. We have implemented two policies, which are extremes of the spectrum, respectively using and not using tree rerooting. In addition, two different strategies for managing action queues have been implemented. The conclusions of our experimentations are the following. Tree rerooting offers more parallelism during distributed GC activity; we explain this phenomenon by the length reduction of causality chains in the distributed GC. Grouping messages per destination dramatically reduces the number of messages, but requires a more complex implementation as messages have to be sorted per destination. Speed up of 100% has been observed on some benchmarks.     

Ordering strategies and related techniques to overcome the trade-off between parallelism and convergence in incomplete factorizations

This paper is concerned with the parallel implementation of the incomplete factorization preconditioned iterative method. Although the use of such parallel ordering as multicolor ordering may increase parallelism in factorization, it often slows convergence when used in the preconditioned method, and thus may offset the gain in speed obtained with parallelization. Further, the higher the parallelism of an ordering, the slower the convergence; the lower the parallelism, the faster the convergence. This well-known trade-off between parallelism and convergence is well explained by the property of compatibility, the level of which can be clearly seen when ordering is presented in graph form (S. Doi, A. Lichnewsky, A graph-theory approach for analyzing the effects of ordering on ILU preconditioning, INRIA report 1452, 1991). In any given method, the fewer the incompatible local graphs in an ordering (i.e., the lower the parallelism), the faster the convergence (S. Doi, Appl. Numer. Math. 7 (1991) 417–436; S. Doi, in: T. Nodera (Ed.), Advances in Numerical Methods for Large Sparse Sets of Linear Systems, 7 Keio University, 1991). An ordering with no incompatible local graphs, for example, such as that implemented on vector multiprocessors by using the nested dissection technique, will have excellent convergence, but its parallelism will be limited (S. Doi, A. Lichnewsky, Int. J. High Speed Comput. 2 (1990) 143–179). To attain a better balance, a certain degree of incompatibility is necessary. In this regard, increasing the number of colors in multicolor ordering can be a useful approach (S. Fujino, S. Doi, in: R. Beauwens (Ed.), Proceeding of the IMACS Internation Symposium on Iterative Methods in Linear Algebra, March 1991; S. Doi, A. Hoshi, Int. J. Comput. Meth. 44 (1992) 143–152). Two related techniques also presented here are the overlapped multicolor ordering (T. Washio, K. Hayami, SIAM J. Sci. Comput. 16 (1995) 631–650), and a fill-in strategy selectively applied to incompatible local graphs. Experiments conducted with an SX-5/16A vector parallel supercomputer show the relative effectiveness of increasing the number of colors and also of using this approach in combination with overlapping and with fill-ins.     

On truthfulness and approximation for scheduling selfish tasks

We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish agent. This is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404–413, 1999) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345–357, 2004) in which the agents cannot choose the machine on which their tasks will be executed. This is done by a centralized authority, the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm, the PTAS of Graham (SIAM J. Appl. Math. 17(2):416–429, 1969) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1+ε)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with the classical result of Shmoys et al. (SIAM J. Comput. 24(6):1313–1331, 1995), we obtain a randomized 2r(1+ε)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1+ε)-algorithm for the off-line case with related machines.     

Mining non-derivable hypercliques

A hyperclique (Xiong et al. in Proceedings of the IEEE international conference on data mining, pp 387–394, 2003) is an itemset containing items that are strongly correlated with each other, based on a user-specified threshold. Hypercliques (HCs) have been successfully used in a number of applications, for example, clustering (Xiong et al. in Proceedings of the 4th SIAM international conference on data mining, pp 279–290, 2004) and noise removal (Xiong et al. in IEEE Trans Knowl Data Eng 18(3):304–319, 2006). Even though HC has been shown to respond well to datasets with skewed support distribution and low support threshold, it may still grow very large for dense datasets and lower h-confidence threshold. In this paper, we propose a new pruning method based on combining HCs and non-derivable itemsets (NDIs) (Calders and Goethals in Proceedings of the PKDD international conference on principles of data mining and knowledge discovery, pp 74–85, 2002) in order to substantially reduce the amount of generated HCs. Specifically, we propose a new collection of HCs, called non-derivable hypercliques (NDHCs). The NDHC collection is a lossless representation of HCs, that is, given the itemsets in NDHCs, we can generate the complete HC collection and their support, without additional scanning of the dataset. We present an efficient algorithm to mine all NDHC sets, NDHCMiner, and an algorithm to derive all HC sets and their support from NDHCs, NDHCDeriveAll. We experimentally compare our collection, NDHC with HC, with respect to runtime performance as well as total number of generated sets, using real and artificial data. We also show comparisons with another condensed representation of HCs, maximal hyperclique patterns (MHPs). Our experiments show that the NDHC collection offers substantial advantages over HCs, and even MHPs, especially for dense datasets and lower h-confidence values.     

Restarted GMRES augmented with harmonic Ritz vectors for shifted linear systems

Frommer and Glassner [Frommer, A. and Glassner, U., 1998, Restarted GMRES for shifted linear systems, SIAM Journal on Scientific Computing, 19, 15–26.] develop a variant of the restarted GMRES method for shifted linear systems at the expense of only one matrix–vector multiplication per iteration. However, restarting slows down the convergence, even stagnation. We present a variant of the restarted GMRES augmented with some approximate eigenvectors for the shifted systems. The convergence can be much faster at little extra expense. Numerical experiments show its efficiency.