Category Archives: Learning Theory

Faster Than SGD 1: Variance Reduction

SGD is well-known for large-scale optimization. In my mind, there are two (and only two) fundamental improvements since the original introduction of SGD: (1) variance reduction, and (2) acceleration. In this guest post at Princeton’s OptiML group, I’d love to conduct … Continue reading

Posted in Algorithm, Learning Theory, Optimization | Leave a comment

Learning Algorithms for DT, DNF, AC0 and r-juntas

This is a section of my reading notes to Prof. Ryan O’Donnell’s <Analysis of Boolean Functions>, I’ve summarized the learning algorithms in this post, which also functions as a personal reference. Class Random Examples Membership Queries poly-size DTs Theorem 5 Theorem … Continue reading

Posted in Learning Theory, Readings | Leave a comment

Learning Zero-One Loss Objective – The Experiment

(Continued from the previous post.) Though the complexity depends crucially on , however, when is a constant (e.g. ) there is still reason to believe that the approximated 0-1 loss function using is more accurate than the hinge loss. However, … Continue reading

Posted in Learning Theory, Readings | Leave a comment

Learning Zero-One Loss Objective – The Theory

(This thread comes from the preliminary version of a subsection of my on-going survey, which will be published soon) Not satisfied by the result in the previous section, [SSSS10] made an interesting attempt towards learning 0-1 objective functions. In classification … Continue reading

Posted in Learning Theory, Readings | Leave a comment

Survey & Experiment: Towards the Learning Accuracy

This survey has been merged into a technical report, see here. 1. Introduction A generic learning problem can be regarded as an optimization over parameter , and the loss function is given by where is a given sample. An empirical … Continue reading

Posted in Learning Theory, Readings | Leave a comment

Generalization for Stochastic / Online Convex Learning

I haven’t touched learning theory for a couple of months, but I always keep my eyes on. Partially due to the reason that I am seeking for a learning theory course project, I decided to take a brief look at … Continue reading

Posted in Learning Theory, Readings | Leave a comment