Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 17 of 17 for “"conditional gradient"”.
-
Faster Conditional Gradient Algorithms for Machine Learning
In this thesis, we focus on Frank-Wolfe (a.k.a. Conditional Gradient) algorithms, a family of iterative algorithms for convex optimization, that work under the assumption that projections onto the feasible region are prohibitive, but linear optimization problems can be efficiently solved over the …
-
A Projection-Free Algorithm for Solving Support Vector Machine Models
… over a polytope. To this goal, we apply the conditional gradient (CG) method by providing explicit solution to the linear programming (LP) subproblem. We also describe the conditional gradient sliding (CGS) method that can be considered as an improvement of CG in terms of number of gradient …
-
A reduction framework for approximate extended formulations and a faster algorithm for convex optimization
… bounds motivates the lazification technique for conditional gradient type algorithms. This technique allows us to replace (approximate) linear optimization in favor of a much weaker subroutine, achieving significant performance improvement in practice. We can summarize the main contributions as …
-
Risk neutral and risk averse stochastic optimization
… projection-free method, referred to as Level Conditional Gradient (LCG) method, for solving convex functional constrained optimization. Different from the constraint-extrapolated conditional gradient type methods (CoexCG and CoexDurCG), LCG, as a primal method, does not assume the existence of …
-
On Variants of Sliding and Frank-Wolfe Type Methods and Their Applications in Video Co-localization
… projection-free sliding algorithm, namely the conditional gradient sliding (CGS) method. Our proposed algorithm, called the conditional gradient sliding with linesearch (CGSls), does not require the knowledge of Lipschitz constant of the gradient of objective function, which is critical in the …
-
Theory and applications of first-order methods for convex optimization with function constraints
… The second part of the thesis is devoted to conditional gradient methods which have attracted much attention in both machine learning and optimization communities recently. These simple methods can guarantee the generation of sparse solutions. In addition, without the computation of full …
-
Improved First-Order Techniques for Certain Classes of Convex Optimization
… are as follows. We first show that the popular Conditional Gradient Sliding (CGS) algorithm can be extended in application to objectives with H\"older continuous gradients. CGS has gained much attention in recent years due to its ability to compute an approximate solution without the necessity …
-
Multi-commodity flow estimation with partial counts on selected links
… Frank-Wolfe algorithm, which is a type of conditional gradient method, is used to solve the assignment problem. The next step is to consider both of the observed traffic counts on selected links and the deterministic user equilibrium assignments on the group of remaining links to produce …
-
Integrated water and power modeling framework for renewable energy integration
… network model called MODSIM is adapted using a conditional gradient method to be able to connect to an overarching optimization routine that decomposes the water and power problems. The water network model is connected to a simple power dispatch model that uses a linear programming approach to …
-
Information, complexity and structure in convex optimization
… of convex functions with Hölder continuous gradients. Our technique relies on the existence of a smoothing kernel, which defines a smooth approximation for any convex function via infimal convolution. As a consequence, we derive lower bounds for \ell_p/\ell_q-setups, where 1\leq p,q\leq …
-
Efficient algorithms for simple bilevel optimization : from convex to non-convex
… with variance reduction techniques and conditional gradient updates. The proposed methods achieve near-optimal oracle complexity bounds for both convex and nonconvex upper-level objectives and significantly improve upon existing results. We then consider deterministic convex smooth …
-
Momentum for the Frank Wolfe Method
… of structural (e.g., sparse) solutions. Conditional gradient, aka Frank Wolfe (FW) algorithms, have well-documented merits in machine learning and signal processing applications that involves minimizing a loss function with constraints. Compared to projection based methods, one of the key …
-
Modeling, learning, and inference of high-dimensional asynchronous event data
… from both the proximal methods and the conditional gradient methods to solve the matrix rank minimization problem under different constraints. Finally, in the data streaming setting, we develop a Bayesian inference algorithm for inferring latent variables and updating the respective …
-
Likelihood-based Density Estimation using Deep Architectures
… deep mixture model can be approximated using the conditional gradient algorithm by a shallow architecture of polynomial size w.r.t. the inverse of the approximation accuracy. Next, we address the more practical problem of density estimation of mixture models for streaming data by proposing an …
-
Efficient Algorithms for Bilevel Optimization Problems with Application in Machine Learning
… optimization problems. Our method combines a gradient flow mechanism for upper-level minimization with a safety filter for enforcing lower-level constraints. Through Lyapunov analysis, we prove convergence to a neighborhood of the global optimum. This continuous-time insight then informs the …
-
Bridging Discrete and Continuous Methods for Faster Optimization and Machine Learning
… In Chapter 3, we focus on improving the rates of conditional gradient variants (in the presence of combinatorial structures) while maintaining their efficiency. We develop a novel theoretical framework that provides a unifying view of various descent directions in the literature and demystifies …