关键词：交流；计算权衡；统计学；数据集；非结构化数据；大数据
摘 要：The goal of this thesis is to study these trade-offs between the computational and statistical aspects of learning problems. This line of research results in several natural questions, some of which are partially addressed in this thesis and others present interesting challenges for future work.
目 录：

1 Introduction

1.1 Classical statistics, big data and computational constraints    

1.2 Connections to existing works            

1.3 Main problems and contributions           

1.4 Thesis Overview               

2 Background

2.1 Typical problem setup             

2.2 Background on convex optimization         

2.3 Background on stochastic convex optimization      

2.4 Background on minimax theory in statistics       

3 Oracle complexity of convex optimization

3.1 Background and problem formulation         

3.2 Main results and their consequences         

3.3 Proofs of results               

3.4 Discussion                

4 Computationally adaptive model selection

4.1 Motivation and setup             

4.2 Model selection over nested hierarchies        

4.3 Fast rates for model selection           

4.4 Oracle inequalities for unstructured models       

4.5 Discussion                

5 Optimization for high-dimensional estimation

5.1 Motivation and prior work            

5.2 Background and problem formulation         

5.3 Main results and some consequences         

5.4 Simulation results              

5.5 Proofs                

5.5.1 Proof of Theorem.1          

5.6 Discussion               

6 Asymptotically optimal distributed learning

6.1 Motivation and related work          

6.2 Setup and Algorithms            

6.3 Convergence rates for delayed optimization of smooth functions

6.4 Distributed Optimization           

6.5 Numerical Results             

6.6 Delayed Updates for Smooth Optimization      

6.7 Proof of Theorem.3            

6.8 Conclusion and Discussion           

7 Conclusions and future directions

7.1 Summary and key contributions         

7.2 Important open questions and immediate future directions  

7.3 Other suggestions for future work