{"id":"9b8471c0-adae-4f64-a278-909fb508168d","arxiv_id":"1909.01051","paper_version":4,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"MANAS frames DARTS-style neural architecture search as parallel adversarial bandits per edge, but its theoretical guarantee requires other agents' actions to be fixed and it omits the key weight-sharing random-search baseline.","lead":"This paper presents MANAS, a neural architecture search method that treats each network edge as an independent bandit agent and updates it with online-learning rules. The authors claim lower memory use than DARTS and competitive accuracy, but the paper was rejected at ICLR 2020 after reviewers noted a missing random-search baseline and a regret proof that assumes other agents stay fixed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's core regret guarantee for MANAS is proved only against fixed choices of the other agents and for a per-agent objective; it does not establish the joint regret claimed in Eq. (3), so the advertised 'vanishing regret' is unsupported.","rationale":"I read the paper as claiming that MANAS couples online-learning agents with weight sharing to yield both practical memory savings and a principled regret guarantee. The empirical numbers are suggestive, and the inclusion of new datasets and random baselines is a genuine strength. But the theoretical support for the headline algorithm is the least secure part: the only theorem for MANAS is stated and proved for a fixed background of other agents, and its per-agent notion of regret does not imply the joint regret used in Eq. (3). Appendix C's reduction works only under the linear-loss assumption of MANAS-LS. Because this gap is in the central 'theoretical rigour' claim, the rejection is justified; no new empirical result is needed to see that the claim is unsupported. The reader's weak-assumption statement identifies the same region of the paper, although I would sharpen it: even a full non-stationary EXP3 extension would not save the joint-regret claim. I would keep the REJECT verdict.","tokens_in":20198,"tokens_out":11935,"duration_ms":129714,"concrete_test":"Run a 2-agent, 2-action coordination game (L_t(a1,a2)=0 when a1=a2, otherwise 1) with both agents using the MANAS/EXP3 update of Eq. 6 for T=100,000. After the run, compute (i) the sum of per-agent regrets as defined in Appendix D.2 and (ii) the joint regret of Eq. (3) relative to the best fixed joint architecture. If (i) is O(sqrt(T log K)) while (ii) grows linearly, Theorem 2's bound is for a different objective than the one advertised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.3 and Appendix D.2 prove a per-agent bound R^*,i_T(pi(Ai)) = sup_{a^{-i},nu} ... in which a^{-i} is held fixed for all T rounds. Algorithm 1 updates every agent's policy every round, so the actual coupled system is not covered by the stated theorem. More importantly, the quantity bounded is not the joint regret defined in Eq. (3): summing N per-agent regrets compares each agent with its own best fixed response to a frozen background, not with min_a sum_t L_t(a) over joint architectures. Appendix C's factorization is valid only under the additive linear-loss assumption used for MANAS-LS (Eq. 4), not for the arbitrary losses that MANAS's coordinate-descent update (Eq. 6) is claimed to handle. Thus the abstract's 'vanishing regrets' overstates what is proved for the headline algorithm. A second, compounding defect is that Theorem 1's H is defined from cumulative B_T, so H grows with T and O(e^{-T/H}) is not an exponential decay unless H is redefined per round.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper frames neural architecture search as a multi-agent online learning problem. Each edge of the DARTS-style cell is controlled by an agent that samples an operation from a private policy, receives the shared validation loss as feedback, and updates its policy. Two instantiations are proposed: MANAS, which uses an EXP3-style softmax update (Eq. 6), and MANAS-LS, which fits a linear model to the validation loss and samples according to a Zipf distribution. The paper claims cumulative regret O(sqrt(T)) for MANAS, exponential simple regret O(e^{-T/H}) for MANAS-LS, a memory reduction to roughly 1/8 of DARTS, state-of-the-art results on CIFAR-10 and ImageNet, and favorable comparisons against random baselines on Sport-8, Caltech-101, and MIT-67. A Gaussian Squeeze Domain experiment is included to illustrate the regret behavior.","tokens_in":20429,"tokens_out":6864,"duration_ms":73261,"significance":"If correct, the manuscript would introduce a genuinely new perspective to NAS: replacing the continuous relaxation of DARTS with a distributed bandit formulation that can search directly over final network depths while retaining theoretical guarantees. The paper deserves credit for several concrete strengths: the agent formulation is clear, the memory-efficient search over 20-cell networks is valuable, the three additional datasets with 8-run means and standard deviations are a step toward reducing benchmark overfitting, and the Gaussian Squeeze Domain experiment makes an explicit empirical connection to the theoretical bound. However, the central advertised guarantees do not hold as stated for the actual algorithm. Theorem 2 is a per-agent bound under a frozen background of other agents, not a bound on the joint regret defined in Eq. (3), and Theorem 1's exponential-rate claim has a scaling problem because H is built from cumulative losses. The empirical evaluation also omits the weight-sharing random-search baseline that would isolate the contribution of the learned updates.","major_comments":[{"comment":"Theorem 2 bounds sum_i R*^i_T(pi^{A_i}), where each per-agent regret is defined with a^{-i} fixed for all T rounds. This is not the joint regret in Eq. (3): in Algorithm 1 every agent updates its policy every round, so the loss sequence seen by any one agent is nonstationary because the other agents are also learning. Moreover, summing per-agent regrets with different frozen background action profiles does not compare against min_a sum_t L_t(a), the joint benchmark in Eq. (3). Consequently the abstract's claim of 'vanishing regrets' for the actual coupled dynamics is unsupported. The authors should either prove a bound for the joint dynamics or explicitly restate the contribution as a per-agent guarantee under a stationary background.","section":"§5.3, Appendix D.2, Eq. (3)"},{"comment":"The stated simple-regret bound O(e^{-T/H}) is not justified by the proof. H is defined through the cumulative quantities B_T^{(A_i)}[j] = sum_{t=1}^T beta_t^{(A_i)}[j], so H grows linearly with T for any non-zero mean gap. Then T/H tends to a constant, not to infinity, and O(e^{-T/H}) is not an exponentially decaying guarantee. The proof's exponent, obtained by substituting Delta_k = B_T[k] - B_T[k*_i] into exp(-(Delta_1)^2 T / (2 N log K / lambda_min)), scales as T^3 for stationary gaps, which is not expressed by the claimed T/H form. In addition, the proof assumes a uniform exploration probability 1/log K, while Section 5.1 specifies Zipf sampling; the analysis therefore does not cover the proposed sampler.","section":"Theorem 1, Appendix D.1"},{"comment":"The random baseline in Section 6.3 samples eight architectures uniformly and trains each from scratch. This is a random-sampling control, not the weight-sharing random search of Li and Talwalkar (RandomNAS-WS), which is the appropriate baseline for isolating the effect of the bandit updates: RandomNAS-WS has the same memory advantage over DARTS and uses the same weight-sharing protocol, differing only in that it does not update sampling distributions. Without this comparison, the empirical claim that MANAS's learned credit assignment drives the observed gains is not established, and the memory-efficiency claim alone does not differentiate MANAS from the omitted baseline.","section":"§6.3, Figure 2"},{"comment":"There is a mismatch between the MANAS-LS algorithm as implemented and the estimator analyzed in the proof. Section 5.1 defines the credit assignment as a least-squares fit over the collected architectures (Eq. 5), while Appendix D.1 analyzes the ComBand-style inverse-propensity estimator ~beta_t = L_t^{(val)} P^dagger Z_t (Eq. 9) under a uniform sampling distribution. These are different estimators, and the paper does not show that the batch least-squares update inherits the regret properties proved for Eq. (9). The theoretical guarantee for MANAS-LS is therefore for a different algorithm than the one evaluated in Section 6.","section":"Eq. (5), Eq. (9), Appendix D.1"}],"minor_comments":[{"comment":"The initialization says each policy is uniform over j in {1,...,N}, but each agent selects among K operations; this appears to be a typo and should read {1,...,K}.","section":"Algorithm 1, line 1"},{"comment":"The reported search costs are internally surprising: 20 cells with 500 epochs cost 2.8 GPU days, while 8 cells with 50 epochs cost 0.8 GPU days. The second has only 1/25 of the search budget, so the costs do not scale as the text would suggest; please clarify whether the numbers are per-run, per-architecture, or otherwise normalized.","section":"Table 1"},{"comment":"The subplots use different y-axis scales, and on Sport-8 the 14-cell MANAS result is visibly worse than the 8-cell result, while the text states that the 14-cell setting is better. The figure and the discussion should be reconciled, and the authors should offer an explanation for the non-monotonic behavior.","section":"Figure 2"},{"comment":"The text switches between 'random sampling' and 'random search' without defining the distinction; since the appendix explicitly samples a fixed number of architectures, the terminology should be made consistent.","section":"Section 6.3"},{"comment":"The sentence 'as show in Section 6 of this work' should read 'as shown in Section 6', and there are several typographical errors elsewhere (e.g., '3 news datasets' and the inconsistent author name 'Xang Xu' vs. 'Hang Xu').","section":"Introduction"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nYou asked for a read on MANAS. The main thing you should know: the headline theoretical claim doesn't hold up. The regret bound for the main MANAS algorithm (Theorem 2) is proved for each agent assuming all other agents' actions are fixed for all T rounds. In the actual algorithm, every agent updates every round, so the environment each agent faces is non-stationary and the bound does not cover the joint system. The abstract's \"vanishing regrets\" overstates what is proved for the algorithm that actually runs.\n\nWhat's genuinely new: framing NAS as a per-edge multi-agent bandit problem, with EXP3 updates and a least-squares credit assignment variant. That's a legitimate new application, and the memory reduction to 1/8th of DARTS is real. The paper also contributes three new evaluation datasets (Sport-8, Caltech-101, MIT-67) and includes random-sampling baselines, which is more than most NAS papers do. The empirical results are competitive on CIFAR-10 and ImageNet, though the margins are small.\n\nThe soft spots are serious. The most decisive is the missing comparison to RandomNAS-WS (Li & Talwalkar), which is essentially MANAS with the update step removed, and it already achieves the same memory savings. Without that baseline, the empirical claim that the bandits are learning anything is unsupported. Second, the search costs are internally inconsistent: 20 cells at 500 epochs cannot cost only 2.8 GPU days per 4 runs if 8 cells at 50 epochs costs 0.8 GPU days. Third, the MANAS-LS simple regret bound has a scaling problem: the complexity measure H is defined from cumulative gaps, so it grows with T, and O(e^{-T/H}) is not exponential decay. That is not a minor typo; it undermines the stated theorem.\n\nThe paper is not a waste of time. The multi-agent framing is worth thinking about, and the new datasets and random-search discussion are useful to the community. But as it stands, the theoretical contribution is not proven, and the missing baseline makes the empirical contribution incomplete. The AC's decision to reject was right.\n\nI'd send it to review if it came in today, because the idea is substantive and the empirical setup is thoughtful, but I'd expect major revision. For yourself, skim the experiments on the three new datasets if you're working on NAS evaluation; otherwise, don't build on the theory.\n\nBest,\n[Your name]","headline":"A useful multi-agent framing and honest empirical effort, but the central regret guarantee does not cover the actual algorithm and the missing RandomNAS-WS baseline undercuts the empirical claims.","tokens_in":20972,"tokens_out":4403,"would_cite":false,"duration_ms":42494,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that treating each edge of a DARTS cell as an online-learning agent, with shared weights and bandit-style updates, finds better architectures than DARTS at about one-eighth of its memory.","keywords":["neural architecture search","multi-agent learning","online learning","adversarial bandits","weight sharing","DARTS search space","CIFAR-10","ImageNet"],"falsifier":"Run MANAS against a uniform-random weight-sharing controller that samples the same architectures and updates the shared weights identically but never updates the sampling distribution, using the same search budget on CIFAR-10 and on the three new datasets; if the random controller matches MANAS's accuracy, the claim that the bandit coordination is what produces the gains is falsified.","tokens_in":19988,"feed_emoji":"🧠","tokens_out":6694,"duration_ms":63826,"temperature":0.7,"pith_summary":"The paper claims that neural architecture search can be recast as a multi-agent online-learning problem: one agent per graph edge chooses an operation, all agents share a single set of network weights, and each agent updates its sampling policy from the validation loss alone. Because the agents never materialize all candidate operations at once, the method cuts GPU memory to roughly one eighth of DARTS while searching the final 20-cell network directly instead of searching on 8 cells and stacking them. On CIFAR-10 and ImageNet the method reports lower test error than DARTS and SNAS, and it introduces three new NAS datasets to check that these gains are not just overfitting to CIFAR-10. The paper also proves regret bounds: an exponentially decreasing simple-regret bound for the least-squares variant and an $O(\\sqrt{T})$ cumulative-regret bound per agent for the EXP3-style variant. A sympathetic reader would take the central claim to be that per-edge bandit coordination under weight sharing is a viable, memory-cheap way to search deep architectures directly.","feed_headline":"Multi-agent bandits search better architectures at 1/8th memory","feed_subtitle":"Per-edge agents pick operations, share one set of weights, and beat DARTS on CIFAR-10 and ImageNet.","key_machinery":"The central object is a per-edge bandit attached to the DARTS cell: agent $A^i$ controls edge $(i,j)$ and chooses one of $K$ operations, and the joint action profile is the architecture $Z_t$. The key identity carrying the argument is the factored regret: under a linear decomposition of the validation loss, the joint worst-case regret splits into a sum of per-agent regrets, letting each agent run an independent bandit in parallel, EXP3 for MANAS and least-squares plus Zipf for MANAS-LS. Weight sharing supplies the common network weights, so no operation parameters are duplicated, which is what gives the memory reduction.","core_discovery":"MANAS is a multi-agent algorithm for neural architecture search in which each directed edge of the DARTS cell is an agent with $K$ possible operations. At every round the agents sample a sparse architecture, the shared weights are updated by backpropagation on the training loss, and the validation loss is used by each agent to update its own estimate of operation quality. Two credit-assignment schemes are proposed: MANAS uses an EXP3-style importance-weighted update with softmax sampling, while MANAS-LS approximates the validation loss as a linear combination of operation contributions and samples with a Zipf distribution. The authors claim that these mechanisms coordinate implicitly through the joint loss, reduce memory from $O(NK)$ to $O(N)$, allow direct search on 20-cell CIFAR-10 and 14-cell ImageNet networks, and deliver test errors of 2.63% and 2.52% on CIFAR-10 and 26.15% on ImageNet, beating DARTS under the same evaluation protocol while using roughly one eighth of its GPU memory.","pith_inferences":["If the fixed-environment assumption in the regret proof were replaced by a non-stationary or game-theoretic analysis, the same algorithm might enjoy a joint no-regret guarantee; absent that, the theoretical guarantee should be read as per-agent against frozen opponents.","The paper's own experiments leave open that a uniform-random weight-sharing controller with the same memory savings could match MANAS's accuracy; a direct head-to-head on the same search budget would isolate the contribution of the bandit updates.","Treating the number of cells as a searchable quantity, rather than fixing it, is a natural next step, since the paper finds that the best cell for an 8-cell network is not the best cell for a 14-cell network.","Because MANAS needs no differentiable architecture objective, it could in principle be combined with non-differentiable hardware metrics such as latency or energy during search, something gradient-based NAS cannot do directly."],"forward_implications":["Search can be run directly on the final network depth, so architecture cells do not need to be repeated; the paper reports gains from this on CIFAR-10.","Memory use drops to about one eighth of DARTS, making direct search on ImageNet feasible; the paper reports a 0.85 percentage-point improvement over DARTS and SNAS when searching on ImageNet directly.","The regret bounds state that, under the paper's assumptions, cumulative regret grows only as $O(\\sqrt{T})$ for MANAS and simple regret decays exponentially for MANAS-LS, so exploration and exploitation are balanced without a hand-tuned reinforcement-learning reward.","On three new datasets, Sport-8, Caltech-101 and MIT-67, MANAS outperforms DARTS and random sampling, especially at 14 cells, suggesting the method transfers beyond CIFAR-10."],"supporting_citations":[{"why":"Defines the DARTS cell search space and the 8-cell-then-stack evaluation protocol; MANAS's search space, main memory baseline, and main accuracy comparison all come from this work.","marker":"Liu et al. (2019)"},{"why":"Introduced weight sharing in NAS, the efficiency mechanism MANAS retains and builds its bandit updates on.","marker":"Pham et al. (2018)"},{"why":"Supplies the EXP3 adversarial multi-armed bandit algorithm whose per-agent regret bound Theorem 2 uses.","marker":"Auer et al. (2002)"},{"why":"Provides the combinatorial-bandit least-squares estimator and analysis used in the MANAS-LS exponential regret bound.","marker":"Cesa-Bianchi and Lugosi (2012)"},{"why":"Provides the best-of-both-worlds Zipf sampling strategy that MANAS-LS uses to balance exploration and exploitation.","marker":"Abbasi-Yadkori et al. (2018)"},{"why":"The random-search analysis that motivates the paper's random baseline and its claim that the search space is easy to do well in.","marker":"Li and Talwalkar (2019)"},{"why":"Supports the claim that many NAS gains over random architectures are small, which the paper tests against.","marker":"Sciuto et al. (2019)"},{"why":"Provides evidence that repeated-cell stacking is suboptimal, motivating direct search on the final number of cells.","marker":"Yang et al. (2020)"}],"fun_headline_variants":["Multi-agent bandits find better architectures at 1/8th memory","Per-edge agents coordinate in NAS, beat DARTS with 8x less memory","MANAS: agent-based NAS with O(sqrt(T)) regret, 1/8th memory","Shrink NAS memory by 8x using multi-agent coordination"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The regret bound assumes every other agent's actions are fixed for all $T$ rounds, while in the actual algorithm every agent updates every round; if the coupled, non-stationary system is not covered by that assumption, the theoretical guarantee does not apply to MANAS as run.","fun_headline_variants_meta":{"raw":{"variants":["Multi-agent bandits find better architectures at 1/8th memory","Per-edge agents coordinate in NAS, beat DARTS with 8x less memory","MANAS: agent-based NAS with O(sqrt(T)) regret, 1/8th memory","Shrink NAS memory by 8x using multi-agent coordination"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000754,"raw_usage":{"total_tokens":3340,"prompt_tokens":915,"completion_tokens":2425,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":2339}},"tokens_in":531,"tokens_out":2425,"duration_ms":17523,"temperature":1.0,"reasoning_tokens":2339,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:28:30.498429+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run MANAS against a uniform-random weight-sharing controller that samples the same architectures and updates the shared weights identically but never updates the sampling distribution, using the same search budget on CIFAR-10 and on the three new datasets; if the random controller matches MANAS's accuracy, the claim that the bandit coordination is what produces the gains is falsified.","supporting_citations":[{"cited_title":"Efficient neural architecture search via parameter sharing","cited_arxiv_id":null,"evidence_quote":"Introduced weight sharing in NAS, the efficiency mechanism MANAS retains and builds its bandit updates on."},{"cited_title":"The nonstochastic multiarmed bandit problem","cited_arxiv_id":null,"evidence_quote":"Supplies the EXP3 adversarial multi-armed bandit algorithm whose per-agent regret bound Theorem 2 uses."},{"cited_title":"Best of both worlds: Stochastic & adversarial best-arm identification","cited_arxiv_id":null,"evidence_quote":"Provides the best-of-both-worlds Zipf sampling strategy that MANAS-LS uses to balance exploration and exploitation."},{"cited_title":"NAS evaluation is frustratingly hard","cited_arxiv_id":null,"evidence_quote":"Provides evidence that repeated-cell stacking is suboptimal, motivating direct search on the final number of cells."}],"review_version":1}