322,892 research outputs found
The Variable Metric Forward-Backward Splitting Algorithm Under Mild Differentiability Assumptions
No full textWe study the variable metric forward-backward splitting algorithm for convex minimization problems without the standard assumption of the Lipschitz continuity of the gradient. In this setting, we prove that, by requiring only mild assumptions on the smooth part of the objective function and using several types of line search procedures for determining either the gradient descent stepsizes or the relaxation parameters, one still obtains weak convergence of the iterates and convergence in the objective function values. Moreover, the o(1/k) convergence rate in the function values is obtained if slightly stronger differentiability assumptions are added. We also illustrate several applications including problems that involve Banach spaces and functions of divergence type
Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis
No full textWe study the block-coordinate forward-backward algorithm in which the blocks are updated in a random and possibly parallel manner, according to arbitrary probabilities. The algorithm allows different stepsizes along the block-coordinates to fully exploit the smoothness properties of the objective function. In the convex case and in an infinite dimensional setting, we establish almost sure weak convergence of the iterates and the asymptotic rate o(1/n) for the mean of the function values. We derive linear rates under strong convexity and error bound conditions. Our analysis is based on an abstract convergence principle for stochastic descent algorithms which allows to extend and simplify existing results
Generalized support vector regression: duality and tensor-kernel representation
No full textIn this paper, we study the variational problem associated to support vector regression in Banach function spaces. Using the Fenchel–Rockafellar duality theory, we give an explicit formulation of the dual problem as well as of the related optimality conditions. Moreover, we provide a new computational framework for solving the problem which relies on a tensor-kernel representation. This analysis overcomes the typical difficulties connected to learning in Banach spaces. We finally present a large class of tensor-kernels to which our theory fully applies: power series tensor kernels. This type of kernels describes Banach spaces of analytic functions and includes generalizations of the exponential and polynomial kernels as well as, in the complex case, generalizations of the Szegö and Bergman kernels.sponsorship: The research leading to these results has received funding from the European Research Council ERC AdG A-DATADRIVE-B (290923) and ERC AdG EDUALITY (787960) under the European Union's Horizon 2020 research and innovation programme. The first author was partly supported by SAP SE. (European Research Council ERC AdG A-DATADRIVE-B under the European Union's Horizon 2020 research and innovation programme|290923, European Research Council ERC AdG EDUALITY under the European Union's Horizon 2020 research and innovation programme|787960, SAP SE)status: Publishe
The method of randomized Bregman projections for stochastic feasibility problems
No full textIn this work, we study the method of randomized Bregman projections for stochastic convex feasibility problems, possibly with an infinite number of sets, in Euclidean spaces. Under very general assumptions, we prove almost sure convergence of the iterates to a random almost common point of the sets. We then analyze in depth the case of affine sets showing that the iterates converge Q-linearly and providing also global and local rates of convergence. This work generalizes recent developments in randomized methods for the solution of linear systems based on orthogonal projection methods. We provided several applications: sketch & project methods for solving linear systems of equations, positive definite matrix completion problem, gossip algorithms for networks consensus, the assessment of robust stability of dynamical systems, and computational solutions for multimarginal optimal transport
ZONING DESIGN FOR HANDWRITTEN NUMERAL RECOGNITION
No full textMicrosoft, Motorola, Siemens, Hitachi, IAPR, NICI, IUF
In the field of Optical Character Recognition (OCR), zoning is used to extract topological information from patterns. In this paper zoning is considered as the result of an optimisation problem and a new technique is presented for automatic zoning. More precisely, local analysis of feature distribution based on Shannon's entropy estimation is performed to determine "core" zones of patterns. An iterative regiongrowing procedure is applied on the "core" zones to determine the final zoning
Regularized learning schemes in feature Banach spaces
No full textThis paper proposes a unified framework for the investigation of constrained learning theory in reflexive Banach spaces of features via regularized empirical risk minimization. The focus is placed on Tikhonov-like regularization with totally convex functions. This broad class of regularizers provides a flexible model for various priors on the features, including, in particular, hard constraints and powers of Banach norms. In such context, the main results establish a new general form of the representer theorem and the consistency of the corresponding learning schemes under general conditions on the loss function, the geometry of the feature space, and the modulus of total convexity of the regularizer. In addition, the proposed analysis gives new insight into basic tools such as reproducing Banach spaces, feature maps, and universality. Even when specialized to Hilbert spaces, this framework yields new results that extend the state of the art
Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
No full textIn this paper, we study the convergence properties of a randomized block-coordinate descent algorithm for the minimization of a composite convex objective function, where the block-coordinates are updated asynchronously and randomly according to an arbitrary probability distribution. We prove that the iterates generated by the algorithm form a stochastic quasi-Fejer sequence and thus converge almost surely to a minimizer of the objective function. Moreover, we prove a general sublinear rate of convergence in expectation for the function values and a linear rate of convergence in expectation under an error bound condition of Tseng type. Under the same condition strong convergence of the iterates is provided as well as their linear convergence rate
A Multi-Expert Signature Verification System for Bank-Check Processing
No full textIn this paper a multi-expert signature verification system is presented. The system has been specifically designed for applications in the field of bankcheck processing. For this purpose, it combines three different algorithms for signature verification. A wholistic approach is used in the first algorithm, a component-oriented approach is used in the second and third algorithm. The second algorithmis based on a structure-based procedure, the third algorithm uses a highly-adaptive neural network. The three algorithms are combined in the multi-expert system by a voting strategy
- …
