nils-herrmann/clean_scirepeval huggingface dataset:
A formal analysis of stopping criteria of decomposition methods for support vector machines

In a previous paper, the author (2001) proved the convergence of a commonly used decomposition method for support vector machines (SVMs). However, there is no theoretical justification about its stopping criterion, which is based on the gap of the violation of the optimality condition. It is essential to have the gap asymptotically approach zero, so we are sure that existing implementations stop in a finite number of iterations after reaching a specified tolerance. Here, we prove this result and illustrate it by two extensions: /spl nu/-SVM and a multiclass SVM by Crammer and Singer (2001). A further result shows that, in final iterations of the decomposition method, only a particular set of variables are still being modified. This supports the use of the shrinking and caching techniques in some existing implementations. Finally, we prove the asymptotic convergence of a decomposition method for this multiclass SVM. Discussions on the difference between this convergence proof and the one in another paper by Lin are also included.
Analysis of switching dynamics with competing support vector machines

We present a framework for the unsupervised segmentation of time series using support vector regression. It is applied to non-stationary time series which alter in time. We follow the architecture of Pawelzik et al. (1996) which consists of competing predictors. In the above paper competing neural networks were used while here we exploit the use of support vector machines, a learning technique. Results indicate that the proposed approach is as good as that of that Pawelzik et al. Differences between the two approaches are also discussed.
On the convergence of the decomposition method for support vector machines

The decomposition method is currently one of the major methods for solving support vector machines (SVM). Its convergence properties have not been fully understood. The general asymptotic convergence was first proposed by Chang et al. However, their working set selection does not coincide with existing implementation. A later breakthrough by Keerthi and Gilbert (2000, 2002) proved the convergence finite termination for practical cases while the size of the working set is restricted to two. In this paper, we prove the asymptotic convergence of the algorithm used by the software SVM(light) and other later implementation. The size of the working set can be any even number. Extensions to other SVM formulations are also discussed.
A note on the decomposition methods for support vector regression

The dual formulation of support vector regression involves with two closely related sets of variables. When the decomposition method is used, many existing approaches use pairs of indices from these two sets as the working set. Basically they select a base set first and then expand it so that all indices are pairs. This makes the implementation different from that for support vector classification. In addition, a larger optimization sub-problem has to be solved in each iteration. In this paper from different aspects we demonstrate that there are no needs to do so. In particular we show that directly using this base set as the working set leads to similar convergence (number of iterations). Therefore, not only the program can be simpler, with a smaller working set and similar number of iterations, it can also be more efficient.
Training ν-Support Vector Classifiers: Theory and Algorithms

The ν-support vector machine (ν-SVM) for classification proposed by Schölkopf, Smola, Williamson, and Bartlett (2000) has the advantage of using a parameter ν on controlling the number of support vectors. In this article, we investigate the relation between ν-SVM and C-SVM in detail. We show that in general they are two different problems with the same optimal solution set. Hence, we may expect that many numerical aspects of solving them are similar. However, compared to regular C-SVM, the formulation of ν-SVM is more complicated, so up to now there have been no effective methods for solving large-scale ν-SVM. We propose a decomposition method for ν-SVM that is competitive with existing methods for C-SVM. We also discuss the behavior of ν-SVM by some numerical experiments.
Training v-Support Vector Classifiers: Theory and Algorithms

The -support vector machine (-SVM) for classification proposed by Schlkopf, Smola, Williamson, and Bartlett (2000) has the advantage of using a parameter on controlling the number of support vectors. In this article, we investigate the relation between -SVM and C-SVM in detail. We show that in general they are two different problems with the same optimal solution set. Hence, we may expect that many numerical aspects of solving them are similar. However, compared to regular C-SVM, the formulation of -SVM is more complicated, so up to now there have been no effective methods for solving large-scale -SVM. We propose a decomposition method for -SVM that is competitive with existing methods for C-SVM. We also discuss the behavior of -SVM by some numerical experiments.
Formulations of Support Vector Machines: A Note from an Optimization Point of View

