pith. sign in

arxiv: 2607.00300 · v1 · pith:MFN3PXQLnew · submitted 2026-07-01 · 💻 cs.GT

Fully Distributed T\^atonnement for Chores Markets

Bhaskar Ray Chaudhury , Christian Kroer , Ruta Mehta , Tianlong Nan This is my paper

Pith reviewed 2026-07-02 00:54 UTC · model grok-4.3

classification 💻 cs.GT
keywords chores marketstâtonnementcompetitive equilibriumFisher marketsmultiplicative updatesdistributed algorithmsCES disutilities
0
0 comments X

The pith

Multiplicative tâtonnement converges to a competitive equilibrium in chores Fisher markets using only local updates.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that a fully distributed price adjustment rule converges to competitive equilibrium in chores markets. Each chore price is multiplied by a factor depending only on its own excess demand, with no global normalization or averaging across chores. The rule works for any continuous, convex, and 1-homogeneous disutilities and, for convex CES disutilities, reaches an approximate equilibrium at an O(1/ε²) rate. This removes the need for the global coupling required by earlier relative tâtonnement methods while preserving the geometry needed for convergence via Walras' law.

Core claim

Multiplicative tâtonnement is a fully distributed dynamics in which each chore price p_j is updated multiplicatively using only its current price and its own excess-demand signal. The authors prove that this process converges to a competitive equilibrium for any chores Fisher market whose disutilities are continuous, convex, and 1-homogeneous. For convex CES disutilities the dynamics further attains an O(1/ε²) convergence rate to an approximate equilibrium, with improved dependence on problem constants compared to prior relative tâtonnement.

What carries the argument

The multiplicative tâtonnement update rule, which adjusts each chore price independently using its excess demand without explicit normalization.

If this is right

  • Convergence holds for all continuous convex 1-homogeneous disutility functions.
  • For convex CES disutilities an approximate competitive equilibrium is reached after O(1/ε²) iterations.
  • The dynamics requires no explicit global coupling or averaging of excess-demand signals.
  • Empirical running time is often an order of magnitude faster than relative tâtonnement on real-world and simulated instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same local multiplicative form may apply to other market models where global signals were previously required to enforce price normalization.
  • Because each update uses only local information, the method is immediately parallelizable across chores.
  • The approach may extend to mixed goods-and-chores markets if the 1-homogeneity condition can be maintained on the chore side.

Load-bearing premise

The disutilities must be continuous, convex, and 1-homogeneous for the local multiplicative updates to preserve the geometry required for convergence.

What would settle it

A chores market instance with continuous convex disutilities that are not 1-homogeneous in which the multiplicative updates diverge or cycle away from equilibrium.

Figures

Figures reproduced from arXiv: 2607.00300 by Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, Tianlong Nan.

