Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for id:"handle:1773/46764". One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Washington

1. Yang, Xin. Towards Better Understanding of Algorithms and Complexity of Some Learning Problems.

Degree: PhD, 2021, University of Washington

We present several novel results on computational problems related to supervised learning.We focus on the computational resources required by algorithms to solve learning problems. The computational resources we consider are running time, memory usage and query complexity, which is the number of positions in the input that the algorithm needs to check. Some contributions include: \begin{itemize} \item Time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be significantly smaller than the concept class of functions and the function values can be from an arbitrary finite set. \item A simple and efficient algorithm for approximating the John Ellipsoid of a symmetric polytope. Our algorithm is near optimal in the sense that our time complexity matches the current best verification algorithm. Experimental results suggest that our algorithm significantly outperforms existing algorithms. \item The first algorithm for the total least squares problem, a variant of the ordinary least squares problem, that runs in time proportional to the sparsity of the input. The core to developing our algorithm involves recent advances in randomized linear algebra. \item A generic space efficient algorithm that is based on deterministic decision trees. \item The first algorithm for the linear bandits problem with prior constraints. \end{itemize} Advisors/Committee Members: Beame, Paul (advisor), Jamieson, Kevin (advisor).

Subjects/Keywords: computational complexity; learning theory; Computer science; Computer science and engineering

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Yang, X. (2021). Towards Better Understanding of Algorithms and Complexity of Some Learning Problems. (Doctoral Dissertation). University of Washington. Retrieved from http://hdl.handle.net/1773/46764

Chicago Manual of Style (16th Edition):

Yang, Xin. “Towards Better Understanding of Algorithms and Complexity of Some Learning Problems.” 2021. Doctoral Dissertation, University of Washington. Accessed April 22, 2021. http://hdl.handle.net/1773/46764.

MLA Handbook (7th Edition):

Yang, Xin. “Towards Better Understanding of Algorithms and Complexity of Some Learning Problems.” 2021. Web. 22 Apr 2021.

Vancouver:

Yang X. Towards Better Understanding of Algorithms and Complexity of Some Learning Problems. [Internet] [Doctoral dissertation]. University of Washington; 2021. [cited 2021 Apr 22]. Available from: http://hdl.handle.net/1773/46764.

Council of Science Editors:

Yang X. Towards Better Understanding of Algorithms and Complexity of Some Learning Problems. [Doctoral Dissertation]. University of Washington; 2021. Available from: http://hdl.handle.net/1773/46764

.