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 20 of 54 for “"iteration complexity"”.
-
Nonconvex Optimization Methods: Iteration Complexity And Applications
… of nonconvex optimization algorithms and their complexity results, including the Riemannian optimization methods for solving manifold constrained problems, and variance reduced cubic regularized Newton's method for computing second-order solution for empirical risk minimization problems. In the …
-
Low-Order Optimization Algorithms: Iteration Complexity and Applications
… substantially lower computational overhead per iteration, lower-order (first-order and zeroth-order) methods have received much attention and become popular in recent years. In this thesis, we present a systematic study of the lower-order algorithms for solving a wide range of different …
-
On Polynomial-time Path-following Interior-point Methods with Local Superlinear Convergence
… of interior-point methods with proven polynomial iteration complexity. Our focus is on linear programming and semidefinite programming special cases. We provide a survey on polynomial iteration complexity interior-point methods which also achieve asymptotic superlinear convergence. We analyze the …
-
On Multistage Stochastic and Distributionally Robust Optimization: New Algorithms, Complexity Analysis, and Performance Comparison
… of complete recourse. We also characterize the iteration complexity of the proposed algorithms, which reveals that the iteration complexity depends polynomially on the number of stages. We further show that the iteration complexity depends linearly on the number of stages $T$, if all the state …
-
A Fast Reduced-Space Algorithmic Framework for Sparse Optimization
… derivatives), which have small computational iteration complexity but often are inefficient on realistic applications, and second-order methods (i.e., those that use first- and second-order derivatives), which have large computational iteration complexity but are robust and efficient in terms …
-
First-order methods for structured optimization
… averaging. In the third part, we derive improved iteration complexity of the stochastic subgradient method for over-parameterized models that satisfy an interpolation condition. The obtained iteration complexity matches the rate of the stochastic gradient method applied to smooth problems that …
-
ON SCALABLE AND FAST LANGEVIN-DYNAMICS-BASED SAMPLING ALGORITHMS
… analysis from finite time to infinite time. Iteration complexity in 2-Wasserstein distance is also characterized and when applied to Langevin Monte Carlo algorithm, we obtain an improved iteration complexity bound.
-
Optimization,minimax, and variational inequality problems: algorithms and applications
… This thesis investigates the algorithmic complexity of such problems, focusing on first-order and second-order methods across different settings. A major theme is the studies of upper and lower bounds on the iteration complexity in each setting and algorithm class, identifying optimal or …
-
Accelerated Inexact First-Order Methods for Solving Nonconvex Composite Optimization Problems
… analysis, and our key results are in the form of iteration complexity bounds and how these bounds compare to other ones in the literature. Our first study problem is the classic unconstrained NCO problem studied by Mine and Fukushima (1981), and we develop an accelerated inexact proximal point …
-
Interior-Point Algorithms Based on Primal-Dual Entropy
… homogeneous and self-dual framework. We present iteration complexity analysis of our algorithms and provide the results of computational experiments on NETLIB problems.
-
Accelerated algorithms for composite saddle-point problems and applications
… monotone inclusion problem which, at every iteration, solves two prox sub-inclusions according to a certain relative error criterion. By exploiting the fact that the two prox sub-inclusions in the context of the CSP problem are equivalent to two composite convex programs, the first part of …
-
Accelerated first-order optimization methods using inertia and error bounds
… is on first-order methods which have low per-iteration complexity and can exploit problem structure to a high degree. First-order methods have the capacity to address large-scale problems for which all alternative methods fail. However, first-order methods can take many iterations to reach the …
-
Convergence in min-max optimization
… variational inequalities, showing improved iteration complexity compared to first-order methods such as Mirror Prox.
-
An inexact interior-point algorithm for conic convex optimization problems
… possess the desirable properties of polynomial iteration complexity and global convergence to the optimal solution set. In practice the best IPMs are primal-dual methods, in which a convex problem is solved together with its dual, which is another convex problem. One downside of existing …
-
AN INEXACT ALTERNATING DIRECTION METHOD OF MULTIPLIERS FOR CONVEX COMPOSITE CONIC PROGRAMMING WITH NONLINEAR CONSTRAINTS
… our targeted model. Global convergence and iteration complexity results of our proposed algorithm are established. Extensive numerical results indicate that our proposed algorithm is very effective in handling both the linear and nonlinear constraints.
-
Risk neutral and risk averse stochastic optimization
… settings. Third, we discuss sample complexity of solving stationary stochastic programs by the Sample Average Approximation (SAA) method. We investigate this in the framework of Stochastic Optimal Control (in discrete time) setting. In particular we derive a Central Limit Theorem …
-
Convex regression and its extensions to learning a Bregman divergence and difference of convex functions
… We provide approximation guarantees and sample complexity bounds for both these extensions. Furthermore, we provide algorithms to solve the resulting optimization problems based on 2-block alternative direction method of multipliers (ADMM). For this algorithm, we provide convergence guarantees …
-
EXPERIMENTAL EVALUATION OF ITERATIVE METHODS FOR GAMES
… methods are prefer because of their cheap per iteration cost. To further increase optimization efficiency, different improvements of deterministic and stochastic gradient methods are proposed, such as acceleration, variance reduction, and random reshuffling. In this work, we explore advanced …
-
ALGORITHMIC HEURISTICS IN DEEP LEARNING: REGULARIZATION AND ROBUSTNESS
… aspects of dropout. We provide precise iteration complexity rates for training two-layer ReLU neural networks with dropout, under certain distributional assumptions and over-parameterization requirements. We also show that dropout implicitly compresses the network. In particular, we show …
-
A Modern Treatise on Variational Inequality Problems: Structures, Algorithms, and Iteration Complexities
… algorithms and analyzing their (sample/gradient) iteration complexities. In particular, we aim to explore the hidden structures in VI that have not been (fully) studied before and use them as insights to guide the development of new optimal algorithms that align with the modern research trends in …
Page 1 of 3