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 6 of 6 for “"lower complexity bound"”.
-
Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods
In this thesis, we construct worst case binary logistic regression datasets for any deterministic first order methods. We show that our datasets require at least $\cO(1/\sqrt{\varepsilon})$ first-order oracle inquires to obtain a $\varepsilon-$approximate solution under the assumption that the …
-
Improved First-Order Techniques for Certain Classes of Convex Optimization
… such as imaging science. We discuss the current lower complexity bounds of solving such problems and suggest a potential method of improvement. By separating the computation of gradient and operator evaluations, we propose two new sliding methods that improve upon the best known convergence rates …
-
Evaluating conjunctive and graph queries over the EL profile of OWL 2
… In this thesis, we present several novel complexity results and algorithms for answering expressive queries over OWL 2 EL knowledge bases (KBs) with regular role inclusions. </p> <p>We first focus on the complexity of conjunctive query (CQ) answering in OWL 2 EL and show that the problem …
-
Design and Analysis of Algorithms for Composite Optimization
… obtain either improved (or sometimes optimal) complexity results or remarkable practical performance. We first study convex nonsmooth composite optimization, and develop a novel proximal bundle method. We show that the proposed method has O(ε−2) complexity for obtaining an ε-solution, and also …
-
Statistical Learning from Shifting, Indirect, or Unseen Data: Efficient Algorithms and Theoretical Guarantees
… as special cases. We present the first complexity guarantees for this problem class, using a randomized algorithm with components inspired by the simulation literature (such as adaptive sampling of new data and adaptive averaging of historical data). We prove convergence guarantees in …
-
Stochastic algorithms for distributed optimization and machine learning
… function per iteration. Moreover, by providing a lower complexity bound for the class of RIG methods for finite-sum optimization, we demonstrate the optimality of RPDG, and this is the first time such an optimal RIG method has been developed for solving finite-sum optimization problems. In the …