PaperlayerView exact revision on arXiv

Source-linked AI summary

Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing

Ryan Babbush, Vasil Denchev, Nan Ding, Sergei Isakov, Hartmut Neven

arXiv:1406.4203v1cs.LGquant-ph

TL;DR

Training noisy binary classifiers requires objectives that retain robustness without losing compatibility with quantum-annealing hardware. The paper constructs cubic and sixth-order polynomial non-convex losses whose risks compile to PUBO and evaluates their robustness and performance. These losses show robustness to label noise and advantages over convex methods, while their evaluation cost can be independent of the number of training examples.

  • Problem

    Training with convex losses can produce poor classifiers under high label noise, while direct 0-1 empirical-risk minimization is NP-Hard.

    Source: §1.2 · p. 2

  • Method

    The paper derives cubic and sixth-order polynomial loss functions of the margin and maps their empirical-risk objectives to PUBO representations compatible with quantum annealing.

    Source: §1.2 · p. 2, §4 · p. 8

  • Results

    Test error for cubic loss does not depend strongly on label noise up to 45%, and sixth-order loss outperforms all tested convex losses on all real data sets.

    Source: §2 · p. 4, §3 · p. 6

  • Takeaways & Limitations

    Polynomial losses can provide robust non-convex classifiers while allowing objective evaluations independent of the number of training examples.

    Source: §2 · p. 4, §5 · p. 8

    Both losses are highly parameterized and imperfect approximations to 0-1 loss, and sixth-order loss performs poorly on the Long-Servedio synthetic data set.

    Source: §3 · p. 6, §5 · p. 8

Abstract

from arXiv · show

Quantum annealing is a heuristic quantum algorithm which exploits quantum resources to minimize an objective function embedded as the energy levels of a programmable physical system. To take advantage of a potential quantum advantage, one needs to be able to map the problem of interest to the native hardware with reasonably low overhead. Because experimental considerations constrain our objective function to take the form of a low degree PUBO (polynomial unconstrained binary optimization), we employ non-convex loss functions which are polynomial functions of the margin. We show that these loss functions are robust to label noise and provide a clear advantage over convex methods. These loss functions may also be useful for classical approaches as they compile to regularized risk expressions which can be evaluated in constant time with respect to the number of training examples.

1. Introduction

Quantum annealing offers a controllable quantum approach to optimization, but training noisy binary classifiers requires objectives that balance robustness with hardware-compatible compilation. The paper develops polynomial non-convex losses whose empirical risks map to PUBO while avoiding variable counts that grow with the number of training examples.

1.1. Quantum annealing

  • Quantum annealing uses quantum resources to search for low-energy configurations of programmable binary systems, although worst-case NP-Hard optimization is not expected to be efficiently solvable.The approach is motivated by evidence that tunneling and entanglement can help on some otherwise difficult problem instances.Source: §1.1 · p. 1

1.2. Training under non-convex loss

  • Polynomial non-convex losses are investigated because convex optimization can yield poor classifiers under high label noise, while non-convex training can remain robust even when nearly half the examples are mislabeled.Minimizing 0-1 empirical risk is NP-Hard, motivating approximate objectives that retain robustness while remaining suitable for heuristic optimization.Source: §1.2 · p. 2
  • The paper replaces an earlier embedding whose variable count was lower-bounded by the number of training examples with a polynomial-loss embedding independent of dataset size.The earlier scheme was considered impractical for medium-scale annealers because of its qubit overhead.Source: §1.2 · p. 2
  • Polynomial functions of the margins produce empirical risks expressible as PUBO, which can be reduced to QUBO using boolean ancilla variables for quantum-hardware compatibility.The resulting objective can be evaluated in an amount of time that does not depend on the number of training examples.Source: §1.2 · p. 2
  • Third-order and sixth-order polynomial losses are studied because cubic is the lowest non-convex degree, while sixth-order more closely resembles 0-1 loss than quartic loss.The paper derives optimal forms, evaluates robustness to label noise, and maps polynomial risk objectives to PUBO tensors.Source: §1.2 · p. 2

2. Cubic loss

The cubic-loss embedding approximates 0-1 risk under ℓ2 regularization by fitting a cubic polynomial to the empirical risk over a Gaussian margin prior. Its coefficients can be computed analytically from training-set correlations, while synthetic experiments show robustness to substantial label noise.

Cubic-loss construction

  • The cubic loss is derived by fitting a polynomial risk function to 0-1 risk under an ℓ2-norm regularizer and Gaussian prior on the weights.The margin vector is modeled as multinormal, enabling analytical integration over the relevant marginal and joint distributions.Source: §2 · pp. 2–3
  • The fitted cubic objective selects α ∈ R4 to minimize the ℓ2 distance between the cubic approximation and 0-1 risk.Fitting the loss function directly would be simpler, but the paper describes that alternative as less useful than embedding the full risk function.Source: §2 · pp. 2, 4

Limitations

  • A maximum-weight scale must be chosen as a hyperparameter because excessively large weights can let the unbounded cubic term overwhelm the quadratic regularizer.The cutoff prevents large negative margins from producing cubic losses that overcome regularization.Source: §2 · p. 3

Coefficient derivation

  • The optimal cubic coefficients are obtained analytically from pairwise margin correlations, then summed across training-example pairs for the full dataset.The resulting coefficient computation has a stated complexity of O… in the supplied passage.Source: §2 · pp. 3–4

Real-data fits

  • Figure 1 shows that different real datasets require unique cubic-loss coefficients because their correlation matrices differ.The figure presents cubic-loss fits for several UCI Machine Learning Repository datasets.Source: Figure 1 · p. 4, §2 · p. 4

