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"”.

  1. 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 …

    clemson Repository record for Worst Case Datasets for Solving Binary Logistic Regression via Deterministic First-Order Methods (opens in a new tab)

  2. 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 …

    clemson Repository record for Improved First-Order Techniques for Certain Classes of Convex Optimization (opens in a new tab)

  3. 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 …

    oxford Repository record for Evaluating conjunctive and graph queries over the EL profile of OWL 2 (opens in a new tab)

  4. 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 …

    gatech Repository record for Design and Analysis of Algorithms for Composite Optimization (opens in a new tab)

  5. 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 …

    washington Repository record for Statistical Learning from Shifting, Indirect, or Unseen Data: Efficient Algorithms and Theoretical Guarantees (opens in a new tab)

  6. 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 …

    gatech Repository record for Stochastic algorithms for distributed optimization and machine learning (opens in a new tab)