In this article, we discuss issues about formulations of support vector machines (SVM) from an optimization point of view. First, SVMs map training data into a higher- (maybe infinite-) dimensional space. Currently primal and dual formulations of SVM are derived in the finite dimensional space and readily extend to the infinite-dimensional space. We rigorously discuss the primal-dual relation in the infinite-dimensional spaces. Second, SVM formulations contain penalty terms, which are different from unconstrained penalty functions in optimization. Traditionally unconstrained penalty functions approximate a constrained problem as the penalty parameter increases. We are interested in similar properties for SVM formulations. For two of the most popular SVM formulations, we show that one enjoys properties of exact penalty functions, but the other is only like traditional penalty functions, which converge when the penalty parameter goes to infinity.
Optical Coating Designs Using the Family Competition Evolutionary Algorithm

A robust evolutionary approach, called the Family Competition Evolutionary Algorithm (FCEA), is described for the synthesis of optical thin-film designs. Based on family competition and adaptive rules, the proposed approach consists of global and local strategies by integrating decreasing mutations and self-adaptive mutations. The method is applied to three different optical coating designs with complex spectral quantities. Numerical results indicate that the proposed approach performs very robustly and is very competitive with other approaches.
An Incomplete Cholesky Factorization for Dense Symmetric Positive Definite Matrices

In this paper, we study the use of an incomplete Cholesky factorization (ICF) as a preconditioner for solving dense symmetric positive definite linear systems. This method is suitable for situations where matrices cannot be explicitly stored but each column can be easily computed. Analysis and implementation of this preconditioner are discussed. We test the proposed ICF on randomly generated systems and large matrices from two practical applications: semidefinite programming and support vector machines. Numerical comparison with the diagonal preconditioner is also presented.
The analysis of decomposition methods for support vector machines

The support vector machine (SVM) is a new and promising technique for pattern recognition. It requires the solution of a large dense quadratic programming problem. Traditional optimization methods cannot be directly applied due to memory restrictions. Up to now, very few methods can handle the memory problem and an important one is the "decomposition method." However, there is no convergence proof so far. In this paper, we connect this method to projected gradient methods and provide theoretical proofs for a version of decomposition methods. An extension to bound-constrained formulation of SVM is also provided.We then show that this convergence proof is valid for general decomposition methods if their working set selection meets a simple requirement.
Topological Fixture Synthesis Using Semide nite Programming

1.  Topological xture synthesis is an important issue to consider for most manufacturing operations performed on solid and sheet metal workpieces. Recent work on optimal xture design has focused on determining the positions of locators and clamps to minimize workpiece deformation. These approaches restrict the locators and clamps to three mutually perpendicular planes selected according to the \3-2-1" or the \N-2-1" locating principle. In this article, mixed-integer quadratic programming is used to identify the optimal distribution and position (i.e., topology) of locators in order to minimize the mean compliance of the workpiece. We present a semide nite programming (SDP) relaxation method to solve the underlying combinatorial problem. Illustrative examples (with symmetric and asymmetric loads) validate the formulation and solution approach.
Incomplete Cholesky Factorizations with Limited Memory

We propose an incomplete Cholesky factorization for the solution of large-scale trust region subproblems and positive definite systems of linear equations. This factorization depends on a parameter p that specifies the amount of additional memory (in multiples of n, the dimension of the problem) that is available; there is no need to specify a drop tolerance. Our numerical results show that the number of conjugate gradient iterations and the computing time are reduced dramatically for small values of p. We also show that in contrast with drop tolerance strategies, the new approach is more stable in terms of number of iterations and memory requirements.
Newton's Method for Large Bound-Constrained Optimization Problems

We analyze a trust region version of Newton's method for bound-constrained problems. Our approach relies on the geometry of the feasible set, not on the particular representation in terms of constraints. The convergence theory holds for linearly constrained problems and yields global and superlinear convergence without assuming either strict complementarity or linear independence of the active constraints. We also show that the convergence theory leads to an efficient implementation for large bound-constrained problems.
Relaxed Cutting Plane Method for Solving Linear Semi-Infinite Programming Problems