Synthetic evaluation

  • Up to 45% label noise, test error remains largely insensitive to label corruption for both the best fifty cubic-loss states and the absolute ground state.The embedding is somewhat noisy because it does not perfectly approximate 0-1 loss, but it shows an advantage over convex methods when label noise is substantial.Source: §2 · p. 4

3. Sixth-order loss

The sixth-order loss uses a fixed highest-order coefficient to avoid the divergence problem of cubic loss while providing a polynomial approximation to 0-1 loss. Across tested real data, it outperforms convex methods, though it performs poorly on the pathological Long-Servedio data set.

Loss construction

  • Cubic loss requires a fixed weight-scale hyperparameter because large negative margins can make the loss diverge faster than ℓ2 regularization penalizes weights.A cutoff on the maximum weight is therefore needed to prevent the cubic term from overwhelming the regularizer.Source: §3 · p. 4
  • For an even-degree polynomial loss, the highest-order coefficient ω is fixed as a hyperparameter because embedding odd 0-1 risk causes the even terms to vanish; the analysis then considers sixth-order loss.Source: §3 · p. 5
  • The sixth-order coefficients are obtained by fitting the loss function directly after evaluating its defining integral and solving ∇I6 = 0.The resulting loss functions are shown for multiple values of ω.Source: §3 · p. 6, Figure 3 · p. 6

Empirical evaluation

  • Sixth-order loss outperforms all tested convex losses on every real data set and performs similarly to other non-convex methods.The evaluation uses simulated annealing as a stand-in for quantum annealing and 10-fold cross-validation.Source: §3 · p. 6
  • Sixth-order loss performs poorly on Long-Servedio because extremely large margins dominate risk minimization and force smaller margins near zero.The authors believe this pathological behavior is unlikely in real data.Source: §3 · p. 6
  • On three of four real data sets, sixth-order loss also outperforms the other non-convex methods.The comparison uses the test-error results shown in Figure 4.Source: §3 · p. 6

4. Explicit tensor construction

The explicit construction maps fixed-point binary weight variables into a degree-k PUBO tensor representation of regularized empirical risk. The resulting formulation supports reduction to QUBO with ancilla requirements independent of the number of training examples.

Binary encoding

  • Fixed-point encoding uses d bits per feature, yielding N = nd binary variables for the weight vector.Floating-point representations are avoided because they require a non-polynomial function of the bits.Source: §4 · p. 6
  • The binary coefficient matrix maps the state vector q to continuous weights through w = k̂q and tiles the encoded weights across features.The construction uses a stair-step pattern induced by an identity-matrix Kronecker product.Source: §4 · pp. 6, 8

PUBO construction

  • A degree-k PUBO is represented as vᵀq^⊗k, and the cubic construction extends directly to polynomial orders below or above three.Here q^⊗k is the kth tensor power of the binary state vector.Source: §4 · p. 8
  • The continuous empirical-risk expression is expanded through the binary encoding and its terms are combined into a common tensor representation.Lower-rank tensors are embedded into the higher-rank tensor after conversion to binary.Source: §4 · p. 8

QUBO reduction

  • The tensor construction can be reduced to QUBO using ancilla variables, with general degree-k quadratization bounded by O(·).The cubic tensor reduction is identified as the most computationally expensive part of the procedure.Source: §4 · p. 8
  • The ancilla requirement is independent of the number of training examples, and the tensor objective can be evaluated in time independent of that number.This removes the training-example-dependent overhead associated with prior encodings.Source: Figure 4 · p. 7, §4 · p. 8

5. Conclusion

The paper introduces cubic and sixth-order non-convex loss functions that are robust to label noise and outperform convex training methods, while retaining efficient embedding properties for quantum annealing.

  • Cubic and sixth-order losses show clear robustness to label noise and outperform classically tractable convex training methods.Both are non-convex and approximate 0-1 loss imperfectly.Source: §5 · p. 8
  • Polynomial losses can be compiled so each objective query is independent of the number of training examples, supporting heuristic optimization and quantum-annealing embeddings with reasonable qubit requirements.The resulting Hamiltonian is suitable for quantum annealing, although non-convex training remains formally NP-Hard.Source: §5 · p. 8

6. Appendix

The appendix describes an ℓ0 regularizer, evaluates convergence of cubic-loss embeddings, and catalogs resource, data, and hyperparameter information for the experiments.

6.1. ℓ0-norm regularization

  • ℓ0-norm regularization uses ancilla indicator bits to penalize nonzero weights and can be combined with the empirical risk objective.The construction enforces the regularizer when φ is sufficiently larger than λ0.Source: §6.1 · p. 9

6.3. Convergence of cubic loss function

  • Cubic loss correlates more closely with 0-1 loss than the convex losses in the adult9 comparison.The risks are computed over 104 randomly selected states and 104 training examples after normalization.Source: Figure 5 · p. 10, §6.3 · p. 10
  • 0.107, 0.0818, 0.062 and 0.055 are the embedding errors for 10, 100, 1,000 and 10,000 training examples, respectively, in the cubic-loss adult9 evaluation.Figure 6 measures empirical-risk embedding error using sampled states and also examines the lowest-energy subspace.Source: §6.3 · p. 11, Figure 6 · p. 11

6.4. Estimated qubit requirements

  • The appendix reports upper-bounds on qubit requirements for selected problems.The supplied material identifies the table but does not provide its numerical entries.Source: Table 1 · p. 12

6.6. Hyperparameters

Loading 1406.4203v1…