{"id":"ca9680f4-343e-41e0-8f0b-89e131870b4d","arxiv_id":"2505.17765","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A dual block-coordinate trust-region solver with random Fourier features trains KRR, KLR, and SVM on millions of samples with 1 to 5 GB GPU memory and accuracy matching or beating Falkon, EigenPro3, and ThunderSVM.","lead":"Joker is a unified optimization framework that trains several kernel machine models with much lower memory than existing large-scale methods. It combines a dual block coordinate trust-region solver with random Fourier features, reaching similar or better accuracy on million-scale datasets using a single consumer GPU.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim depends on DBCD-TR reaching near-optimal dual solutions within fixed budgets, but no convergence proof or KKT certificate is given; a final-iterate stationarity check would settle whether the reported accuracy is attributable to the solver.","rationale":"I read the paper as an empirical systems contribution: a dual BCD solver with trust region and RFF that scales kernel methods to millions of points on a 10GB GPU. The dual derivations in Theorem 1 and Table 2 check out for KRR, L2-SVC, SVR, and KLR (the KLR expression in Section 3.2 differs from the exact conjugate term by a constant (n/λ)log λ, so the minimizer is unchanged). The complexity analysis in Table 3 is coherent, and the memory claims are plausible from the reported settings. The main soft spot is not the duality or the experiments; it is the absence of any convergence certificate for DBCD-TR. The paper itself flags this in Section 5, and Algorithm 2 is explicitly heuristic. Since the central claim is that Joker reaches the same or better accuracy as strong baselines within fixed budgets, the solver's ability to actually minimize (4) is load-bearing. The KKT-residual check I propose would empirically settle whether the reported final iterates are near-stationary. If the residuals are small, the reader's CONDITIONAL verdict can stand with the requested proof and reproducibility conditions; if not, the framework's performance claims would need to be re-attributed to early stopping rather than to convergence of the proposed optimizer.","tokens_in":20005,"tokens_out":14155,"duration_ms":154756,"concrete_test":"Compute a block-wise projected-gradient KKT residual for the final iterates of Joker-KRR, Joker-SVM, and Joker-KLR on HIGGS using the exact Table A.3 settings: res_i = |α_i − clip(α_i − ∇J_i(α), τ^L_i, τ^U_i)| and report res_max / max(1, ||α||_∞). If this normalized residual exceeds 1e-2 for any model, convergence to the dual solution is not empirically established and the accuracy numbers should be interpreted as early-stopping results; if it is below 1e-3, the convergence concern is settled for the reported workloads.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing assumption is that DBCD-TR, within the fixed iteration and block-size budgets, returns near-optimal solutions of the dual problem (4). The paper explicitly leaves this open: Section 5 states 'the convergence speed of DBCD-TR is still unclear', and Algorithm 2 is a heuristic truncated CG-Steihaug method that breaks on box violations and then projects the step. Algorithm 1's trust-region acceptance/rejection plus projection can produce zero or clipped steps, and no monotone-decrease argument or KKT-residual certificate is provided. The empirical evidence in Figure 3 shows dual/primal objective plots for only two settings (MSD exact KRR, HIGGS inexact KLR), not for all models and datasets in Table 4. If the solver stops far from optimality for Joker-KLR or Joker-SVM on HIGGS or CIFAR-5M, the reported accuracy and timing do not establish the framework's superiority; the results could be an artifact of early stopping. For KLR the situation is sharper: Section 3.2 caps the Hessian at ε^{-1/2} and truncates the feasible region to ε ≤ bα_i ≤ 1/λ − ε, changing the subproblem and making the route to a stationary point of (4) heuristic.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Joker, a joint optimization framework for large-scale kernel machines that covers KRR, Huber regression, KLR, SVC, and SVR through a common dual formulation. The dual problem is solved by a dual block coordinate descent method with a trust-region subproblem solver (DBCD-TR), and the inexact variant replaces the kernel with random Fourier features. Experiments on MSD, HEPC, SUSY, HIGGS, and CIFAR-5M report lower GPU memory than Falkon, LogFalkon, EigenPro3, and ThunderSVM, with comparable or better accuracy and competitive training time. The dual derivation in Appendix A is standard and appears correct, and the code is released.","tokens_in":20301,"tokens_out":4861,"duration_ms":39161,"significance":"If the solver-convergence concern is resolved, this is a useful engineering contribution: a single dual BCD trust-region solver uniformly handles several kernel models, the inexact variant achieves large-scale results on a consumer GPU, and the empirical comparison is broad, with multiple baselines, error bars, and public datasets. The released code and the use of standard benchmarks strengthen reproducibility. However, the central empirical claims depend on DBCD-TR reaching near-optimal dual solutions within the reported budgets, and that point is currently unsupported; the significance of the results is therefore conditional on added convergence evidence or a proof.","major_comments":[{"comment":"The manuscript itself states in Section 5 that \"the convergence speed of DBCD-TR is still unclear,\" and Section 2.2 introduces Algorithm 2 as \"a heuristic truncated CG-Steihaug method\" that terminates early on box violations and then projects the step. Because Algorithm 1 can reject steps and leave the block unchanged, there is no demonstrated monotone-decrease or stationarity guarantee, and no KKT residual or duality gap is reported for the runs in Table 4. Figure 3 shows primal/dual objective plots for only two settings (MSD exact KRR and HIGGS inexact KLR), so the reader cannot tell whether the reported accuracy and timing for Joker-KLR or Joker-SVM on the other datasets reflect solver quality or early stopping. I request either a convergence proof for DBCD-TR or, at minimum, final-iterate KKT residuals / duality gaps for every model-dataset combination in Table 4, together with a sensitivity check (e.g., doubling the iteration budget) on at least HIGGS and CIFAR-5M.","section":"Section 5, Algorithm 2, Figure 3"},{"comment":"For KLR, the feasible region is redefined as ε ≤ bα_i ≤ 1/λ − ε and the Hessian is capped via H̃_ii = min(∇²f(bα_B)_ii, ε^{-1/2}). This changes the dual objective that is actually minimized. The paper does not prove that a stationary point of this modified problem is close to a stationary point of the original KLR dual (4). Since the KLR results in Table 4 are produced with this modified problem and a larger block size, the reported KLR accuracy cannot be directly attributed to solving the original dual problem. Please provide a quantitative bound or an empirical verification (for example, reporting both the modified and true objective values at termination) that the truncation and Hessian cap do not materially change the solution.","section":"Section 3.2"},{"comment":"For the nonsmooth SVR case, the trust-region subproblem is derived by replacing the ℓ1 term with sign(α_B)ᵀs, which is exact only when the signs of α_B and α_B + s agree. The text argues that this requires a sufficiently small trust-region radius, but it does not give a bound or a mechanism that enforces sign consistency, and no safeguard is described for cases where the projected truncated CG step crosses zero. Because the Joker-SVM results on MSD and HEPC in Table 4 rely on this approximation, the paper should either justify that the signs are preserved in practice (e.g., report sign-change statistics) or replace the approximation with a proximal trust-region step that handles the nonsmooth term exactly.","section":"Appendix B.2"}],"minor_comments":[{"comment":"There is a typo in the paragraph after Equation (10): \"e can find a comprehensive summary\" should read \"We can find a comprehensive summary.\"","section":"Section 2.3"},{"comment":"The heading \"Details of Dual Block Coordinate Descent with T rust Region\" contains a typo: \"T rust\" should be \"Trust.\"","section":"Appendix B heading"},{"comment":"The abstract claims memory savings \"up to 90%,\" but the largest datasets in Table 4 show about 81% savings on HIGGS (9.9 GB vs. 1.9 GB) and about 46% on CIFAR-5M (9.9 GB vs. 5.3 GB). The claim should state the exact comparison basis (e.g., the >50 GB Falkon configuration in Table 1) so the reader can reconcile it with the measured numbers in Table 4.","section":"Abstract and Table 4"},{"comment":"In the sentence starting \"Falkon-based methods are the fastest and have a substantial gap compared to EigenPro3 and ThunderSVM,\" the intended contrast is clear but the wording is awkward; consider rewriting to say that Falkon is fastest, EigenPro3 and ThunderSVM are much slower, and Joker sits between them.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the missing convergence certificate for the core solver; this is not a novelty problem but a soundness-of-evidence problem. The paper would benefit from a short convergence analysis or, failing that, a systematic stationarity check across all reported configurations. I do not see signs of circularity or data leakage; per-dataset hyperparameter tuning is standard in this literature. The fit with the journal's scope is appropriate for a systems/optimization contribution, provided the empirical claims are backed by solver verification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this if you work on large-scale kernel methods. Joker is a unified dual block-coordinate descent with trust region (DBCD-TR) framework that covers KRR, Huber, L2-SVC, SVR, and KLR, using random Fourier features for the inexact variants. The experiments are extensive: five datasets up to 10^7 samples, baselines Falkon, LogFalkon, EigenPro3, ThunderSVM, with error bars and memory/time. The results are plausible and often strong. The code is available.\n\nWhat is genuinely new: the joint treatment, not the individual pieces. The Fenchel dual derivation is standard, but Proposition 2 (infimal convolution) is a clean way to handle Huber and other losses. The complexity analysis is useful. DBCD-TR is a sensible heuristic combining trust region with block updates, and the paper honestly says in Section 5 that the convergence speed is unclear.\n\nSoft spots: the lack of convergence analysis is load-bearing. Algorithm 2 is a truncated CG with projection and a heuristic break on box violations. For KLR, the feasible region is truncated (epsilon <= balpha_i <= 1/lambda - epsilon) and the Hessian is capped at epsilon^{-1/2}, so it is not exactly solving the original dual. There is no KKT residual or final-iterate stationarity check in the experiments. Figure 3 shows primal/dual plots for only two settings (MSD exact KRR and HIGGS inexact KLR), not for all models. Without such evidence, it is hard to rule out early stopping as the source of reported accuracy for the harder cases (e.g., Joker-KLR on HIGGS). Hyperparameters are tuned per dataset, which is common but should be disclosed with a validation protocol.\n\nThe paper is honest and the empirical contribution is real. The central claim—training kernel machines on consumer hardware with comparable accuracy—is likely true when the solver works, but the solver's reliability is unproven. That makes the paper conditional, not wrong. I would accept it for peer review with a request for stationarity measurements (dual gap or KKT residual) and a more detailed ablation of trust-region settings.\n\nI'd bring it to reading group as a representative example of current large-scale kernel practice, and I'd cite it for the unified dual formulation and memory comparison. Recommend: serious referee, with the caveat above.","headline":"Joker is a credible empirical framework for large-scale kernel machines; its missing convergence analysis and lack of stationarity checks are real weaknesses, but not fatal to the practical claim.","tokens_in":20831,"tokens_out":2763,"would_cite":true,"duration_ms":24810,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","90C25","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that one dual block-coordinate-descent trust-region solver with random Fourier features trains KRR, KLR, and SVM on up to 10^7 samples using 0.7–5.9 GB GPU memory, with accuracy at or above Falkon, LogFalkon, EigenPro3…","keywords":["kernel methods","dual block coordinate descent","trust region","random Fourier features","large-scale learning","kernel ridge regression","kernel logistic regression","support vector machines"],"falsifier":"Take a medium dataset such as a $10^{5}$-sample subset of HIGGS, compute the exact dual optimum of problem (4) for KRR and KLR with a certified solver, run Joker with the paper's default iteration and block-size budgets, and check whether the dual objective approaches that optimum; if the gap remains large or validation accuracy is substantially below the exact solution, the convergence premise fails.","tokens_in":19787,"feed_emoji":"⚙️","tokens_out":7368,"duration_ms":62444,"temperature":0.7,"pith_summary":"The paper tries to show that a single optimization scheme can train the major kernel machines—kernel ridge regression, kernel logistic regression, and support vector machines—at scales up to roughly ten million samples on one consumer GPU. Its route is a dual formulation in which every listed model becomes the same kind of box-constrained quadratic-plus-conjugate problem, solved by a dual block coordinate descent method whose block steps are taken by a trust-region procedure. With random Fourier features replacing exact kernel evaluations, the method stores only the current block kernel and a maintained weight vector, which is why memory stays around 0.7–5.9 GB. The reported experiments on MSD, HEPC, SUSY, HIGGS, and CIFAR-5M show accuracy comparable to or better than Falkon, LogFalkon, EigenPro3, and ThunderSVM in similar or shorter time while using far less memory.","feed_headline":"One solver trains kernel models on 10M samples in low GPU memory","feed_subtitle":"Joker unifies KRR, logistic regression, and SVM, cutting memory by up to 90% while matching or beating current methods.","key_machinery":"The central object is the Fenchel-conjugate dual problem of Theorem 1, which converts each kernel model's primal regularized risk into a convex box-constrained problem whose Hessian is the kernel matrix. The carrying mechanism is DBCD-TR: block coordinate descent over fixed random blocks, with each block subproblem solved by a trust-region method—Algorithm 1 constructs a quadratic model using the block kernel and the Hessian of the conjugate loss, and Algorithm 2, a truncated CG-Steihaug method, computes a step inside the trust radius and projects it onto the box constraints. For inexact Joker, the random Fourier feature map $\\psi(x)=\\sqrt{2/M}\\cos(Wx+b)$ supplies a finite-dimensional approximation, so the full kernel-gradient product $K_{B,:}\\alpha$ becomes $\\psi(X_B)^\\top \\theta$ and the maintained weight vector $\\theta$ is updated incrementally after each block step. This reduces space to $O(|B|^2 + Md)$ and avoids the $O(M^2)$ preconditioner storage of Nyström-based methods, which is the concrete bottleneck the paper targets.","core_discovery":"On the paper's own terms, Joker establishes that a single dual problem—minimizing $\\frac{1}{2}\\alpha^\\top K\\alpha + \\frac{1}{\\lambda}\\sum_i \\xi^*_{y_i}(-\\lambda \\alpha_i)$ over box constraints—captures KRR, Huber regression, L2-SVC, SVR, and KLR through their Fenchel conjugates. The authors derive this as Theorem 1, then solve it by DBCD-TR: each iteration picks a block $B$, forms a quadratic model with kernel block $K_{B,B}$ and gradient $K_{B,:}\\alpha$, and takes a trust-region step computed by a truncated CG-Steihaug method with projection onto the box. For inexact Joker, random Fourier features $\\psi(x)=\\sqrt{2/M}\\cos(Wx+b)$ make the expensive gradient reduce to $\\psi(X_B)^\\top \\theta$, with $\\theta$ maintained incrementally after each block update. The paper reports that this combination trains all three model families on datasets with $n$ up to $1.1\\times 10^7$ using 0.7–5.9 GB GPU memory, with accuracy at or above the compared state-of-the-art methods in most cases, including better HIGGS and CIFAR-5M accuracy than Falkon, EigenPro3, and ThunderSVM.","pith_inferences":["Beyond the paper's own claims, the practical reach of Joker likely depends on DBCD-TR's unproved convergence behavior: on a dataset whose dual is badly scaled or whose proposed block steps are frequently rejected by the trust-region ratio, the fixed iteration budget may be far too small.","The same duality recipe using infimal convolutions of losses could extend to other composite losses and to multi-class machines, but the equality constraints of multi-class SVM and softmax would require a different subproblem solver than the box-constrained one used here.","Because the accuracy of inexact Joker is tied to the number of random Fourier features $M$, a natural testable extension is to plot test accuracy versus $M$ for each model family to see where the framework's memory savings start to cost generalization."],"forward_implications":["Kernel logistic regression and SVM become as scalable as kernel ridge regression, because the same solver and the same per-iteration cost apply to classification losses.","A single RTX 3080 (10 GB) suffices for datasets with up to roughly 10^7 samples, whereas Falkon and LogFalkon need more than 50 GB at comparable model size.","Training time drops relative to EigenPro3 and ThunderSVM: on HIGGS, Joker-SVM converges in about one hour where EigenPro3 takes about 18 hours and ThunderSVM times out after a week.","The exact version of Joker stays competitive on medium datasets (about 5×10^5 samples), using under 1 GB of GPU memory and giving the best MSD relative error among the compared methods."],"supporting_citations":[{"why":"Falkon supplies the main KRR baseline and the Nyström-based approach whose memory bottleneck Joker targets.","marker":"[RCR17]"},{"why":"Provides the Falkon/LogFalkon state of the art, the HIGGS result at M=10^5 requiring over 50 GB, and the memory-versus-performance dilemma Joker claims to break.","marker":"[MCRR20]"},{"why":"LogFalkon is the large-scale KLR baseline whose Newton solver has the same memory issue as Falkon.","marker":"[MBR19]"},{"why":"EigenPro3 is the low-memory KRR baseline that Joker compares against in time and accuracy.","marker":"[ABP23]"},{"why":"ThunderSVM is the GPU SVM baseline that Joker-SVM must match or exceed in time and accuracy.","marker":"[WSL+18]"},{"why":"Random Fourier features are the kernel approximation technique that inexact Joker relies on for its O(Md) gradient evaluation.","marker":"[RR07]"},{"why":"The CG-Steihaug trust-region step is what Algorithm 2 truncates and projects, providing the solver's step-quality mechanism.","marker":"[Ste83]"},{"why":"Block coordinate descent theory is used to justify the block-size choices and the expected linear-rate bound for DBCD-TR.","marker":"[NLS22]"},{"why":"Provides the Fenchel-conjugate and infimal-convolution identities behind the unified dual problems in Theorem 1 and Proposition 2.","marker":"[Bec17]"}],"fun_headline_variants":["Kernel learning unified: one solver for KRR, SVM, and logistic regression","Joker trains kernel models on 10M samples with 90% less memory","Low-memory kernel training: Joker unifies KRR, SVR, and KLR","One dual problem fits many kernel models, minus the memory cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that DBCD-TR actually reaches a near-optimal solution of the dual problem within the chosen iteration and block-size budgets; the paper does not prove this—Section 5 says the convergence speed of DBCD-TR is still unclear and Algorithm 2's truncation and projection are heuristic—so if those steps stall on KLR or SVR on the tested data, the reported accuracy and timing claims do not support the framework's stated superiority.","fun_headline_variants_meta":{"raw":{"variants":["Kernel learning unified: one solver for KRR, SVM, and logistic regression","Joker trains kernel models on 10M samples with 90% less memory","Low-memory kernel training: Joker unifies KRR, SVR, and KLR","One dual problem fits many kernel models, minus the memory cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000257,"raw_usage":{"total_tokens":1597,"prompt_tokens":982,"completion_tokens":615,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":598,"completion_tokens_details":{"reasoning_tokens":529}},"tokens_in":598,"tokens_out":615,"duration_ms":5042,"temperature":1.0,"reasoning_tokens":529,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:41:06.057119+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a medium dataset such as a $10^{5}$-sample subset of HIGGS, compute the exact dual optimum of problem (4) for KRR and KLR with a certified solver, run Joker with the paper's default iteration and block-size budgets, and check whether the dual objective approaches that optimum; if the gap remains large or validation accuracy is substantially below the exact solution, the convergence premise fails.","supporting_citations":[],"review_version":1}