One of the major computational tasks of using the traditional cutting plane approach to solve linear semi-infinite programming problems lies in finding a global optimizer of a nonlinear and nonconvex program. This paper generalizes the Gustafson and Kortanek scheme to relax this requirement. In each iteration, the proposed method chooses a point at which the infinite constraints are violated to a degree, rather than a point at which the violations are maximized. A convergence proof of the proposed scheme is provided. Some computational results are included. An explicit algorithm which allows the unnecessary constraints to be dropped in each iteration is also introduced to reduce the size of computed programs.
Preconditioning Dense Linear Systems from Large-scale Semideenite Programming Problems

In this paper we show semideenite programming (SDP) could be a resource for large dense systems. The preconditioned conjugate gradient method is used to solve fully dense linear systems during each iteration of an optimization algorithm. An incomplete Cholesky factorization is proposed, and some numerical results are obtained. These results generate better lower bounds for the quadratic assignment problem, an application of SDP.
An Infeasible Start Predictor Corrector Method for Semi-deenite Linear Programming

In this paper we present an infeasible start path following predictor corrector method for semideenite linear programming problem. This method does not assume that the dual pair of semideenite programs have feasible solutions, and, in at most O(jlog((A;b;C))jn) iterations of the predictor corrector method, nds either an approximate solution to the dual pair or shows that there is no optimal solution with duality gap zero in a well deened bounded region. The nonexistence of optimal solutions is detected in a nite number of iterations. Here is a measure of non-optimality and infeasibility of the pair of solutions found, and is generally chosen to be small; (A; b; C) is a function of the data of the problem and is a measure of the size of the region searched, and is generally large. The method we present generalizes a method for linear programming developed by Mizuno. We give some preliminary computational experience for this method, and compare its performance (measured by the number of iterations) with that of the code SP of Vandenberghe and Boyd which is Supported by the grant number CCR{9321550 from the National Science Foundation. 0 based on a potential reduction strategy, and the code SDPA of Fujisawa and Kojima which is based on a path following and potential reduction strategy.
7. Markov chains with exponential transitions

7.1. Model definition 
 
 
7.2. The reduction principle 
 
 
7.3. Excursion from a domain 
 
 
7.4. Fast reduction algorithm 
 
 
7.5. Elevation function and cycle decomposition 
 
 
7.6. Mean hitting times and ordered reduction 
 
 
7.7. Convergence speeds 
 
 
7.8. Generalized simulated annealing algorithm
3. Non cumulated mean risk

3.1. The progressive mixture rule 
 
 
3.1.1. Estimation of a conditional density 
 
 
3.1.2. Some variants of the progressive mixture estimator 
 
 
 
 
 
 
3.2. Estimating a Bernoulli random variable 
 
 
3.2.1. The Laplace estimator 
 
 
3.2.2. Some adaptive Laplace estimator 
 
 
 
 
 
 
3.3. Adaptive histograms 
 
 
3.4. Some remarks on approximate Monte-Carlo computations 
 
 
3.5. Selection and aggregation : a toy example pointing out some differences 
 
 
3.6. Least square regression 
 
 
3.7. Adaptive regression estimation in Besov spaces
A PAC-Bayesian approach to adaptive classification

This is meant to be a self-contained presentation of adaptive classification seen from the PAC-Bayesian point of view. Although most of the results are original, some review materials about the VC dimension and support vector machines are also included. This study falls in the field of statistical learning theory, where complex data have to be analyzed from a limited amount of informations, drawn from a finite sample. It relies on non asymptotic deviation inequalities, where the complexity of models is captured through the use of prior measures. The main improvements brought here are more localized bounds and the use of exchangeable prior distributions. Interesting consequences are drawn for the generalization properties of support vector machines and the design of new classification algorithms.
1. Universal lossless data compression

1.1. A link between coding and estimation 
 
 
1.1.1. Coding and Shannon entropy 
 
 
1.1.2. Instantaneous codes 
 
 
 
 
 
 
1.2. Universal coding and mixture codes 
 
 
1.2.1. The Bayesian approach 
 
 
1.2.2. The minimax approach 
 
 
1.2.3. Oracle inequalities 
 
 
 
 
 
 
1.3. Lower bounds for the minimax compression rate 
 
 
1.4. Mixtures of i.i.d. coding distributions 
 
 
1.5. Double mixtures and adaptive compression 
 
 
1.5.1. General principle 
 
 
1.5.2. The context tree weighting coding distribution 
 
 
1.5.3. Context tree weighting without initial context 
 
 
1.5.4. Weighting of trees of arbitrary depth
4. Gibbs estimators

4.1. General framework 
 
 
4.2. Dichotomic histograms 
 
 
4.3. Mathematical framework for density estimation 
 
 
4.4. Main oracle inequality 
 
 
4.5. Checking the accuracy of the bounds on the Gaussian shift model 
 
 
4.6. Application to adaptive classification 
 
 
4.6.1. Randomized classification rule, general case 
 
 
4.6.2. Randomized classification rule for “non-ambiguous” classification problems 
 
 
4.6.3. Deterministic classification rule 
 
 
4.6.4. Counter example 
 
 
 
 
 
 
4.7. Two stage adaptive least square regression 
 
 
4.8. One stage piecewise constant regression 
 
 
4.9. Some abstract inference problem 
 
 
4.10. Another type of bound
5. Randomized estimators and empirical complexity

5.1. A pseudo-Bayesian approach to adaptive inference 
 
 
5.1.1. General framework 
 
 
5.1.2. Some pervading ideas 
 
 
 
 
 
 
5.2. A randomized rule for pattern recognition 
 
 
5.3. Generalizations of theorem 5.2.3 
 
 
5.4. The non-ambiguous case 
 
 
5.5. Empirical complexity bounds for the Gibbs estimator 
 
 
5.6. Non randomized classification rules 
 
 
5.7. Application to classification trees 
 
 
5.8. The regression setting 
 
 
5.9. Links with penalized least square regression 
 
 
5.9.1. The general case 
 
 
5.9.2. Adaptive linear least square regression estimation 
 
 
 
 
 
 
5.10. Some elementary bounds 
 
 
5.11. Some refinements about the linear regression case
Simulated annealing algorithms and Markov chains with rare transitions

In these notes, written for a D.E.A. course at University Paris XI during the first term of 1995, we prove the essentials about stochastic optimisation algorithms based on Markov chains with rare transitions, under the weak assumption that the transition matrix obeys a large deviation principle. We present a new simplified line of proofs based on the Freidlin and Wentzell graphical approach. The case of Markov chains with a periodic behaviour at null temperature is considered. We have also included some pages about the spectral gap approach where we follow Diaconis and Stroock [13] and Ingrassia  in a more conventional way, except for the application to non reversible Metropolis algorithms (subsection 6.2.2) where we present an original result.
Piecewise constant triangular cooling schedules for generalized simulated annealing algorithms

We investigate how to tune a generalized simulated annealing algorithm with piecewise constant cooling schedule to get an optimal convergence exponent. The optimal convergence exponent of generalized simulated annealing algorithms has been computed in  and . It is reached only with triangular sequences of temperatures, meaning that di erent nite sequences are used depending on the time resource available for computations (expressed by an overall number of iterations). We show rst that it is possible to get close to the optimal convergence exponent uniformly over suitably bounded families of energy landscapes using a xed number of temperature steps. Then we show that letting the number of steps increase with the time resource, we can build a cooling schedule which is universally robust with respect to the convergence exponent: a xed triangular sequence of temperatures gives an optimal convergence exponent for any energy landscape. Piecewise constant temperature sequences are often used in practice: in favourable cases, the use of the same temperature during a large number of iterations allows to tabulate the exponential penalties appearing in the transition matrix, thus sparing a signi cant amount of computer time. The proofs we give rely on Freidlin and Wentzell's closed formulas for the exit time and point from subdomains of time homogeneous Markov chains. key words: Large deviations, Metropolis dynamics, cycle decomposition, simulated annealing, di culty, critical depth. DMI, Laboratoire de Math ematiques de l'Ecole Normale Sup erieure, UA 762 du CNRS, 45 rue d'Ulm, 75230 Paris Cedex 05-France and Laboratoire de Mod elisation Stochastique et Statistique, Universit e Paris Sud, Math ematiques, Bat̂ ment 425, 91405 Orsay Cedex, France. E-mail address: cot@dmi.ens.fr and cot@stats.matups.fr y DIAM, Laboratoire de Math ematiques de l'Ecole Normale Sup erieure, UA 762 du CNRS, 45 rue d'Ulm, 75230 Paris Cedex 05-France. E-mail adress: catoni@dmi.ens.fr
The energy transformation method for the Metropolis algorithm compared with Simulated Annealing

We present and analyze a new speed-up technique for Monte Carlo optimization: the Iterated Energy Transformation algorithm, where the Metropolis algorithm is used repeatedly with more and more favourable energy functions derived from the original one by increasing transformations. We show that this method allows a better speed-up than Simulated Annealing when convergence speed is measured by the probability of failure of the algorithm after a large number of iterations. We study also the limit of a large state space in the special case when the energy is made of a sum of independent terms. We show that the convergence time of the I.E.T. algorithm is polynomial in the size (number of coordinates) of the problem, but with a worse exponent than for Simulated Annealing. This indicates that the I.E.T. algorithm is well suited for moderate size problems but not for too large ones. The independent component case is a good model for the end of many optimization processes, when at low temperature a neighbourhood of a local minimum is explored by small and far apart modifications of the current solution. We show that in this case both global optimization methods, Simulated Annealing and the I.E.T. algorithm, are less efficient than repeated local stochastic optimizations. Using the general concept of “slow stochastic optimization algorithm”, we show that any “slow” global optimization scheme should be followed by a local one to perform the last approach to a minimum.
Solving Scheduling Problems by Simulated Annealing

We define a general methodology to deal with a large family of scheduling problems. We consider the case where some of the constraints are expressed through the minimization of a loss function. We study in detail a benchmark example consisting of some jigsaw puzzle problem with additional constraints. We discuss some algorithmic issues typical of scheduling problems, such as the apparition of small unused gaps or the representation of proportionality constraints. We also carry on an experimental comparison between the Metropolis algorithm, simulated annealing, and the iterated energy transformation method to see whether asymptotical theoretical results are a good guide towards practically efficient algorithms.
Metropolis, Simulated Annealing, and Iterated Energy Transformation Algorithms

In this paper, we compare from the theoretical and experimental points of view three stochastic optimization algorithms: the Metropolis, simulated annealing, and iterated energy transformation algorithms. We give the optimal exponents for the concentration of the marginal distribution of the final state of these algorithms around the global minima of the virtual energy function. Experiments are performed on an N.P. complete benchmark which tries to retain the main aspects of scheduling problems. They lead to the same qualitative ranking of algorithms as the theory does.
The exit path of a Markov chain with rare transitions

We study the exit path from a general domain after the last visit to a set of a Markov chain with rare transitions. We prove several large deviation principles for the law of the succession of the cycles visited by the process (the cycle path), the succession of the saddle points gone through to jump from cycle to cycle on the cycle path (the saddle path) and the succession of all the points gone through (the exit path). We estimate the time the process spends in each cycle of the cycle path and how it decomposes into the time spent in each point of the exit path. We describe a systematic method to find the most likely saddle paths. We apply these results to the reversible case of the Metropolis dynamics. We give in appendix the corresponding large deviation estimates in the non homogeneous case, which are corollaries of already published works by Catoni (1992) and Trouve (1992, 1996a).