Figure 1
Figure 1. Figure 1: Multiplicative Tâtonnement v.s. Relative Tâtonnement on Spliddit instances. The marker [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Multiplicative Tâtonnement v.s. Relative Tâtonnement on synthetic instances with truncated [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The best stepsizes in practice or the number of iterations to compute an approximate CE v.s. maximum ratio of the disutility coefficients with ρ ∈ {1.2, 2, 5}. Each point in the plots corresponding to a Spliddit instance that finds an approximate CE within the iteration budget. Discussions. Overall, multiplicative tâtonnement significantly outperforms relative tâtonnement. On Spliddit instances, multiplica… view at source ↗
Figure 4
Figure 4. Figure 4: Multiplicative Tâtonnement v.s. Relative Tâtonnement on AAMAS bidding instances. The [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Multiplicative Tâtonnement v.s. Relative Tâtonnement on synthetic instances with lognor [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
read the original abstract

We study price-adjustment dynamics for computing competitive equilibria (CE) in Fisher markets with chores. Unlike in classical goods markets, prices in chores markets are payments for taking on undesirable tasks, and natural excess-demand dynamics can fail; even the na\"ive analogue of Walrasian t\^atonnement may diverge. Recent work of Chaudhury et al. [2025] overcomes this obstacle via relative t\^atonnement, which subtracts the average excess-demand signal from the excess demand vector. This recovers convergence, but at the cost of coupling the price updates across all chores. This leaves open whether such global coupling is inherent, or whether convergent t\^atonnement can be recovered through a genuinely local update in which each chore reacts only to its own excess demand. We answer this question affirmatively through multiplicative t\^atonnement, a fully distributed dynamics in which each chore price is updated using only its current price and its own excess-demand signal. Although the update contains no explicit normalization term, Walras' law and the multiplicative form of the update implicitly preserve the relevant aggregate price geometry. We prove that multiplicative t\^atonnement converges to a CE in any chores Fisher market with continuous, convex, and $1$-homogeneous (CCH) disutilities. For convex CES disutilities, we further prove an approximate-CE convergence rate with the same $O(1/\varepsilon^2)$ dependence as relative t\^atonnement, but with improved dependence on problem constants. Experiments on real-world and simulated instances show that multiplicative t\^atonnement is substantially faster in practice, often by an order of magnitude.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces multiplicative tâtonnement, a fully distributed price-adjustment dynamics for chores Fisher markets in which each chore's price is updated using only its own excess-demand signal and current price. It proves convergence to a competitive equilibrium for any market with continuous, convex, and 1-homogeneous (CCH) disutilities, establishes an O(1/ε²) approximate-CE rate for convex CES disutilities (with improved dependence on problem constants relative to relative tâtonnement), and reports that the dynamics is substantially faster in practice than the coupled alternative of Chaudhury et al. [2025].

Significance. If the stated convergence proofs hold, the result is significant because it shows that global coupling across chores is not required to obtain convergent tâtonnement in chores markets; the multiplicative form together with Walras' law and 1-homogeneity suffices to preserve the necessary aggregate price geometry. This yields a genuinely local update rule, matching the best-known rate while improving constant factors and delivering order-of-magnitude practical speedups on the reported instances. The work thereby strengthens the algorithmic toolkit for distributed equilibrium computation under the CCH structural assumption.

minor comments (3)
  1. Abstract: the claim that experiments show 'substantially faster' performance 'often by an order of magnitude' should be supported by at least one quantitative table or figure reference (e.g., iteration counts or wall-clock times versus relative tâtonnement on the same instances) so that the empirical contribution can be assessed.
  2. The manuscript should explicitly state whether the CCH class is closed under the operations used in the convergence argument or whether additional regularity (e.g., strict convexity or interiority of the equilibrium) is tacitly required for the local update to remain well-defined when excess demand is zero for some chores.
  3. Notation: the precise definition of the multiplicative update rule (including any implicit normalization or handling of zero prices) should appear in the main text before the convergence theorem, rather than being left to the abstract's high-level description.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work on multiplicative tâtonnement and for recommending minor revision. We appreciate the recognition that the result demonstrates local updates suffice under the CCH assumption and that the practical speedups are notable. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes convergence of multiplicative tâtonnement to competitive equilibrium for CCH disutilities via a direct mathematical argument that invokes the local update rule, Walras' law, and 1-homogeneity to preserve price geometry. This is presented as an independent proof, not a reduction of any claimed result to a fitted parameter, self-referential definition, or prior self-citation. The reference to Chaudhury et al. [2025] supplies only background on relative tâtonnement and does not carry the load of the new fully-distributed convergence claim. No steps in the described derivation chain match any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the domain assumption that disutilities are CCH; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Disutilities are continuous, convex, and 1-homogeneous (CCH)
    Invoked to prove convergence of the multiplicative updates (abstract convergence statement).

pith-pipeline@v0.9.1-grok · 5836 in / 1249 out tokens · 33656 ms · 2026-07-02T00:54:06.722147+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

54 extracted references · 7 canonical work pages

  1. [1]

    Graphical economies with resale

    Gabriel Andrade, Rafael Frongillo, Sharadha Srinivasan, and Elliot Gorokhovsky. Graphical economies with resale. InProceedings of the 22nd ACM Conference on Economics and Computation, pages 71–90, 2021

    2021

  2. [2]

    On the stability of the competitive equilibrium, ii.Econometrica: Journal of the Econometric Society, pages 82–109, 1959

    Kenneth J Arrow, Henry D Block, and Leonid Hurwicz. On the stability of the competitive equilibrium, ii.Econometrica: Journal of the Econometric Society, pages 82–109, 1959

    1959

  3. [3]

    On the stability of the competitive equilibrium, i

    Kenneth J Arrow and Leonid Hurwicz. On the stability of the competitive equilibrium, i. Econometrica: Journal of the Econometric Society, pages 522–552, 1958

    1958

  4. [4]

    A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications.Mathematics of Operations Research, 42(2):330–348, 2017

    Heinz H Bauschke, Jérôme Bolte, and Marc Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications.Mathematics of Operations Research, 42(2):330–348, 2017

    2017

  5. [5]

    Distributed algorithms via gradient descent for fisher markets

    Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao. Distributed algorithms via gradient descent for fisher markets. InProceedings of the 12th ACM conference on Electronic commerce, pages 127–136. ACM, 2011

    2011

  6. [6]

    Competitive division of a mixed manna.Econometrica, 85(6):1847–1871, 2017

    Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaya. Competitive division of a mixed manna.Econometrica, 85(6):1847–1871, 2017

    2017

  7. [7]

    Polynomial time algorithms to find an approximate competitive equilibrium for chores

    Shant Boodaghians, Bhaskar Ray Chaudhury, and Ruta Mehta. Polynomial time algorithms to find an approximate competitive equilibrium for chores. InSODA, pages 2285–2302. SIAM, 2022

    2022

  8. [8]

    Proportional dynamics in exchange economies

    Simina Brânzei, Nikhil Devanur, and Yuval Rabani. Proportional dynamics in exchange economies. InProceedings of the 22nd ACM Conference on Economics and Computation, pages 180–201, 2021

    2021

  9. [9]

    Algorithms for competitive division of chores.Math

    Simina Brânzei and Fedor Sandomirskiy. Algorithms for competitive division of chores.Math. Oper. Res., 49(1):398–429, 2024

    2024

  10. [10]

    Competitive equilibrium with chores: Combinatorial algorithm and hardness

    Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. Competitive equilibrium with chores: Combinatorial algorithm and hardness. InEC, pages 1106–1107. ACM, 2022

    2022

  11. [11]

    Competitive equilib- rium for chores: from dual eisenberg-gale to a fast, greedy, lp-based algorithm

    Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan. Competitive equilib- rium for chores: from dual eisenberg-gale to a fast, greedy, lp-based algorithm. InProceedings of the 25th ACM Conference on Economics and Computation, pages 40–40, 2024. 10

    2024

  12. [12]

    Tâtonnement dynamics for fisher markets with chores.arXiv preprint arXiv:2511.21162, 2025

    Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, and Tianlong Nan. Tâtonnement dynamics for fisher markets with chores.arXiv preprint arXiv:2511.21162, 2025

    work page arXiv 2025

  13. [13]

    Accelerated price adjustment for fisher markets with exact recovery of competitive equilibrium.arXiv preprint arXiv:2510.07759, 2025

    He Chen, Chonghe Jiang, and Anthony Man-Cho So. Accelerated price adjustment for fisher markets with exact recovery of competitive equilibrium.arXiv preprint arXiv:2510.07759, 2025

    work page arXiv 2025

  14. [14]

    Tatonnement beyond gross substitutes? gradient descent to the rescue

    Yun Kuen Cheung, Richard Cole, and Nikhil Devanur. Tatonnement beyond gross substitutes? gradient descent to the rescue. InProceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 191–200, 2013

    2013

  15. [15]

    Tatonnement beyond gross substitutes? gradient descent to the rescue.Games and Economic Behavior, 2019

    Yun Kuen Cheung, Richard Cole, and Nikhil R Devanur. Tatonnement beyond gross substitutes? gradient descent to the rescue.Games and Economic Behavior, 2019

    2019

  16. [16]

    Tatonnement in ongoing markets of complementary goods

    Yun Kuen Cheung, Richard Cole, and Ashish Rastogi. Tatonnement in ongoing markets of complementary goods. InProceedings of the 13th ACM Conference on Electronic Commerce, pages 337–354, 2012

    2012

  17. [17]

    Dynamics of distributed updating in fisher markets

    Yun Kuen Cheung, Richard Cole, and Yixin Tao. Dynamics of distributed updating in fisher markets. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 351–368, 2018

    2018

  18. [18]

    Proportional response dynamics in gross substitutes markets.arXiv preprint arXiv:2506.02852, 2025

    Yun Kuen Cheung, Richard Cole, and Yixin Tao. Proportional response dynamics in gross substitutes markets.arXiv preprint arXiv:2506.02852, 2025

    work page arXiv 2025

  19. [19]

    Market equilibrium via the excess demand function

    Bruno Codenotti, Benton McCune, and Kasturi Varadarajan. Market equilibrium via the excess demand function. InProceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 74–83, 2005

    2005

  20. [20]

    Fast-converging tatonnement algorithms for one-time and ongoing market problems

    Richard Cole and Lisa Fleischer. Fast-converging tatonnement algorithms for one-time and ongoing market problems. InProceedings of the fortieth annual ACM symposium on Theory of computing, pages 315–324, 2008

    2008

  21. [21]

    Balancing the robustness and convergence of tatonnement.arXiv preprint arXiv:1908.00844, 2019

    Richard Cole and Yixin Tao. Balancing the robustness and convergence of tatonnement.arXiv preprint arXiv:1908.00844, 2019

    work page arXiv 1908

  22. [22]

    Devanur and Ravi Kannan

    Nikhil R. Devanur and Ravi Kannan. Market equilibria in polynomial time for fixed number of goods or agents. In49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 45–53. IEEE Computer Society, 2008

    2008

  23. [23]

    Market equilibrium via a primal-dual algorithm for a convex program.Journal of the ACM (JACM), 55(5):1–18, 2008

    Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani. Market equilibrium via a primal-dual algorithm for a convex program.Journal of the ACM (JACM), 55(5):1–18, 2008

    2008

  24. [24]

    Stochastic bregman subgradient methods for nonsmooth nonconvex optimization problems.arXiv preprint arXiv:2404.17386, 2024

    Kuangyu Ding and Kim-Chuan Toh. Stochastic bregman subgradient methods for nonsmooth nonconvex optimization problems.arXiv preprint arXiv:2404.17386, 2024

    work page arXiv 2024

  25. [25]

    A combinatorial polynomial algorithm for the linear arrow– debreu market.Information and Computation, 243:112–132, 2015

    Ran Duan and Kurt Mehlhorn. A combinatorial polynomial algorithm for the linear arrow– debreu market.Information and Computation, 243:112–132, 2015

    2015

  26. [26]

    A finite algorithm for the linear exchange model

    B Curtis Eaves. A finite algorithm for the linear exchange model. 1975

    1975

  27. [27]

    Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959

    Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959

    1959

  28. [28]

    First-order methods for large-scale market equilibrium computa- tion

    Yuan Gao and Christian Kroer. First-order methods for large-scale market equilibrium computa- tion. InNeural Information Processing Systems 2020, NeurIPS 2020, 2020

    2020

  29. [29]

    Computing competitive equilibria with mixed manna

    Jugal Garg and Peter McGlaughlin. Computing competitive equilibria with mixed manna. In AAMAS Conference proceedings, 2020

    2020

  30. [30]

    A consumer-theoretic characterization of fisher market equilibria

    Denizalp Goktas, Enrique Areyan Viqueira, and Amy Greenwald. A consumer-theoretic characterization of fisher market equilibria. InInternational Conference on Web and Internet Economics, pages 334–351. Springer, 2021. 11

    2021

  31. [31]

    Tâtonnement in homothetic fisher markets

    Denizalp Goktas, Jiayi Zhao, and Amy Greenwald. Tâtonnement in homothetic fisher markets. InProceedings of the 24th ACM Conference on Economics and Computation, EC’23, pages 760–781, 2023

    2023

  32. [32]

    Spliddit: Unleashing fair division algorithms.ACM SIGecom Exchanges, 13(2):41–46, 2015

    Jonathan Goldman and Ariel D Procaccia. Spliddit: Unleashing fair division algorithms.ACM SIGecom Exchanges, 13(2):41–46, 2015

    2015

  33. [33]

    The use of knowledge in society.The American economic review, 35(4):519–530, 1945

    Friedrich August Hayek. The use of knowledge in society.The American economic review, 35(4):519–530, 1945

    1945

  34. [34]

    A polynomial time algorithm for computing an arrow–debreu market equilibrium for linear utilities.SIAM Journal on Computing, 37(1):303–318, 2007

    Kamal Jain. A polynomial time algorithm for computing an arrow–debreu market equilibrium for linear utilities.SIAM Journal on Computing, 37(1):303–318, 2007

    2007

  35. [35]

    Vazirani, and Yinyu Ye

    Kamal Jain, Vijay V . Vazirani, and Yinyu Ye. Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. InProceedings of the Sixteenth Annual ACM- SIAM Symposium on Discrete Algorithms (SODA), pages 63–71. SIAM, 2005

    2005

  36. [36]

    Graphical economics

    Sham M Kakade, Michael Kearns, and Luis E Ortiz. Graphical economics. InInternational Conference on Computational Learning Theory, pages 17–32. Springer, 2004

    2004

  37. [37]

    Relatively smooth convex optimization by first-order methods, and applications.SIAM Journal on Optimization, 28(1):333–354, 2018

    Haihao Lu, Robert M Freund, and Yurii Nesterov. Relatively smooth convex optimization by first-order methods, and applications.SIAM Journal on Optimization, 28(1):333–354, 2018

    2018

  38. [38]

    Preflib: A library for preferences http://www.preflib.org

    Nicholas Mattei and Toby Walsh. Preflib: A library for preferences http://www.preflib.org. In Patrice Perny, Marc Pirlot, and Alexis Tsoukiàs, editors,Algorithmic Decision Theory - Third International Conference, ADT 2013, Bruxelles, Belgium, November 12-14, 2013, Proceedings, Lecture Notes in Computer Science, pages 259–270. Springer, 2013

    2013

  39. [39]

    Fast and interpretable dynamics for fisher markets via block-coordinate updates

    Tianlong Nan, Yuan Gao, and Christian Kroer. Fast and interpretable dynamics for fisher markets via block-coordinate updates. InProceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5832–5840, 2023

    2023

  40. [40]

    On the convergence of tâtonnement for linear fisher markets

    Tianlong Nan, Yuan Gao, and Christian Kroer. On the convergence of tâtonnement for linear fisher markets. InProceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 14027–14035, 2025

    2025

  41. [41]

    One algorithm for finding solutions of the arrow-debreu model

    EI Nenakov and ME Primak. One algorithm for finding solutions of the arrow-debreu model. Kibernetica, 3:127–128, 1983

    1983

  42. [42]

    James B. Orlin. Improved algorithms for computing fisher’s market clearing prices: computing fisher’s market clearing prices. InSTOC, pages 291–300. ACM, 2010

    2010

  43. [43]

    The stability of equilibrium: comparative statics and dynamics.Economet- rica: Journal of the Econometric Society, pages 97–120, 1941

    Paul A Samuelson. The stability of equilibrium: comparative statics and dynamics.Economet- rica: Journal of the Econometric Society, pages 97–120, 1941

    1941

  44. [44]

    An algorithm for finding equilibrium in the linear exchange model with fixed budgets.Journal of Applied and Industrial Mathematics, 3(4):505, 2009

    Vadim I Shmyrev. An algorithm for finding equilibrium in the linear exchange model with fixed budgets.Journal of Applied and Industrial Mathematics, 3(4):505, 2009

    2009

  45. [45]

    Fisher meets lindahl: A unified duality framework for market equilibrium.arXiv preprint arXiv:2511.04572, 2025

    Yixin Tao and Weiqiang Zheng. Fisher meets lindahl: A unified duality framework for market equilibrium.arXiv preprint arXiv:2511.04572, 2025

    work page arXiv 2025

  46. [46]

    Eléments d’économie pure.Economica, 1874

    Léon Walras. Eléments d’économie pure.Economica, 1874

  47. [47]

    Proportional response dynamics leads to market equilibrium

    Fang Wu and Li Zhang. Proportional response dynamics leads to market equilibrium. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 354– 363, 2007

    2007

  48. [48]

    A path to the arrow–debreu competitive market equilibrium.Mathematical Program- ming, 111(1):315–348, 2008

    Yinyu Ye. A path to the arrow–debreu competitive market equilibrium.Mathematical Program- ming, 111(1):315–348, 2008

    2008

  49. [49]

    The second-order t \ˆ atonnement: De- centralized interior-point methods for market equilibrium.arXiv preprint arXiv:2508.04822, 2025

    Chuwen Zhang, Chang He, Bo Jiang, and Yinyu Ye. The second-order t \ˆ atonnement: De- centralized interior-point methods for market equilibrium.arXiv preprint arXiv:2508.04822, 2025. 12

    work page arXiv 2025

  50. [50]

    Proportional response dynamics in the fisher market.Theoretical Computer Science, 412(24):2691–2698, 2011

    Li Zhang. Proportional response dynamics in the fisher market.Theoretical Computer Science, 412(24):2691–2698, 2011

    2011

  51. [51]

    Fisher markets with social influence

    Jiayi Zhao, Denizalp Goktas, and Amy Greenwald. Fisher markets with social influence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5900–5909, 2023. 13 Appendix A Additional related work Computation of CE in Fisher markets.A series of foundational works established convex pro- gramming and linear complementarity proble...

    2023

  52. [52]

    For anyp k ∈∆ B,p k+1 ∈∆ B

  53. [53]

    For anyp k ∈∆ B and eachj∈[m], ifp k j ≤ℓ 0 thenp k+1 j > p k j + 1 2 ηk

  54. [54]

    The first fact is true because of Proposition 1

    For anyp k ∈R m + and eachj∈[m], ifp k j > ℓ 0, thenp k+1 j > ℓ0 2 . The first fact is true because of Proposition 1. The second fact follows from Lemma 6. The third fact is true because of the following: for any yk ∈Y(p k), we have |yk j | ≤β . Thus, pk+1 j = pk j (1 +η kyk j )> p k j (1−η kβ)≥ 1 2 pk j > ℓ0 2 . Then, we prove Lemma 2. The first statemen...

    2000