{"id":"10e1d13e-9d95-490e-807a-1ed7b02eb5fa","arxiv_id":"2608.04324","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Lexi-LowGLM learns lexicographic generalized low-rank matrix bandits with regret that scales with the effective low-rank dimension and uses online updates that reduce cost from O(T^2) to O(T).","lead":"This paper gives an algorithm for online decisions where each choice is a matrix and rewards are several goals with strict priority. It claims near-optimal learning with computation that grows linearly, not quadratically, in the number of rounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed O~((d1+d2)r√T) regret requires an unstated lower bound on D_rr and oracle knowledge of it; both the parameter setting and the final rate break when D_rr is small or misestimated.","rationale":"I read the paper in good faith and find the central construction — objective-specific subspace estimation followed by lexicographic filtering with online Newton-type updates — technically plausible and a genuinely useful combination. The claimed O(T) estimator-update complexity is credible because each online step solves a fixed-dimension proximal problem, and the objective-wise regret decomposition in Lemma 10/11 is internally consistent. The weakest point is exactly the role of D_rr, which the reader also identified. I would go slightly further: the issue is not only that the learner must know D_rr to set T1 and S⊥, but that the final rate in Theorem 1 and Theorem 2 is only obtained by an unstated lower-bound condition on D_rr. The proofs explicitly contain the line 'under the standard scaling condition sqrt(M(d1+d2)r)/D_rr ≲ (d1+d2)r' and then drop the 1/D_rr term; this condition does not appear in the theorem hypotheses or in Assumptions 1–6. Since D_rr can be arbitrarily small for a rank-r matrix satisfying all stated assumptions, the advertised dimension dependence is not uniform in the problem instance. The secondary experimental issue — continuous exploration distribution used with a discrete arm set — is real but less central; it can be repaired by either assuming a continuous exploration set contained in the arm set or by re-running experiments with a discrete exploration design that satisfies Assumption 6. Overall, the reader's CONDITIONAL verdict is appropriate. I do not see a fatal flaw in the reduction itself, but the theoretical guarantee should be restated as conditional on a known or lower-bounded D_rr, and the hidden scaling condition should be made an explicit assumption. For these reasons I agree with the conditional verdict and do not propose a change.","tokens_in":26563,"tokens_out":19197,"duration_ms":193985,"concrete_test":"Re-derive the final step of the proof of Theorem 2 without using the displayed 'standard scaling condition' sqrt(M(d1+d2)r)/D_rr ≲ (d1+d2)r. If the resulting bound contains an explicit sqrt(M(d1+d2)r)/D_rr term that is not dominated by k=(d1+d2)r−r^2, then the theorem as stated is false without an additional assumption. Independently, run a rank-1 synthetic instance with d1=d2=10 and Θ*_1 = ε e1 e1^T for ε=1 and ε=0.01, using the prescribed T1, λ⊥, S⊥ formulas with the true D_rr=ε; if the ε=0.01 case requires T1 ≥ T or yields empirical regret far exceeding (d1+d2)r√T, the missing assumption is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorem statements in Section 4.2–4.3 claim regret O~(W_i^lex sqrt(m)(d1+d2)r sqrt(T)) for every objective, but the proof of both Theorem 1 and Theorem 2 depends critically on D_rr, the minimum r-th singular value of the objective parameter matrices. Specifically, the configuration prescribed in Theorem 1 sets T1 ∝ sqrt(M(d1+d2)rT)/D_rr and S⊥ = M(d1+d2)r log(...)/(T1 D_rr^2). These are not benign constants: the subspace tail bound in Lemma 3 is S⊥, and if D_rr is overestimated, S⊥ is too small, the high-probability event in Lemma 4/9 fails to contain the true parameter, and the confidence widths are invalid. If D_rr is unknown, the learner cannot choose T1 or S⊥ at all. Moreover, even with oracle knowledge of D_rr, the proof's final step silently invokes the displayed 'standard scaling condition' sqrt(M(d1+d2)r)/D_rr ≲ (d1+d2)r to drop a 1/D_rr term. This condition is not stated among Assumptions 1–6. When it fails, the regret bound derived in the proof is O~(W_i^lex sqrt(m)(k + sqrt(M(d1+d2)r)/D_rr) sqrt(T)), which can exceed the advertised low-rank rate and can even make T1 larger than T. Since the central claim is that the regret depends on the intrinsic dimension (d1+d2)r rather than the ambient d1d2, the hidden D_rr dependence is load-bearing: it is exactly the quantity that determines whether the low-rank advantage is realized. The paper provides no practical estimator or adaptive choice for D_rr, so as stated the guarantee is conditional on an unverifiable oracle.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces lexicographic generalized low-rank matrix bandits, a multi-objective bandit setting in which each objective has its own low-rank generalized linear model and the learner uses a lexicographic preference order. The authors propose two algorithms: Scalar-LowGLM, a scalarized batch-estimation baseline, and Lexi-LowGLM, which combines objective-specific subspace estimation, sequential lexicographic arm filtering, and online Newton-style estimator updates. For both algorithms they state objective-wise regret bounds of O~(W (d_1+d_2) r sqrt(T)) with W depending on the lexicographic trade-off parameter w, and they claim that Lexi-LowGLM reduces the cumulative estimator-update complexity from O(T^2) to O(T). The proofs follow a three-stage structure: subspace estimation via a nuclear-norm regularized Stein-type estimator, confidence sets for (batch or online) generalized linear estimators in a transformed feature space, and a lexicographic filtering argument. Numerical experiments on synthetic rank-one and rank-two instances compare the proposed methods with G-ESTT and MTLO.","tokens_in":1803,"tokens_out":1854,"duration_ms":73589,"significance":"If the stated guarantees were fully established, this would be a useful contribution: it extends low-rank matrix bandits to multiple lexicographically ordered objectives and obtains a dimension dependence on the intrinsic rank parameter (d_1+d_2)r instead of the ambient d_1 d_2, while also proposing an online estimator-update scheme that reduces the per-horizon computational cost relative to repeated batch refitting. The problem formulation and the algorithmic idea are clear and well motivated, and the paper explicitly provides regret theorems with a nontrivial filtering analysis for the lexicographic candidate set. However, the advertised low-rank rate is currently conditional on an unstated and practically unavailable oracle for D_rr (the minimum r-th singular value of the objective matrices) and on a 'standard scaling condition' that does not appear among Assumptions 1-6.","major_comments":[{"comment":"The parameter specification in Theorem 1 and the proof of Lemma 3 require the learner to know D_rr, the minimum r-th largest singular value of the objective parameter matrices, in order to set T1 and S_perp. D_rr is not an observable quantity, and no practical estimator or adaptive choice is provided. If D_rr is overestimated, S_perp is too small and the high-probability event in Lemma 3 fails, invalidating the confidence widths; if D_rr is underestimated, T1 may exceed T. Moreover, the final step of both proofs silently invokes the condition sqrt(M(d1+d2)r)/D_rr <= O((d1+d2)r) to drop the 1/D_rr term. This condition is not stated in Assumptions 1-6, and when it fails the derived bound is O~(W (sqrt(M(d1+d2)r)/D_rr + (d1+d2)r) sqrt(T)), which is not the advertised intrinsic-dimension rate. The theorems should either include an explicit lower-bound assumption on D_rr and the scaling condition, or state the regret bound with the full 1/D_rr dependence.","section":"Theorems 1 and 2 (Sections 4.2-4.3) and their proofs (Appendices B-C)"},{"comment":"The confidence-bound proof for the batch estimator uses the equality gt,i(theta_hat) = sum_tau y_tau x_tau as the first-order optimality condition for the estimator defined in Eq. (7), which includes the constraint ||theta||_2 <= S. If the constrained minimizer lies on the boundary, the KKT condition contains a Lagrange multiplier term and the displayed equality is not valid. This affects the derivation of the confidence radius beta_t and consequently the regret bound. The authors should either argue that the unconstrained minimizer is always inside the feasible ball (e.g., by choosing S appropriately), or redo the argument with the proper KKT conditions.","section":"Lemma 4 (Appendix B, Eq. (7))"},{"comment":"The claim that Lexi-LowGLM reduces the estimator-update complexity from O(T^2) to O(T) is not fully supported. Each round requires solving the constrained proximal problem in Eq. (10), a p-dimensional quadratic program with a ball constraint, yet the paper does not specify the solver, the number of iterations, or the per-round cost. If the proximal solve requires an iterative algorithm, the per-round cost may be polynomial in p and could dominate the T-round complexity. The O(T) claim is only justified if each update is shown to cost O(1) or O(p) with explicit constants; otherwise the computational contribution should be restated as a number-of-data-passes claim rather than a per-round complexity claim.","section":"Section 4.3, Eq. (10); Section 1 complexity claim"},{"comment":"Assumptions 3 and 4 refer to constants c_mu, L_mu, U that are uniform 'over the relevant domain', but the relevant domain is never defined. Since the link functions are evaluated at fi(X)^T theta for estimated parameters and at <X, Theta*> for the true parameters, the domain should be specified (e.g., a bounded interval implied by ||X||_F <= 1 and ||Theta*_i||_F <= S, along with the estimator norm constraint). Without this, the existence of the constants is not well posed.","section":"Assumptions 3-4"}],"minor_comments":[{"comment":"The theorems state the regret bound with probability 1-2*delta, but the proofs use delta in the individual concentration steps and union bounds; it would be helpful to state explicitly how the two delta terms in the exploration phase and the online phase are combined.","section":"Theorems 1 and 2"},{"comment":"The algorithm inputs include S_perp, but the formula for S_perp appears only inside the proof of Theorem 1. For reproducibility, the theorem statement should list the full parameter assignments for T1, S_perp, lambda_perp, and lambda_0 explicitly.","section":"Algorithm input and Theorem 1 parameter list"},{"comment":"The experiments are averaged over 10 trials but no error bars or standard deviations are shown, which makes it hard to judge the stability of the reported regret curves.","section":"Figures 1 and 2"},{"comment":"There are several minor typos and inconsistencies in the text, e.g., the use of '~O' versus 'O~' for the big-O notation, and the definition of W_sca in Theorem 1 uses (1+w)^(i-1) while the proof uses (1+w)^(m-j); these should be harmonized.","section":"Various equations"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a worthwhile problem and the algorithmic idea is natural, but the main theorems are currently conditional on an unverifiable oracle for D_rr and an unstated scaling condition, and the constrained-estimator proofs have a real gap. I would be willing to reconsider after the authors add explicit assumptions, repair the KKT argument, and clarify the complexity of the per-round proximal solve. The fit with cs.LG is appropriate if the issues are fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a legitimate new combination of lexicographic bandits and low-rank matrix structure, and the O(T) online estimator update is a real improvement over the batch refitting baseline. The problem is worth studying, and the algorithms are sensible. But the stress-test note is right: the advertised regret bound is conditional on knowing D_rr, the smallest r-th singular value across objectives, and on a scaling condition that the paper never states as an assumption.\n\nWhat is genuinely new: the formulation of lexicographic generalized low-rank matrix bandits, and the Lexi-LowGLM algorithm that combines lexicographic candidate filtering with Stein-type subspace estimation and online Newton steps. The regret bound O~(W_i^lex sqrt(m)(d1+d2)r sqrt(T)) has the right shape, matching the single-objective effective-dimension rate, and the complexity reduction from O(T^2) to O(T) is credible and demonstrated in the runtime table. The proofs are coherent and lean on standard machinery (Abbasi-Yadkori, Kang et al.). No circularity; the self-citations are appropriate.\n\nThe soft spots, in order of importance. First, Theorem 1 and Theorem 2 require the learner to set T1 and S_perp using D_rr. There is no estimator or adaptive scheme for it, and if D_rr is overestimated the subspace tail bound in Lemma 3 fails, which breaks the confidence widths. This is not a benign constant. Second, the proof's final step silently invokes sqrt(M(d1+d2)r)/D_rr <= (d1+d2)r to drop the 1/D_rr term. This condition is not in Assumptions 1-6; when it fails the bound becomes O~(W(k + sqrt(M(d1+d2)r)/D_rr) sqrt(T)), and T1 can even exceed T. That is load-bearing because it is exactly this condition that makes the low-rank dimension appear. Third, there is a concrete mismatch between the theorem statement and the proof for S_perp: the theorem writes S_perp = sqrt(M(d1+d2)r log)/(D_rr^2 T), but the proof uses S_perp = A/T1 = sqrt(A/T), which differs by a factor D_rr. One of them is a typo, but the paper should say which. Minor issues: the experiments sample a continuous exploration distribution while the arm set is finite and discrete, which Assumption 6 does not cover; there is no released code or data; Lemma 4 uses constrained first-order optimality without discussing boundary cases. The first minor issue is a real gap between theory and the empirical setup, but it is patchable.\n\nWho this is for: anyone working on multi-objective or low-rank bandits. It deserves a serious referee. I would send it out with a request to fix the D_rr dependence (state it as an assumption, or estimate it adaptively), reconcile the S_perp expression, and align the experiments with the modeled arm set. As written, the central theorem is conditional on an unstated oracle, but the underlying idea is sound and the revision path is clear.","headline":"New combination of lexicographic bandits and low-rank structure with a real online speedup, but the main regret bound needs an oracle D_rr and an unstated scaling condition.","tokens_in":27521,"tokens_out":4861,"would_cite":true,"duration_ms":40940,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Lexicographic low-rank matrix bandits are solved near-optimally with online updates.","keywords":["lexicographic bandits","low-rank matrix bandits","generalized linear bandits","multi-objective optimization","online Newton updates","subspace estimation","regret bound","computational efficiency"],"falsifier":"Run Lexi-LowGLM on a synthetic instance where the true minimum singular value $D_{rr}$ is ten times smaller than the value supplied to the algorithm, and track objective-wise regret and subspace estimation error over $T=10^5$; if the overestimate breaks the confidence intervals, the regret should stop following the claimed $\\widetilde{O}(\\sqrt{T})$ slope or the subspace error should exceed the theorem's bound.","tokens_in":26360,"feed_emoji":"🎯","tokens_out":8051,"duration_ms":75624,"temperature":0.7,"pith_summary":"The paper claims that lexicographic generalized low-rank matrix bandits—where the learner pulls matrix-valued arms and receives rewards for several objectives ordered by priority—can be solved with per-objective regret $\\widetilde{O}(W_i^{\\mathrm{lex}}\\sqrt{m}\\,(d_1+d_2)r\\sqrt{T})$ and with total estimator-update cost $O(T)$ instead of $O(T^2)$. The bound depends on the intrinsic low-rank dimension $(d_1+d_2)r$, not the ambient dimension $d_1d_2$, so the low-rank structure is preserved under lexicographic preferences. If true, multi-objective problems with matrix interactions can be learned at essentially the same rate as their single-objective counterparts, with only a lexicographic trade-off factor and a $\\sqrt{m}$ factor in the bound. The paper also gives a scalarized batch baseline to separate the value of lexicographic filtering from the value of online updates.","feed_headline":"Low-rank matrix bandits keep square-root-T regret","feed_subtitle":"Priority-ordered objectives learn at the intrinsic dimension, and online updates cut computation from quadratic to linear.","key_machinery":"The argument is carried by three components. Objective-specific Stein-type subspace estimation solves a nuclear-norm regularized loss on score-transformed exploration samples to obtain estimates of each parameter matrix's row and column subspaces, with error controlled by $T_1$ and by $D_{rr}$, the smallest $r$-th singular value across all objective matrices. A transformed feature map $f_i(X)$ rotates the arm into the estimated subspaces and vectorizes four blocks, so the first $k=(d_1+d_2)r-r^2$ coordinates carry the low-rank signal and the remaining coordinates form the tail; anisotropic regularization $\\Lambda=\\mathrm{diag}(\\lambda_0 I_k,\\lambda_\\perp I_{p-k})$ with $\\lambda_\\perp\\gg\\lambda_0$ pushes learning onto the signal coordinates. Finally, Lexi-LowGLM filters the candidate set objective by objective with tolerance $W_i\\,c_{t,i_t}(X_t)$, keeping the lexicographically optimal arm inside while bounding each objective's gap, and updates estimators via an online Newton-type proximal step whose logarithmic potential sum yields the $O(T)$ update cost.","core_discovery":"The central claim is that a lexicographic generalized low-rank matrix bandit admits a computationally light algorithm whose regret is uniformly sublinear on every objective. Concretely, under low-rank, bounded-link, bounded-noise, and lexicographic trade-off assumptions, Lexi-LowGLM first estimates each objective's row and column subspaces from $T_1$ exploration samples, then runs lexicographic candidate filtering on reduced features while maintaining each objective estimator by one proximal Newton step per round. Theorem 2 states that with probability at least $1-2\\delta$, the cumulative regret on objective $i$ is $\\widetilde{O}(W_i^{\\mathrm{lex}}\\sqrt{m}\\,(d_1+d_2)r\\sqrt{T})$, where $W_i^{\\mathrm{lex}}=1+w+\\cdots+w^{i-1}$; Theorem 1 gives the scalarized variant with factor $W^{\\mathrm{sca}}$. The effective dimension replaces $d_1d_2$ with $(d_1+d_2)r$, and the online update reduces the cumulative estimator-update complexity over $T$ rounds from $O(T^2)$ to $O(T)$, matching the single-objective rate when $m=1$.","pith_inferences":["Editorial: A hidden practical cost is $D_{rr}$, the smallest $r$-th singular value across objectives; the theorem fixes this number when setting $T_1$ and $S_\\perp$, so a fully parameter-free version of the algorithm would need to estimate $D_{rr}$ online and would likely pay an extra burn-in or multiplicative cost.","Editorial: Because each estimator update consumes only the current observation rather than replaying all history, the online Newton step should extend naturally to non-stationary or delayed rewards without changing the $O(T)$ complexity.","Editorial: The rank-two experiments show the third-objective regret still growing at $T=10{,}000$; the theory predicts eventual $\\widetilde{O}(\\sqrt{T})$ growth, so running the same instance well past $T=100{,}000$ would directly test whether the slope flattens as predicted.","Editorial: The common confidence width used in the filtering tolerance may be conservative for arms with small uncertainty in all active objectives; exploiting each objective's estimated subspace geometry could sharpen the candidate elimination without changing the theoretical order."],"forward_implications":["Every objective's regret is sublinear in $T$ simultaneously, so the learner approaches the lexicographically optimal arm while keeping lower-priority losses controlled.","The regret depends on $(d_1+d_2)r$ rather than $d_1d_2$, so matrix structure pays off even when outcomes are vector-valued and priority-ordered.","Lexi-LowGLM's estimator-update cost is $O(T)$ over $T$ rounds, compared with $O(T^2)$ for batch refitting, making the method feasible for long horizons.","When $w=0$, the lexicographic factor is $W_i^{\\mathrm{lex}}=1$ for every objective, and the $\\sqrt{m}$ factor improves on the scalarized baseline's factor $m$.","With a single objective the bound reduces to $\\widetilde{O}((d_1+d_2)r\\sqrt{T})$, matching the rate of prior generalized low-rank matrix bandit methods.","The confidence and potential arguments separate estimation from lexicographic decision making, so the online-update proof strategy can be reused in related bandit problems.","When $w=0$, the lexicographic filtering cost disappears and the algorithm degrades gracefully to a multi-objective low-rank bandit with uniform guarantees."],"supporting_citations":[{"why":"Supplies the Stein-type subspace estimator and the generalized low-rank matrix bandit framework that Lexi-LowGLM extends to lexicographic objectives and replaces with online updates.","marker":"Kang et al. [2022]"},{"why":"Provides the self-normalized martingale and elliptical-potential inequalities used in both confidence and regret proofs.","marker":"[Abbasi-yadkori et al., 2011]"},{"why":"Provides the online Newton proximal inequality that underlies the one-step estimation recursion in Lemma 6.","marker":"[Hazan et al., 2007]"},{"why":"Formulates lexicographic linear bandits, supplies the trade-off assumption, and is the MTLO baseline compared in the experiments.","marker":"[Xue et al., 2025b]"},{"why":"Introduces the explore-subspace-then-refine strategy and bilinear low-rank bandit model that motivates the transformed feature representation.","marker":"[Jun et al., 2019]"},{"why":"Extends low-rank bandits to generalized linear models, providing the generalized link formulation that the paper adopts for each objective.","marker":"[Lu et al., 2021]"}],"fun_headline_variants":["Lexicographic low-rank bandits: linear updates, root-T regret","Priority-ordered matrix bandits with low-rank regret","Lexi-LowGLM: efficient lexicographic low-rank bandits","Lexicographic low-rank bandits: sqrt(T) regret, linear ops"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof relies on knowing in advance the minimum strength, across objectives, of the $r$-th singular value of each unknown parameter matrix; an overestimate makes the exploration length and tail bound too small, and the confidence intervals that carry the regret bound need not hold.","fun_headline_variants_meta":{"raw":{"variants":["Lexicographic low-rank bandits: linear updates, root-T regret","Priority-ordered matrix bandits with low-rank regret","Lexi-LowGLM: efficient lexicographic low-rank bandits","Lexicographic low-rank bandits: sqrt(T) regret, linear ops"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000754,"raw_usage":{"total_tokens":3412,"prompt_tokens":1065,"completion_tokens":2347,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":2270}},"tokens_in":681,"tokens_out":2347,"duration_ms":17757,"temperature":1.0,"reasoning_tokens":2270,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T19:45:52.725139+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Lexi-LowGLM on a synthetic instance where the true minimum singular value $D_{rr}$ is ten times smaller than the value supplied to the algorithm, and track objective-wise regret and subspace estimation error over $T=10^5$; if the overestimate breaks the confidence intervals, the regret should stop following the claimed $\\widetilde{O}(\\sqrt{T})$ slope or the subspace error should exceed the theorem's bound.","supporting_citations":[],"review_version":1}