{"id":"3ca3a7bb-e825-4acb-8943-17f5f5b92e6b","arxiv_id":"2502.04282","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A two-level Phase selection reformulation of real-valued phase retrieval, with simultaneous temperature and L2 regularization annealing, lets simulated annealing, AMP, and Langevin dynamics approach the Bayes-optimal sample efficiency in numerical experiments.","lead":"This paper introduces Phase selection, a two-level formulation of noiseless real-valued phase retrieval that first picks the missing measurement signs and then solves a plain linear regression for the signal. Using replica-theory large deviations and heuristic solvers, it argues that simultaneously annealing temperature and L2 regularization lets these methods approach the Bayes-optimal sample efficiency around alpha = 1.13.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'approaching Bayes-optimal sample efficiency' claim rests on finite-size success-rate curves with no error bars or scaling analysis; the theory itself is acknowledged to be RS-unstable, so the numerical extrapolation is the only direct support.","rationale":"The reader's verdict is CONDITIONAL and identifies both the RSB-related instability of the replica analysis and the absence of error bars/scaling as weaknesses. I agree that the RSB issue is real, but I judge the finite-size extrapolation to be more directly load-bearing for the abstract's central claim: 'with simultaneous annealing ... they are shown to approach the Bayes-optimal sample efficiency.' That sentence asserts an asymptotic algorithmic property, and the only evidence offered is a family of finite-size curves with no statistical uncertainty and no extrapolation procedure. The replica computation cannot independently establish the property because the paper itself states that the RS branch-merging threshold (alpha=1.7) does not match the unregularized algorithmic threshold, with the mismatch attributed to RSB and left unquantified. Therefore the numerical scaling is the weakest link. My proposed test is a standard finite-size scaling analysis of the success-probability threshold; it directly checks whether the data support convergence to alpha_BO. If the test passes, the concern is resolved; if it fails, the central claim should be weakened to a phenomenological observation. Either way, the current CONDITIONAL verdict remains appropriate, so I set verdict_should_be to UNCHANGED rather than moving it.","tokens_in":20909,"tokens_out":5088,"duration_ms":60376,"concrete_test":"Reproduce the SA and AMP experiments using Algorithms 1 and 2 for N in {400, 800, 1600, 3200} with at least 100 independent instances per (N, alpha) point and annealing rates epsilon in {0.1, 0.03, 0.01, 0.003}. Estimate the half-success threshold alpha_h(N, epsilon) by logistic regression with bootstrap confidence intervals, then fit alpha_h = alpha_infinity + c N^{-theta} and extrapolate to epsilon -> 0. If the 95% confidence interval for alpha_infinity excludes alpha_BO = 1.13, the claim that the algorithms approach Bayes-optimal sample efficiency is not supported by the numerics.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the three heuristics, under simultaneous annealing of mu and lambda, approach the Bayes-optimal sample efficiency alpha_BO = 1.13. The evidence is the set of success-probability curves in Figs. 6-8: 100 random instances per point, system sizes up to N=800 (SA, Langevin) or N=3200 (AMP), and two annealing rates. These curves are plotted without error bars or confidence intervals, and the half-success threshold alpha_h(N, epsilon) is read off by eye. The abstract's claim is asymptotic in N and epsilon, but no scaling analysis is provided: there is no fit of alpha_h to a limit, no extrapolation in epsilon, and no statement of how the threshold would behave as N -> infinity with epsilon -> 0. The plotted trends could be consistent with a limit above alpha_BO, or with finite-size effects that make small instances easier or harder than the asymptotic task. The replica theory does not fill this gap: the RS analysis predicts branch merging at alpha = 1.7, and the paper reports that unregularized simulated annealing actually succeeds only for alpha > 1.7, a discrepancy attributed to replica symmetry breaking without a quantitative 1RSB check. Thus the load-bearing support for the headline claim is the unquantified finite-size extrapolation, and that support is currently missing.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a two-level formulation of real-valued phase retrieval, called Phase selection, in which the missing signs of the measurements are treated as explicit binary variables and the signal is recovered by a nested convex linear regression. The authors perform a replica-theoretic large-deviation analysis of the sign-configuration complexity and free-energy landscape under a replica-symmetric ansatz, showing that an L2 regularization can anticipate the merging of the informed and uninformed branches. They then propose a simultaneous annealing of inverse temperature and regularization and report finite-size success rates for three heuristics (Simulated Annealing, Approximate Message Passing, and Langevin dynamics), claiming that these approach the Bayes-optimal sample efficiency alpha_BO = 1.13.","tokens_in":21118,"tokens_out":3953,"duration_ms":39807,"significance":"If the headline claim is established, the paper would provide a physically motivated decomposition of phase retrieval into a hard combinatorial sign-selection subproblem and a convex regression subproblem, and it would show that standard heuristics with a carefully designed annealing schedule can reach near-information-theoretic sample efficiency. The large-deviation computation and the stability analysis are valuable contributions, and the paper is honest in reporting that the replica-symmetric ansatz is not globally stable. However, the central numerical claim is currently supported only by finite-size success-probability curves without error bars, confidence intervals, or scaling analysis, so the asymptotic statement in the abstract is not yet justified.","major_comments":[{"comment":"The central claim of approaching alpha_BO = 1.13 rests on success-probability curves for 100 instances per point and system sizes up to N=800 (SA, Langevin) or N=3200 (AMP), but the curves are plotted without error bars and the half-success thresholds are read off by eye. No scaling analysis in N or in the annealing rate epsilon is provided: there is no fit of the threshold alpha_h(N, epsilon) to a limit, no extrapolation as epsilon -> 0, and no statement about how finite-size effects behave. Please add binomial confidence intervals, describe the threshold extraction procedure, and provide a scaling or extrapolation analysis, or explicitly soften the asymptotic claim in the abstract.","section":"Sec. IV A-C, Figs. 6-8"},{"comment":"The theoretically motivated annealing schedule is derived from a replica-symmetric analysis, but the paper itself states (Appendix A 2 a) that the RS solutions are not globally stable and (Sec. IV) that the RS prediction of branch merging at alpha = 1.7 disagrees with the unregularized SA recovery threshold, attributing the discrepancy to replica symmetry breaking. Since the RSB effects are not computed quantitatively, the free-energy branch structure that motivates the simultaneous annealing is not established beyond the RS approximation, and the only direct support for the headline claim is the finite-size numerics. A quantitative 1RSB analysis of the thresholds, or an explicit argument that the qualitative branch picture survives RSB, is needed.","section":"Sec. III C 2 and Appendix A 2"},{"comment":"The abstract's claim that the algorithms 'are shown to approach the Bayes-optimal sample efficiency' is stronger than the paper's own hedging in the body, e.g., 'the heuristic seems to approach the alpha_BO threshold in the limit of vanishing annealing rate' (Sec. IV B) and 'seems to approach' in the caption of Fig. 6. Without the missing scaling analysis, the strong asymptotic claim is not supported. Please either provide the scaling evidence or revise the claim to state that the finite-size thresholds decrease with N and slower annealing and extrapolate to a value near alpha_BO.","section":"Abstract and Sec. V"}],"minor_comments":[{"comment":"The word 'istogram' should be 'histogram'.","section":"Fig. 3 caption"},{"comment":"'sistem size' should be 'system size'.","section":"Fig. 6 caption"},{"comment":"The sentence 'The continuous optimization of theta an be performed' should read 'can be performed'.","section":"Sec. IV C"},{"comment":"The loop condition 'while t <= T' is unclear because the pseudocode never increments t; please state explicitly how T relates to the number of Monte Carlo steps and annealing updates.","section":"Algorithm 1"},{"comment":"The definition of a successful run as 'm ~ 1 and MSE_y = 0' needs explicit numerical thresholds, since exact equality will never be attained in floating point.","section":"Figs. 6-8"},{"comment":"The caption calls the solver 'GD-based' while the text describes Langevin dynamics; please unify the terminology.","section":"Fig. 8 caption"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the scope of a statistical physics or disordered-systems journal well, and the replica computation is a genuine contribution. The main issue is the gap between the abstract's strong asymptotic claim and the finite-size numerical evidence. I would also encourage the editor to require a data/code availability statement, since the numerical results are central to the claim and no code or data is provided even in the appendices."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nYou should know this paper is worth a serious look: the Phase selection formulation—decoupling sign selection from the nested ridge regression—is a clean idea, and the large-deviation analysis of sign-selection complexity is genuinely new. The observation that annealing the L2 regularization during temperature cooling shifts the branch-merging threshold is also fresh, and the replica computation is substantial. The authors are honest about its limits, and that honesty is where the problems start.\n\nThe abstract says the three heuristics 'are shown to approach the Bayes-optimal sample efficiency.' What the numerics actually show is success-probability curves: 100 instances per point, N up to 800 for SA/Langevin and 3200 for AMP, with no error bars, no confidence intervals, and no scaling analysis. The half-success threshold is read off by eye. There is no fit of alpha_h(N, epsilon) to a limit, no extrapolation in epsilon, and no argument that the finite-size trends continue to alpha_BO. The curves could be consistent with a limit above alpha_BO. So the load-bearing claim rests on exactly the kind of eyeballed extrapolation that the rest of the formalism is meant to replace.\n\nThe theory does not rescue it. The RS analysis predicts branch merging around alpha = 1.7, and the authors report that unregularized SA succeeds only for alpha > 1.7. They attribute the gap to replica symmetry breaking, which is plausible, but they also show the RS solution is not globally stable, and they provide only a 1RSB stability check, not a full 1RSB branch analysis. The discrepancy is acknowledged but not quantified.\n\nCredit where it is due: the complexity function at fixed sign overlap, the stability analysis of the stabilities distribution, and the regularization phase diagram are real contributions. The numerical finding that slow simultaneous annealing of mu and lambda systematically improves recovery is useful and likely reproducible, even if the asymptotic limit is unproven. The citation pattern is appropriate, and the borrowing from Obuchi et al. is explicit.\n\nWho should read it: anyone working on phase retrieval or high-dimensional non-convex inference from a statistical physics angle. It deserves a serious referee, but the referee should push hard on the scaling analysis and ask for code and data. Without those, the 'approaching alpha_BO' claim should be downgraded to 'consistent with approaching.'\n\nMy recommendation: send to peer review with major revision. Do not desk reject—but do not let the abstract's claim through without a finite-size scaling argument or error bars.","headline":"A clever reformulation of phase retrieval with a genuine large-deviation analysis, but the headline 'approaching Bayes-optimal' claim is softer than the abstract suggests.","tokens_in":21691,"tokens_out":2170,"would_cite":true,"duration_ms":21633,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Splitting phase retrieval into sign selection plus regression lets standard heuristics reach the Bayes-optimal sample efficiency.","keywords":["phase retrieval","phase selection","replica theory","large deviations","simulated annealing","approximate message passing","Langevin dynamics","Bayes-optimal threshold"],"falsifier":"Run the simulated-annealing solver with the fixed-$\\mu\\lambda$ schedule on instances of size $N=3200$ at a dataset size strictly between $\\alpha_{BO}=1.13$ and the RS merging prediction $\\alpha\\approx1.7$, and measure the success fraction over many instances as $N$ grows; if it tends to zero instead of one, simultaneous annealing does not reach the Bayes-optimal efficiency. Independently, a one-step replica-symmetry-breaking calculation of the free entropy at the same $(\\mu,\\lambda)$ values would show whether the informed and uninformed branches still merge at a finite $\\alpha$.","tokens_in":20631,"feed_emoji":"🎯","tokens_out":9696,"duration_ms":91896,"temperature":0.7,"pith_summary":"In noiseless real-valued phase retrieval, the signal is hidden behind the absolute values of linear measurements; the genuinely hard part is the missing signs. The paper introduces 'Phase selection,' a two-level formulation in which a combinatorial loop chooses the signs and an inner ridge regression recovers the signal in closed form. A replica large-deviation analysis maps the free-energy landscape and shows two branches—one uninformed, one aligned with the signal—that merge at a first-order transition whose location depends on dataset size and on an L2 penalty. The paper's central proposal is to anneal temperature and regularization simultaneously, keeping their product fixed, so that early regularization steers the search toward informative signs and late weak regularization removes the bias. Numerical experiments with simulated annealing, approximate message passing, and Langevin dynamics all approach the Bayes-optimal threshold $\\alpha_{BO}=1.13$, which would make the hard core of phase retrieval accessible to standard solvers.","feed_headline":"Two-level phase retrieval scheme nears Bayes-optimal data limit","feed_subtitle":"Annealing temperature and L2 together lets standard solvers reach the 1.13 information limit.","key_machinery":"The load-bearing object is the Phase selection loss $H_{A,y}(x,S)=\\|S\\odot y-Ax\\|_2^2+\\frac{\\lambda}{2}\\|x\\|_2^2$, with binary sign variables $S\\in\\{-1,1\\}^M$ and signal $x\\in\\mathbb{R}^N$. For fixed signs the inner problem is ridge regression with the closed-form estimator $\\hat{x}(S)=(A^\\top A+\\lambda I)^{-1}A^\\top(S\\odot y)$; the outer problem is a combinatorial optimization over signs. The analytical machinery is a replica large-deviation computation of the free entropy $\\Phi(\\mu,\\phi)$, whose Legendre transform gives the complexity $\\Sigma(O,e)$ of sign configurations at overlap $O$ and energy $e$, plus a stability analysis of the replica-symmetric saddle point. The proposed annealing schedule keeps $\\mu\\lambda$ constant while $\\mu\\to\\infty$, so early strong regularization guides the search toward informative signs and late weak regularization removes the bias.","core_discovery":"The central claim is that noiseless real-valued phase retrieval should be solved by selecting the signs first and regressing second, and that this decomposition changes the algorithmic picture even though it leaves the information-theoretic threshold untouched. For each sign assignment the inner problem is a convex ridge regression with the closed-form estimator $\\hat{x}(S)=(A^\\top A+\\lambda I)^{-1}A^\\top(S\\odot y)$, so the whole difficulty resides in the binary outer optimization over $S\\in\\{-1,1\\}^M$. The replica computation of the free entropy $\\Phi(\\mu,\\phi)$ reveals, at low temperature near the Bayes-optimal threshold, two coexisting branches: an uninformed branch connected to random initialization and an informed branch connected to the signal, with a first-order transition at which they merge. The paper shows that an $L_2$ regularization anticipates this merging to smaller dataset sizes, and that a simultaneous annealing of the inverse temperature $\\mu$ and the regularization $\\lambda$ (holding $\\mu\\lambda$ fixed) removes the bias that a fixed $\\lambda$ would leave. The three solvers tested—simulated annealing, approximate message passing, and Langevin dynamics on relaxed signs—are reported to approach the Bayes-optimal sample efficiency $\\alpha_{BO}=1.13$ as the annealing is slowed, in the sense that their finite-size success curves move toward that threshold.","pith_inferences":["Editorial extension: the same decomposition should apply to other problems where a discrete selection is coupled to continuous estimation, such as quantized compressed sensing or spike-and-slab regression; the paper suggests this direction but does not test it.","Editorial extension: a sharper test of the central claim is to fix $\\alpha\\in(1.13,1.7)$ and check whether the success probability at fixed computational budget converges to 1 as $N\\to\\infty$; the presented curves are consistent with this but do not prove it.","Editorial extension: if replica-symmetry-breaking corrections are the reason the RS threshold $\\alpha\\approx1.7$ disagrees with simulated annealing, a one-step RSB large-deviation computation would predict a different merging point, and the simultaneous-annealing schedule might be improvable by adapting the $\\mu\\lambda$ product to that corrected phase diagram."],"forward_implications":["If the central claim holds, generic solvers can solve noiseless real-valued phase retrieval with roughly $1.13$ measurements per signal dimension, close to the information-theoretic limit.","The L2 regularization's role is demystified: it biases the optimization toward correcting large-magnitude sign errors, which anticipates the branch merging in the free-energy landscape.","The simultaneous-annealing protocol (fixed $\\mu\\lambda$) provides a concrete schedule for removing the regularization bias while keeping its early benefit.","The Phase selection decomposition preserves the original problem's information-theoretic threshold, so it is a reformulation, not a relaxation that changes what is recoverable."],"supporting_citations":[{"why":"Supplies the two-replica large-deviation method for variable selection that the Phase selection free-entropy computation is built on.","marker":"[18]"},{"why":"Establishes the injectivity threshold $\\alpha_{IT}=1$ for phase retrieval, the information-theoretic baseline the paper keeps.","marker":"[15]"},{"why":"Provides the Bayes-optimal phase diagram for high-dimensional generalized linear models from which the $\\alpha_{BO}=1.13$ target comes.","marker":"[14]"},{"why":"Gives the approximate survey propagation framework that the AMP solver's equations extend to the two-level Phase selection problem.","marker":"[5]"},{"why":"Shows that $L_2$ regularization helps amplitude-based phase retrieval optimization, the observation the paper re-derives from the free-energy landscape.","marker":"[20]"},{"why":"Supplies the simulated annealing heuristic used as one of the three solvers and as the main numerical evidence near $\\alpha_{BO}$.","marker":"[27]"},{"why":"Provides the large-deviations perceptron analysis whose complexity computations are adapted to the Phase selection sign configurations.","marker":"[24]"}],"fun_headline_variants":["Phase selection splits sign and regression to hit Bayes limit","Annealing L2 and temperature lets solvers hit 1.13 limit","Replica analysis finds branch merge in phase selection","Sign-first strategy nears Bayes-optimal sample efficiency"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis assumes that a single symmetric description of the disorder captures the relevant free-energy branches; if that description breaks down, the predicted transition and the annealing schedule that depends on it could give the wrong threshold.","fun_headline_variants_meta":{"raw":{"variants":["Phase selection splits sign and regression to hit Bayes limit","Annealing L2 and temperature lets solvers hit 1.13 limit","Replica analysis finds branch merge in phase selection","Sign-first strategy nears Bayes-optimal sample efficiency"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00064,"raw_usage":{"total_tokens":3044,"prompt_tokens":1139,"completion_tokens":1905,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":755,"completion_tokens_details":{"reasoning_tokens":1838}},"tokens_in":755,"tokens_out":1905,"duration_ms":15567,"temperature":1.0,"reasoning_tokens":1838,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T22:52:32.026974+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the simulated-annealing solver with the fixed-$\\mu\\lambda$ schedule on instances of size $N=3200$ at a dataset size strictly between $\\alpha_{BO}=1.13$ and the RS merging prediction $\\alpha\\approx1.7$, and measure the success fraction over many instances as $N$ grows; if it tends to zero instead of one, simultaneous annealing does not reach the Bayes-optimal efficiency. Independently, a one-step replica-symmetry-breaking calculation of the free entropy at the same $(\\mu,\\lambda)$ values would show whether the informed and uninformed branches still merge at a finite $\\alpha$.","supporting_citations":[{"cited_title":"Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem","cited_arxiv_id":null,"evidence_quote":"Supplies the two-replica large-deviation method for variable selection that the Phase selection free-entropy computation is built on."},{"cited_title":"Fundamental Limits of Weak Recovery with Applications to Phase Retrieval","cited_arxiv_id":null,"evidence_quote":"Establishes the injectivity threshold $\\alpha_{IT}=1$ for phase retrieval, the information-theoretic baseline the paper keeps."},{"cited_title":"Complex dynamics in simple neural networks: Understanding gradient flow in phase retrieval","cited_arxiv_id":null,"evidence_quote":"Provides the Bayes-optimal phase diagram for high-dimensional generalized linear models from which the $\\alpha_{BO}=1.13$ target comes."},{"cited_title":"We thus set ϕ = 0 in the following, allowing the overlap O to vary with µ","cited_arxiv_id":null,"evidence_quote":"Gives the approximate survey propagation framework that the AMP solver's equations extend to the two-level Phase selection problem."},{"cited_title":"Typology of phase transitions in bayesian inference problems","cited_arxiv_id":null,"evidence_quote":"Shows that $L_2$ regularization helps amplitude-based phase retrieval optimization, the observation the paper re-derives from the free-energy landscape."},{"cited_title":"Phase retrieval in high dimensions: Statistical and computational phase transitions, 2020","cited_arxiv_id":null,"evidence_quote":"Supplies the simulated annealing heuristic used as one of the three solvers and as the main numerical evidence near $\\alpha_{BO}$."},{"cited_title":"Candes, Xiaodong Li, and Mahdi Soltanolkotabi","cited_arxiv_id":null,"evidence_quote":"Provides the large-deviations perceptron analysis whose complexity computations are adapted to the Phase selection sign configurations."}],"review_version":1}