Finding practically relevant problems where quantum computation offers a speedup compared to the best known classical algorithms is one of the central challenges in the field. Quantifying a speedup requires a provable convergence rate of the quantum algorithms, which restricts us to studying algorithms that can be analyzed rigorously. The impressive recent progress on building quantum computers gives us a new possibility: We can use heuristic quantum algorithms that can be run on current devices to demonstrate the speedup empirically. This however requires a hardware friendly implementation, i.e., a moderate number of qubits and shallow circuits. In recent years, more and more evidence has been found supporting machine learning tasks as good candidates for demonstrating quantum advantage [1-4]. In particular, the so-called supervised learning setting, where in the simplest case the goal is to learn a binary classifier of classical data, received much attention. The reasons are manifold: (i) The algorithms only require classical access to data.

Quantum support vector machines have the potential to achieve a quantum speedup for solving certain machine learning problems. The key challenge for doing so is finding good quantum kernels for a given data set -- a task called kernel alignment. In this paper we study this problem using the Pegasos algorithm, which is an algorithm that uses stochastic gradient descent to solve the support vector machine optimization problem. We extend Pegasos to the quantum case and and demonstrate its effectiveness for kernel alignment. Unlike previous work which performs kernel alignment by training a QSVM within an outer optimization loop, we show that using Pegasos it is possible to simultaneously train the support vector machine and align the kernel. Our experiments show that this approach is capable of aligning quantum feature maps with high accuracy, and outperforms existing quantum kernel alignment techniques. Specifically, we demonstrate that Pegasos is particularly effective for non-stationary data, which is an important challenge in real-world applications.

In this paper, we propose online algorithms for multiclass classification using partial labels. We propose two variant s of Perceptron called Avg Perceptron and Max Perceptron to deal with the par tial labeled data. We also propose Avg Pegasos and Max Pegasos, whic h are extensions of Pegasos algorithm. We also provide mistake bounds for Avg Perceptron and regret bound for Avg Pegasos. We show the effec tiveness of the proposed approaches by experimenting on various data sets and comparing them with the standard Perceptron and Pegasos.

We present a new algorithm, which we call PROBE, to find the minimum of a convex function. Such a minimization is important in many machine learning methods, including Support Vector Machines (SVM). We show that PROBE is a viable alternative to published algorithms for SVM learning with several important advantages. PROBE is a simple and easily programmed algorithm, with a well-defined, parametrized stopping criterion; it is not limited to SVM, but can be applied to other convex loss functions, such as the Huber and Maximum Entropy models; and its time and memory requirements are consistently modest in handling very large training sets.

We present a method to stop the evaluation of a decision making process when the result of the full evaluation is obvious. This trait is highly desirable for online margin-based machine learning algorithms where a classifier traditionally evaluates all the features for every example. We observe that some examples are easier to classify than others, a phenomenon which is characterized by the event when most of the features agree on the class of an example. By stopping the feature evaluation when encountering an easy to classify example, the learning algorithm can achieve substantial gains in computation. Our method provides a natural attention mechanism for learning algorithms. By modifying Pegasos, a margin-based online learning algorithm, to include our attentive method we lower the number of attributes computed from $n$ to an average of $O(\sqrt{n})$ features without loss in prediction accuracy. We demonstrate the effectiveness of Attentive Pegasos on MNIST data.